Biorthogonal wavelets for subdivision volumes

ABSTRACT

We present a biorthogonal wavelet construction based on Catmull-Clark-style subdivision volumes. Our wavelet transform is the three-dimensional extension of a previously developed construction of subdivision-surface wavelets that was used for multiresolution modeling of large-scale isosurfaces. Subdivision surfaces provide a flexible modeling tool for surfaces of arbitrary topology and for functions defined thereon. Wavelet representations add the ability to compactly represent large-scale geometries at multiple levels of detail. Our wavelet construction based on subdivision volumes extends these concepts to trivariate geometries, such as time-varying surfaces, free-form deformations, and solid models with non-uniform material properties. The domains of the repre-sented trivariate functions are defined by lattices composed of arbitrary polyhedral cells. These are recursively subdivided based on stationary rules converging to piecewise smooth limit-geometries. Sharp features and boundaries, defined by specific polygons, edges, and vertices of a lattice are explicitly represented using modified subdivision rules. Our wavelet transform provides the ability to reverse the subdivision process after a lattice has been re-shaped at a very fine level of detail, for example using an automatic fitting method. During this coarsening process all geometric detail is compactly stored in form of wavelet coefficients from which it can be reconstructed without loss.

REFERENCES

• 1: C. Bajaj, J. Warren, and G. Xu, A smooth subdivision scheme for hexahedral meshes, The Visual Computer, special issue on subdivision (submitted), 2002, http://www.cs.rice.edu/ jwarren/
• 2: Martin Bertram , Daniel E. Laney , Mark A. Duchaineau , Charles D. Hansen , Bernd Hamann , Kenneth I. Joy, Wavelet representation of contour sets, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 3: Martin Bertram , Mark A. Duchaineau , Bernd Hamann , Kenneth I. Joy, Bicubic subdivision-surface wavelets for large-scale isosurface representation and visualization, Proceedings of the conference on Visualization '00, p.389-396, October 2000, Salt Lake City, Utah, United States
• 4: Martin Bertram, Multiresolution modeling for scientific visualization, 2000
• 5: Henning Biermann , Adi Levin , Denis Zorin, Piecewise smooth subdivision surfaces with normal control, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.113-120, July 2000 [doi>10.1145/344779.344841]
• 6: Georges-Pierre Bonneau, Multiresolution Analysis on Irregular Surface Meshes, IEEE Transactions on Visualization and Computer Graphics, v.4 n.4, p.365-378, October 1998 [doi>10.1109/2945.765329]
• 7: Georges-Pierre Bonneau, Optimal triangular Haar bases for spherical data, Proceedings of the conference on Visualization '99: celebrating ten years, p.279-284, October 1999, San Francisco, California, United States
• 8: E. Catmull and J. Clark, Recursively generated B-spline surfaces on arbitrary topological meshes, Computer-Aided Design, Vol. 10, No. 6, Nov. 1978, pp. 350--355
• 9: Tony DeRose , Michael Kass , Tien Truong, Subdivision surfaces in character animation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.85-94, July 1998 [doi>10.1145/280814.280826]
• 10: D. Doo and M. Sabin, Behaviour of recursive division surfaces near extraordinary points, Computer-Aided Design, Vol. 10, No. 6, Nov. 1978, pp. 356--360
• 11: 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]
• 12: 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]
• 13: 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]
• 14: Leif Kobbelt, √3-subdivision, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.103-112, July 2000 [doi>10.1145/344779.344835]
• 15: L.P. Kobbelt, J. Vorsatz, U. Labsik, and H.-P. Seidel, A shrink wrapping approach to remeshing polygonal surfaces, Proceedings of Eurographics '99, Computer Graphics Forum, Vol. 18, Blackwell Publishers, 1999, pp. 119--129
• 16: L. Kobbelt, Interpolatory subdivision on open quadrilateral nets with arbitrary topology, Proceedings of Eurographics '96, Computer Graphics Forum Vol. 15, Blackwell Publishers, 1996, pp. 409--420
• 17: Aaron W. F. Lee , Wim Sweldens , Peter Schröder , Lawrence Cowsar , David Dobkin, MAPS: multiresolution adaptive parameterization of surfaces, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.95-104, July 1998 [doi>10.1145/280814.280828]
• 18: Nathan Litke , Adi Levin , Peter Schröder, Fitting subdivision surfaces, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 19: C.T. Loop, Smooth subdivision surfaces based on triangles, M.S. thesis, Department of Mathematics, University of Utah, 1987
• 20: John Michael Lounsbery, Multiresolution analysis for surfaces of arbitrary topological type, University of Washington, Seattle, WA, 1995
• 21: Michael Lounsbery , Tony D. DeRose , Joe Warren, Multiresolution analysis for surfaces of arbitrary topological type, ACM Transactions on Graphics (TOG), v.16 n.1, p.34-73, Jan. 1997 [doi>10.1145/237748.237750]
• 22: Ron MacCracken , Kenneth I. Joy, Free-form deformations with lattices of arbitrary topology, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.181-188, August 1996 [doi>10.1145/237170.237247]
• 23: Kevin T. McDonnell , Hong Qin, FEM-based subdivision solids for dynamic and haptic interaction, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.312-313, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376998]
• 24: Alistair Moffat , Radford M. Neal , Ian H. Witten, Arithmetic coding revisited, ACM Transactions on Information Systems (TOIS), v.16 n.3, p.256-294, July 1998 [doi>10.1145/290159.290162]
• 25: Gregory M. Nielson , Il-Hong Jung , Junwon Sung, Haar wavelets over triangular domains with applications to multiresolution models for flow over a sphere, Proceedings of the 8th conference on Visualization '97, p.143-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 26: V. Pascucci, Slow-growing subdivision in any dimension: towards Removing the curse of dimensionality, Technical Report, Lawrence Livermore National Laboratory, July 2001
• 27: Jörg Peters , Ulrich Reif, The simplest subdivision scheme for smoothing polyhedra, ACM Transactions on Graphics (TOG), v.16 n.4, p.420-431, Oct. 1997 [doi>10.1145/263834.263851]
• 28: Jörg Peters , Ulrich Reif, Analysis of Algorithms Generalizing B-Spline Subdivision, SIAM Journal on Numerical Analysis, v.35 n.2, p.728-748, April 1998 [doi>10.1137/S0036142996304346]
• 29: H. Prautzsch, Analysis of Ck-subdivision surfaces at extraordinary points Technical Report, University of Karlsruhe (Germany), 1995
• 30: Ulrich Reif, A unified approach to subdivision algorithms near extraordinary vertices, Computer Aided Geometric Design, v.12 n.2, p.153-174, March 1995 [doi>10.1016/0167-8396(94)00007-F]
• 31: 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]
• 32: Thomas W. Sederberg , Jianmin Zheng , David Sewell , Malcolm Sabin, Non-uniform recursive subdivision surfaces, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.387-394, July 1998 [doi>10.1145/280814.280942]
• 33: Jos Stam, Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.395-404, July 1998 [doi>10.1145/280814.280945]
• 34: W. Sweldens, The lifting scheme: a custom-design construction of biorthogonal wavelets, Applied and Computational Harmonic Analysis, Vol. 3, No. 2, pp. 186--200, 1996
• 35: Denis Zorin , Peter Schröder , Wim Sweldens, Interpolating Subdivision for meshes with arbitrary topology, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.189-192, August 1996 [doi>10.1145/237170.237254]
• 36: D. Zorin, Smoothness of subdivision on irregular meshes, Constructive Approximation, Vol. 16, No. 3, 2000, pp. 359--397

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computation of transforms (e.g., fast Fourier transform)

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Wavelets and fractals; Approximation of surfaces and contours

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
arbitrary topology, b-spline wavelets, geometry compression, hierarchical b-splines, multiresolution modeling, subdivision surfaces, subdivision volumes