Extended Quadric Error Function for Surface Simplification

Mid-Semester Update (10/26/00)

STUFF DONE

• Read most of the quadric error metric based simplification references (Garland, Erikson).
• Worked out some math related to the distance function and how it should be applied to simplification.
• Installed QSlim 2.0, read and understood the code for the toolkit and the main simplification library.
• Hacked the library code to keep everything else the same, just change the order of picking vertex pairs to merge based on nearness calculated with the distance metric, not least error in selecting the point. If this change is made, we propose that the quality of simplification will not suffer very much, while the work done is reduced a lot (instead of computing the optimal point for every vertex pair, compute it only for the pair that has been picked to be merged, based on them having the smallest value of our distance function).

RESULTS

original cow model	original bunny model
cow, 3000 triangles, original	cow, 3000 triangles, distance function
2000 triangles, original	2000 triangles, distance function
1000 triangles, original	1000 triangles, distance function
250 triangles, original	250 triangles, distance function
250 triangles, original side on	250 triangles, distance function side on
250 triangles, original tail view	250 triangles, distance function tail view
bunny, 10000 triangles, original	bunny, 10000 triangles, distance function
1000 triangles, original	1000 triangles, distance function
250 triangles, original	250 triangles, distance function

DISCUSSION OF RESULTS

1. Both the algorithms give similar results when not too many edges have been collapsed. However the order of edges picked is very different. Since we do not see the difference in structure of the simplified model until we come down to very coarse resolutions, we conclude that initially both algorithms are picking a reasonable set of edges to simplify. As the initial edges (before any combination/merging has taken place) correspond to direct use of our distance function on real edges, we conclude that our distance function is likely to pick edges having a low cost of merging.
   
   
2. On trivial models (eg. a cube model made with 12 triangles), both the algorithms always pick the same pair of edges.
   
   
3. When we get down to lower numbers of faces (where low is defined as some function of the original number of faces), our variant of the algorithm progressively messes up.
   • It erodes thin projections of the model such as the cow's horns.
   • Lots of areas such as the cow's teats are oversimplified with respect to the rest of the model and the manifold structure of the model is lost in those areas (this is visible in the 2000 triangles images).
   • Disconnection or spurious connection can occur (in the cow's tail view the tail is disconnected from the rump and spuriously attached between the cow's legs).
   • Finally, spurious geometry may be introduced around holes in the model. For example in the bunny images, weird "teeth" are visible below the base, around the rims of the holes in the base.
   
   
4. It is not clearly understood why the distance function is yielding these strange artifacts. However, the encouraging sign is that the quality of simplification is not an order of magnitude worse at sufficiently high triangle counts.
   
   
5. For my next report, I expect to plug in the distance function into a lot more than just the order of edge selection (eg. in computing the merge error of a pair merge and the resultant error of the new vertex smartly, rather than calling the distance function again on the physical location of the merged vertex and all its neighbors).