Piecewise smooth surface reconstruction

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Ruud M. Bolle , Baba C. Vemuri, On Three-Dimensional Surface Reconstruction Methods, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.1, p.1-13, January 1991 [doi>10.1109/34.67626]
	2	James F. Brinkley. Knowledge-driven ultrasonic three-dimensional or-gan modeling. IEEE Trans. Pat. Anal. Mach. Intell., 7(4):431-441, July 1985.
	3	E. Catmull and J. Clark. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer-Aided Design, 10:350-355, September 1978.
	4	T. DeRose, H. Hoppe, T. Duchamp, J. McDonald, and W. Stuetzle. Fitting of surfaces to scattered data. SPIE, 1830:212-220, 1992.
	5	D. Doo and M. Sabin. Behaviour of recursive division surfaces near extraordinary points. Computer-Aided Design, 10(6):356-360, September 1978.
	6	Gerald Farin, Curves and surfaces for computer aided geometric design (3rd ed.): a practical guide, Academic Press Professional, Inc., San Diego, CA, 1993
	7	Ardeshir Goshtasby. Surface reconstruction from scattered measure-ments. SPIE, 1830:247-256, 1992.
	8	Mark Halstead , Michael Kass , Tony DeRose, Efficient, fair interpolation using Catmull-Clark surfaces, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.35-44, September 1993 [doi>10.1145/166117.166121]
	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.
	10	Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Surface reconstruction from unorganized points, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.71-78, July 1992
	11	Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Mesh optimization, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.19-26, September 1993 [doi>10.1145/166117.166119]
	12	Hugues Hoppe, Surface reconstruction from unorganized points, University of Washington, Seattle, WA, 1995
	13	Charles Loop. Smooth subdivision surfaces based on triangles. Mas-ter's thesis, Department of Mathematics, University of Utah, August 1987.
	14	Michael Lounsbery , Stephen Mann , Tony DeRose, Parametric Surface Interpolation, IEEE Computer Graphics and Applications, v.12 n.5, p.45-52, September 1992 [doi>10.1109/38.156012]
	15	Ahmad H. Nasri, Polyhedral subdivision methods for free-form surfaces, ACM Transactions on Graphics (TOG), v.6 n.1, p.29-73, Jan. 1987 [doi>10.1145/27625.27628]
	16	A. H. Nasri, Boundary-corner control in recursive-subdivision surfaces, Computer-Aided Design, v.23 n.6, p.405-410, July/Aug. 1991 [doi>10.1016/0010-4485(91)90008-K]
	17	G. Nielson. A transfinite, visually continuous, triangular interpolant. In G. Farin, editor, Geometric Modeling: Algorithms and New Trends, pages 235-246. SIAM, 1987.
	18	Michael Plass , Maureen Stone, Curve-fitting with piecewise parametric cubics, Proceedings of the 10th annual conference on Computer graphics and interactive techniques, p.229-239, July 25-29, 1983, Detroit, Michigan, United States
	19	Ulrich Reif. A unified approach to subdivision algorithms. Mathema-tisches Institute A 92-16, Universit~ at Stuttgart, 1992.
	20	Francis J M Schmitt , Brian A. Barsky , Wen-hui Du, An adaptive subdivision method for surface-fitting from sampled data, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.179-188, Aug. 1986
	21	Francis Schmitt , Xin Chen , Wen-Hui Du , Farouk Sair, Adaptive G1 approximation of range data using triangular patches, Curves and surfaces, Academic Press Professional, Inc., San Diego, CA, 1991
	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.
	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.
	24	Stan Sclaroff , Alex Pentland, Generalized implicit functions for computer graphics, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.247-250, July 1991
	25	L. Shirman and C. S~ equin. Local surface interpolation with B~ ezier patches. Computer Aided Geometric Design, 4(4):279-296, 1988.
	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.
	27	R.C. Veltkamp. 3D computational morphology. Computer Graphics Forum, 12(3):116-127, 1993.

Collaborative Colleagues:

Hugues Hoppe: colleagues

Tony DeRose: colleagues

Tom Duchamp: colleagues

Mark Halstead: colleagues

Hubert Jin: colleagues

John McDonald: colleagues

Jean Schweitzer: colleagues

Werner Stuetzle: colleagues