Multi-level partition of unity implicits

ABSTRACT

We present a new shape representation, the multi-level partition of unity implicit surface, that allows us to construct surface models from very large sets of points. There are three key ingredients to our approach: 1) piecewise quadratic functions that capture the local shape of the surface, 2) weighting functions (the partitions of unity) that blend together these local shape functions, and 3) an octree subdivision method that adapts to variations in the complexity of the local shape.Our approach gives us considerable flexibility in the choice of local shape functions, and in particular we can accurately represent sharp features such as edges and corners by selecting appropriate shape functions. An error-controlled subdivision leads to an adaptive approximation whose time and memory consumption depends on the required accuracy. Due to the separation of local approximation and local blending, the representation is not global and can be created and evaluated rapidly. Because our surfaces are described using implicit functions, operations such as shape blending, offsets, deformations and CSG are simple to perform.

REFERENCES

• 1: Marc Alexa , Johannes Behr , Daniel Cohen-Or , Shachar Fleishman , David Levin , Claudio T. Silva, Point set surfaces, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 2: Nina Amenta , Marshall Bern , Manolis Kamvysselis, A new Voronoi-based surface reconstruction algorithm, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.415-421, July 1998 [doi>10.1145/280814.280947]
• 3: BABUŠKA, I., AND MELENK, J. M. 1997. The partition of unity method. International Journal of Numerical Methods in Engineering 40, 727--758.
• 4: Ivo Babuška , Gabriel Caloz , John E. Osborn, Special finite element methods for a class of second order elliptic problems with rough coefficients, SIAM Journal on Numerical Analysis, v.31 n.4, p.945-981, Aug. 1994 [doi>10.1137/0731051]
• 5: Chandrajit L. Bajaj , Fausto Bernardini , Guoliang Xu, Automatic reconstruction of surfaces and scalar fields from 3D scans, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.109-118, September 1995 [doi>10.1145/218380.218424]
• 6: R. K. Beatson , W. A. Light , S. Billings, Fast Solution of the Radial Basis Function Interpolation Equations: Domain Decomposition Methods, SIAM Journal on Scientific Computing, v.22 n.5, p.1717-1740, 2000 [doi>10.1137/S1064827599361771]
• 7: BERNARDINI, F., BAJAJ, C., CHEN, J., AND SCHIKORE, D. 1999. Automatic reconstruction of 3D CAD models from digital scans. International Journal of Computational Geometry & Applications 9, 4, 327--369.
• 8: James F. Blinn, A Generalization of Algebraic Surface Drawing, ACM Transactions on Graphics (TOG), v.1 n.3, p.235-256, July 1982 [doi>10.1145/357306.357310]
• 9: Jules Bloomenthal , Brian Wyvill, Introduction to Implicit Surfaces, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 10: Jules Bloomenthal, An implicit surface polygonizer, Graphics gems IV, Academic Press Professional, Inc., San Diego, CA, 1994
• 11: J. C. Carr , R. K. Beatson , J. B. Cherrie , T. J. Mitchell , W. R. Fright , B. C. McCallum , T. R. Evans, Reconstruction and representation of 3D objects with radial basis functions, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.67-76, August 2001 [doi>10.1145/383259.383266]
• 12: CURLESS, B. VripPack User's Guide. http://graphics.stanford.edu/software/vrip/.
• 13: Brian Curless , Marc Levoy, A volumetric method for building complex models from range images, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.303-312, August 1996 [doi>10.1145/237170.237269]
• 14: DINH, H. Q., SLABAUGH, G., AND TURK, G. 2001. Reconstructing surfaces using anisotropic basis functions. In International Conference on Computer Vision (ICCV) 2001, 606--613.
• 15: Huong Quynh Dinh , Greg Turk , Greg Slabaugh, Reconstructing Surfaces by Volumetric Regularization Using Radial Basis Functions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.10, p.1358-1371, October 2002 [doi>10.1109/TPAMI.2002.1039207]
• 16: Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, ACM Transactions on Graphics (TOG), v.13 n.1, p.43-72, Jan. 1994 [doi>10.1145/174462.156635]
• 17: Shachar Fleishman , Daniel Cohen-Or , Marc Alexa , Cláudio T. Silva, Progressive point set surfaces, ACM Transactions on Graphics (TOG), v.22 n.4, p.997-1011, October 2003 [doi>10.1145/944020.944023]
• 18: FRANKE, R., AND NIELSON, G. 1980. Smooth interpolation of large sets of scattered data. International Journal of Numerical Methods in Engineering 15, 1691--1704.
• 19: Sarah F. Frisken , Ronald N. Perry , Alyn P. Rockwood , Thouis R. Jones, Adaptively sampled distance fields: a general representation of shape for computer graphics, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.249-254, July 2000 [doi>10.1145/344779.344899]
• 20: Michael Griebel , Marc Alexander Schweitzer, A Particle-Partition of Unity Method for the Solution of Elliptic, Parabolic, and Hyperbolic PDEs, SIAM Journal on Scientific Computing, v.22 n.3, p.853-890, 2000 [doi>10.1137/S1064827599355840]
• 21: Michael Griebel , Marc Alexander Schweitzer, A Particle-Partition of Unity Method--Part III: A Multilevel Solver, SIAM Journal on Scientific Computing, v.24 n.2, p.377-409, 2002 [doi>10.1137/S1064827501395252]
• 22: HART, J. C. 1996. Sphere tracing: a geometric method for the antialiased ray tracing of implicit surfaces. The Visual Computer 12, 527--545.
• 23: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Surface reconstruction from unorganized points, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.71-78, July 1992
• 24: HYPERFUN: F-REP LIBRARY. http://cis.k.hosei.ac.jp/F-rep/HF_lib.html.
• 25: ISKE, A., AND LEVESLEY, J. 2002. Multilevel scattered data approximation by adaptive domain decomposition. Tech. rep., University of Leicester, April.
• 26: Armin Iske, Hierarchical scattered data filtering for multilevel interpolation schemes, Mathematical Methods for Curves and Surfaces: Oslo 2000, Vanderbilt University, Nashville, TN, 2001
• 27: Tao Ju , Frank Losasso , Scott Schaefer , Joe Warren, Dual contouring of hermite data, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 28: Leif P. Kobbelt , Mario Botsch , Ulrich Schwanecke , Hans-Peter Seidel, Feature sensitive surface extraction from volume data, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.57-66, August 2001 [doi>10.1145/383259.383265]
• 29: KOJEKINE, N., HAGIWARA, I., AND SAVCHENKO, V. 2003. Software tools using CSRBFs for processing scattered data. Computers & Graphics 27, 2 (April).
• 30: Marc Levoy , Kari Pulli , Brian Curless , Szymon Rusinkiewicz , David Koller , Lucas Pereira , Matt Ginzton , Sean Anderson , James Davis , Jeremy Ginsberg , Jonathan Shade , Duane Fulk, The digital Michelangelo project: 3D scanning of large statues, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.131-144, July 2000 [doi>10.1145/344779.344849]
• 31: Chek T. Lim , George M. Turkiyyah , Mark A. Ganter , Duane W. Storti, Implicit reconstruction of solids from cloud point sets, Proceedings of the third ACM symposium on Solid modeling and applications, p.393-402, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218090]
• 32: MOORE, D., AND WARREN, J. 1991. Approximation of dense scattered data using algebraic surfaces. In Proceedings of the 24th Hawaii International Conference on System Sciences, IEEE Computer Society Press, Kauai, Hawaii, 681--690.
• 33: Bryan S. Morse , Terry S. Yoo , David T. Chen , Penny Rheingans , K. R. Subramanian, Interpolating Implicit Surfaces from Scattered Surface Data Using Compactly Supported Radial Basis Functions, Proceedings of the International Conference on Shape Modeling & Applications, p.89, May 07-11, 2001
• 34: Shigeru Muraki, Volumetric shape description of range data using “Blobby Model”, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.227-235, July 1991
• 35: Yutaka Ohtake , Alexander G. Belyaev, Dual/Primal mesh optimization for polygonized implicit surfaces, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany [doi>10.1145/566282.566308]
• 36: Y. Ohtake , A. Belyaev , H.-P. Seidel, A Multi-scale Approach to 3D Scattered Data Interpolation with Compactly Supported Basis Functions, Proceedings of the Shape Modeling International 2003, p.292, May 12-15, 2003
• 37: PASKO, A., AND SAVCHENKO, V. 1994. Blending operations for the functionally based constructive geometry. In Set-theoretic Solid Modeling: Techniques and Applications, CSG 94 Conference Proceedings, Information Geometers, 151--161.
• 38: Robert J. Renka, Multivariate interpolation of large sets of scattered data, ACM Transactions on Mathematical Software (TOMS), v.14 n.2, p.139-148, June 1988 [doi>10.1145/45054.45055]
• 39: RICCI, A. 1973. A constructive geometry for computer graphics. The Computer Journal 16, 2 (May), 157--160.
• 40: SAVCHENKO, V. V., PASKO, A. A., OKUNEV, O. G., AND KUNII, T. L. 1995. Function representation of solids reconstructed from scattered surface points and contours. Computer Graphics Forum 14, 4, 181--188.
• 41: SCHABACK, R., AND WENDLAND, H. 2000. Adaptive greedy techniques for approximate solution of large RBF systems. Numerical Algorithms 24, 239--254.
• 42: Gabriel Taubin, Estimation of Planar Curves, Surfaces, and Nonplanar Space Curves Defined by Implicit Equations with Applications to Edge and Range Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.11, p.1115-1138, November 1991 [doi>10.1109/34.103273]
• 43: Greg Turk , Marc Levoy, Zippered polygon meshes from range images, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.311-318, July 1994 [doi>10.1145/192161.192241]
• 44: Greg Turk , James F. O'brien, Modelling with implicit surfaces that interpolate, ACM Transactions on Graphics (TOG), v.21 n.4, p.855-873, October 2002 [doi>10.1145/571647.571650]
• 45: Joe Warren, Free-form blending: a technique for creating piecewise implicit surfaces, Topics in surface modeling, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 46: WENDLAND, H. 2002. Fast evaluation of radial basis functions: Methods based on partition of unity. In Approximation Theory X: Wavelets, Splines, and Applications, Vanderbilt University Press, Nashville, L. Schumaker and J. Stöckler, Eds., 473--483.
• 47: ZHAO, H., AND OSHER, S. 2002. Visualization, analysis and shape reconstruction of unorganized data sets. In Geometric Level Set Methods in Imaging, Vision and Graphics, Springer, S. Osher and N. Paragios, Eds.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Keywords:
adaptive distance, error-controlled subdivision, field approximation, implicit modeling, partition of unity approximation