Okino Computer Graphics primarily develops software for 3d data translation and for photo-realistic rendering. We developed this polygon reduction system as a built-in means to reduce the size of huge datasets down to something more reasonable (which is ideal for the import and optimization of large CAD datasets). It was added to the PolyTrans and NuGraf software as an important means to reduce polygon counts, such as to aid in the speeding up of rendering times for massive datasets.
In the end, we had spent several years implementing the system and refining it to produce very good results and with high compression. We typically see 80-95% reduction of models, using the geometric error method, with little or no degradation in model quality. In addition, the usage of the most modern "wedge" techniques allow for the usage of normals, u/v texture coordinates and vertex colors as 'constraints' on vertices and edges, to prevent degradation of 3D models where normals/textures/colors would otherwise be an important visual aspect of the model. The polygon reduction system is included in every copy of PolyTrans and NuGraf, and not an add-on or optional component as in other 3D conversion packages.
The basic core of the polygon reduction algorithm is based on the technique described by Michael Garland in his Ph.D. thesis,
Quadric-Based Polygonal Surface Simplification, available at
This technique uses what Garland calls quadric error metrics (QEM) and vertex pair contraction, which has been restricted to edge contraction in this application.
Edge contraction simply means that the two end vertices of a model edge are replaced by a single new vertex. This target vertex is usually somewhere in between the other two, in a place where it best approximates the original model. This edge contraction step removes a vertex and one, two, or more faces from the model, depending on the mesh neighborhood.
When this step is repeated several times, it results in a simpler model, which is an approximation to the original. Since any time data is removed from the original model the resulting model will only be an approximation; each of these steps is associated with a given increase in error. Garland uses quadric error matrices to estimate the error of each possible edge being contracted, and stores the edge contractions in a heap in order of increasing error (also called the cost of contraction). At each step the contraction with the lowest error (at the top of the heap) is performed, and the errors associated with the affected edges have to be recalculated. Then the lowest cost contraction is performed again until the desired target face count is reached. Simplification can also be stopped when the lowest error contraction is above a certain error threshold.