• L.Balmelli, Efficient approach to adaptive 4-8 mesh generation, Sept 24th 2001. (27 slides in pdf).download pdf.
• L.Balmelli, Interactive 4-8 mesh decimation. play with applet.

Related publications

L. Balmelli, T. Liebling and M. Vetterli, Computational analysis of 4-8 meshes with application to surface simplification using global error, Proc. of the 13th Canadian Conference of Computational Geometry (CCCG), August 2001.  download pdf.

Triangular meshes with subdivision connectivity are popular in applications such as visualization and finite element analysis. We consider a particular class of such meshes known as 4-8 meshes. These meshes are used to triangulate matrices of amplitudes (e.g. terrains). Recently, Velho and Zorin have shown how to obtain approximations of subdivision surfaces using 4-8 subdivision rules.  We present an efficient approach to generate adaptive representations of 4-8 meshes. In adaptive representations, triangles are concentrated in regions with "high activity", whereas smooth areas are approximated with large triangles. 

Our algorithm is inspired from an algorithm used to compute adaptive quantizers for compression presented by Chou et al. A similar algorithm has also been used by Ramchandran and Vetterli to compute optimal wavelet bases for image coding. Our mesh approximation problem poses further constraints and we explain how to 
address them in this talk. 

Our algorithm to generate adaptive representations has a fine to coarse approach. More precisely, an approximation of an initial fine mesh is obtained by successive decimations of vertices. Coarse to fine approaches have previously been proposed by Lindstrom et al. and Pajarola et al. However, these solutions use local error metrics and a greedy strategy to optimize the mesh. In contrast, we use a global error metric based on an optimal approach used in compression. 

We define a rate-distortion framework to obtain a metric for simplifying the mesh. A rate and a distortion functional is evaluated at each vertex. We show how to maintain global error estimates for the vertices when computing approximations. We explain that a direct algorithm using the global estimate has cost $\Theta(n^2)$. Our solution uses several properties of the 4-8 construction to obtain an efficient $Theta(n \log n)$ algorithm using the  same error metric. In conclusion, our approach, optimal with respect to a global error metric, has the same computational cost as previously proposed greedy strategies using local error.