Method of generating surface defined by boundary of three-dimensional point cloud
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.
1. A computer-implemented method of generating a three-dimensional (3D) surface from a plurality of 3D points, the method comprising:
initializing a plurality of depth values and a plurality of density values on a 2D projection plane, wherein the 2D projection plane is generated by a processing unit;
projecting the plurality of 3D points onto the 2D projection plane to generate a plurality of projected points in the projection plane;
generating a depth map by updating the plurality of depth values according to coordinates associated with the plurality of projected points;
generating a density map by updating the plurality of density values according to the coordinates associated with the plurality of projected points;
generating a two-dimensional (2D) mesh from the depth map and the density map; and
transforming the 2D mesh into a 3D mesh for storage in a memory or display on a display screen.
2. The method of claim 1 , 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 the location of each node in the projection plane define coordinates for the node.
3. The method of claim 2 , wherein the 2D grid is a rectangular grid.
4. The method of claim 2 , 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.
5. The method of claim 4 , 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.
6. The method of claim 5 , 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.
7. The method of claim 6 , wherein projecting the 3D points onto the 2D projection plane comprises:
multiplying each of the 3D points by a projection matrix.
8. The method of claim 7 , 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.
9. The method of claim 8 , 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.
10. The method of claim 9 , further comprising:
defining interpolated nodes between adjacent interior and exterior nodes;
wherein vertices of the polygons are defined by the interior and interpolated nodes.
11. The method of claim 10 , wherein transforming the 2D mesh into a 3D mesh comprises:
multiplying the coordinates of each node by an inverse of the projection matrix.
12. The method of claim 11 , further comprising:
sending 3D polygons defined by the 3D mesh to a graphics rendering pipeline.
13. The method of claim 8 , wherein the polygons comprise triangles.
14. The method of claim 12 , further comprising:
before sending the 3D polygons to the graphics rendering pipeline, defining vertex normals for each vertex in the 3D polygons.
15. The method of claim 14 , 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.
16. The method of claim 10 , wherein coordinates for each interpolated node are determined by linear interpolation of the adjacent interior and exterior nodes.
17. The method of claim 1 , wherein each of the plurality of 3D points represents a particle in a particle based fluids model.
18. The method of claim 1 , 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).
19. The method of claim 1 , further comprising:
after generating the depth map, smoothing the depth values by applying a filter thereto.
20. The method of claim 19 , wherein the filter is a separable binomial filter.
21. The method of claim 8 , 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.
22. The method of claim 8 , further comprising:
simplifying the 2D mesh by combining similar adjacent cells in the 2D grid using a quad-tree hierarchy.
23. The method of claim 22 , 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.