Extended Quadric Error Function for Surface Simplification

Deepak Bandyopadhyay

Initial Proposal (9/23/00)

Go to update 1 | final report | presentation slides (PPT, 850k).

CAVEAT: This page is best viewed with Internet Explorer 4.0 and above. If you view on Netscape 4.0x or another browser, some of the math symbols won't show properly, but otherwise you should be fine.

BRIEF DESCRIPTION

Current software for triangle mesh simplification (eg. Michael Garland's QSlim) can rapidly produce coarser approximations to a fine surface mesh. The algorithm behind this software iteratively collapses the two vertices which minimize an error function called the quadric error metric, a measure of the square of the distance of the proposed new point from all the planes associated with the original points. I want to modify this algorithm incorporating an error function that is a generalization of the quadric function, and compare its performance with that of the original.

MOTIVATION AND PERSONAL INTEREST

My current research work often throws up geometric modeling problems from the areas of model acquisition and representation. Surface simplification may be very helpful when we are trying to transmit or interactively render huge laser-scanned datasets. During the project I plan to learn about this and other areas of geometric modeling in depth to open up the possibility of further research. Also, Gopi Meenakshi is working on surface reconstruction that uses a form of the extended quadric error function. He has proved that this function is equivalent to distance functions that are based on curvature. Working with Gopi, I hope to investigate if we can extend the applicability of his technique to other geometric operations, starting with surface simplification.

PROPOSED APPROACH

I present here a mathematical description of what I plan to do.

The quadric-based algorithm chooses a pair of points to contract, based on which pair has the minimum error as defined by the Quadric Error Metric:

$v$ ^T Q v, Q=Q₁+Q₂, v=the new vertex position

$Q$ _i, the quadric matrix term, so named because it is a quadratic expression in terms of the variables in the equation of the plane, is initially set to:

$Q$ _i=∑_{planes thru v}{K K^T} ; $K:=[a b c d]$ ^T has the coefficients from the plane equation.

This can be used to compute the squared distance from any point to all the planes passing through a point. When two vertices are combined, their Q matrices get added, and the new point v gets chosen in such a way that the error function is minimized.

Now we introduce the new distance function proposed by Gopi, for two points p, q with normals $N$ _p, N_q:

$D(p,q) = E$ ²(p,q) + T_p²(q) + T_q²(p)

where E is euclidean distance, and

T

_p(q) is distance from q to the tangent plane of p. This can be expressed in matrix form:

D(p,q) = [p-q]

^T [p-q] + [p] ^T ([N_q] [N_q]^T) [p] + [q]^T ([N_p] [N_p]^T) [q]

p, q, $N$ _p, N_q are homogenous column vectors. With a little substitution, we can get the final form of the error function:

$D(p,q) = [p-q]$ ^T {α*I'_4x4 + (1-α)*(Q_p + Q_q)} [p-q]

$α$ is a parameter, and $I'$ _4x4 is a 4x4 identity matrix with the last row all zeros - this is the contribution from Euclidean distance.

When $α=0$ , this reduces to the Quadric Error Metric itself, whereas as $α$ increases, the weight of the Euclidean distance term increases. That is why I call it an extended quadric error function (neither Garland's quadric nor this function are metrics in the linear algebra sense, as they do not satisfy the triangle inequality).

I hope to show that this function performs better than the original quadric error metric, i.e. the simplification is faster/better in at least a few significant cases. But even a performance equal to that of QEM (or of GAPS, a system based on QEM) would serve the purpose of the project. Gopi's plan for future work is to show that the same error function can be extended to improve the performance or decrease the cost of other geometric techniques, viz. reconstruction (going from point set to triangle mesh), resampling (dense point set to sparser point set that represents the same reconstructed surface) and clustering (hierarchical subdivision of the mesh into components).

GOALS TILL DECEMBER

For October 15: Literature survey and understanding QSlim code. Working out the math for the new error metric. Coming up with good models on the basis of my study that may demonstrate the superiority of the modified algorithm.

For November 10 First implementation of the modified algorithm. Initial results of a comparison with the original algorithm.

For November 30 (final) Finished implementation and all results. Demonstrate the results with a presentation and/or demo. Give some conclusions based on a study of how the method can be applied to other problems in geometry.

REFERENCES AND PREVIOUS WORK

Michael Garland's PhD thesis at CMU, "Quadric-based Polygonal Surface Simplification" (PDF, 10 MB) has details about the simplification algorithm and the subsequently released source code for Garland's simplification package, QSlim.

Garland and Heckbert also have a SIGGRAPH 97 paper, "Surface Simplification Using Quadric Error Metrics" (PDF, 766 KB) , which describes the algorithm.

Garland, Michael and Paul Heckbert, "Simplifying Surfaces with Color and Texture Using Quadric Error Metrics", IEEE Visualization 98(PDF, 1 MB) is an extension to the method for surfaces with attributes

Ericson, Carl and Dinesh Manocha, "GAPS : General and Automatic Polygonal Simplification", Symposium on Interactive 3D Graphics, 1999 (PDF, 216KB).

Dey, Edelsbrunner, et al, Topology-preserving Edge Contraction, Publ. Inst. Math. (Beograd), 1999 use the quadric based algorithm to perform simplification with additional properties that preserve topology.

HOW IS IT NOVEL? AND USEFUL?

It is clear from the last few references that a lot of people are working on projects that use the quadric method to achieve some kind of surface simplification. This work, by modifying the fundamental algorithm behind the method, can potentially be useful to a large class of geometric problems that use simplification.