Method of generating surface defined by boundary of three-dimensional point cloud

• US 20070024620A1
• Filed: 08/01/2005
• Published: 02/01/2007
• Est. Priority Date: 08/01/2005
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Schirm, Simon, Duthaler, Stefan, Muller-Fischer, Matthias
• Granted Patent: US 7,586,489 B2
• Time in Patent Office: Days
• US Class Current: 345/427
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 7/50 Depth or shape recovery

Abstract

Disclosed is a method of generating a three-dimensional (3D) surface defined by a boundary of a 3D point cloud. The method comprises generating density and depth maps from the 3D point cloud, constructing a 2D mesh from the depth and density maps, transforming the 2D mesh into a 3D mesh, and rendering 3D polygons defined by the 3D mesh.

Claims

1. A method of generating a three-dimensional (3D) surface from a plurality of 3D points, the method comprising:

generating a depth map from the plurality of 3D points;

generating a two-dimensional (2D) mesh from the depth map; and

,

transforming the 2D mesh into a 3D mesh.

2. The method of claim 1, further comprising:

generating a density map before generating the 2D mesh; and

,

using the density map together with the depth map to generate the 2D mesh.

3. The method of claim 2, wherein generating the depth map comprises:

initializing a plurality of depth values on a 2D projection plane;

projecting the 3D points onto the 2D projection plane to generate a plurality of projected points in the projection plane; and

,

updating the depth values according to coordinates of the projected points.

4. The method of claim 3, wherein generating the density map comprises:

initializing a plurality of density values on the 2D projection plane; and

,

updating the density values according to the coordinates of the projected points.

5. The method of claim 4, wherein the 2D projection plane comprises a 2D grid characterized by a plurality of cells defined by a plurality of nodes;

wherein each of the nodes is characterized by a depth value, a density value, and by a location in the projection plane; and

,

wherein the depth value and location of each node in the projection plane define coordinates for the node.

6. The method of claim 5, wherein the 2D grid is a rectangular grid.

7. The method of claim 5, wherein updating the depth values according to the coordinates of the projected points comprises:

computing projected radii for each of the projected points;

replacing each existing depth value stored at each node in the 2D grid with a minimum of the existing depth value and depth coordinates of projected points separated from the node by less than a predetermined projected radius.

8. The method of claim 7, wherein updating the density values according to the coordinates of the projected points comprises:

replacing each existing density value stored at each node in the 2D grid with a sum of the existing density value and density values of projected points separated from the node by less than a predetermined projected radius.

9. The method of claim 8, wherein the depth coordinate and density value of each projected point is weighted according to the distance of the projected point from a node in the 2D grid.

10. The method of claim 9, wherein projecting the 3D points onto the 2D projection plane comprises:

multiplying each of the 3D points by a projection matrix.

11. The method of claim 10, generating the 2D mesh comprises:

designating each node in the 2D grid as an interior node or an exterior node; and

,

applying one of a plurality of mesh patterns to each cell in the 2D grid based on a pattern of interior and exterior nodes in the cell;

wherein the mesh patterns define connectivities for polygons formed in the 2D mesh.

12. The method of claim 11, wherein designating each node in the 2D grid as an interior node or an exterior node comprises:

upon determining that a density value of the node is greater than or equal to a density threshold, designating the node as an interior node; and

,

upon determining that the density value of the node is less than the density threshold, designating the node as an exterior node.

13. The method of claim 12, further comprising:

defining interpolated nodes between adjacent interior and exterior nodes;

wherein vertices of the polygons are defined by the interior and interpolated nodes.

14. The method of claim 13, wherein transforming the 2D mesh into a 3D mesh comprises:

multiplying the coordinates of each node by an inverse of the projection matrix.

15. The method of claim 14, further comprising:

sending 3D polygons defined by the 3D mesh to a graphics rendering pipeline.

16. The method of claim 11, wherein the polygons comprise triangles.

17. The method of claim 15, further comprising:

before sending the 3D polygons to the graphics rendering pipeline, defining vertex normals for each vertex in the 3D polygons.

18. The method of claim 17, wherein each vertex normal is computed as a weighted sum of the normals of polygons containing the vertex;

wherein the weight of each normal in the sum is proportional to an angle between the normal and the vertex.

19. The method of claim 13, wherein coordinates for each interpolated node are determined by linear interpolation of the adjacent interior and exterior nodes.

20. The method of claim 2, wherein each of the plurality of 3D points represents a particle in a particle based fluids model.

21. The method of claim 2, wherein the 3D surface is generated by a computational platform including at least one of a physics processing unit (PPU), a graphics processing unit (GPU) and a central processing unit (CPU).

22. The method of claim 3, further comprising:

after generating the depth map, smoothing the depth values by applying a filter thereto.

23. The method of claim 22, wherein the filter is a separable binomial filter.

24. The method of claim 11, further comprising:

smoothing a silhouette of the 2D mesh by smoothing coordinates of each interior node in the 2D grid lying adjacent to an exterior node.

25. The method of claim 11, further comprising:

simplifying the 2D mesh by combining similar adjacent cells in the 2D grid using a quad-tree hierarchy.

26. The method of claim 25, wherein the quad-tree hierarchy is a restricted quad-tree hierarchy wherein adjacent cells in the 2D grid are prevented from differing by more than one level.