Abstract
We describe and demonstrate an algorithm that takes as input an unorganized set of points {xl, . . . . xn} ⊂ R3 on or near an unknown manifold M, and produces as output a simplicial surface that approximates M. Neither the topology, the presence of boundaries, nor the geometry of M are assumed to be known in advance - all are inferred automatically from the data. This problem naturally arises in a variety of practical situations such as range scanning an object from multiple view points, recovery of biological shapes from two-dimensional slices, and interactive surface sketching.
- 1 E.L. Allgower and P. H. Schmidt. An algorithm for piecewise linear approximation of an implicitly defined manifold. SlAM Journal of Numerical Analysis, 22:322-346, April 1985.Google ScholarDigital Library
- 2 J.L. Bentley. Multidimensional divide and conquer. Comm. ACM, 23(4):214--229, 1980. Google ScholarDigital Library
- 3 Y. Breseler, J. A. Fessler, and A. Macovski. A Bayesian approach to reconstruction from incomplete projections of a multiple object 3D domain. IEEE Trans. Pat. Anal. Mach. InteU., 11 (8):840-858, August 1989. Google ScholarDigital Library
- 4 James F. Brinkley. Knowledge-driven ultrasonic threedimensional organ modeling. IEEE Trans. Pat. Anal. Mach. lntell., 7(4):431-441, July 1985.Google ScholarDigital Library
- 5 David P. Dobkin, Silvio V. E Levy, William P. Thurston, and Allan R. Wilks. Contour tracing by piecewise linear approximations. ACM TOG, 9(4):389-423, October 1990. Google ScholarDigital Library
- 6 John A. Eisenman. Graphical editing of composite bezier curves. Master's thesis, Department of Electrical Engineering and Computer Science, M.I.T., 1988.Google Scholar
- 7 T.A. Foley. interpolation to scattered data on a spherical domain. In M. Cox and J. Mason, editors, Algorithms for Approximation l}, pages 303-310. Chapman and Hall, London, 1990.Google ScholarCross Ref
- 8 Michael R. Garey and David S. Johnson. Computers and Intractability. W. H. Freeman and Company, 1979.Google ScholarDigital Library
- 9 T. Hastie and W. Stuetzle. Principal curves. JASA, 84:502- 516, 1989.Google ScholarCross Ref
- 10 Averill M. Law and W. David Kelton. Simulation Modeling and Analysis. McGraw-Hill, Inc., second edition, 1991. Google ScholarDigital Library
- 11 Marshal L. Merriam. Experience with the cyberware 3D digitizer. In NCGA Proceedings, pages 125-133, March 1992.Google Scholar
- 12 David Meyers, Shelly Skinner, and Kenneth Sloan. Surfaces from contours: The correspondence and branching problems. In Proceedings of Graphics Interface '91, pages 246-254, June 1991.Google Scholar
- 13 Doug Moore and Joe Warren. Approximation of dense scattered data using algebraic surfaces. TR 90-135, Rice University, October 1990.Google Scholar
- 14 Doug Moore and Joe Warren. Adaptive mesh generation ii: Packing solids. TR 90-139, Rice University, March 1991.Google Scholar
- 15 Shigeru Muraki. Volumetric shape description of range data using "blobby model". Computer Graphics (SIGGRAPH '91 Proceedings), 25(4):227-235, July 1991. Google ScholarDigital Library
- 16 Gregory M. Nielson, Thomas A. Foley, Bernd Hamann, and David Lane. Visualizing and modeling scattered multivariate data. IEEECG&A, 11(3):47-55, May 1991. Google ScholarDigital Library
- 17 Barrett O'Neill. Elementary Differential Geometry. Academic Press, Orlando, Florida, 1966.Google Scholar
- 18 Vaughan Pratt. Direct least-squares fitting of algebraic surfaces. Computer Graphics (SIGGRAPH '87 Proceedings), 21(4): 145-152, July 1987. Google ScholarDigital Library
- 19 Emanuel Sachs, Andrew Roberts, and David Stoops. 3-Draw: A tool for designing 3 D shapes. {EEE Computer Graphics and Applications, 11(6):18-26, November 1991. Google ScholarDigital Library
- 20 Hanan Samet. Applications of Spatial Data Structures. Addison-Wesley, 1990. Google ScholarDigital Library
- 21 Philip J. Schneider. Phoenix: An interactive curve design system based on the automatic fitting of hand-sketched curves. Master's thesis, Department of Computer Science, U. of Washington, 1988.Google Scholar
- 22 R. B. Schudy and D. H. Ballard. Model detection of cardiac chambers in ultrasound images. Technical Report 12, Computer Science Department, University of Rochester, 1978.Google Scholar
- 23 R.B. Schudy and D. H, Ballard. Towards an anatomical model of heart motion as seen in 4-d cardiac ultrasound data. In Proceedings of the 6th Conference on Computer Applications in Radiology and Computer.Aided Analysis of Radiological Images, 1979.Google Scholar
- 24 Stan Sclaroff and Alex Pentland. Generalized implicit functions for computer graphics. Computer Graphics (SIGGRAPH '91 Proceedings), 25(4):247-250, July 1991. Google ScholarDigital Library
- 25 G. Taubin. Estimation of planar curves, surfaces and nonplanat space curves defined by implicit equations, with applications to edge and range image segmentation. Technical Report LEMS-66, Division of Engineering, Brown University, 1990.Google Scholar
- 26 B. C. Vemuri. Representation and Recognition of Objects From Dense Range Maps. PhD thesis, Department of Electrical and Computer Engineering, University of Texas at Austin, 1987. Google ScholarDigital Library
- 27 B. C. Vemuri, A. Mitiche, and J. K. Aggarwal. Curvaturebased representation of objects from range data. Image and Vision Computing, 4(2): 107-114,1986. Google ScholarDigital Library
- 28 13. Wyvill, C. McPheeters, and B. Wyvill. Data structures for soft objects. The Visual Computer, 2(4):227-234, August 1986.Google ScholarCross Ref
Index Terms
- Surface reconstruction from unorganized points
Recommendations
Surface reconstruction from unorganized points
SIGGRAPH '92: Proceedings of the 19th annual conference on Computer graphics and interactive techniquesWe describe and demonstrate an algorithm that takes as input an unorganized set of points {xl, . . . . xn} ⊂ R3 on or near an unknown manifold M, and produces as output a simplicial surface that approximates M. Neither the topology, the presence of ...
Surface Reconstruction from Unorganized Points
Seminal Graphics Papers: Pushing the Boundaries, Volume 2We describe and demonstrate an algorithm that takes as input an unorganized set of points {x<sub>l</sub>, . . . . x<sub>n</sub>} ⊂ R<sup>3</sup> on or near an unknown manifold M, and produces as output a simplicial ...
Piecewise smooth surface reconstruction
SIGGRAPH '94: Proceedings of the 21st annual conference on Computer graphics and interactive techniquesWe present a general method for automatic reconstruction of accurate, concise, piecewise smooth surface models from scattered range data. The method can be used in a variety of applications such as reverse engineering—the automatic generation of CAD ...
Comments