Surface Simplification

Chris Tchou

Algorithm Description


The presented surface simplification algorithm simplifies the input mesh using edge contractions. The edge to be contracted at each step is chosen by trying to minimize the error introduced. If a vertex v represents a set of original vertices V; let F be the set of all original polygonal faces incident upon vertices in V. Then we define error as the sum over all faces in F of the distance between v and the plane of the face. An approximation of this error function is given by the Quadric Error Metric [1]. Each vertex is assigned a quadric error metric based on the planes of the incident faces. At each contraction, instead of recalculating the error over all original faces, we can simply sum the quadric error metric of the two vertices involved. Note this may double (or triple) count some faces, but it works well nonetheless as a fast approximation. Also, in most cases, given a QEM it is possible to solve directly for the point of minimum error.


To implement this efficiently, every edge contraction candidate is put into a queue based on the minimum possible error introduced by contracting that edge. The lowest error edge is contracted at each step, and appropriate modifications are made to contractions still in the queue. However, if an edge contraction is chose that results in a face 'flipping' it's normal around (which generally occurs in regions with lots of nearly planar polygons - contractions may fold triangles over other triangles), then the contraction is not used, but is put back into the queue with a slightly higher error.

Furthermore, the algorithm was made to use color as an additional 3 dimensions over which to consider error by using a 6 dimensional vector (x,y,z,r,g,b) in place of the standard 3 dimensional one (and doing the appropriate things to the math).

Papers:
[1] Michael Garland and Paul Heckbert. Surface Simplification Using Quadric Error Metrics. In SIGGRAPH '97 Proc. Aug 1997.
[2] Michael Garland and Paul Heckbert. Simplifying Surfaces with Color and Texture using Quadric Error Metrics. In IEEE Visualization 98.

Experiments:


I am using surface simplification as a method of identifying major light sources in a scene.

I originally intended to use an extrapolated 3d model of the scene to project color onto, thereby adding information about the size and relative orientation of light sources. Unfortunately, the model I intended to use was highly degenerate (many unconnected incident faces with non-incident vertices); it looks like it will require general vertex pair contraction, additional edge constraints, and some form of smart subdivision to accomplish automatically without destroying the scene.

In the meantime, the results of using 6 dimensional quadric error metrics (x,y,z,r,g,b), can be seen in the figures below. The first sphere uses a projected texture of the interior of St. Peter's Cathedral.

Figures:

St. Peter's Basilica projected onto a sphere and decimated to 8000 faces (click for a larger picture)
St. Peter's on a Sphere (73728 faces) Decimated Version (8000 faces)
73728 faces 8000 faces

The 'texture' used here is a high-dynamic range texture. Rather than having the colors limited to the range 0-255, the colors are stored as floating point values, representing the actual intensity (and color) of light coming from that direction. The windows in this image have over 1000.0 times the brightness of the rest of the scene; as you can see in the decimated version, the algorithm tries very hard to keep those bright vertices from changing. This effectively isolates the bright light sources, reducing the number of less important (darker) triangles. When calculating the effect of each of these 'light' triangles on an object we are lighting virtually, we are much more interested in the high frequency information of bright spots, and can make do with low frequency information in the dark spots.




A cow, decimated to 1000 and 500 faces:
Cow Model (5804 faces) Decimated (1000 faces) Heavily Decimated (500 faces)
5804 faces 1000 faces 500 faces

The 1000 face model of the cow, while losing some detail, still retains much of the overall shape. At 500 faces however, the model begins to degrade greatly; we lose the tips of the horns and the shape of the ears.



A spiral color pattern on a curved surface, decimated to 1000 faces:
Swirl Model (18050 faces) Decimated (1000 faces) Decimated Mesh (1000 faces)
18050 faces 1000 faces 1000 faces

The vertices on an open 'edge' of a mesh tend to shrink inwards. To fix this, Garland and Heckbert suggest adding additional heavily weighted constraint planes (perpendicular to the edge) to the quadrics of 'edge' vertices. In the interior of the mesh, however, we can see that the decimated version has remained fairly faithful to the color contours.

Swirl Overlap (1000 faces) Swirl No Overlap (1000 faces)
Face Flipping Edge
Contractions Allowed
Face Flipping Edge
Contractions Not Allowed

Notice the existence of triangle overlaps in the decimated swirl mesh on the left. When we disallow face flipping edge contractions, (by increasing their error and putting them back in the queue), these overlaps are removed.



A globe color pattern on a sphere, decimated to 8000 faces:
Globe Model (73728 faces) Decimated (8000 faces) Decimated Mesh (8000 faces)
73728 faces 8000 faces 8000 faces

The globe. Note the algorithm tends to prefer smaller triangles near perceived color edges, and decimates the mesh to a greater extent in regions of more constant color.




Timings:


Run on a Pentium II 450 Mhz with 384 MB RAM, running Windows NT 4.0
CommandInitial # FacesFinal # FacesSeconds
SimplifySurface -s -f 73700 globe-rgb.smf73728737003.594
SimplifySurface -s -f 60000 globe-rgb.smf73728600004.984
SimplifySurface -s -f 30000 globe-rgb.smf73728300008.016
SimplifySurface -s -f 8000 globe-rgb.smf73728800010.719
SimplifySurface -s -f 800 globe-rgb.smf7372880011.172
SimplifySurface -s -f 5000 cow.smf580450000.359
SimplifySurface -s -f 2500 cow.smf580425000.578
SimplifySurface -s -f 1000 cow.smf580410000.719
SimplifySurface -s -f 100 cow.smf58041000.781
SimplifySurface -s -f 16000 swirl.smf18050160001.032
SimplifySurface -s -f 12000 swirl.smf18050120001.407
SimplifySurface -s -f 8000 swirl.smf1805080001.860
SimplifySurface -s -f 4000 swirl.smf1805040002.203
SimplifySurface -s -f 1000 swirl.smf1805010002.469

Win32 Executables:


Sample Models and Files:

cow - SMF model of a cow cube - SMF model of a cube
stpeters - RAD model of St. Peter's Basilica (interior) dragon - SMF model of a dragon
globe - SMF model of the globe swirl - SMF model of a spiral on a curved surface
- Environment Map of St. Peter's Basilica
(Low dynamic range jpg)