“Automatic reconstruction of B-spline surfaces of arbitrary topological type” by Eck and Hoppe

Creating freeform surfaces is a challenging task even with advanced geometric modeling systems. Laser range scanners offer a promising alternative for model acquisition—the 3D scanning of existing objects or clay maquettes. The problem of converting the dense point sets produced by laser scanners into useful geometric models is referred to as surface reconstruction. In this paper, we present a procedure for reconstructing a tensor product B-spline surface from a set of scanned 3D points. Unlike previous work which considers primarily the problem of fitting a single B-spline patch, our goal is to directly reconstruct a surface of arbitrary topological type. We must therefore define the surface as a network of B-spline patches. A key ingredient in our solution is a scheme for automatically constructing both a network of patches and a parametrization of the data points over these patches. In addition, we define the B-spline surface using a surface spline construction, and demonstrate that such an approach leads to an efficient procedure for fitting the surface while maintaining tangent plane continuity. We explore adaptive refinement of the patch network in order to satisfy user-specified error tolerances, and demonstrate our method on both synthetic and real data.

1. ANDERSSON, E., ANDERSSON, R., BOMAN, M., ELM- ROTH, T., DAHLBERG, B., AND JOHANSSON, B. Automatic construction of surfaces with prescribed shape. CAD 20 (1988), 317-324.
2. BAJAJ, C., BERNARDINI, F., AND XU, G. Automatic reconstruction of surfaces and scalar fields from 3D scans. Computer Graphics (SIGGRAPH ’95 Proceedings) (1995), 109-118.
3. CURLESS, B., AND LEVOY, M. A volumetric method for building complex models from range images. Computer Graphics (SIGGRAPH ’96 Proceedings) (1996).
4. DIETZ, U. Erzeugung glatter Fl~ichen aus Mef3punkten. Technical Report 1717, Department of Mathematics, University of Darmstadt, Germany, February 1995.
5. DOO, D., AND SABIN, M. Behaviour of recursive division surfaces near extraordinary points. CAD 10, 6 (September 1978), 356-360.
6. ECK, M., DEROSE, T., DUCHAMP, T., HOPPE, H., LOUNSBERY~ M.~ AND STUETZLE~ W. Multiresolution analysis of arbitrary meshes. Computer Graphics (SIGGRAPH ’95 Proceedings) (1995), 173-182.
7. FANG~ L.~ AND GOSSARD~ D. Reconstruction of smooth parametric surfaces from unorganized data points. In Curves and Swfaces in Computer Vision and Graphics 3 (1992), J. Warren, Ed., vol. 1830, SPIE, pp. 226-236.
8. FARIN, G. Curves and Surfaces for Computer Aided Geometric Design, 3rd ed. Academic Press, 1992.
9. FORSEY~ D.~ AND BARTELS~ R. Surface fitting with hierarchical splines. ACM Transactions on Graphics 14, 2 (1995), 134-161.
10. GREINER~ G. Variational design and fairing of spline surfaces. Computer Graphics Forum 13, 3 (1994), 143-154.
11. HOPPE, H., DEROSE, T., DUCHAMP, T., HALSTEAD~ M., JIN, H., MCDONALD, J., SCHWEITZER, J., AND STUETZLE, W. Piecewise smooth surface reconstruction. Compuwr Graphics (SIGGRAPH ’94 Proceedings) (1994), 295-302.
12. HOPPE, H., DEROSE, T., DUCHAMP, T., MCDONALD, ,J., AND STUETZLE, W. Surface reconstruction from unorganized points. Computer Graphics (SIGGRAPH ’92 Proceedings) 26, 2 (1992), 71-78.
13. HOPPE, H., DEROSE, T., DUCHAMP, T., MCDONALD, ,J., AND STUETZLE, W. Mesh optimization. Computer Graphics (SIGGRAPH ’93 Proceedings) (1993), 19-26.
14. HOSCHEK, J., AND LASSER, D. Fundamentals of Computer Aided Geometric Design. AK Peters, Wellesley, 1993.
15. HOSCHEK, J., SCHNEIDER, F.-J., AND WASSUM, P. Optimal approximate conversion of spline surfaces. CAGD 6 (1989), 293-306.
16. IMAGEWARE~ CORP. Surfacer product information, http:- //www’iware’c~m/htmls/surfacer’html”
17. KRISHNAMURTHY~ V.~ AND LEVOY~ M. Fitting smooth surfaces to dense polygon meshes. Computer Graphics (DIG- GRAPH ’96 Proceedings) (1996).
18. LAWLER~ E. L. Combinatorial optimization: networks and matroids. Holt, Rinehart, and Winston, 1976.
19. LAWSON, C., AND HANSON, R. Solving Least Squares Problems. Prentice-Hall, Englewood Cliffs, NJ, 1974.
20. LEE, S., TAN, H., AND MAJID, A. Smooth piecewise biquartic surfaces from quadrilateral control polyhedra with isolated n-sided faces. CAD 27 (1995), 741-758.
21. Loop, C. Smooth spline surfaces over irregular meshes. Computer Graphics (SIGGRAPH ’94 Proceedings) (1994), 303-310.
22. MA, W., AND KRUTH, J. Parametrization of randomly measured points for least squares fitting of B-spline curves and surfaces. CAD 27 (1995), 663-675.
23. MILROY, M., BRADLEY, C., VICKERS, G., AND WEIR, D. G1 continuity of B-spline surface patches in reverse engineering. CAD 27 (1995), 471-478.
24. MOORE, D., AND WARREN, ,J. Approximation of dense scattered data using algebraic surfaces. In Proc. of the 24th Annual Hawaii Intnl. Conf. on System Sciences, Kauai, HI, USA (1991), V. Milutinovic and D. Shriver, Eds., IEEE Comp. Soc. Press, pp. 681-690.
25. MORETON, H., AND SI~QUIN, C. Functional optimization for fair surface design. Computer Graphics 26, 3 (July 1992), 167-176.
26. NASRI, A. H. Boundary-corner control in recursivesubdivision surfaces. CAD 23, 6 (1991), 405-410.
27. PETERS, J. Constructing C~ surfaces of arbitrary topology using biquadratic and bicubic splines. In Designing Fair Curves and Swfaces, N. Sapidis, Ed. SIAM, 1994, pp. 277- 293.
28. PETERS, J. Biquartic C~-surface splines over irregular meshes. CAD (1995). submitted.
29. REIF, U. Biquadratic G-spline surfaces. CAGD 12 (1995), 193-205.
30. ROGERS, D., AND FOG, N. Constrained B-spline curve and surface fitting. CAD 21 (1989), 641-648.
31. SARKAR, B., AND MENQ, C.-H. Parameter optimization in approximating curves and surfaces to measurement data. CAGD 8 (1991), 267-290.
32. SCHMITT, F., BARSKY, B., AND DU, W. H. An adaptive subdivision method for surface fitting from sampled data. Compuwr Graphics (SIGGRAPH ’86 Proceedings) 20 (1986), 179-188.
33. TARJAN, R. Data structures and network algorithms. CBMS- NSF Regional Conference Series in Applied Mathematics 44 (1983).
34. TURK, G., AND LEVOY, M. Zippered polygon meshes from range images. Computer Graphics (SIGGRAPH ’94 Proceedings) 28, 3 (1994), 311-318.