PARALLEL SURFACE RECONSTRUCTION

• US 20100085352A1
• Filed: 10/04/2008
• Published: 04/08/2010
• Est. Priority Date: 10/04/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhou, Kun, Huang, Xin, Guo, Baining, Gong, Minmin
• Granted Patent: US 8,610,706 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

Described is a technology in which point cloud surface reconstruction is performed via parallel processing on a graphics processing unit, achieving real-time reconstruction rates. An octree is built for a given set of oriented points, with each node containing a set of points enclosed by the node. The data structure is built on the GPU, in parallel, using level-order traversals to process nodes at a same tree level. The surface is reconstructed based on data configured and located via the traversals. To produce the surface, an implicit function over the volume spanned by the octree nodes is computed using the GPU, e.g., based on a Poisson surface reconstruction method. A sparse linear system is built and a multi-grid solver is employed to solve the system. An adaptive marching cubes procedure is performed on the GPU to extract an isosurface of the implicit function as a triangular mesh

Claims

1. In a computing environment, a method comprising, performing surface reconstruction in parallel via a graphics processing unit, including building a data structure of nodes for a given set of oriented points, each node containing a set of points enclosed by the node, traversing the data structure using level-order traversals to process nodes at a same tree level in parallel, and reconstructing the surface based on data located in the nodes.

2. The method of claim 1 wherein each node of at least some of the nodes further contains an identifying key and pointers to related nodes.

3. The method of claim 1 wherein the data structure comprises an octree, and wherein building the data structure comprises building a node array via a reverse level-order traversal of the octree from a finest depth level towards a root level.

4. The method of claim 1 wherein each node of at least some of the nodes at a level further contains an identifying key and pointers to related nodes, and wherein building the data structure comprises, using the pointers of nodes at one depth level to build a higher level depth node array.

5. The method of claim 1 further comprising, building at least one lookup table to record the indirect pointers to a node'"'"'s relatives, and wherein traversing the data structure includes accessing each lookup table.

6. The method of claim 5 further comprising, using at least one lookup table to determine neighborhood information for a node, and further comprising, using the neighborhood information to compute vertex, edge and face structures.

7. The method of claim 5 wherein one lookup table comprises a parent table that maintains information related to a node'"'"'s parent, and further comprising, accessing the parent table to determine neighborhood information for that node.

8. The method of claim 5 wherein one lookup table comprises a child table that maintains information related to a node'"'"'s child, and further comprising, accessing the child table to determine neighborhood information for that node.

9. The method of claim 1 wherein reconstructing the surface comprises extracting an isosurface as a triangle mesh.

10. The method of claim 9 further comprising performing an adaptive marching cubes procedure for extracting the isosurface.

11. The method of claim 1 wherein reconstructing the surface comprises using Poisson equation for surface reconstruction.

12. The method of claim 1 further comprising, performing a procedure for evaluating a divergence vector in a Poisson equation.

13. In a computing environment having a graphics processing unit, a system comprising, a surface construction mechanism coupled to the graphics processing unit that builds an octree to represent a set of points from which surfaces are extracted, the octree built by computing nodes of the octree, including by traversing the octree using level-order traversals, each level order traversal performed in parallel via the graphics processing unit for nodes of that level.

14. The system of claim 13 wherein each node of at least some of the nodes contains an identifying key, a subset of the set of points corresponding to those points contained in the node, and pointers to related nodes.

15. The system of claim 13 further comprising means for extracting a surface from the node, including by accessing at least one lookup table that maintains information related to a node'"'"'s related nodes.

16. The system of claim 13 wherein the surface construction mechanism is coupled to an interactive application, the interactive application communicating with the surface construction mechanism to display a scene in real time by rebuilding the octrees and extracting surfaces to produce frames of the scene.

17. One or more computer-readable media having computer-executable instructions, which when executed perform steps, comprising, building an octree of nodes for a given set of oriented points, each node containing a set of points enclosed by the node and pointers to related nodes, including by communicating with a graphics processing unit to process nodes at a same tree depth level in the octree in parallel, and, when pointers of nodes at one depth level are available, using the pointers to build nodes of a higher level depth.

18. The one or more computer-readable media of claim 17 having further computer-executable instructions comprising, extracting an isosurface by processing the octree.

19. The one or more computer-readable media of claim 18 wherein extracting the isosurface comprises using a Poisson equation for surface reconstruction.

20. The one or more computer-readable media of claim 17 having further computer-executable instructions comprising, building at least one lookup table to record the indirect pointers to a node'"'"'s relatives.