(12) United States Patent
`Edelsbrunner et al.
`
`USOO6377865B1
`(10) Patent No.:
`US 6,377,865 B1
`(45) Date of Patent:
`Apr. 23, 2002
`
`(54) METHODS OF GENERATING THREE-
`DIMENSIONAL DIGITAL MODELS OF
`OBJECTS BY WRAPPING POINT CLOUD
`DATA POINTS
`(75) Inventors: Herbert Edelsbrunner; Ping Fu, both
`of Chapel Hill, NC (US)
`(73) Assignee: Raindrop Geomagic, Inc., Research
`Triangle Park, NC (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(*) Notice:
`
`(21) Appl. No.: 09/248,587
`1-1.
`(22) Filed:
`Feb. 11, 1999
`Related U.S. Application Data
`(60) Provisional application No. 60/074,415, filed on Feb. 11,
`1998.
`
`(51) Int. Cl." ................................................ G06F 19/00
`
`(52) U.S. Cl. .............................. 700/98; 703/2; 345/419
`(58) Field of Search ............................. 700/98, 97,117,
`700/118, 119, 120, 182; 345/419, 420;
`703/2
`
`(56)
`
`References Cited
`
`5,850.229 A * 12/1998 Edelsbrunner et al. ...... 345/473
`5,870.220 A 2/1999 Migdal et al. .............. 359/216
`5,886,702 A * 3/1999 Migdal et al. .............. 345/423
`(List continued on next page.)
`OTHER PUBLICATIONS
`“Computing Dirichlet tessallations,' A Bowyer; The Com
`puter Journal, vol. 24, No. 2, pp. 162-166, 1981: Heyden &
`Son Ltd., 1981.
`“Optimal Surface Reconstuction From Planar Contours.”
`Fuchs, et al., Copyright 1977, ASSociation for Computing
`Machinery, Inc., Communications, vol. 20, pp. 693–702;
`Oct. 1977, ACM, Box 12105, Church Street Station, New
`York, NY 11249.
`“Geometric Structures for Three-Dimensional Shape Rep
`resentation, Boissonnat, ACM Transactions on Graphics,
`vol. 3, No. 4, pp. 267–286, Oct. 1984.
`“Shape Reconstruction From Planar Cross Sections.” Bois
`Sonnat, Computer Vision, Graphics and Image Processing
`44; pp. 1-29; 1988.
`“Construction of Three-Dimensional Delaunay Triangula
`tions Using Local Transformations, Joe; Computer Aided
`Geometric Design 8, 1991; pp. 123-142; Elsevier Science
`Publishers B.V. (North-Holland).
`(List continued on next page.)
`Primary Examiner William Grant
`Assistant Examiner Zoila Cabrera
`Bigel Siblew & &
`74Y Aff
`Agent
`Firm-M
`s R. Orney, Agent, or firm-Vyers 51gel Sloley
`
`(57)
`
`ABSTRACT
`
`U.S. PATENT DOCUMENTS
`4,719,585 A * 1/1988 Cline et al. ................. 345/424
`A method of automatic conversion of a physical object into
`5,214,752. A
`5/1993 Meshkat et al. ............ 395/123.
`a three-dimensional digital model. The method acquires a Set
`5,278,948 A
`1/1994 Luken, Jr. ................... 395/123
`of measured data points on the Surface of a physical model.
`5,357,599 A 10/1994 Luken .......
`... 395/134
`From the measured data points, the method reconstructs a
`5,440,674. A 8/1995 Park .............
`... 395/123
`digital model of the physical object using a Delaunay
`5,506,785 A 4/1996 Blank et al. ...
`... 364/468
`5. A o R et al. .
`3.25 complex of the points, a flow Strcuture of the Simplicies in
`5,555,356 A 9/1996 Scheibl.......................
`the Play ople an rts stally "ple
`5,600,060 A 2/1997 Grant .......................... 75, into a digital model of the physical object using the flow
`5617.322 A
`4/1997 Yokota ........................ 700/98
`structure. The method then outputs the digital model of the
`5,668,894. A
`9/1997 Hamano et al. ... 382.242
`physical object.
`5,760,783 A
`6/1998 Migdal et al. .............. 345/473
`5,768,156 A 6/1998 Tautges et al. ............. 364/578
`30 Claims, 19 Drawing Sheets
`
`2- - 12
`
`llc .........
`
`
`
`
`
`22
`
`NPSIAPEX
`
`
`
`FOREVERY PROPERCOFACE OF DO
`
`26
`NOTHEREISFLOW YES
`FROM TO
`
`628
`OUTPUT:EQUINOCAL
`
`630s,
`FOREWER PROPERFACE OF EDO
`
`
`
`634,
`—- OUTPUT: CONFIDENT
`36 Y
`OUTPUT CETERED
`
`EX1082
`Yita v. MacNeil
`IPR2020-01139
`
`

`

`US 6,377,865 B1
`US 6,377,865 B1
`
`Page 2
`Page 2
`
`
`
`U.S. PATENT DOCUMENTS
`U.S. PATENT DOCUMENTS
`5,903,458 A
`5/1999 Stewart et al.
`......... 364/468.04
`5,903,458 A 5/1999 Stewart et al. ......... 364/468.04
`
`5,923,573 A
`7/1999 Hatanaka...
`.... 364/578
`5,923,573 A
`7/1999 Hatanaka ...
`... 364/578
`
`5,929,860 A
`TF/1999 Hoppe ....... ee
`w. 345/419
`5,929,860 A 7/1999 Hoppe ..............
`... 345/419
`5.936,869 A * 8/1999 Sakaguchi et al. ............. 703/1
`5,936,869 A *
`8/1999 Sakaguchiet al.
`............ 703/1
`
`5,945.996 A 8/1999 Migdal et al. ...
`... 345/420
`5,945,996 A
`8/1999 Migdal et al.
`....
`.. 345/420
`
`5,963,209 A
`10/1999 Hoppe ......... cee 345/419
`5,963,209 A 10/1999 Hoppe ........................ 345/419
`5,966,133 A
`10/1999 Hoppe ......... cee 345/420
`5,966,133 A 10/1999 Hoppe ........................ 345/420
`5,966,140 A 10/1999 Popovic et al.
`... 345/441
`5,966,140 A
`10/1999 Popovic etal.
`. 345/441
`
`5,966,141 A
`10/1999 Ito etal. wu.
`... 345/473
`5,966,141 A 10/1999 Ito et al. ...........
`... 345/473
`5.991,437 A 11/1999 Migdal et al. .
`... 382/154
`5,991,437 A
`11/1999 Migdal et al.
`.
`. 382/154
`5,995,650 A 11/1999 Migdal et al. .............. 34.5/154
`5,995,650 A
`11/1999 Migdal et al. o.. 345/154
`6,044,170 A 3/2000 Migdal et al. .............. 382/154
`6,044,170 A
`3/2000 Migdal et al.
`......000.. 382/154
`6,046,744 A
`4/2000 Hoppe..........
`w. 345/419
`6,046,744 A 4/2000 Hoppe ..........
`... 345/419
`
`6,064,771 A 5/2000 Migdal et al. .
`... 382/232
`6,064,771 A
`5/2000 Migdalet al.
`.
`382/232
`6,100,893 A *
`8/2000 Enszet al.
`.....
`.. 345/420
`6,100,893 A * 8/2000 Ensz et al......
`... 345/420
`
`6,108,006 A *
`8/2000 Hoppe.......
`we 345/423
`6,108,006 A * 8/2000 Hoppe .......
`... 345/423
`6,133,921. A * 10/2000 Turkiyyah et al. .......... 345/420
`6,133,921 A * 10/2000 Turkiyyah etal. ........... 345/420
`6,176.427 B1 * 1/2001 Antognini et al. .......... 235/454
`6,176,427 B1 *
`1/2001 Antogniniet al.
`.......... 235/454
`
`6,205.243 B1
`3/2001 Migdal et al. ...
`... 382/154
`6,205,243 B1
`3/2001 Migdalet al.
`....
`. 382/154
`
`6,208,347 B1 * 3/2001 Migdal et al. .
`... 345/419
`6,208,347 B1 *
`3/2001 Migdal et al.
`.
`... 345/419
`6,266,062 Bl *
`7/2001 Rivara .........0...
`w. 345/419
`6,266,062 B1 * 7/2001 Rivara ..............
`... 345/419
`6,278,457 B1 *
`8/2001 Bernardiniet al.
`......... 345/420
`6.278,457 B1 * 8/2001 Bernardini et al. ......... 345/420
`OTHER PUBLICATIONS
`OTHER PUBLICATIONS
`“Surface Reconstruction From Unorganized Points.” Hoppe
`“Surface Reconstruction From Unorganized Points,” Hoppe
`et al.; Computer Graphics 26; Jul. 1992; pp. 71-78.
`et al; Computer Graphics 26; Jul. 1992; pp. 71-78.
`“Surfaces From Contours,” Meyers et al.; ACM Transac
`“Surfaces From Contours,” Meyers et al.; ACM Transac-
`tions on Graphic, vol. 11; No. 3; Jul. 1992; pp. 228-258.
`tions on Graphic;, vol. 11; No. 3; Jul. 1992; pp. 228-258.
`“Closed Object Boundaries From Scattered Points,” Remco
`“Closed Object Boundaries From Scattered Points,” Remco
`Coenraad Veltkamp; Proefschrift Rotterdam, Netherlands;
`Coenraad Veltkamp; Proefschrift Rotterdam,;Netherlands;
`IBSBN 90-9005424-3; 1991; pp. 1-149.
`IBSBN 90-9005424-3; 1991; pp. 1-149.
`“Mesh Optimization,"Hoppe et al.; Computer Graphics Pro
`“Mesh Optimization,”Hoppeet al.; Computer Graphics Pro-
`ceedings, Annual Conference Series, 1993; pp. 19-26.
`ceedings, Annual Conference Series, 1993; pp. 19-26.
`“Incremental Topological Flipping Works For Regular Tri
`“Incremental Topological Flipping Works For Regular Tri-
`angulations.” Eldelsbrunner et al.; Algorithmica, 1996;
`angulations,” Eldelsbrunner et al; Algorithmica, 1996;
`Springer-Verlag New York Inc., pp. 223-241.
`Springer-Verlag New York Inc.; pp. 223-241.
`“Three-Dimensional Alpha Shapes,” Edlesbrunner et al.;
`“Three—Dimensional Alpha Shapes,” Edlesbrunner et al;
`ACM Transactions on Graphics; vol. 13; No. 1; Jan. 1994;
`ACM Transactions on Graphics; vol. 13; No. 1; Jan. 1994;
`pp. 43-72.
`pp. 43-72.
`“Piecewise Smooth Surface Reconstruction.” Hoppe et
`“Piecewise Smooth Surface Reconstruction,” Hoppe et
`al.; Computer Graphics Proceedings, Annual Conference
`al.;Computer Graphics Proceedings, Annual Conference
`Series 1994; pp. 295-302.
`Series 1994; pp. 295-302.
`“Smooth Spline Surfaces Over Irregular Meshes,' Loop;
`“Smooth Spline Surfaces Over Irregular Meshes,” Loop;
`Computer Graphics Proceedings, Annual Conference Series
`Computer Graphics Proceedings, Annual Conference Series
`1994; pp. 303-310.
`1994,; pp. 303-310.
`“C-Surface Splines.” Peters; Society for Industrial and
`“C-Surface Splines,” Peters; Society for Industrial and
`Applied Mathematics; 1995, vol. 32; No. 2; pp. 645-666.
`Applied Mathematics; 1995,;vol. 32; No. 2; pp. 645-666.
`“Modeling With Cubic A-Patches,” Bajaj et al.; ACM
`“Modeling With Cubic A—Patches,” Bajaj et al; ACM
`Transactions on Graphics, vol. 14, No. 2, Apr. 1995; pp.
`Transactions on Graphics, vol. 14, No. 2, Apr. 1995; pp.
`103-133.
`103-133.
`“Automatic Reconstruction Of Surfaces And Scalar Fields
`“Automatic Reconstruction Of Surfaces And Scalar Fields
`From 3D Scans,” Bajaj et al.; ACM-0–89791-701-4/95/
`From 3D Scans,” Bajaj et al.; ACM-—0-89791-701-4/95/
`008; Computer Graphics Proceedings, Annual Conference
`008; Computer Graphics Proceedings, Annual Conference
`Series 1995; pp. 109-118.
`Series 1995; pp. 109-118.
`“Piecewise-Linear Interpolation
`Between Polygonal
`“Piecewise-Linear
`Interpolation Between
`Polygonal
`Slices,” Barequet et al., Computer Vision and Image Under
`Slices,” Barequet et al.; Computer Vision and Image Under-
`standing, vol. 63, No. 2, Mar. 1996; pp. 251-272.
`standing, vol. 63, No. 2, Mar. 1996; pp. 251-272.
`
`ss
`
`“AVolumetric Method For Building Complex Models From
`“A Volumetric Method For Building Complex Models From
`Range Images, Curless et al., Computer Graphics ProceSS
`Range Images,” Curless et al.; Computer Graphics Process-
`dings, Annual Conference Series, Aug. 1996; pp. 303-312.
`dings, Annual Conference Series, Aug. 1996; pp. 303-312.
`“Automatic Reconstruction Of B-Spline Surfaces Of Arbi
`“Automatic Reconstruction Of B-Spline Surfaces Of Arbi-
`trary Topological Type,” Eck et al., Computer Graphics
`trary Topological Type,” Eck et al.; Computer Graphics
`Proceedings, Annual Conference Series, Aug., 1996, pp.
`Proceedings, Annual Conference Series, Aug., 1996; pp.
`325-334.
`325-334.
`“Fitting Smooth Surfaces To Dense Polygon Meshes.”
`“Fitting Smooth Surfaces To Dense Polygon Meshes,”
`Krishnamurthy et al., Computer Graphics Proceedings,
`Krishnamurthy et al; Computer Graphics Proceedings,
`Annual Conference Series, Aug. 1996; pp. 313-324.
`Annual Conference Series, Aug. 1996; pp. 313-324.
`Clarkson et al., “Four Results on Randomized Incremental
`Clarkson et al., “Four Results on Randomized Incremental
`Constructions.” Lecture Notes in Computer Science, 9"
`Constructions,” Lecture Notes in Computer Science, 9”
`Symposium on Theoretical Aspects of Computer Science,
`Symposium on Theoretical Aspects of Computer Science,
`Cachan, France, Feb. 1992 Proceedings, pp. 463-474.
`Cachan, France, Feb. 1992 Proceedings, pp. 463-474.
`Dey et al., “Topology Preserving Edge Contraction,” Pub
`Deyet al., “Topology Preserving Edge Contraction,” Pub-
`lications De L'Institut Mathematique, vol. 66, No. 80, 1999,
`lications De L’Institut Mathematique, vol. 66, No. 80, 1999,
`pp. 23-45.
`pp. 23-45.
`Eck et al., “Automatic Reconstruction of B-Spline Surfaces
`Ecket al., “Automatic Reconstruction of B-Spline Surfaces
`of Arbitrary Topological Type,” Computer Graphics Pro
`of Arbitrary Topological Type,” Computer Graphics Pro-
`ceedings, Annual Conference Series, SIGGRAPH 96, New
`ceedings, Annual Conference Series, SIGGRAPH 96, New
`Orleans, LA, Aug. 4-9, 1996, pp. 325-334.
`Orleans, LA, Aug. 4-9, 1996, pp. 325-334.
`Edelsbrunner, et al., “Simulation of Simplicity: A Technique
`Edelsbrunner,et al., “Simulation of Simplicity: A Technique
`to Cope with Degenerate Cases in Geometric Algorithms,”
`to Cope with Degenerate Cases in Geometric Algorithms,”
`ACM Transactions on Graphics, vol. 9, No. 1, Jan. 1990, pp.
`ACM Transactions on Graphics, vol. 9, No. 1, Jan. 1990,pp.
`66-104.
`66-104.
`Edelsbrunner, H., “An Acyclicity Theorem for Cell Com
`Edelsbrunner, H., “An Acyclicity Theorem for Cell Com-
`plexes ind Dimension,'Combinatorica, vol. 10, No. 3, 1990,
`plexes in d Dimension,’Combinatorica, vol. 10, No. 3, 1990,
`pp. 251-260.
`pp. 251-260.
`Garland et al., "Surface Simplification Using Quadric Error
`Garlandet al., “Surface Simplification Using Quadric Error
`Metrics,” Computer Graphics Proceedings (SIGGRAPH),
`Metrics,” Computer Graphics Proceedings (SIGGRAPH),
`1997, pp.209–216.
`1997, pp.209-216.
`Hagen et al., “Variational Design with Boundary Conditions
`Hagenet al, “Variational Design with Boundary Conditions
`and Parameter Optimized Surface Fitting,” Geometric Mod
`and Parameter Optimized Surface Fitting,” Geometric Mod-
`eling: Theory and Practice, Springer-Verlag, 1997, pp.
`eling: Theory and Practice, Springer-Verlag, 1997, pp.
`3-13.
`3-13.
`Hsu et al., “Minimizing the Squared Mean Curvature Inte
`Hsuet al., “Minimizing the Squared Mean Curvature Inte-
`gral for Surfaces in Space Forms,” Experimental Math, vol.
`gral for Surfaces in Space Forms,” Experimental Math,vol.
`1, 1992, pp. 191–207.
`1, 1992, pp. 191-207.
`Lee et al., MAPS: Multiresolution Adaptive Parameteriza
`Lee et al., MAPS: Multiresolution Adaptive Parameteriza-
`tion of Surfaces, Computer Graphics Proceedings (SIG
`tion of Surfaces, Computer Graphics Proceedings (SIG-
`GRAPH), 1998, pp. 95–104.
`GRAPH), 1998, pp. 95-104.
`Lodha et al., “Scattered Data Techniques for Surfaces,” no
`Lodhaet al., “Scattered Data Techniques for Surfaces,” no
`date, 42 pages.
`date, 42 pages.
`Nakamoto Atsuhiro, “Diagonal Transformations and Cycle
`Nakamoto Atsuhiro, “Diagonal Transformations and Cycle
`Parities of Quadrangulations on Surfaces,” Journal of Com
`Parities of Quadrangulations on Surfaces,” Journal of Com-
`binatorial Theory, Series B 67, 1996, pp. 202-211.
`binatorial Theory, Series B 67, 1996, pp. 202-211.
`Nakamoto, Atsuhiro, “Diagonal Transformations in Qua
`Nakamoto, Atsuhiro, “Diagonal Transformations in Qua-
`drangulations of Surfaces,” Journal of Graph Theory, vol.
`drangulations of Surfaces,” Journal of Graph Theory, vol.
`21, No. 3, 1996, pp. 289-299.
`21, No. 3, 1996, pp. 289-299.
`Yang et al., "Segmentation of measured point data using a
`Yang et al., “Segmentation of measured point data using a
`parametric quadric Surface approximation, Comput
`parametric quadric
`surface
`approximation,” Comput-
`er-Aided Design 31, 1999, pp. 449-457.
`er—-Aided Design 31, 1999, pp. 449-457.
`* cited by examiner
`* cited by examiner
`
`

`

`US 6,377,865 B1
`US 6,377,865 B1
`
`AG.I.
`
`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 1 of 19
`Sheet 1 of 19
`
`
`
`DEVICE
`
`3DMODEL
`
`
`
`WRAPPROCESS
`
`
`
`POINTDATA
`
`INPUT
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 2 of 19
`Sheet 2 of 19
`
`US 6,377,865 B1
`US 6,377,865 B1
`
`200
`
`PREPROCESS
`PREPROCESS
`
`
`
`OO
`100
`
`200
`
`OUTPUT
`
`
`
`RECONSTRUCT
`OUTPUT
`RECONSTRUCT
`
`
`
`
`
`
`POSTPROCESS
`POSTPROCESS
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 3 of 19
`Sheet 3 of 19
`
`US 6,377,865 B1
`US 6,377,865 B1
`
`OOOR200
`
`400
`
`500
`
`800 OR 900
`
`DELAUNAY
`
`
`
`RETRACTION
`
`OUTPUT
`
` DELAUNAY
`RETRACTION OUTPUT AG. 3.
`
`FIG 3
`
`
`
`DELETION
`DELETION
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 4 of 19
`Sheet 4 of 19
`
`US 6,377,865 B1
`US 6,377,865 B1
`
`402
`
`D4-TETRAHEDRON plppp
`D4a~ TETRAREDRON PyPoP93P4
`
`[~«—
`I-e-
`
`
`
`
`
`
`
`
`
`44
`
`
`
`INPUT POINT
`INPUTPOINT
`
`p;
`EXISTS
`OUTPUT: D,
`P41 EXISTS
`OUTPUT: D;
`
`
`402
`
`
`
`
`
`
`FIG. 4.
`fic. 4.
`
` i~=-i+]
`INPUT: 2;
`
`
`
`
`o --TETRAHEDRON IND CONTAINING pi
`o ~~ TETRAHEDRONIN D;_) CONTAINING p;
`
`
`
`
`
`D-D-WITH p, CONNECTED TO ALL VISIBLE TRIANGLES
`D~~-D,_| WH; CONNECTED TO ALL VISIBLE TRIANGLES
`
`4. 2.
`D - DAFTER FLIPPINGSIMPLICESINLINK OF pi
`j ~~ D AFTER FLIPPING SIMPLICES IN LINK OF p;
`
`\ D
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 5 of 19
`Sheet 5 of 19
`
`US 6,377,865 B1
`US 6,377,865 B1
`
`A
`
`
`
`FIG 5.
`AG. 3.
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 6 of 19
`Sheet 6 of 19
`
`US 6,377,865 B1
`US 6,377,865 B1
`
`“/
`-4/
`SA
`yes
`Le
`
`x\\
`xs
`x |
`x
`an
`nig. 6A
`
`.
`
`yI™~
`“i
`a eis
`a aa
`a a
`wi
`wits
`wis
`wis
`
`FIG. 6B
`HG. OB.
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 7 of 19
`Sheet 7 of 19
`
`US 6,377,865 B1
`US 6,377,865 B1
`
`FIG VA,
`HG. 7A.
`
`AIG VB
`AG. 7B.
`
`FIG VC.
`AG. 7C
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 8 of 19
`Sheet 8 of 19
`
`US 6,377,865 B1
`US 6,377,865 B1
`
`622
`622
`
`INPUT: SIMPLEX
`INPUT: SIMPLEX +
`
`
`
`624
`624
`FOREVERY PROPER COFACE OF DO
`
`FOR EVERY PROPER COFACE v OF + DO 628
`
`FRO 5 be ©
`E. s ty YES
`
`628
`
`OUTPUT: EQUIVOCAL
`OUTPUT: EQUIVOCAL
`
`630
`630
`FOREVERY PROPERFACEO OF L DO
`FOR EVERY PROPER FACE o OF t DO
`
`632
`632
`NOTHERE IS FLOW YES
`
`NO}
`THERE IS FLOW [YES
`FROMt T00
`FROM TO O.
`
`634
`634
`
`636
`636
`
`OUTPUT: CONFIDENT
`OUTPUT: CONFIDENT
`
`OUTPUT CENTERED
`OUTPUT: CENTERED
`
`FIG 8.
`AiG. 8.
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 9 of 19
`Sheet 9 of 19
`
`US 6,377,865 B1
`US 6,377,865 B1
`
`582
`582
`
`INPUT: SIMPLICESt., of
`INPUT: SIMPLICES t, o
`
`584
`584
`FOREVERY FACE OF O THATIS
`FOR EVERY FACE » OF o THATIS
`COFACE OF AND DIM u = DIMO - DO
`COFACE OF + AND DIM v = DIMo -1 DO
`
`586 Nu-N
`588
`586. ———~
`588
`NOTEREYES
`
`No(_,THEREIS ~Wyec
`ELEMENTARY FLOW
`OUTPUT NO
`ELEMENTARY FLOW
`OUTPUT: NO
`FROM O TO
`FROM 10 v
`
`590
`590
`
`OUTPUT: YES
`OUTPUT: YES
`
`FIG 9.
`AG. 9
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 10 of 19
`Sheet 10 0f 19
`
`US 6,377,865 B1
`US 6,377,865 B1
`
`602
`
`
`
`INPUT: SIMPLICES t, o
`
`INPUT:SIMPLICES to
`
`ASSERT LIS FACE OF O AND DIM L = DIMO
`ASSERT + IS FACE OF o AND DIMt = DIMo-1
`
`606
`606
`
`p-VERTEX OF O NOT OFt.
`P—~VERTEX OF o NOT OF +
`K-SMALLESSPHERESPANNED BYT
`K~ SMALLEST SPHERE SPANNED BY +
`
`610
`60
`OUTPUT: YES
`OUTPUT: YES
`
`608
`608
`YES}
`YES
`
`p LIES
`p LIES
`insipg
`INSIDE
`K
`K
`
`|N0
`NO
`
`612
`62
`OUTPUT: NO
`OUTPUT NO
`
`FIG 10
`AG. 10.
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 11 of 19
`Sheet 11 0f 19
`
`US 6,377,865 B1
`US 6,377,865 B1
`
`INPUT: SIMPLEX+
`INPUTsIMPLExt
`
`HG. IL
`FIG 11.
`
`642
`642
`
`644
`644
`
`FOREVERY PROPER COFACE O OF DO
`FOR EVERY PROPER COFACE o OF + DO
`
`646
`646
`THERE IS FLOW INO
`THERE IS FLOW |NO
`FROM O TO L
`FROM o 10 t
`
`YES
`YES
`
`648
`648
`
`OUTPUTC)
`QUIPUT: o
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 12 of 19
`Sheet 12 of 19
`
`US 6,377,865 B1
`US 6,377,865 B1
`
`662
`INPUT: SIMPLEXT
`INPUT: SIMPLEX +
`Oo T
`O --
`
`
`
`662
`
`
`
`THERE IS FLOW
`THERE IS FLOW
`YES FRAND NO
`YES TeROM TO v AND (Ae
`DIMu < DIMO
`DIMy < DIM
`
`
`
`
`
`FOREVERY PROPER FACE OF DO
`FOR EVERY PROPER FACE v OF + DO
`
`
`
`668
`668
`
`
`
`
`
`670
`670
`OUTPUT: O.
`OUTPUT: o
`
`AG. 12
`FIG 12
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 13 of 19
`Sheet 13 0f 19
`
`US 6,377,865 B1
`US 6,377,865 B1
`
`502
`502
`
`INPUT COMPLEX AND STACK OF BOUNDARY SIMPLICES
`INPUT: COMPLEX AND STACK OF BOUNDARY SIMPLICES
`
`54
`514
`
`STOP
`STOP
`
`504
`504
`
`CoYES
`i. YES
`
`506
`506
`
`NO
`NO
`
`O--TOPMOST SIMPLEX ON STACK
`o—~ TOPMOST SIMPLEX ON STACK
`
`508
`508
`
`t-UNIQUE PREDECESSOR OF O.
`t= UNIQUE PREDECESSOR OF o
`
`510
`510
`NO? (O,t) IS
`Of
`(oz) IS
`COLLAPSIBLE
`COLLAPSIBLE
`YES
`
`52
`512
`COLLAPSE (oft)
`COLLAPSE (0,1)
`
`AG. 13
`FIG 13
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 14 of 19
`Sheet 14 of 19
`
`US 6,377,865 B1
`US 6,377,865 B1
`
`522
`
`522
`INPUT: SIMPLEX AND PROPER (OFACET OF
`INPUT: SIMPLEX 1 AND PROPER COFACE t OF v
`
`
`
`524
`
`
`
`FOREVERY FACE p OF DO
`FOR EVERY FACE p OF x DO
`
`
`
`528
`528
`REMOVE
`REMOVEp
`
`
`
`
`
`526
`526
`VES vac NO
`YES u ISFACE NO
`
`530
`PUSH o ON STACK
`PUSH p ONSTACK
`
`532
`
`RETURN
`
`FIG 14.
`HG. 14.
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 15 of 19
`Sheet 15 0f 19
`
`US 6,377,865 B1
`US 6,377,865 B1
`
`
`
`s
`
`- -
`
`N s s w
`--- - t
`He. 15¢.
`FIG 15.
`
`
`
`
`
`HG. 15a.
`FIG. J.5a.
`
`HG. 15h
`
`
`
` SaaS
`HG.1a
`FIG. J.5e.
`
`AG. 15a.
`FIG 15d
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 16 of 19
`Sheet 16 0f 19
`
`US 6,377,865 B1
`US 6,377,865 B1
`
`542
`542
`
`INPUT SIMPLEX
`INPUT: SIMPLEX v
`
`544
`544
`u ISFREE AND
`vISFREEAND
`EQUIVOCAL
`EQUIVOCAL
`
`NO
`{NO
`
`546
`546
`Y
`.
`
`VES
`YES
`
`T - UNIQUE PREDECESSOR OF
`t ~ UNIQUE PREDECESSOR OF v
`k-- MAXIMUM DIMENSION OF ANY COFACE OF
`k~- MAXIMUM DIMENSION OF ANY COFACE OF v
`
`548
`
`548 - U.
`DM L = k
`
`NO
`
`550,
`230,
`O-LOWEST-DIMENSIONAL SUCCESSOR OF L
`
`YES
`YES
`
`
`
`o — LOWEST-DIMENSIONAL SUCCESSOR OF + 556
`
`OUTPUT: YES
`
`556
`OUTPUT NO
`OUTPUT: NO
`
`FG. 16.
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 17 of 19
`Sheet 17 of 19
`
`US 6,377,865 B1
`US 6,377,865 B1
`
`562
`562
`
`INPUT: SIMPLEX
`INPUT: SIMPLEX
`
`
`
`
`
`564
`
`
`
`
`
`
`
`
`
`y --NUMBER OF COFACES OFu
`y ~~ NUMBER OF COFACES OF v
`I-MAXIMUM DIMENSION OF ANY COFACE OF
`MAXIMUM DIMENSION OF ANY COFACE OF u
`k--DIMENSION OF
`k~—DIMENSION OF v
`
`568
`570
`568
`3/0
`566
`
`
`OUTPUT: NO NO|ogee [YES OUTPUT: YES
`OUTPUT NO
`OUTPUT: YES
`
`
`
`
`
`
`
`HG. 17.
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 18 of 19
`Sheet 18 of 19
`
`US 6,377,865 B1
`US 6,377,865 B1
`
`702
`102
`
`INPUT: SIMPLEXO.
`INPUT: SIMPLEX o
`
`704
`/04
`
`REMOVEO
`REMOVE o
`
`706
`/06
`
`FOREACH PROPERFACET OF O DO
`FOR EACH PROPER FACE t OF o DO
`PUSHT ON STACK
`PUSH « ON STACK
`
`708
`/08
`
`RETRACT
`RETRACT
`
`FIG. 18.
`AG. 18.
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr.23, 2002
`Apr. 23, 2002
`
`Sheet 19 of 19
`Sheet 19 of 19
`
`US 6,377,865 B1
`US 6,377,865 B1
`
`722
`INPUT, SIMPLExt
`
`
`
`
`
`TIS
`CENTERED
`
`730
`----------------------
`S-- INFINITY
`
`
`
`YES
`
`t IS
`CONFIDENT
`
`
`
`734
`FOREVERY PROPER FACE OF I.
`WITH FLOW FROM TO DO
`
`
`
`
`
`K-SPHERESPANNED BY
`s --RADIUS OFK
`
`
`
`OUTPUT:
`
`
`N
`FOREVERY PROPER COFACE O OF
`FOR EVERY PROPER COFACE o OF t
`WITH FLOW FROM TO O. DO
`WITH FLOW FROM + T0 o DO
`
`736
`
`it --SIZE OF
`
`
`
`
`
`
`
`
`
`it --SIZE OF O.
`
`
`
`42
`OUTPUTs
`
`
`FIG. 19.
`AiG. 19.
`
`OUTPUT: s
`OUTPUTs
`
`

`

`US 6,377,865 B1
`US 6,377,865 B1
`
`1
`1
`METHODS OF GENERATING THREE-
`METHODS OF GENERATING THREE
`DIMENSIONAL DIGITAL MODELS OF
`DIMENSIONAL DIGITAL MODELS OF
`OBJECTS BY WRAPPING POINT CLOUD
`OBJECTS BY WRAPPING POINT CLOUD
`DATA POINTS
`DATA POINTS
`
`10
`
`2
`2
`the latter two methods are automatic in fitting patches, they
`the latter two methods are automatic in fitting patches, they
`do not automate the task of shape reconstruction, which is
`do not automate the task of shape reconstruction, which is
`needed to produce the triangulated Surface and is a prereq
`needed to produce the triangulated surface and is a prereq-
`uisite of the patch fitting methods.
`uisite of the patch fitting methods.
`Among the automatic Solutions, three approaches are
`Among the automatic solutions,
`three approaches are
`distinguished: reconstruction from Slices, reconstruction
`distinguished:
`reconstruction from slices,
`reconstruction
`from dense measurement, and reconstruction from 3D com
`from dense measurement, and reconstruction from 3D com-
`plexes. The first two approaches are limited to shapes that
`plexes. The first two approaches are limited to shapes that
`can be described by a closed Surface.
`can be described by a closed surface.
`The reconstruction of a Surface is considerably easier than
`The reconstruction of a surface is considerably easier than
`in the general case if the measured points represent a
`in the general case if the measured points represent a
`sequence of parallel slices. Henry Fuchs, Zvi M. Kedem and
`sequenceof parallel slices. Henry Fuchs, Zvi M. Kedem and
`Sam P. Uselton, Optional Surface Reconstruction from Pla
`Sam P. Uselton, Optional Surface Reconstruction from Pla-
`nar Contours (1977) show how to connect two polygons in
`nar Contours (1977) show how to connect two polygons in
`parallel planes with a cylindrical Surface of minimum area.
`parallel planes with a cylindrical surface of minimum area.
`The problem is more difficult if there are more than one
`The problem is more difficult if there are more than one
`polygon per Slice. Various heuristics for determining which
`polygonperslice. Various heuristics for determining which
`polygons to connect and how to connect them have been
`polygons to connect and how to connect them have been
`investigated. For example, David Meyers, Shelly Skinner
`investigated. For example, David Meyers, Shelly Skinner
`and Kenneth Sloan, Surfaces from Contours (1992) use the
`and Kenneth Sloan, Surfaces from Contours (1992) use the
`minimum set of edges that connect all points, known as a
`minimum set of edges that connect all points, known as a
`Spanning tree of the measurements to guide the matching
`spanning tree of the measurements to guide the matching
`process for the polygons. Jean-Daniel Boissonnat, Shape
`process for the polygons. Jean-Daniel Boissonnat, Shape
`Reconstruction from Planar Cross Sections (1988) uses the
`Reconstruction from Planar Cross Sections (1988) uses the
`3D Delaunay complex for both purposes: to decide which
`3D Delaunay complex for both purposes: to decide which
`polygons to connect and also how to connect them. In spite
`polygons to connect and also how to connect them. In spite
`of the effort reflected in a large body of literature, no
`of the effort reflected in a large body of literature, no
`algorithm appears to produce Surfaces from Sliced data in a
`algorithm appears to produce surfaces from sliced data in a
`generally Satisfactory manner to produce a 3D model.
`generally satisfactory manner to produce a 3D model.
`Nevertheless, the reconstruction from Slices is a fast and
`Nevertheless, the reconstruction from slices is a fast and
`effective method for Simple organic forms, Such as eggs,
`effective method for simple organic forms, such as eggs,
`bones, etc. They are part of commercially available Systems
`bones, etc. They are part of commercially available systems
`Such as the Cyberware scanners and medical imaging hard
`such as the Cyberware scanners and medical imaging hard-
`ware and software.
`ware and Software.
`A method for surface reconstruction that has become
`A method for Surface reconstruction that has become
`popular in the computer graphics community uses the mea
`popular in the computer graphics community uses the mea-
`surements to construct a continuous function defined over
`Surements to construct a continuous function defined over
`the entire three-dimensional Space. The Surface is recon
`the entire three-dimensional space. The surface is recon-
`structed as the set where the function assumesa constant
`Structed as the Set where the function assumes a constant
`Value. This is the 2-dimensional analogue of the
`value. This is the 2-dimensional analogue of the
`1-dimensional contour or isoline in geographic maps that
`1-dimensional contour or isoline in geographic maps that
`traces out a curve along which a possibly mountainous
`traces out a curve along which a possibly mountainous
`landscape assumes a constant height. The 2-dimensional
`landscape assumes a constant height. The 2-dimensional
`analogue of an isoline is an isoSurface and can be con
`analogue of an isoline is an isosurface and can be con-
`Structed with the marching cube algorithm. Hugues Hoppe,
`structed with the marching cube algorithm. Hugues Hoppe,
`Tony DeRose, Tom Duchamp, John McDonal D, Werner
`Tony DeRose, Tom Duchamp, John McDonaLD, Werer
`Stuezle, Surface Reconstruction from Unorganized Points
`Stuezle, Surface Reconstruction from Unorganized Points
`(1992) construct this function So it approximates the signed
`(1992) construct this function so it approximates the signed
`Euclidean distance from the measured Surface. A necessary
`Euclidean distance from the measured surface. A necessary
`assumption in their work is that measurement are uniformly
`assumption in their work is that measurementare uniformly
`dense over the entire Surface and that the density exceeds the
`dense overthe entire surface and that the density exceeds the
`smallest feature size of the shape. Brian Curless and Marc
`smallest feature size of the shape. Brian Curless and Marc
`Levoy, A Volumetric Method for Building Complex Models
`Levoy, A Volumetric Method for Building Complex Models
`from Range Images (1996) use information about rays
`from Range Images (1996) use information about rays
`available from Some types of Scanners to extrapolated the
`available from some types of scanners to extrapolated the
`function over gaps in the measured data. A fundamental
`function over gaps in the measured data. A fundamental
`requirement of this approach is that the signed distance
`requirement of this approach is that the signed distance
`function is differentiable in the normal direction along the
`function is differentiable in the normal direction along the
`entire Surface, which is not possible unless the Surface is a
`entire surface, which is not possible unless the surface is a
`closed manifold. In other words, the Surface is restricted to
`closed manifold. In other words, the surface is restricted to
`form the boundary of a Solid Volume in Space. Examples of
`form the boundary of a solid volume in space. Examples of
`Surfaces that do not satisfy this property are thin sheets or the
`surfaces that do not satisfy this property are thin sheets or the
`common case where only a portion of the Volume's Surface
`common case where only a portion of the volume’s surface
`is accessible to measurement.
`is accessible to measurement.
`A 3D complex decomposes a 3-dimensional Volume into
`A 3D complex decomposes a 3-dimensional volumeinto
`cells. An example is the Delaunay complex of a point Set,
`cells. An example is the Delaunay complex of a point set,
`which connects the points with edges and triangles and this
`which connects the points with edges and triangles and this
`
`This application claims priority to U.S. Provisional
`This application claims priority to U.S. Provisional
`Application Serial No. 60/074,415, filed Feb. 11, 1998.
`Application Serial No. 60/074,415, filed Feb. 11, 1998.
`FIELD OF THE INVENTION
`FIELD OF THE INVENTION
`This invention is a method for the automatic conversion
`This invention is a method for the automatic conversion
`of a physical object into a 3D digital model. Combined with
`of a physical object into a 3D digital model. Combined with
`3D Scanning technologies it can reverse engineer
`3D scanning technologies it can reverse engineer
`mechanical, organic, and other shapes.
`mechanical, organic, and other shapes.
`BACKGROUND OF THE INVENTION
`BACKGROUND OF THE INVENTION
`The reconstruction of 3D physical objects has applica
`The reconstruction of 3D physical objects has applica-
`tions in various commercial markets and has been practiced
`tions in various commercial markets and has been practiced
`in the Arts and in Engineering disciplines. The computa
`in the Arts and in Engineering disciplines. The computa-
`tional problem of converting physical measurements into a
`tional problem of converting physical measurements into a
`full-fledged digital model has been Studied in computer
`full-fledged digital model has been studied in computer
`graphics and in computer-aided geometric design, both of
`graphics and in computer-aided geometric design, both of
`which are disciplines within the Computer Sciences.
`which are disciplines within the Computer Sciences.
`This invention concerns the automatic conversion of a
`This invention concerns the automatic conversion of a
`3-dimensional physical object into a digital model of exactly
`3-dimensional physical object into a digital model of exactly
`the same shape. The method is illustrated in FIG. 1 and the
`the same shape. The methodis illustrated in FIG. 1 and the
`logical Steps are depicted in FIG. 2. It starts with measure
`logical steps are depicted in FIG. 2. It starts with measure-
`ments taken with a 3D Scanner. The measurements are points
`ments taken with a 3D scanner. The measurements are points
`on the Surface, which are automatically converted into a
`on the surface, which are automatically converted into a
`Surface description using triangles connected to each other
`surface description using triangles connected to each other
`along shared edgeS. The Surface description can either be
`along shared edges. The surface description can either be
`used to produce a physical copy of the object using a 3D
`used to produce a physical copy of the object using a 3D
`printing machine, and it can be further processed with
`printing machine, and it can be further processed with
`animation or geometric design Software.
`animation or geometric design software.
`The prior art uses a variety of systems to make 3D models
`Theprior art uses a variety of systems to make 3D models
`of obj