Multiresolution analysis for surfaces of arbitrary topological type

ABSTRACT

Multiresolution analysis and wavelets provide useful and efficient tools for representing functions at multiple levels of detail. Wavelet representations have been used in a broad range of applications, including image compression, physical simulation, and numerical analysis. In this article, we present a new class of wavelets, based on subdivision surfaces, that radically extends the class of representable functions. Whereas previous two-dimensional methods were restricted to functions difined on R2, the subdivision wavelets developed here may be applied to functions defined on compact surfaces of arbitrary topological type. We envision many applications of this work, including continuous level-of-detail control for graphics rendering, compression of geometric models, and acceleration of global illumination algorithms. Level-of-detail control for spherical domains is illustrated using two examples: shape approximation of a polyhedral model, and color approximation of global terrain data.

REFERENCES

• 1: ANDERSSON, L., HALL, N., JAWERTH, B., AND PETERS, G. 1993. Wavelets on closed subsets of the real line. In Recent Advances in Wavelet Analysis, L. L. Schumaker and G. Webb, Eds. Academic Press, New York, 1-61.
• 2: BARTLE, R.a. 1964. The Elements of Real Analysis. Wiley, New York.
• 3: Deborah F. Berman , Jason T. Bartell , David H. Salesin, Multiresolution painting and compositing, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.85-90, July 1994 [doi>10.1145/192161.192181]
• 4: BEYLKIN, G., COIFMAN, R., AND ROKHLIN, V. 1991. Fast wavelet transforms and numerical algorithms. Commun. Pure Appl. Math. 44, 141-183.
• 5: CARNICER, J. M., DAHMEN, W., AND PEi~A, J. M. 1994. Local decompositions of refinable spaces. Tech. Rep. Institut ffir Geometric und Praktische Mathematik, RWTH Aachen, Aachen, Germany.
• 6: CATMULL, E. AND CLARK, g. 1978. Recursively generated B-spline surfaces on arbitrary topological meshes. Comput. Aided Des. 10, 6, 350-355.
• 7: Andrew Certain , Jovan Popovic , Tony DeRose , Tom Duchamp , David Salesin , Werner Stuetzle, Interactive multiresolution surface viewing, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.91-98, August 1996 [doi>10.1145/237170.237213]
• 8: CHUI, C. AND QUAK, E. 1992. Wavelets on a bounded interval. In Numerical Methods of Approximation Theory, D. Braess and L. L. Schumaker, Eds. Birkh~iuser-Verlag, Basel, 1-24.
• 9: CHUI, C. 1992. Wavelet Analysis and its Applications, Vol. 1. Academic Press, Boston, MA.
• 10: Charles K. Chui , Xianliang Shi, Wavelets and multiscale interpolation, Mathematical methods in computer aided geometric design II, Academic Press Professional, Inc., San Diego, CA, 1992
• 11: COHEN, A., DAUBECHIES, I., AND VIAL, P. 1993. Multiresolution analysis, wavelets and fast algorithms on an interval. Appl. Comput. Harmon. Anal. 1, 1, 100-115.
• 12: COHEN, A., DAUBECHIES, I., AND FEAUVEAU, J.-C. 1992. Biorthogonal bases of compactly supported wavelets. Commun. Pure Appl. Math. XLV, 485-560.
• 13: DAHMEN, W. 1994. Stability of multiscale transformations. Tech. Rep. Institut ffir Geometrie und Praktische Mathematik, RWTH Aachen, Aachen, Germany.
• 14: DAHMEN, W., KLEEMAN, B., PROSSDORF, S., AND SCHNEIDER, R. 1993. A multiscale method for the double layer potential equation on a polyhedron. Tech. Rep. 91, Institut ffir Geometrie und Praktische Mathematik, Rheinisch-Westf~ilische Technische Hochschule Aachen, Nov.
• 15: Wolfgang Dahmen , Charles A. Micchelli, Using the refinement equation for evaluating integrals of wavelets, SIAM Journal on Numerical Analysis, v.30 n.2, p.507-537, April 1993 [doi>10.1137/0730024]
• 16: DAUBECHIES, I. 1988. Orthonormal bases of compactly supported wavelets. Comm. Pure Appl. Math. 41, 909-996.
• 17: Ingrid Daubechies, Ten lectures on wavelets, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 18: DEVORE, R., JAWERTH, B., AND LUCIER, B. 1992. Image compression through wavelet transform coding. IEEE Trans. Inf. Theory 38, 2 (March), 719-746.
• 19: DONOHO, D.L. 1994. Unconditional bases are optimal bases for data compression and for statistical estimation. Appl. Comput. Harmon. Anal. 1, 1, 100-115.
• 20: Doo, D. AND SABIN, M. 1978. Behaviour of recursive division surfaces near extraordinary points. Computer Aided Design, 10, 6, 356-360.
• 21: Doo, D. W. H. 1978. A recursive subdivision algorithm for fitting quadratic surfaces to irregular polyhedrons. PhD Thesis, Brunel Univ.
• 22: Nira Dyn , David Levine , John A. Gregory, A butterfly subdivision scheme for surface interpolation with tension control, ACM Transactions on Graphics (TOG), v.9 n.2, p.160-169, April 1990 [doi>10.1145/78956.78958]
• 23: Matthias Eck , Tony DeRose , Tom Duchamp , Hugues Hoppe , Michael Lounsbery , Werner Stuetzle, Multiresolution analysis of arbitrary meshes, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.173-182, September 1995 [doi>10.1145/218380.218440]
• 24: Adam Finkelstein , David H. Salesin, Multiresolution curves, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.261-268, July 1994 [doi>10.1145/192161.192223]
• 25: David R. Forsey , Richard H. Bartels, Hierarchical B-spline refinement, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.205-212, Aug. 1988
• 26: 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]
• 27: Hugues Hoppe, Surface reconstruction from unorganized points, University of Washington, Seattle, WA, 1995
• 28: Hugues Hoppe , Tony DeRose , Tom Duchamp , Mark Halstead , Hubert Jin , John McDonald , Jean Schweitzer , Werner Stuetzle, Piecewise smooth surface reconstruction, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.295-302, July 1994 [doi>10.1145/192161.192233]
• 29: 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]
• 30: Rong-Qing Jia , Charles A. Micchelli, Using the refinement equations for the construction of Pre-Wavelets II: powers and two, Curves and surfaces, Academic Press Professional, Inc., San Diego, CA, 1991
• 31: Zicheng Liu , Steven J. Gortler , Michael F. Cohen, Hierarchical spacetime control, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.35-42, July 1994 [doi>10.1145/192161.192169]
• 32: LooP, C.T. 1987. Smooth subdivision surfaces based on triangles. Master's thesis, Dept. of Mathematics, Univ. of Utah, (August).
• 33: John Michael Lounsbery, Multiresolution analysis for surfaces of arbitrary topological type, University of Washington, Seattle, WA, 1995
• 34: Bradley J. Lucier, Wavelets and image compression, Mathematical methods in computer aided geometric design II, Academic Press Professional, Inc., San Diego, CA, 1992
• 35: S. G. Mallat, A Theory for Multiresolution Signal Decomposition: The Wavelet Representation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.7, p.674-693, July 1989 [doi>10.1109/34.192463]
• 36: MALLAT, S. AND HWANG, W. L. 1992. Singularity detection and processing with wavelets. IEEE Trans. Inf. Theory 38, 2 (March) 617-643.
• 37: MEYER, Y. 1992. Ondelettes sur l'intervalle. Rev. Mat. Iberoamericana 7, 115-133.
• 38: MEYER, Y. 1993. Wavelets and Operators. Cambridge University Press.
• 39: MEYERS, D. 1994a. Multiresolution tiling. In Proceedings of Graphics Interface, (May) 25-32.
• 40: David Meyers, Reconstruction of surfaces from planar contours, University of Washington, Seattle, WA, 1995
• 41: PENTLAND, A.P. 1992. Fast solutions to physical equilibrium and interpolation problems. Visual Comput. 8, 5-6 (June) 303-314.
• 42: Peter Schröder , Wim Sweldens, Spherical wavelets: efficiently representing functions on the sphere, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.161-172, September 1995 [doi>10.1145/218380.218439]
• 43: William J. Schroeder , Jonathan A. Zarge , William E. Lorensen, Decimation of triangle meshes, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.65-70, July 1992
• 44: SWELDENS, W. 1994. Construction and applications of wavelets in numerical analysis. PhD thesis, Katholieke Universiteit Leuven, Leuven, Belgium.
• 45: Greg Turk, Re-tiling polygonal surfaces, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.55-64, July 1992

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Spline and piecewise polynomial approximation

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Theory

Keywords:
compression, geometriac modeling, level-of-detail control, splines, subdivision surfaces, wavelets