Barycentric parametrization and quantization

Before emitting tetrahedron data its geometry is reparametrized into barycentric coordinates. Each inner point is expressed as a linear combination of the 4 tetrahedron corners, while points lying on tetrahedron faces are expressed as combination of only the three corners defining the face. The latter, ensures continuity between neighboring tetrahedra since the points on shared faces will be defined as combination of the same three vertices, see Fig.5.3(b). We chose this representation because it offers a compact representation that can be locally quantized without producing cracks between adjacent tetrahedra. However, due

Chapter 5.Compression-domain Seamless Multiresolution Visualization of Gigantic Meshes

on Mobile Devices

52

(a) Inner boundary

I

F

E c

(b) Barycentric coordinates

Figure 5.3: Tetrahedra merging.

a) Geometry simplification. An edge shared between two neighboring tetrahedra should be simplified only over the plane defined by the face connecting the tetrahedra. This way, the

barycentric coordinates of the vertices will depend only on the coordinates of the vertices defining face and so will be common for both tetrahedra. The blue edge disappears when blue vertices are merged. Green edges appear during the re-triangulation of the clipped geometry.b)

Barycentric coordinates.Four examples of vertices with their positions with respect to the tetrahedron: I inner, F on face, E on Edge, C on corner. For each vertex, we show the corners

which provide non null barycentric coordinate contribution.

to precision error, boundary points could be placed not exactly on the faces, thus producing different values on different tetrahedra, once data is quantized, see Fig.5.4.

Figure 5.4: Geometry quantization.Projecting boundary vertices on tetrahedron faces permit to solve mesh discontinuity among adjacent tetrahedra, which are due to quantization of slightly different values.

Hence, to ensure consistent quantizations, we subdivide the points in 4 cases depending on their position with respect to the containing tetrahedra: near a corner, near an edge, near one face, and inner point. In the first case the point is represented with only 1 not null coefficient, 2 coefficients for the second case

Chapter 5.Compression-domain Seamless Multiresolution Visualization of Gigantic Meshes

on Mobile Devices

53

expressing linear interpolation among 2 points, 3 in the third case for barycentric coordinates over a 3D triangle, and finally 4 for inner points. These cases are checked in this order, and with decreasing epsilon, to be sure to behave in the same manner on adjacent tetrahedra for the same points, see Fig.5.5.

(a) Input vertex snapping (b) Snap to corners (c) Snap to edges (d) Snap to faces

Figure 5.5: Vertex snapping.(a) Shows sample vertices that must be snapped onto (b) corners;

(c) edges or (d) faces.

The quantized geometry is stripified in a cache coherent way to maximize the number of cache hits of transformed vertices. Thereafter, vertices are reordered to match the order of appearance in the strip. This sorting permits to reflect the spatial position in the memory layout, thus keeping similar values (i.e., neighboring vertices) near each other, which will be useful for the compression step.

5.3.4 Compression

The quantized vertex coordinates are encoded together with normals and colors into a compact 64bit representation suitable for direct rendering, where 3 bytes are used for position, 2 bytes for normal and 3 bytes for color. Position is parametrized with 4 barycentric coordinates, but only 3 components are required since the four components sum to one. This 64bit/vertex encoding provides an extremely compact aligned representation that can be efficiently accessed on current GPUs, which typically require vertex data to be aligned on 32 bit boundaries. For a colored representation, 64bit/vertex is thus an optimal size. Normals are encoded using theoctahedron normal vectorapproach [Meye 10], which maps unit vectors to two parametric coordinates. This encoding consists in projecting the normals onto the octahedron by normalizing them with the 1-norm. The octahedron is unwrapped to a square and the[u, v]parameters in the plane are quantized to 8 bits, leading to sub-degree precision [Meye 10]. Decompression is numerically

Chapter 5.Compression-domain Seamless Multiresolution Visualization of Gigantic Meshes

on Mobile Devices

54

stable and requires only few basic operations which can be executed in the vertex shader.

This compact representation is well suited for rendering through a simple shader (see Sec.5.5), but higher compression rates can be achieved using a low-complexity codec applied to both vertex data and topology. In order to maximize data correlation for the entropy coding, color is transformed to the YCoCg reversible format [Malv 08], and all of the vertex attributes (i.e., posi-tion, normal and color) are deinterleaved and separated into their components and stored as a sequence of streams, to which strip indices are also appended (i.e., [P₀⁰..P_n⁰],[P₀¹..P_n¹],[P₀²..P_n²],[N₀^u..N_n^u],[N₀^v..N_n^v],[Y0..Yn],[Co0..Con],[Cg0..Cgn],[Io..Im]).

Each stream is then transformed using a reversible n-bit to n-bit wavelet based on the Haar wavelet transform in order to reduce entropy [Sene 04]. This ap-proach uniformly treats topology and vertex data, and generalizes the usual linear prediction methods typically applied to vertex positions. The low-pass coefficients produced by the wavelet transformation are iteratively filtered by the same wavelet until we remain with a single (root) approximation coefficient.

The resulting approximation and detail coefficients are then transformed with a range codec: integers are arithmetically coded using a single symbol for the value 0, while other values are encoded using exponent, mantissa and sign, with different context for each encoded bit. This is a variation of the symbol encoding method used in the FFV1 Video Codec [Mart 79]. During decompression all the steps are undone in reverse order.

In the course of the building process we also maintain a temporary version of the simplified data stored uncompressed on an external memory data reposi-tory, which is used to build coarser level simplifications without accumulating quantization errors.