Scalable volumetric 3d reconstruction

Abstract

Scalable volumetric reconstruction is described whereby data from a mobile environment capture device is used to form a 3D model of a real-world environment. In various examples, a hierarchical structure is used to store the 3D model where the structure comprises a root level node, a plurality of interior level nodes and a plurality of leaf nodes, each of the nodes having an associated voxel grid representing a portion of the real world environment, the voxel grids being of finer resolution at the leaf nodes than at the root node. In various examples, parallel processing is used to enable captured data to be integrated into the 3D model and/or to enable images to be rendered from the 3D model. In an example, metadata is computed and stored in the hierarchical structure and used to enable space skipping and/or pruning of the hierarchical structure.

1 . A computer-implemented method comprising:
 receiving, at a processor, a stream of depth maps of the real-world environment captured by a mobile environment capture device;   calculating, from the depth maps, a 3D model comprising values representing surfaces in the real-world environment;   storing the 3D model in a hierarchical structure comprising a root level node, a plurality of interior level nodes and a plurality of leaf nodes, each of the nodes having an associated voxel grid representing a portion of the real world environment, the voxel grids being of finer resolution at the leaf nodes than at the root node;   storing, at the root and interior nodes, metadata describing the hierarchical structure;   storing at the leaf nodes, the values representing surfaces.   
     
     
         2 . A method as claimed in  claim 1  wherein storing the 3D model in a hierarchical structure comprises forming the interior level nodes and the leaf nodes on the basis of a refinement strategy which checks whether a depth observation from a depth map is near to at least some of the values representing surfaces in the real-world environment. 
     
     
         3 . A method as claimed in  claim 2  wherein the refinement strategy checks whether a depth observation from a depth map is near to at least some of the values by using a truncation region which adapts according to the depth observation from the mobile environment capture device. 
     
     
         4 . A method as claimed in  claim 1  wherein storing the 3D model in a hierarchical structure comprises forming, in parallel, interior nodes for selected voxels of the voxel grid of the root node, by using a thread block for each of the selected voxels. 
     
     
         5 . A method as claimed in  claim 1  wherein storing the 3D model in a hierarchical structure comprises forming, in parallel, a child node for each of selected voxels of voxel grids of interior nodes, by using one thread per selected voxel of an interior node. 
     
     
         6 . A method as claimed in  claim 1  wherein storing the 3D model in a hierarchical structure comprises allocating, for each of a plurality of levels of the hierarchical structure, a fixed size memory pool. 
     
     
         7 . A method as claimed in  claim 6  wherein each fixed size memory pool comprises a backing store which is a plurality of memory blocks each sized according to a voxel grid size used at a level of the hierarchy, and a free list, which is a queue of indices of the backing store memory blocks. 
     
     
         8 . A method as claimed in  claim 7  wherein storing the 3D model in a hierarchical structure comprises forming interior and leaf nodes by using memory blocks from the backing store according to the free lists. 
     
     
         9 . A method as claimed in  claim 1  wherein the metadata comprises a near surface flag indicating whether at least one depth observation associated with a node is near to at least some of the values representing surfaces in the real-world environment. 
     
     
         10 . A method as claimed in  claim 1  wherein the metadata comprises a minimum weight value related to a minimum number of depth observations associated with a node. 
     
     
         11 . A method as claimed in  claim 1  comprising, computing and storing the metadata by traversing the hierarchical data structure from each of the leaf nodes in parallel to the root level node. 
     
     
         12 . A method as claimed in  claim 1  comprising, for each leaf node, checking, in parallel, each voxel of the leaf node voxel grid, by comparing the value stored at the leaf node voxel with a threshold, and setting a near surface flag of a parent node of the leaf node according to the results of the checks. 
     
     
         13 . A method as claimed in  claim 1  comprising pruning the hierarchical structure by removing nodes on the basis of the metadata. 
     
     
         14 . A method as claimed in  claim 1  comprising rendering an image from the hierarchical structure using a raycasting process with space skipping, the space skipping being facilitated using the metadata. 
     
     
         15 . A computer-implemented method comprising:
 receiving, at a processor, a stream of depth maps of the real-world environment captured by a mobile environment capture device, and also receiving at the processor a position and orientation of the mobile environment capture device associated with each depth map;   calculating, from the depth maps, a 3D model comprising values representing surfaces in the real-world environment;   storing in memory of a parallel processing unit the 3D model;   calculating an active region of the real-world environment using a current position and orientation of the mobile environment capture device;   mapping the active region to a working set of the memory;   streaming values of the 3D model between the memory of the parallel processing unit and memory of a host device on the basis of the mapping.   
     
     
         16 . A method as claimed in  claim 15  comprising storing the 3D model in a hierarchical structure at the memory of the parallel processing unit and using compression criteria to select values of the 3D model to be streamed out of the memory at the parallel processing unit. 
     
     
         17 . An apparatus for constructing a 3D model of a real-world environment comprising:
 an input interface arranged to receive a stream of depth maps of the real-world environment captured by a mobile environment capture device;   a plurality of parallel processing units arranged to calculate, from the depth maps, a 3D model comprising values representing surfaces in the real-world environment;   each parallel processing unit having a memory storing at least part of the 3D model using the same amount of memory and where the memory is mapped to different physical dimensions in the real-world environment for each of the parallel processing units.   
     
     
         18 . An apparatus as claimed in  claim 17  each parallel processing unit arranged to calculate the 3D model independently from the depth maps. 
     
     
         19 . An apparatus as claimed in  claim 17  wherein each of the parallel processing units represents a different sized volume centered on a same position in the real world environment. 
     
     
         20 . An apparatus as claimed in  claim 17  comprising calculating the 3D model at the parallel processing unit representing a smallest volume and aggregating values from that parallel processing unit to fill the 3D model at the other parallel processing units.