Bicubic Subdivision Surface Wavelets
Martin Bertram, Mark A. Duchaineau, Bernd Hamann, and Ken Joy
In this project, we have constructed a new wavelet transform based on uniform bicubic B-spline subdivision. Our approach is the first to use a simple lifting-style filtering operation with bicubic precision. Compared to the previous smooth subdivision-surface wavelets constructions, our approach requires only fast and local lifting-style 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 Catmull-Clark subdivision, has comparable simplicity, and it also produces piecewise bicubic patches.
Subdivision surfaces are limit surfaces that result from recursive refinement of polygonal-based 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 Catmull-Clark subdivision, which generalizes bicubic B-spline subdivision to arbitrary topology. Vertices in the supermesh correspond to faces, edges, or vertices in the submesh. All faces produced by Catmull-Clark subdivision are quadrilaterals.
Given a piecewise linear function defined by a list of "control points," the one-dimensional 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 tensor-product wavelet transform is defined by performing a one-dimensional wavelet transform for all rows and then all columns of the mesh.
To generate our lifting scheme, we have re-oriented the tensor-product 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 edge-collapse method of Hoppe, then use a refinement fitting procedure to convert the surface to have subdivision-surface 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.
- 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. 619--625, 2000.
- Martin Bertram, Mark A. Duchaineau, Bernd Hamann, Ken Joy, Bicubic Subdivision-Surface wavelets for Large-Scale Isosurface Representation and Visualization, in: IEEE Visualization 2000, pp. 389--396, 2000.