 |
 |
| a. | b. |
 |
 |
| c. | d. |
[Technical Sketch, SIGGRAPH'97]
We study the use of wavelet compression of a volumetric representation
of polyhedral surfaces. The surface is first represented by the zero set
of a distance function. We apply wavelet multiresolution analysis to this
function. This allows us to represent a polyhedral object of arbitrary
topology to a variable level of detail. By reducing the number of detailed
coefficients, we can achieve very high compression ratios of the geometry
data with little loss in image quality. Secondly, this method allows reduction
of the genus of the object as level of detail is decreased. Most current
methods of surface simplification ([ED95], and many others) do not allow
variations of genus as resolution is lowered. This is a significant drawback
when used for the purpose of low resolution approximations of object for
rapid rendering. Indeed, if we are given a grid of n intersecting
cylinders, the number of triangles necessary for a genus-preserving representation
is necessarily greater than n2. The method of [RB93]
and [HH94] are an exception. In the former, simplification is done by merging
surface vertices. Our method uses a volumetric representation, as
in [HH94] where a low-pass filtering method is used on a different representation.
We combine several techniques, and proceed as follows. Given a polyhedral
surface S, we define a distance function d(x,y,z)
on 3D space such that S is the zero set of d. The function
d will be the distance from the point (x,y,z)
to the surface for points outside the object, and the negative of the distance
for points inside. This function is piecewise linear and discontinuities
occur at the faces, edges, and vertices of the Voronoi diagram of the polygonal
object surface.
We sample this function at a regular 3D grid (the sample interval is a
function of curvature and triangle size), and perform three-dimensional
wavelet analysis [M93]. See below for the type of wavelet used. We now
have a multiresolution representation of the distance function: a series
of wavelet coefficients. Next, we apply wavelet compression: the number
of largest wavelet coefficients we keep depends the desired level of detail
and accuracy. At this point, the object has a very compact representation
which can be efficiently stored or transmitted.
To reconstruct the surface, the distance function is approximated by wavelet
reconstruction. The next step is to reconstruct the polygonal surface.
This is accomplished by using the classical marching cubes algorithm. Using
the function d instead of the classical "volume inside voxel"
function reduces the blockyness of the reconstructed surface [J96]. The
final step involves simplifying the resulting surface. We employ a triangle
decimation method. An alternative to our last two steps is to use the methods
of [SF+96], which produces an already simplified triangular mesh.
In Figure 1, we give an example of the results obtainable by our method. We used Battle-Lemarié wavelets for their smoothness and symmetry. The original object is shown in Figure 1a. In b., keeping 0.5% of coefficients yields, yields a compression of 36:1 without much loss of image quality. In c., we show an intermediate resolution., and in d., we use Haar wavelets, keep 0.1% of coefficients, and obtain a reduction of genus.
|
|
| a. | b. |
|
|
| c. | d. |
In summary, we achieve high compression ratios of polyhedral surfaces. Other advantages of our method are that it allows simplifying and possibly merging several objects. In addition, this method is well suited for progressive transmission of surfaces. We plan to continue the study of this type of object representation including using different distance functions, studying different types of wavelets, and comparing to other simplification algorithms.
[D95] M. Deering. Geometry Compression. Proc. SIGGRAPH 95, 13-20.
[ED+95] M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Loundbery, W. Stuetzle,
Multiresolution Analysis of Arbitrary Meshes, Proc. SIGGRAPH 95, 173-182.
[J96] M. Jones, The Production of Volume Data from Triangular Meshes Using
Voxelisation. Computer Graphics forum, vol. 15, number 4, 311-318.
[HH+94] T. He, L. Hong, A. Kaufman, A. Varshney, S. Wang, Voxel Based Object
Simplification, Visualization 94, 85-92.
[M93] S. Muraki, Volume Data and Wavelet Transforms. IEEE Computer Graphics
and Applications, vol. 13, 4, 1993, 50-56.
[RB93] J. Rossignac, P. Borrel, Multi-Resolution 3D Approximations for
Rendering Complex Scenes, Modeling in Computer Graphics, Springer-Verlag,
1993, 455-465.
[SF+96] R. Shekhar, E. Fayyad, R. Yagel, J.F. Cornhill, Octree-based Decimation
of Marching Cubes Surfaces, IEEE Visualization '96.