Methods, apparatus and computer program products that reconstruct surfaces from data point sets

• US 20030067461A1
• Filed: 05/21/2002
• Published: 04/10/2003
• Est. Priority Date: 09/24/2001
• Status: Active Grant

• Current Assignee: 3D Systems, Inc. (3D Systems Corporation)
• Original Assignee: Geomagic, Inc. (3D Systems Corporation)
• Inventors: Gloth, Tobias, Edelsbrunner, Herbert, Fu, Ping, Fletcher, G. Yates
• Granted Patent: US 7,023,432 B2
• Time in Patent Office: Days
• US Class Current: 345/420
• CPC Class Codes: B33Y 50/00 Data acquisition or data processing for additive manufacturing
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

Methods, apparatus and computer program products provide efficient techniques for reconstructing surfaces from data point sets. These techniques include reconstructing surfaces from sets of scanned data points that have preferably undergone preprocessing operations to improve their quality by, for example, reducing noise and removing outliers. These techniques include reconstructing a dense and locally two-dimensionally distributed 3D point set (e.g., point cloud) by merging stars in two-dimensional weighted Delaunay triangulations within estimated tangent planes. The techniques include determining a plurality of stars from a plurality of points p_i in a 3D point set S that at least partially describes the 3D surface, by projecting the plurality of points p_i onto planes T_i that are each estimated to be tangent about a respective one of the plurality of points p_i. The plurality of stars are then merged into a digital model of the 3D surface.

Claims

1. A method of modeling a three-dimensional (3D) surface, comprising the steps of:

determining a plurality of stars from a plurality of points p_i in a 3D point set S that at least partially describes the 3D surface, by projecting the plurality of points p_i onto planes T_i that are each estimated to be tangent about a respective one of the plurality of points p_i; and

merging the plurality of stars into a digital model of the 3D surface.

2. The method of claim 1, wherein said determining step comprises identifying a respective subset of near points S_i for each of the plurality of points p_i.

3. The method of claim 2, wherein said determining step comprises projecting a plurality of points p_j in each subset of near points S_i to a respective estimated tangent plane T_i.

4. The method of claim 3, wherein said determining step comprises determining for each of a plurality of estimated tangent planes, T_j, a star of the projection of a respective point p_i onto the estimated tangent plane T_i.

5. The method of claim 4, wherein the star of the projection of a respective point p_i onto the estimated tangent plane T_i constitutes a two-dimensional (2D) Delaunay triangulation.

6. The method of claim 4, wherein the star of the projection of a respective point p_i onto the estimated tangent plane T_i constitutes a two-dimensional (2D) weighted Delaunay triangulation.

7. The method of claim 6, wherein a distance between at least one point p_i and its orthogonal projection onto a respective estimated tangent plane T_i is non-zero.

8. The method of claim 1, wherein said determining step comprises identifying a respective subset of near points S_i for each of the plurality of points p_i by storing the 3D point set S in an oct-tree.

9. The method of claim 2, where:

S_i=□

_i(r₀)∩

N_i(k₀),

and □

_i(r₀) is defined as the set of points p_jε

S with an l_∞

-distance at most r₀ from p_i and N_i(k₀) is the set of k₀ points that are closest in Euclidean distance to p_i, including p_i itself, and k₀ is a positive integer.

10. The method of claim 1, wherein said determining step comprises identifying a respective subset of near points S_i for each of the plurality of points p_i by determining a width of a near point search cube using a random sample R⊂

S and identifying those points in S that are within a respective near point search cube that is centered about each of the plurality of points p_i.

11. The method of claim 1, wherein said determining step comprises identifying a respective subset of near points S_i for each of the plurality of points p_i by:

storing the 3D point set S in an oct-tree;

determining a width 2r₀ of a near point search cube using a random sample R⊂

S, where r₀ is a positive real number; and

then, for each of the plurality of points p_i,

determining a subset of k₀ points that are closest in Euclidean distance to p_i and selecting from the subset all points that are also within a respective near point search cube that is centered about a corresponding point p_i and has a width equal to 2r₀, where k₀ is a positive integer.

12. The method of claim 1, wherein said determining step comprises identifying a respective subset of near points S_i for each of the plurality of points p_i by:

storing the 3D point set S in an oct-tree;

determining a width 2r₀ of a near point search cube using a random sample R⊂

S, where r₀ is a positive real number that equals a minimum value of r for which an average of a yield is greater than or equal to m₀ , where m₀ is a positive constant and the yield equals the number of points in S that are within a near point search cube of width 2r centered about a respective point in the random sample R; and

then, for each of the plurality of points p_i in the 3D point set S,

determining a subset of k₀ points that are closest in Euclidean distance to p_i and selecting from the subset all points that are also within a respective near point search cube that is centered about a corresponding point p_i and has a width equal to 2r₀ , where k₀ is a positive integer.

13. The method of claim 11, where m₀ is about equal to 100 and k₀ is about equal to 30.

71. A surface modeling apparatus, comprising:

means for performing the method of any one of claims 1-53 and 66-70.

72. A computer program product readable by a machine and tangibly embodying a program of instructions executable by the machine to perform the method of any one of claims 1-53 and 66-70.

14. A method of modeling a three-dimensional (3D) surface, comprising the steps of:

determining a plurality of stars from a plurality of points p_i in a 3D point set S that at least partially describes the 3D surface, by projecting each of the plurality of points p_i onto a respective plane; and

merging the plurality of stars into a model of the 3D surface by eliminating edges and triangles from the plurality of stars that are in conflict and merging nonconflicting edges and triangles from the plurality of stars into a 3D surface triangulation.

15. The method of claim 14, wherein said merging step comprises:

sorting triangles within the plurality of stars and removing those sorted triangles that are not in triplicate;

connecting the sorted triangles that have not been removed to define a triangulated pseudomanifold as a two-dimensional simplicial complex in which edges and triangles of a star that share a vertex form a portion of an open disk;

sorting edges within the plurality of stars that do not belong to any of the triangles in the triangulated pseudomanifold and removing those sorted edges that are not in duplicate; and

adding the sorted edges that have not been removed to the triangulated pseudomanifold.

16. The method of claim 14, wherein said merging step comprises:

sorting triangles within the plurality of stars and removing those sorted triangles that are not in triplicate.

17. The method of claim 16, wherein said merging step further comprises:

connecting the sorted triangles that have not been removed to define a triangulated pseudomanifold as a two-dimensional simplicial complex.

18. The method of claim 17, wherein said merging step further comprises:

sorting edges within the plurality of stars that do not belong to any of the triangles in the triangulated pseudomanifold and removing those sorted edges that are not in duplicate; and

adding the sorted edges that have not been removed to the triangulated pseudomanifold.

19. A method of modeling a three-dimensional (3D) surface, comprising the steps of:

determining a plurality of triangulated neighborhoods from a plurality of points in a 3D point set that at least partially describes the 3D surface, by projecting each of the plurality of points and one or more neighboring points in the 3D point set to a respective plane; and

merging the plurality of triangulated neighborhoods into a digital model of the 3D surface.

20. The method of claim 19, wherein said determining step comprises projecting each of the plurality of points and one or more neighboring points in the 3D point set to a respective tangent plane.

21. A method of modeling a surface of an object, comprising the steps of:

projecting each point and corresponding set of one or more neighboring points in a point set to a respective plane;

determining a star for each plane; and

merging the stars into a surface triangulation.

22. The method of claim 21, wherein said projecting step comprises projecting each point and corresponding set of one or more neighboring points in a point set to a respective plane that is estimated to be tangent about the point.

23. The method of claim 21, wherein said step of determining a star for each plane comprises determining a star having vertices that are weighted as a function of projection distance for each plane.

24. A method of modeling a three-dimensional (3D) surface, comprising the steps of:

determining an estimated normal for each of a plurality of points in a 3D point set that at least partially describes the 3D surface;

evaluating a differential structure of the estimated normals associated with the plurality of points to estimate principal curvature directions on the 3D surface and classify a respective local neighborhood of each of the plurality of points in terms of its shape characteristic;

determining a respective approximating surface for each of the local neighborhoods; and

denoising the 3D point set by moving each of the plurality of points to a respective approximating surface that is associated with a local neighborhood of the respective point.

25. A method of modeling a three-dimensional (3D) surface, comprising the steps of:

determining a respective set of near points S_i for each of a plurality of points p_i in a 3D point set S that at least partially describes the 3D surface, where S_i⊂

S;

determining a normal bundle for the 3D point set S by determining a respective plane h_i of best fit for each of the sets of near points S_i and a respective normal n_i for each of the planes h_i of best fit; and

determining a respective approximating surface for each of the sets of near points S_i using the normal bundle to estimate respective principal curvature directions for each of the sets of near points S_i.

26. A method of modeling a three-dimensional (3D) surface, comprising the steps of:

determining a respective set of near points S_i for each of a first plurality of points p1_i in a first 3D point set S1 that at least partially describes the 3D surface, where S_i⊂

S1;

fitting each set of near points S_i with a respective approximating surface;

denoising the first 3D point set S1 into a second 3D point set S2 by moving at least some of the first plurality of points p1_i in the first 3D point set S1 to the approximating surfaces associated with their respective sets of near points S_i;

determining a plurality of stars from a second plurality of points p2_i in the second 3D point set S2, by projecting the second plurality of points p2_i onto planes T_i that are estimated to be tangent about a respective one of the second plurality of points p2_i; and

merging the plurality of stars into a digital model of the 3D surface.

27. The method of claim 26, wherein said step of fitting each set of near points S_i with a respective approximating surface comprises fitting a first set of near points S₁ with a first approximating surface by:

determining respective planes h_j of best fit for each of a plurality of points p_j in the first set of near points S₁; and

determining an estimated normal n_j for each of the points p_j as a normal of its respective plane h_j of best fit.

28. The method of claim 26, wherein said step of fitting each set of near points S_i with a respective approximating surface comprises fitting a first set of near points S₁ with a first approximating surface by:

determining respective planes h_j of best fit for each of a plurality of points p_j in the first set of near points S₁;

determining an estimated normal n_j for each of the points p_j as a normal of its respective plane h_j of best fit; and

classifying the first set of near points S₁ in terms of its shape characteristic, by determining estimates of principal curvature directions for a point p1_i from a plurality of the estimated normals n_j.

29. The method of claim 26, wherein said step of fitting each set of near points S_i with a respective approximating surface comprises classifying a shape characteristic of each set of near points S_i as plane-like and/or edge-like and/or corner-like.

30. A method of modeling a three-dimensional (3D) surface, comprising the steps of:

determining a respective set of near points for each of a plurality of points in a 3D point set that at least partially describes the 3D surface;

fitting each set of near points with a respective approximating surface that is a selected from a group consisting of cylinders and quadratic and/or cubic surfaces; and

denoising the 3D point set by moving each of the plurality of points in the 3D point set to the approximating surface associated with its respective set of near points.

31. A method of modeling a three-dimensional (3D) surface, comprising the steps of:

determining a respective set of near points for each of a first plurality of points in a 3D point set that at least partially describes the 3D surface; and

determining an estimated normal for each of the first plurality of points by;

determining a respective plane of best fit for each of the sets of near points; and

determining a normal for each of the planes of best fit.

32. A method of modeling a three-dimensional (3D) surface, comprising the steps of:

determining a respective set of near points for each of a first plurality of points in a 3D point set that at least partially describes the 3D surface;

determining a normal bundle by determining a respective plane of best fit for each of the sets of near points and a normal for each of the planes of best fit; and

determining from the normal bundle at least one respective principal curvature direction for each of the sets of near points.

33. A method of modeling a three-dimensional (3D) surface, comprising the step of:

denoising a 3D point set that at least partially describes the 3D surface by;

classifying a first neighborhood of points in the 3D point set S1 using a mass distribution matrix of the first neighborhood of points to estimate first normals associated with the first neighborhood of points and a normal distribution matrix of the first normals to estimate principal curvature directions;

fitting an approximate surface, which is selected from a group consisting of cylindrical, quadratic and cubic surfaces, to the first neighborhood of points; and

moving at least one point in the first neighborhood of points to the approximate surface.

34. A method of modeling a three-dimensional (3D) surface, comprising the steps of:

identifying a respective subset of near points for each of a plurality of points in a 3D point set that at least partially describes the 3D surface by;

determining dimensions of a near point search space using a random sample of the 3D point set; and

selecting, for each of the plurality of points, a respective set of points in the 3D point set that are within a respective near point search space that is oriented about a respective one of the plurality of points;

determining a plurality of stars from the plurality of points in the 3D point set by projecting the points in each subset of near points to a respective plane; and

merging the plurality of stars into a digital model of the 3D surface.

35. The method of claim 34, wherein each near point search space comprises a space selected from the group consisting of cubes, elipsoids, spheres and parallelpipeds.

36. The method of claim 34, wherein said step of determining a plurality of stars comprises determining a plurality of stars from the plurality of points in the 3D point set by projecting the points in each subset of near points to a respective estimated tangent plane.

37. A method of reconstructing a surface of an object from a three-dimensional (3D) point cloud data set S derived from scanning the object, comprising the steps of:

determining a respective subset of near points S_i⊂

S for each of a plurality of points p_iε

S;

estimating a tangent plane T_i for each subset of near points S_i;

projecting each subset of near points S_i onto its respective tangent plane T_i;

constructing a respective star of each of the plurality of points p_i from the projected points on each of the tangent planes T_i;

merging the stars associated with the tangent planes T_i into a 3D model of the surface by eliminating edges and triangles from the stars that are in conflict and merging nonconflicting edges and triangles from the stars into a 3D surface triangulation; and

filling one or more holes in the 3D surface triangulation.

38. A method of reconstructing a surface of an object from a three-dimensional dimensional (3D) point cloud, comprising the steps of:

determining for each of a first plurality of points in the point cloud a respective approximating surface that fits the point'"'"'s neighborhood;

moving each of the first plurality of points to its respective approximating surface;

determining an estimated tangent plane for each of a second plurality of points that have been moved to a respective approximating surface;

projecting each of the second plurality of points and points in their respective neighborhoods to a respective one of the estimated tangent planes;

constructing stars from points projected to the estimated tangent planes; and

merging the stars into a surface triangulation.

39. The method of claim 38, further comprising the step of filling one or more holes in the surface triangulation.

40. A method of reconstructing a surface of an object from a three-dimensional (3D) point cloud, comprising the steps of:

denoising the point cloud;

determining an estimated tangent plane for each of a plurality of points in the denoised point cloud;

projecting each of the plurality of points and other points in its respective neighborhood to a respective one of the estimated tangent planes;

constructing stars from points projected to the estimated tangent planes; and

merging the stars into a surface triangulation.

41. The method of claim 40, further comprising the step of filling one or more holes in the surface triangulation by:

constructing a directed graph that represents each principal edge of the surface triangulation by its two directed versions and each boundary edge as a single directed edge; and

identifying a boundary cycle of at least one hole by partitioning the directed graph into directed cycles.

42. The method of claim 41, wherein said step of identifying a boundary cycle is followed by the step of identifying simple holes.

43. The method of claim 42, wherein said step of identifying simple holes comprises identifying holes having index cycles that are Davenport-Schinzel cycles of order less than three.

44. A method of denoising a three-dimensional (3D) point set, comprising the steps of:

estimating directions of a local collection of normals associated with a local collection of data points in the 3D point set by determining eigenvectors of a mass distribution matrix of the local collection of data points; and

estimating directions of curvature associated with the local collection of data points by determining eigenvectors of a normal distribution matrix of the local collection of normals.

45. A method of modeling a three-dimensional (3D) surface, comprising the steps of:

moving each of a plurality of first points in a point set that at least partially describes the 3D surface to a respective approximating surface that is derived by evaluating a respective first point and a plurality of its neighboring points in the point set;

projecting at least one of the first points, which has been moved to an approximating surface, to a first plane that is estimated to be tangent about the at least one of the first points;

projecting a plurality of points in a neighborhood of the at least one of the first points to the first plane; and

generating a star from a plurality of projected points on the first plane.

46. A method of modeling a three-dimensional (3D) surface, comprising the step of:

determining a star of a first point in a 3D point set that at least partially describes the 3D surface, by;

projecting the first point and second, third and fourth points in a neighborhood of the first point to a plane;

assigning respective weights to each of the second, third and fourth points that are based on projection distance; and

evaluating whether the projection of the fourth point is within an orthocircle defined by a triangle having projections of the first, second and third points as vertices.

47. A method of modeling a three-dimensional (3D) surface, comprising the step of:

determining a first star of a first point in a 3D point set that at least partially describes the 3D surface, by;

projecting the first point and first near points in a neighborhood of the first point to a first plane that is estimated to be tangent to the first point;

assigning respective weights to each of the projected first near points that are based on distances between the first near points and the projected first near points; and

connecting the projected first point and at least some of the projected first near points with triangles that share the projected first point as a vertex, by evaluating whether a next projected near point in a first sequence of projected first near points is closer than orthogonal to an orthocenter of a triangle having the projected first point and two of the projected first near points as vertices.

48. The method of claim 47, further comprising the step of:

determining a second star of a second point in the 3D point set by;

projecting the second point and second near points in a neighborhood of the second point to a second plane that is estimated to be tangent to the second point;

assigning respective weights to each of the projected second near points that are based on distances between the second near points and the projected second near points; and

connecting the projected second point and at least some of the projected second near points with triangles that share the projected second point as a vertex, by evaluating whether a next projected near point in a second sequence of projected second near points is closer than orthogonal to an orthocenter of a triangle having the projected second point and two of the projected second near points as vertices.

49. A method of modeling a three-dimensional (3D) surface, comprising the step of:

sequentially connecting a neighborhood of projected points on a plane to a first projected point on the plane by evaluating whether at least one projected point in the neighborhood of projected points is closer than orthogonal to an orthocircle defined by a triangle containing the first projected point and two projected points in the neighborhood of projected points as vertices, with the neighborhood of projected points having weights associated therewith that are each a function of a projection distance between a respective projected point in the neighborhood of projected points and a corresponding point in a 3D point set that at least partially describes the 3D surface.

50. The method of claim 49, wherein the connected neighborhood of projected points constitutes a weighted Delaunay triangulation.

51. The method of claim 49, wherein the plane is estimated to be tangent to the 3D surface.

52. A method of modeling a three-dimensional (3D) surface, comprising the steps of:

projecting a first point in a 3D point set that at least partially describes the surface and a set of points in a neighborhood of the first point to a plane that is estimated to be tangent to the surface at the first point; and

creating a weighted Delaunay triangulation comprising triangles that share a projection of the first point in the plane as a vertex and include at least some of the projections of the set of points in the neighborhood of the first point as vertices that are weighted as a function of projection distance.

53. The method of claim 52, wherein the vertices are weighted as a function of projection distance squared.

54. An apparatus for modeling a three-dimensional (3D) surface, comprising:

means for determining a plurality of stars from a plurality of points p_i in a 3D point set S that at least partially describes the 3D surface, by projecting the plurality of points p_i onto planes T_i that are each estimated to be tangent about a respective one of the plurality of points p_i; and

means for merging the plurality of stars into a digital model of the 3D surface.

55. The apparatus of claim 54, wherein said determining means comprises means for identifying a respective subset of near points S_i for each of the plurality of points p_i.

56. The apparatus of claim 55, wherein said determining means comprises means for projecting a plurality of points p_j in each subset of near points S_i to a respective estimated tangent plane T_i.

57. The apparatus of claim 56, wherein said determining means comprises means for determining for each of a plurality of estimated tangent planes, T_i, a star of the projection of a respective point p_i onto the estimated tangent plane T_i.

58. The apparatus of claim 57, wherein the star of the projection of a respective point p_i onto the estimated tangent plane T_i constitutes a two-dimensional (2D) weighted Delaunay triangulation.

59. An apparatus for modeling a three-dimensional (3D) surface, comprising:

means for determining a plurality of stars from a plurality of points p_i in a 3D point set S that at least partially describes the 3D surface, by projecting each of the plurality of points p_i onto a respective plane; and

means for merging the plurality of stars into a model of the 3D surface by eliminating edges and triangles from the plurality of stars that are in conflict and merging nonconflicting edges and triangles from the plurality of stars into a 3D surface triangulation.

60. The apparatus of claim 59, wherein said merging means comprises means for sorting triangles within the plurality of stars and removing those sorted triangles that are not in triplicate.

61. The apparatus of claim 60, wherein said merging means further comprises:

means for connecting the sorted triangles that have not been removed to define a triangulated pseudomanifold as a two-dimensional simplicial complex.

62. The apparatus of claim 61, wherein said merging means further comprises:

means for sorting edges within the plurality of stars that do not belong to any of the triangles in the triangulated pseudomanifold and removing those sorted edges that are not in duplicate; and

means for adding the sorted edges that have not been removed to the triangulated pseudomanifold.

63. A computer program product that models three-dimensional (3D) surfaces and comprises a computer-readable storage medium having computer-readable program code embodied in said medium, said computer-readable program code comprising:

computer-readable program code that determines a plurality of stars from a plurality of points p_i in a 3D point set S that at least partially describes the 3D surface, by projecting each of the plurality of points p_i onto a respective plane; and

computer-readable program code that merges the plurality of stars into a model of the 3D surface by eliminating edges and triangles from the plurality of stars that are in conflict and merging nonconflicting edges and triangles from the plurality of stars into a 3D surface triangulation.

64. The computer program product of claim 63, wherein said computer-readable program code that merges the plurality of stars comprises:

computer-readable program code that sorts triangles within the plurality of stars and removes those sorted triangles that are not in triplicate;

computer-readable program code that connects the sorted triangles that have not been removed to define a triangulated pseudomanifold as a two-dimensional simplicial complex in which edges and triangles of a star that share a vertex form a portion of an open disk;

computer-readable program code that sorts edges within the plurality of stars that do not belong to any of the triangles in the triangulated pseudomanifold and removes those sorted edges that are not in duplicate; and

computer-readable program code that adds the sorted edges that have not been removed to the triangulated pseudomanifold.

65. A computer program product that models three-dimensional (3D) surfaces and comprises a computer-readable storage medium having computer-readable program code embodied in said medium, said computer-readable program code comprising:

computer-readable program code that projects a first point in a 3D point set that at least partially describes a 3D surface and a set of points in a neighborhood of the first point to a plane that is estimated to be tangent to the 3D surface at the first point; and

computer-readable program code that creates a weighted Delaunay triangulation comprising triangles that share a projection of the first point in the plane as a vertex and include at least some of the projections of the set of points in the neighborhood of the first point as vertices that are weighted as a function of projection distance.

66. A method of modeling a three-dimensional (3D) surface, comprising the steps of:

projecting a first point in a 3D point set that at least partially describes the surface and a set of points in a neighborhood of the first point to a plane that is estimated to be tangent to the surface at the first point; and

creating a weighted Delaunay triangulation comprising triangles that share a projection of the first point in the plane as a vertex and include at least some of the projections of the set of points in the neighborhood of the first point as vertices that are weighted as a function of projection distance, by evaluating whether or not one or more of the projections of the set of points in the neighborhood of the first point are closer than orthogonal to an orthocenter of a first triangle in the weighted Delaunay triangulation.

67. The method of claim 66, wherein each of at least a plurality the vertices is weighted as a function of projection distance squared.

68. The method of claim 66, wherein said creating step comprises evaluating a matrix containing coordinates of the vertices of the first triangle as entries therein.

69. The method of claim 68, wherein said creating step comprises computing a determinant of the matrix.

70. The method of claim 69, wherein the matrix is a 4×

4 matrix; and

wherein at least some of the entries in the matrix are functionally dependent on the weights associated with the vertices of the first triangle.