Random notes on Quadric Error Metrics

Mesh decimation is the process of simplifying a mesh. Most of the time you do this to improve performance. A popular method of mesh decimation is called the edge collapse. You move a vertex from one side of an edge in a mesh to the other. Then you delete any degenerate triangles. One of the first things you need to do is decide which edge is the best to collapse! Computing a Quadric Error Metric) (QEM) for a vertex is a method of determining the cost of an edge collapse.

The basic idea is that the QEM gives you the sum of the squared distance of a point to a set of planes. Then for each point in your mesh, you build a set of planes from the triangles it belongs to and you can use the QEM to compute the cost for moving a vertex from its starting position to a new position. It has some neat properties. If you add two quadrics together, it’ll return the same results as if you built a quadric with all of their source planes from scratch. This is convenient during mesh decimation because you can combine quadrics after performing an edge collapse.

After implementing the QEM code, I noticed some things:

1. If you calculate the error for a vertex without moving it, it should be zero. This is one way to validate your implementation of QEM.

2. If you look at the formulas given in section 5.1 of (http://graphics.cs.uiuc.edu/~garland/papers/quadric2.pdf). You’ll see that it calculates two edge vectors to define a plane. The vectors are defined (in pseudo code) as: e1 = q-pe1.normalize()side2 = r - p

   side2.normalize() // <- This is not in the original paper

   e2 = side2 - (e1 dot (side2)) * e1

   e2.normalize()It turns out that it’s better to normalize side2 before calculating e2. You can confirm this by doing a dot product between e1 and e2, it should be very close to zero. For larger triangles, or nearly degenerate triangles, I ended up with e1 & e2 not being perpendicular at all. This just causes havok later on, producing large negative values for the distance calculation, which should be impossible! ;)

3. The verts that you choose for p,q,r matter. If you play with the ordering, you can see that the error will change a bit. I tried to make sure that (q-r) dot (r - p) was as close to zero (as close to perpendicular) as possible. So I swap p,q,r until I find the combination that’s closest to zero.

4. For some inputs, it works much better with doubles vs. floats. But even with doubles, you must make sure that the double precision rounding is enabled. DirectX will often change this on you unless you tell it not too! If I had remembered this sooner (this has caused other problems for coworkers), I probably would not have figured out 1 & 2 above! ;)

I’m working on improving the rest of the decimation system. Some of that work will involve not feeding the QEM bad triangles that are nearly degenerate which will make the changes above less important. But now that I’ve explored and fixed some of these issues I’m confident that this brick in the decimation system is solid!