“Multi-level partition of unity implicits” by Ohtake, Belyaev, Alexa, Turk and Seidel

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.

1. ALEXA, M., BEHR, J., COHEN-OR, D., FLEISHMAN, S., LEVIN, D., AND SILVA, C. T. 2001. Point set surfaces. In IEEE Visualization 2001, 21–28. Google ScholarDigital Library
2. AMENTA, N., BERN, M., AND KAMVYSSELIS, M. 1998. A new Voronoi-based surface reconstruction algorithm. In Proceedings of ACM SIGGRAPH 1998, 415–421. Google Scholar
3. BABUŠKA, I., AND MELENK, J. M. 1997. The partition of unity method. International Journal of Numerical Methods in Engineering 40, 727–758.Google ScholarCross Ref
4. BABUŠKA, CALOZ, G., AND OSBORN, J. E. 1994. Special finite element methods for a class of second order elliptic problems with rough coefficients. SIAM J. Numerical Analysis 31, 4, 745–981. Google ScholarDigital Library
5. BAJAJ, C. L., BERNARDINI, F., AND XU, G. 1995. Automatic reconstruction of surfaces and scalar fields from 3D scans. In Proceedings of ACM SIGGRAPH 95, 109–118. Google Scholar
6. BEATSON, R. K., LIGHT, W. A., AND BILLINGS, S. 2000. Fast solution of the radial basis function interpolation equations: domain decomposition methods. SIAM J. Sci. Comput. 22, 5, 1717–1740. Google ScholarDigital Library
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.Google ScholarCross Ref
8. BLINN, J. F. 1982. A generalization of algebraic surface drawing. ACM Transactions on Graphics 1, 3 (July), 235–256. Google ScholarDigital Library
9. BLOOMENTHAL, J., BAJAJ, C., BLINN, J., CANI-GASCUEL, M. P., ROCKWOOD, A., WYVILL, B., AND WYVILL, G. 1997. Introduction to Implicit Surfaces. Morgan Kaufmann. Google Scholar
10. BLOOMENTHAL, J. 1994. An implicit surface polygonizer. In Graphics Gems IV. 324–349. Google Scholar
11. CARR, J. C., BEATSON, R. K., CHERRIE, J. B., MITCHELL, T. J., FRIGHT, W. R., MCCALLUM, B. C., AND EVANS, T. R. 2001. Reconstruction and representation of 3D objects with radial basis functions. In Proceedings of ACM SIGGRAPH 2001, 67–76. Google Scholar
12. CURLESS, B. VripPack User’s Guide. http://graphics.stanford.edu/software/vrip/.Google Scholar
13. CURLESS, B., AND LEVOY, M. 1996. A volumetric method for building complex models from range images. In Proceedings of ACM SIGGRAPH 1996, 303–312. Google Scholar
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.Google Scholar
15. DINH, H. Q., TURK, G., AND SLABAUGH, G. 2002. Reconstructing surfaces by volumetric regularization. IEEE Trans. on Pattern Analysis and Machine Intelligence 24, 10 (October), 1358–1371. Google Scholar
16. EDELSBRUNNER, H., AND MÜCKE, E. P. 1994. Three-dimensional alpha shapes. ACM Transactions on Graphics 13, 1 (January), 43–72. Google ScholarDigital Library
17. FLEISHMAN, S., COHEN-OR, D., ALEXA, M., AND SILVA, C. T. 2003. Progressive point set surfaces. ACM Transactions on Graphics 22, 4 (October). Google ScholarDigital Library
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.Google ScholarCross Ref
19. FRISKEN, S. F., PERRY, R. N., ROCKWOOD, A., AND JONES, T. R. 2000. Adaptively sampled distance fields: A general representation of shape for computer graphics. In Proceedings of ACM SIGGRAPH 2000, 249–254. Google Scholar
20. GRIEBEL, M., AND SCHWEITZER, M. A. 2000. A Particle-Partition of Unity Method for the solution of Elliptic, Parabolic and Hyperbolic PDE. SIAM J. Sci. Comp. 22, 3, 853–890. Google ScholarDigital Library
21. GRIEBEL, M., AND SCHWEITZER, M. A. 2002. A Particle-Partition of Unity Method – Part III: A Multilevel Solver. SIAM J. Sci. Comp. 24, 2, 377–409. Google ScholarDigital Library
22. HART, J. C. 1996. Sphere tracing: a geometric method for the antialiased ray tracing of implicit surfaces. The Visual Computer 12, 527–545.Google ScholarCross Ref
23. HOPPE, H., DEROSE, T., DUCHAMP, T., MCDONALD, J., AND STUETZLE, W. 1992. Surface reconstruction from unorganized point. In Proceedings of ACM SIGGRAPH 1992, 71–78. Google ScholarDigital Library
24. HYPERFUN: F-REP LIBRARY. http://cis.k.hosei.ac.jp/F-rep/HF_lib.html.Google Scholar
25. ISKE, A., AND LEVESLEY, J. 2002. Multilevel scattered data approximation by adaptive domain decomposition. Tech. rep., University of Leicester, April.Google Scholar
26. ISKE, A. 2001. Hierarchical scattered data filtering for multilevel interpolation schemes. In Mathematical methods for curves and surfaces (Oslo, 2000). Vanderbilt Univ. Press, Nashville, TN, 211–221. Google ScholarDigital Library
27. JU, T., LOSASSO, F., SCHAEFER, S., AND WARREN, J. 2002. Dual contouring of hermite data. ACM Transactions on Graphics 21, 3 (July), 339–346. Proceedings of ACM SIGGRAPH 2002. Google ScholarDigital Library
28. KOBBELT, L. P., BOTSCH, M., SCHWANECKE, U., AND SEIDEL, H.-P. 2001. Feature sensitive surface extraction from volume data. In Proceedings of ACM SIGGRAPH 2001, 57–66. Google Scholar
29. KOJEKINE, N., HAGIWARA, I., AND SAVCHENKO, V. 2003. Software tools using CSRBFs for processing scattered data. Computers & Graphics 27, 2 (April).Google ScholarCross Ref
30. LEVOY, M., PULLI, K., CURLESS, B., RUSINKIEWICZ, S., KOLLER, D., PEREIRA, L., GINZTON, M., ANDERSON, S., DAVIS, J., GINSBERG, J., SHADE, J., AND FULK, D. 2000. The Digital Michelangelo Project: 3D scanning of large statues. In Proceedings of ACM SIGGRAPH 2000, 131–144. Google Scholar
31. LIM, C., TURKIYYAH, G. M., GANTER, M. A., AND STORTI, D. W. 1995. Implicit reconstruction of solids from cloud point sets. In Proceedings of the third ACM symposium on Solid Modeling and Applications, ACM Press, 393–402. Google Scholar
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.Google Scholar
33. MORSE, B. S., YOO, T. S., RHEINGANS, P., CHEN, D. T., AND SUBRAMANIAN, K. R. 2001. Interpolating implicit surfaces from scattered surface data using compactly supported radial basis functions. In Shape Modeling International 2001, 89–98. Google ScholarDigital Library
34. MURAKI, S. 1991. Volumetric shape description of range data using “Blobby Model”. Computer Graphics 25, 4 (July), 227–235. Proceedings of ACMSIGGRAPH 1991. Google ScholarDigital Library
35. OHTAKE, Y., AND BELYAEV, A. G. 2002. Dual/primal mesh optimization for polygonized implicit surfaces. In 7th ACM Symposium on Solid Modeling and Applications, 171–178. Google Scholar
36. OHTAKE, Y., BELYAEV, A. G., AND SEIDEL, H.-P. 2003. A multi-scale approach to 3D scattered data interpolation with compactly supported basis functions. In Shape Modeling International 2003. Accepted. Google ScholarDigital Library
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.Google Scholar
38. RENKA, R. J. 1988. Multivariate interpolation of large sets of scattered data. ACM Transactions on Mathematical Software 14, 2 (June), 139–148. Google ScholarDigital Library
39. RICCI, A. 1973. A constructive geometry for computer graphics. The Computer Journal 16, 2 (May), 157–160.Google ScholarCross Ref
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.Google ScholarCross Ref
41. SCHABACK, R., AND WENDLAND, H. 2000. Adaptive greedy techniques for approximate solution of large RBF systems. Numerical Algorithms 24, 239–254.Google ScholarCross Ref
42. TAUBIN, G. 1991. Estimation of planar curves, surfaces and nonplanar space curves defined by implicit equations, with applications to edge and range image segmentation. IEEE Trans. on Pattern Analysis and Machine Intelligence 13, 11, 1115–1138. Google ScholarDigital Library
43. TURK, G., AND LEVOY, M. 1994. Zippered polygon meshes from range images. In Proceedings of ACM SIGGRAPH 1994, 311–318. Google Scholar
44. TURK, G., AND O’BRIEN, J. 2002. Modelling with implicit surfaces that interpolate. ACM Transactions on Graphics 21, 4 (October), 855–873. Google ScholarDigital Library
45. WARREN, J. 1992. Free-form blending: a technique for creating piecewise implicit surfaces. In Topics in Surface Modeling, H. Hagen, Ed. SIAM Press, Philadelphia, 473–483. Google ScholarDigital Library
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.Google Scholar
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.Google Scholar