Project archive

Dynamic mesh compression

This project focuses on size reduction of dynamic meshes. A dynamic mesh is a sequence of static triangular meshes of equal connectivity, describing the temporal development of a physical surface. Compression of such data is similar to static mesh compression, with two extra constraints:

• The dynamicity of the data must be exploited: subsequent meshes are similar, which can be used for better prediction and higher efficiency.
• The dynamicity of the data must be addressed: temporal artefacts such as shaking, which cannot appear in the static case, must be identified and avoided.

People

• Ing. Libor Váša, Ph.D. (lvasa@kiv.zcu.cz) — compression algorithms, simplification, project lead
• Jan Rus, Bc. — connectivity encoding, clustering-based approaches
• Ing. František Zadražil — evaluation algorithm testing

Publications

• Váša, L.: Methods for size reduction of dynamic meshes, Ph.D. thesis, University of West Bohemia, 2008.
• Váša, L., Skala, V.: COBRA: Compression of the Basis for PCA Represented Animations, Computer Graphics Forum.
• Váša, L., Skala, V.: Combined Compression and Simplification of Dynamic 3D Meshes, Computer Animation and Virtual Worlds.
• Rus, J.: Web based player for compressed dynamic meshes including a full implementation of EdgeBreaker algorithm, Bc. thesis, University of West Bohemia, 2008 (Czech only).
• Zadražil, F.: Methods of triangular dynamic meshes comparison, MSc. thesis, University of West Bohemia, 2007 (Czech only).
• Collective of authors: Three-Dimensional Television: Capture, Transmission, Display, Springer, December 2007.
• Váša, L., Skala, V.: CoDDyAC: Connectivity Driven Dynamic Mesh Compression, 3DTV Conference 2007.
• Váša, L.: Methods for dynamic mesh size reduction, Technical report DCSE/TR-2006-07, University of West Bohemia, October 2006.

Achievements

We view the input as a set of vertex trajectories. Principal Component Analysis of the trajectory set yields a new basis; most coordinates in that basis can be neglected, giving a 70–90% reduction of dimensionality without losing more than about one percent of the original variance.

Parallelogram prediction of PCA coefficients then reduces residual entropy. Residuals are quantized and sent to the decoder. This idea was published as CoDDyAC.

A later extension adds a simplification step by vertex decimation, performed by encoder and decoder after transmitting connectivity and before geometry. Geometry is sent in inverse decimation order, so vertices are added into fully known neighbourhoods. Extrapolation is replaced by more precise interpolation, and the stream becomes scalable.

An RBF-based interpolation predictor reduced data rate by about 25%. Because PCA combination coefficients predict well, the orthonormal PCA basis dominates the stream. Importance-dependent quantization plus motion-based prediction reduced encoded basis size by about 90% (COBRA).

Standard distortion metrics (MSE, DA error) correlate poorly with perceived distortion of dynamic meshes. Subjective tests led to the STED error, with Pearson correlation around 0.95; details are in thePh.D. thesis.

Results

Rate–distortion curves for two testing models. Rate is in bits per frame per vertex; error follows Karni and Gotsman. Comparison is against FAMC (part of the MPEG standard).

Dance model

Cow model

Downloads

A set of modules for the MVE-2 environment is useful for developing new dynamic mesh compression algorithms. The current compressor is not included; the library covers:

• Loading an animation from a VRML file
• Saving an animation into a VRML file
• Comparing two animations using the KG error metric
• A torso of a compression module, which can be expanded into a new compression algorithm

The package also contains two example maps, one for compression evaluation and one for playback of VRML files. See the original project download atMeshCompression.zip if present on the server.

A note on comparisons

There is a small ambiguity in the interpretation of the KG error (Karni, Gotsman: “Compression of soft body animation sequences”). The C# fragment below is the consensus procedure used in this work. The same note appears on the KG error page.

int pointCount = ((UnstrGrid)input1[0]).Points.Count;
int frameCount = input1.Count;

double[,] means = new double[frameCount, 3];
for (int i = 0; i < pointCount; i++)
{
    for (int j = 0; j < frameCount; j++)
    {
        TriangleMesh mesh = (TriangleMesh)input1[j];
        Point3D point = (Point3D)mesh.Points[i];
        means[j, 0] += point.X;
        means[j, 1] += point.Y;
        means[j, 2] += point.Z;
    }
}
for (int i = 0; i < frameCount; i++)
{
    means[i, 0] /= pointCount;
    means[i, 1] /= pointCount;
    means[i, 2] /= pointCount;
}

double s1 = 0;
double s2 = 0;

for (int i = 0; i < frameCount; i++)
{
    UnstrGrid frame1 = (UnstrGrid)input1[i];
    UnstrGrid frame2 = (UnstrGrid)input2[i];

    UniformDataArray points1 = frame1.Points;
    UniformDataArray points2 = frame2.Points;
    for (int j = 0; j < pointCount; j++)
    {
        Point3D p1 = (Point3D)points1[j];
        Point3D p2 = (Point3D)points2[j];
        s1 += (p1.X - p2.X) * (p1.X - p2.X);
        s1 += (p1.Y - p2.Y) * (p1.Y - p2.Y);
        s1 += (p1.Z - p2.Z) * (p1.Z - p2.Z);
        s2 += (p1.X - means[i, 0]) * (p1.X - means[i, 0]);
        s2 += (p1.Y - means[i, 1]) * (p1.Y - means[i, 1]);
        s2 += (p1.Z - means[i, 2]) * (p1.Z - means[i, 2]);
    }
}
result = new Scalar((Math.Sqrt(s1) / Math.Sqrt(s2)) * 100);

SetOutput("KG error", result);