Bicubic Subdivision Surface Wavelets
Martin Bertram, Mark A. Duchaineau, Bernd Hamann, and Ken Joy
Abstract
In this project, we have constructed a new wavelet transform based on uniform bicubic Bspline subdivision. Our approach is the first to use a simple liftingstyle filtering operation with bicubic precision. Compared to the previous smooth subdivisionsurface wavelets constructions, our approach requires only fast and local liftingstyle filtering operations rather than global sparse matrix solutions, which makes large data surface compression feasible. This wavelet construction also includes modifications to support boundary curves and sharp features. Our wavelet transform is structurally similar to CatmullClark subdivision, has comparable simplicity, and it also produces piecewise bicubic patches.
Subdivision surfaces are limit surfaces that result from recursive refinement of polygonalbased meshes. A subdivision step refines a submesh to a supermesh by inserting vertices. The positions of all vertices of the supermesh are computed from the positions of the vertices of the submesh, based on certain subdivision rules. Most subdivision schemes converge rapidly to a continuous limit surface, and a mesh obtained from just a few subdivisions is often a good approximation for surface rendering. Subdivision surfaces that reproduce piecewise polynomial patches can be evaluated in a closed form at arbitrary parameter values.
Our method is based on CatmullClark subdivision, which generalizes bicubic Bspline subdivision to arbitrary topology. Vertices in the supermesh correspond to faces, edges, or vertices in the submesh. All faces produced by CatmullClark subdivision are quadrilaterals.
Given a piecewise linear function defined by a list of "control points," the onedimensional wavelet transform eliminates every second control point and thus provides a coarser representation of this function. The eliminated points are replaced by accumulated differences from which the function and its original resolution can be reconstructed without loss. The entire process is called decomposition and is recursively applied to the function until a base resolution is reached.
Our wavelet transform is based on a lifting scheme. Lifting operations are used to design wavelets with certain properties, like vanishing moments, and to split the computation into small local steps, each called a "lifting operation." Every decomposition step is computed by two lifting operations, implemented as in the diagram below: Here, "a" and "b" are parameters that control the lifting operation.
The inverse operation of a decomposition step is called reconstruction, and it is defined by a similar lifting operation. Reconstruction is recursively applied, starting with the coarsest representation, and reproducing the finer approximation levels.
In the special case of a rectilinear mesh, the tensorproduct wavelet transform is defined by performing a onedimensional wavelet transform for all rows and then all columns of the mesh.
To generate our lifting scheme, we have reoriented the tensorproduct lifting operation as is shown in the diagram below:
This simple step allows us to define a lifting operation from meshes of arbitrary topology.
The scaling function for a vertex of valence four is shown in the title picture (note the vertex of valence five in the mesh). The three pictures below show the wavelet functions for an edge (left), a sharp edge (middle), and a face (right).



We have used our wavelet construction to compute detail coefficients at multiple levels of surface resolution when control points on the finest subdivision level are given. We first construct a base mesh using a variant of the edgecollapse method of Hoppe, then use a refinement fitting procedure to convert the surface to have subdivisionsurface connectivity, a fair parameterization, and a close approximation to the original unstructured geometry. The following illustration shows the reconstruction of a very complex isosurface.
Our subdivision surface wavelets form a powerful multiresolution approximation tool for highly detailed surfaces of arbitrate topology.
Publications
 Martin Bertram, Mark A. Duchaineau, Bernd Hamann, Ken Joy, Wavelets on Planar Tessellations, in: Proceedings of The 2000 International Conference on Imaging Science, Systems, and Technology, pp. 619625, 2000.
 Martin Bertram, Mark A. Duchaineau, Bernd Hamann, Ken Joy, Bicubic SubdivisionSurface wavelets for LargeScale Isosurface Representation and Visualization, in: IEEE Visualization 2000, pp. 389396, 2000.