Extended Quadric Error Function for Surface Simplification

End-Semester Final Report (12/16/00)

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.

REDEFINITION OF GOALS

• I set out with the distance function in the form it was stated (specifically, with α assumed to be 0.5, or to be a parameter that was tweakable to allow varying importance to be given to the Euclidean distance). Unfortunately, this idea didn't work and I found that giving zero weight to the Euclidean term was the best setting to avoid errors in choosing the vertex similar to those shown here (with and without quadrics drawn).

 
• Early attempts. The distance function being used only in picking the vertices to merge (but quadric error metric being used for everything else) was not as successful as some later variants, and hence is not described in detail in the final proposal. For some of the mid-term results, refer here.

 
• Focus. There was no time in this semester to expound on which other stages of the geometric modeling pipeline the distance function can be applied to. Gopi, who proposed the function, is applying it to sampling and reconstruction, and has ideas on how it can be applied to resampling and clustering.

 
• Detailed plan of action. I identified 3 places in the quadric simplification algorithm and planned to improve it by:
1. Picking an edge for simplification, from the heap on edges keyed on some kind of error metric
2. Choosing the position of the new vertex formed from the picked edge, to minimize this error metric
3. Assigning an error value to the new vertex (and the edges arising from it) so that it can play a part in the following steps of simplification.

STUFF DONE

• Merge error formulation for the simplification. This is based on a formula derived by Gopi:




$Error(x)\; =\; Error(p)\; +\; Error(q)\; +\; Merge\_Error(p,q,x)$

Here the merge error refers to the error in creating new vertex x by collapsing vertices p and q. This error is what we quantify using either our distance function (in which case it just depends on p and q) or using the quadric error metric (where x is chosen to minimize this metric).
 

• Vertex error propagation. Having the errors accumulating in the vertices as they are created by merges is another addition to the QEM. When everything else remains the same, just adding vertex error propagation results in a quality of simplification that is no worse than the original QEM. Thus it paves the way for using this formulation for the distance function where it is essential to prevent very average looking results such as those from the midterm report, due to some heavily merged edges being repeatedly picked because of their length being favorable in "distance function space".

 
• DF minimization. With merge error and vertex error accumulation/propagation, we can replace the picking stage and the propagation stage with something calculated using the distance function. For the new vertex positioning stage, we were still using the quadric error metric to find the point with minimum error. To incorporate distance function here, a method was required that would place the new vertex to reduce (maybe not minimize) the distance function value on all the edges arising from that new vertex. As a first attempt, we have used a linear interpolation that works thus:


_pq / (p^TQ_qp + q^TQ_pq) 

The effect of this is to place the new point closer to the planes of p if the distance of q from the planes of p is less than that of p from q's planes.
 

• With the framework ready, I put all these changes as compile-time options to Garland's Mixkit library on top of which QSlim is based. Depending on how you compile it, the behavior of the simplification changes into one of four supported modes:

 
1. Original QSlim (QEM)
2. QEM with vertex error propagation (Q/VEP)
3. Distance function with new vertex position chosen by QEM minimization (DF/VEP, QEM for new vertex position (QNV))
4. Distance function with new vertex position chosen to reduce the distance function error (DF all the way)
   
   
• Optimizations. The significant one that got the run time of the DF variants down was realizing that the order of computatation used by QSlim (to compute the QEM for each and every edge first, and then choose the minimum cost edge on the heap, and when collapsing that edge, use the precomputed minimum error and the position of new vertex that minimizes this error, was an overkill when doing a hybrid of the two methods (my second variant). It suffices to calculate the DF value on all edges (a fast computation compared to QEM minimization which involves a 4x4 matrix inversion) beforehand, and to calculate the minimization (using QEM or DF minimization) only for an edge that has been selected to merge. So the new pipeline is:

 
1. create all edges & place in a heap, keyed by Vertex Error (not simply Merge Error) values
2. loop starts. Pick least cost edge (V1,V2) from heap to merge
3. Calculate new vertex position X minimizing some metric (QEM, DF)
4. Calculate propagated error of new vertex using the E(X) = E(V1) + E(V2) + ME formulation
5. Relink all edges that connected to V1 or V2 to X, and call the "create edge" routine to recalculate the heap key for these edges and change their position in the heap.
6. Loop back to step 2, stopping when the target number of faces is achieved.
• Finally, a visualization tool was needed to quantify how good the simplification was in terms of quality, and for this as suggested by Gopi I calculated the average (RMS) plane radius for a point as follows:


$R\; =\; sqrt(pTQ$_pp / n),   where n is the number of planes in the quadric matrix Q_p for point p. 

With this radius and a suitable multiplicative factor (100 or 1000 depending on the amount of simplification and the model) I was able to visualize the error accumulated at each point, which if the radius is picked right ought to be a rough indicator of where the true surface lies, using the concept of simplification envelopes (Jon Cohen's work).

RESULTS

original cow model	original bunny model
cow, 3000 triangles, spheres x1000, original QEM	cow, 3000 triangles, Variant 1 (QVEP)
3000 triangles, Variant 2 (DF/VEP QNV Hybrid)	3000 triangles, Variant 3 (DF All the Way)
1000 triangles, spheres x100, original QEM	1000 triangles, Variant 1 (QVEP)
1000 triangles, Variant 2 (DF/VEP QNV Hybrid)	1000 triangles, Variant 3 (DF All the Way)
250 triangles, original QEM	250 triangles, Variant 1 (QVEP)
250 triangles, Variant 2 (DF/VEP QNV Hybrid)	250 triangles, Variant 3 (DF All the Way)
1000 triangles tail view, original QEM	1000 triangles tail view, Variant 1 (QVEP)
1000 triangles tail view, Variant 2 (DF/VEP QNV Hybrid)	1000 triangles tail view, Variant 3 (DF All the Way)
bunny, 1000 triangles, spheres x1000, original	bunny, 1000 triangles, Variant 3 (DF all the way)

DISCUSSION OF RESULTS

1. Variant 1 is just a proof of concept of vertex error propagation. So we don't discuss its properties other than that it behaves surprisingly similar to the original QEM, from the plane sphere diagrams we can see that almost all the vertices picked for simplification are the same. This seems to indicate that having vertex error propagation does not alter the QEM substantially, since maybe it has this error inherent in the merge error of each vertex. To illustrate, when 2 merged vertices x and y formed out of unmerged vertices (p,q) and (r,s), $E(x)\; =\; E(p)\; +\; E(q)\; +\; xT(Q$_p+Q_q)x and E(y) = E(r) + E(s) + y^T(Q_r+Q_s)y are merged to z, the error is now E(z) = z^T(Q_p+Q_q+Q_r+Q_s)z + E(x) + E(y). This now has some terms depending on x and y, though the z term has all the 4 quadrics and z itself depended on the quadrics of x and y, so it is conceivable that this term still dominates as is seen to happen.
2. Variant 2 is sort of the best of both worlds - its results are pretty good (except for fidelity to the model at low triangle counts). Using QEM to position the new vertex does bring an improvement of quality over variant 3 which is mostly perceptible from the plane spheres though it is hard to tell by looking at the simplified model.
3. Variant 3 is our most significant finding - here we have kept the backbone of the QSlim code but apart from maintaining quadrics for calculating the distance function easily, we don't use them at all. In particular there is no quadric optimization at any stage of the algorithm. Still the quality is very similar to that attained by the original at most high to average (not very low) triangle counts.
4. The weird black spots seen in some of the demos and some non-manifold surfaces in simplified models of the cow are nothing but flipped triangles drawn with the back face facing the viewer. QSlim, possibly due to some clever properties of the QEM, manages to avoid showing too many of these at high enough triangle counts, though in the DF-based variants they do show up over time, for example in the Happy Buddha demonstration when 407k triangles are compressed to 4k.
5. The spurious geometry that one saw in the models for the midterm report went away when we stopped using the Euclidean part of the distance function, or alternatively when we constrained the new vertex to lie on the edge instead of anywhere in space. So we got rid of the Euclidean term, though this may have been a premature termination of this route in the heat of the deadline, a route which could yield interesting results if we take it up again after solving the spurious geometry problem another way.
6. Disconnection or spurious connection near the cow's tail was improved quite a lot at moderately low triangle counts (eg. 1000) by eliminating the Euclidean distance term in the DF.