Methods of generating three-dimensional digital models of objects by wrapping point cloud data points

• US 6,377,865 B1
• Filed: 02/11/1999
• Issued: 04/23/2002
• Est. Priority Date: 02/11/1998
• Status: Expired due to Term

• Current Assignee: 3D Systems, Inc. (3D Systems Corporation)
• Original Assignee: Raindrop Geomagic, Inc. (3D Systems Corporation)
• Inventors: Edelsbrunner, Herbert, Fu, Ping
• Primary Examiner(s): Grant, William
• Assistant Examiner(s): CABRERA, ZOILA E
• Application Number:
  US09/248,587
• Time in Patent Office: 1,167 Days
• Field of Search: 700/98, 700/97, 700/117, 700/118, 700/119, 700/120, 700/182, 345/419, 345/420, 703/2
• US Class Current: 700/98
• CPC Class Codes: G06T 17/10 Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06V 30/144 using a slot moved over the image; using discrete sensing elements at predetermined points; using automatic curve following means
• CPC Class Codes: G16Z 99/00 Subject matter not provided for in other main groups of this subclass

Abstract

A method of automatic conversion of a physical object into a three-dimensional digital model. The method acquires a set of measured data points on the surface of a physical model. From the measured data points, the method reconstructs a digital model of the physical object using a Delaunay complex of the points, a flow strcuture of the simplicies in the Delaunay complex and retracting the Delaunay complex into a digital model of the physical object using the flow structure. The method then outputs the digital model of the physical object.

Claims

1. A method of converting a physical object into a three-dimensional digital model, the method comprising the steps of:

acquiring data points measured from a surface of the physical object;

reconstructing a three-dimensional digital model of the physical object from the data points by;

constructing a Delaunay complex of the data points and a flow structure of simplices in the Delaunay complex; and

retracting the Delaunay complex into three-dimensional digital model of the physical object using the flow structure; and

modifying the three-dimensional digital model using a shape improvement method selected from the group consisting of data relaxation by filtering out high surface frequencies, surface refinement by decomposing edges and triangles, surface decimation by reducing a number of edges and triangles and surface thickening.

2. The method according to claim 1 wherein the data points are represented as a list of Cartesian coordinates.

3. The method according to claim 1 wherein the data points are acquired by a three-dimensional scanner, digitizer or other hardware able to measure points in three-dimensional space.

4. The method according to claim 1 wherein the data points are derived from a previously generated three-dimensional digital model.

5. The method according to claim 1 wherein the three- dimensional digital model is used to fabricate or manufacture copies or modifications of the physical object.

6. The method according to claim 1 wherein the three-dimensional digital model is used for computer visualizations, animations, or other uses in computer graphics.

7. The method according to claim 1 wherein the three-dimensional digital model is stored for purposes of archiving or supporting database searches.

8. The method according to claim 1 wherein the three-dimensional digital model comprises a description of a volume of the physical object in terms of tetrahedra connecting the data points.

9. A method of generating a model of an object, comprising the steps of:

acquiring data points that define a shape of the object; and

constructing a three-dimensional digital model of the object by;

determining a Delaunay complex from the data points;

determining an acyclic flow relation of simplices in the Delaunay complex;

determining a first boundary of the Delaunay complex; and

retracting the Delaunay complex by collapsing a first simplex pair in the acyclic flow relation at the first boundary.

10. The method according to claim 9, wherein the acquiring step and the constructing step are interleaved.

11. The method according to claim 10 further comprising the steps of:

considering additional points to be used in constructing the three-dimensional digital model;

discarding redundant ones of the additional points; and

changing the three-dimensional digital model by incorporating at least some of the additional points that contribute valuable information about the object.

12. The method according to claim 9, wherein the constructing step comprises the step of editing the retracted Delaunay complex to remove extraneous surfaces and punch holes in the Delaunay complex that appear as tunnels in the three-dimensional digital model having a non star-shaped surface that outlines a volume.

13. The method of claim 9, wherein the step of collapsing a first simplex pair in the acyclic flow relation at the first boundary defines a second boundary and is followed by the step of collapsing a second simplex pair in the acyclic flow relation at the second boundary.

14. A method of modeling a non star-shaped surface of a physical object, comprising the steps of:

acquiring data points that describe the non star-shaped surface of the physical object and are identified by their Cartesian coordinates;

processing the data points using an automated wrap function that, independent of information in excess of the Cartesian coordinates of the data points, converts the data points into a three-dimensional digital model of the non star-shaped surface of the physical object; and

outputting the three-dimensional digital model of the non star-shaped surface of the physical object.

15. The method according to Claim 14 wherein the processing step is performed by hardware functioning as a three-dimensional faxing machine.

16. The method according to claim 14 wherein the processing step is performed by three-dimensional scanning hardware.

17. The method according to claim 14 wherein the processing step is made automatic by a customized template, wherein the template reflects shared data characteristics acquired from multiple reconstructions.

18. The method according to claim 14 wherein the processing step is performed by software embedded in an inventory system that stores digital models of three-dimensional physical objects in a database and supports the operations of retrieving and matching digital models.

19. The method according to claim 14 wherein the processing step generates a unique three-dimensional digital model of the non star-shaped surface of the physical object.

20. The method according to claim 19 wherein the uniqueness of the three-dimensional digital model is exploited to facilitate the interleaving of the acquiring step and the processing step.

21. The method according to claim 14 wherein the processing step generates digital surface models with manifold structure and with non-manifold structure.

22. The method according to claim 14 wherein the processing step is performed by software operating within a computer.

23. The method according to claim 14 wherein the three-dimensional digital model consists of an impeccable surface without cracks and without self-intersections.

24. A method of generating a model of an object, comprising the steps of:

acquiring a set of data points that define a shape of the object and carry information regarding respective probing half-lines; and

constructing a three-dimensional digital model of the object from the set of data points by;

generating a first three-dimensional digital model having a first boundary;

checking for intersections between a probing half-line and

simplices of the first three-dimensional digital model;

eliminating simplices of the first three-dimensional digital model that intersect the probing half-line to thereby define a second three-dimensional digital model having a second boundary; and

retracting the second three-dimensional digital model by removing simplices on the second boundary.

25. The method according to claim 24 wherein the constructing step and the acquiring step are interleaved.

26. The method according to claim 25 wherein the constructing step samples a subset of data points within the set of data points and then partially constructs the three-dimensional digital model from the sampled points and then uses the partially constructed three-dimensional model as a filter to determine which ones of remaining data points within the set of data points are to be used in generating a final three-dimensional digital model.

27. A method of generating a model of an object, comprising the steps of:

constructing a Delaunay complex of points and a flow structure of simplices in the Delaunay complex; and

retracting the Delaunay complex into a three-dimensional digital model of the object using the flow structure as a guide.

28. A computer program product that models an object 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 means that constructs a Delaunay complex of points and a low structure of simplices in the Delaunay complex; and

computer-readable program code means that retracts the Delaunay complex into a three-dimensional digital model of the object using the flow structure as a guide.

29. The program product of claim 28, wherein said medium comprises a CD-ROM.

30. A method of modeling a non star-shaped surface of a physical object, comprising the steps of:

acquiring data points that describe the non star-shaped surface of the physical object and are identified by their Cartesian coordinates; and

processing the data points using an automated wrap function that, independent of connectivity information linking the data points by edges and triangles, converts the data points into a three-dimensional digital model of the non star-shaped surface of the physical object.