ABSTRACT
We 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 models from physical objects. Novel aspects of the method are its ability to model surfaces of arbitrary topological type and to recover sharp features such as creases and corners. The method has proven to be effective, as demonstrated by a number of examples using both simulated and real data.
A key ingredient in the method, and a principal contribution of this paper, is the introduction of a new class of piecewise smooth surface representations based on subdivision. These surfaces have a number of properties that make them ideal for use in surface reconstruction: they are simple to implement, they can model sharp features concisely, and they can be fit to scattered range data using an unconstrained optimization procedure.
Supplemental Material
Available for Download
- 1.Ruud M. Bolle and Baba C. Vemuri. On three-dimensional surface reconstruction methods. IEEE Trans. Pat. Anal. Mach. Intell., 13(1):13, January 1991. Google ScholarDigital Library
- 2.James F. Brinkley. Knowledge-driven ultrasonic three-dimensional or-gan modeling. IEEE Trans. Pat. Anal. Mach. Intell., 7(4):431-441, July 1985.Google ScholarDigital Library
- 3.E. Catmull and J. Clark. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer-Aided Design, 10:350-355, September 1978.Google ScholarCross Ref
- 4.T. DeRose, H. Hoppe, T. Duchamp, J. McDonald, and W. Stuetzle. Fitting of surfaces to scattered data. SPIE, 1830:212-220, 1992.Google Scholar
- 5.D. Doo and M. Sabin. Behaviour of recursive division surfaces near extraordinary points. Computer-Aided Design, 10(6):356-360, September 1978.Google ScholarCross Ref
- 6.G. Farin. Curves and Surfaces for Computer Aided Geometric Design. Academic Press, 3rd edition, 1992. Google ScholarDigital Library
- 7.Ardeshir Goshtasby. Surface reconstruction from scattered measure-ments. SPIE, 1830:247-256, 1992.Google Scholar
- 8.Mark Halstead, Michael Kass, and Tony DeRose. Efficient, fair in-terpolation using Catmull-Clark surfaces. Computer Graphics (SIG-GRAPH '93 Proceedings), pages 35-44, August 1993. Google ScholarDigital Library
- 9.H. Hoppe, T. DeRose, T. Duchamp, H. Jin, J. McDonald, and W. Stuet-zle. Piecewise smooth surface reconstruction. TR 94-01-01, Dept. of Computer Science and Engineering, University of Washington, Jan-uary 1994.Google Scholar
- 10.H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. Surface reconstruction from unorganized points. Computer Graphics (SIGGRAPH '92 Proceedings), 26(2):71-78, July 1992. Google ScholarDigital Library
- 11.H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. Mesh optimization. Computer Graphics (SIGGRAPH '93 Proceed-ings), pages 19-26, August 1993. Google ScholarDigital Library
- 12.Hugues Hoppe. Surface reconstruction from unorganized points. PhD thesis, Department of Computer Science and Engineering, University of Washington, In preparation. Google ScholarDigital Library
- 13.Charles Loop. Smooth subdivision surfaces based on triangles. Mas-ter's thesis, Department of Mathematics, University of Utah, August 1987.Google Scholar
- 14.Michael Lounsbery, Stephen Mann, and Tony DeRose. Parametric surface interpolation. IEEE Computer Graphics and Applications, 12(5):45-52, September 1992. surface reconstruction pro-cedure surface models from un-organized determines the topo-logical and location of sharp new subdivision sur-face surface features such as Finally, we have demon-strated surface optimization pro-cedure from range data, and swept surfaces and including: model a wider va-riety darts meeting at corner. algorithms that allow implementations on parallel ar-chitectures. 12(5):45-52, September 1992. Google ScholarDigital Library
- 15.Ahmad H. Nasri. Polyhedral subdivision methods for free-form sur-faces. ACM Transactions on Graphics, 6(1):29-73, January 1987. Google ScholarDigital Library
- 16.Ahmad H. Nasri. Boundary-corner control in recursive-subdivision surfaces. Computer Aided Design, 23(6):405-410, July-August 1991. Google ScholarDigital Library
- 17.G. Nielson. A transfinite, visually continuous, triangular interpolant. In G. Farin, editor, Geometric Modeling: Algorithms and New Trends, pages 235-246. SIAM, 1987.Google Scholar
- 18.Michael Plass and Maureen Stone. Curve-fitting with piecewise para-metric cubics. Computer Graphics (SIGGRAPH '83 Proceedings), 17(3):229-239, July 1983. Google ScholarDigital Library
- 19.Ulrich Reif. A unified approach to subdivision algorithms. Mathema-tisches Institute A 92-16, Universit~ at Stuttgart, 1992.Google Scholar
- 20.F. Schmitt, B.A. Barsky, and W. Du. An adaptive subdivision method for surface fitting from sampled data. Computer Graphics (SIG-GRAPH '86 Proceedings), 20(4):179-188, 1986. Google ScholarDigital Library
- 21.F. Schmitt, X. Chen, W. Du, and F. Sair. Adaptive approximation of range data using triangular patches. In P.J. Laurent, A. Le Mehaute, and L.L. Schumaker, editors, Curves and Surfaces. Academic Press, 1991. Google ScholarDigital Library
- 22.R. B. Schudy and D. H. Ballard. Model detection of cardiac cham-bers 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.S. Sclaroff and A. Pentland. Generalized implicit functions for com-puter graphics. Computer Graphics (SIGGRAPH '91 Proceedings), 25(4):247-250, July 1991. Google ScholarDigital Library
- 25.L. Shirman and C. S~ equin. Local surface interpolation with B~ ezier patches. Computer Aided Geometric Design, 4(4):279-296, 1988.Google ScholarDigital Library
- 26.R. Szeliski, D. Tonnesen, and D. Terzopoulos. Modeling surfaces of arbitrary topology with dynamicparticles. In 1993IEEE Computer So-ciety Conference on Computer Vision and Pattern Recognition, pages 82-87. IEEE Computer Society Press, 1993.Google Scholar
- 27.R.C. Veltkamp. 3D computational morphology. Computer Graphics Forum, 12(3):116-127, 1993.Google Scholar
Index Terms
- Piecewise smooth surface reconstruction
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 ...
Piecewise algebraic surface computation and smoothing from a discrete model
This paper describes a constrained smoothing method for implicit surfaces defined on a voxelization. This method is suitable for computing a closed smooth surface that approximates an initial set of face connected voxels. The implicit surface is defined ...
Surface fitting with cyclide splines
The cyclide spline surface is a G 1 smooth piecewise surface composed of Dupin cyclide patches, thus inheriting several favorable geometric properties of the Dupin cyclide, such as the closeness under offset operation. Due to the lack of shape ...
Comments