You are here: Home » Specialized Sections » Polygon Reduction 

The Okino Polygon Reduction Algorithm, A Technical White Paper
The following is a discussion of the polygon reduction technique implemented by Okino and originated by Michael Garland, as documented in his Ph.D. thesis, QuadricBased Polygonal Surface Simplification, available at http://graphics.cs.uiuc.edu/~garland/research/thesis.html The following technical white paper was written by the Okino software developer of the polygon reduction algorithm.
Loading Copy generic mesh structure to the algorithm’s internal structures, detecting connectivity Initialization For each face in the model Calculate the face (plane) quadric Add face quadric to each vertex’s quadric For each edge in the model If this edge is a mesh edge Add a constraint quadric to the vertices of this edge If there is a property discontinuity at either vertex or the adjacent faces have a different material pointer Add a constraint quadric to the vertices of this edge Gather up all the edges of the model Calculate the target and cost of all edge contractions, store them in increasing order on the heap Simplification While the target face number is not reached or the error of the lowest error contraction is below the cutoff error value Get the lowest cost contraction off the top of the heap Contract endpoints of edge to the already calculated target Make sure dead faces, edges and vertices are killed properly Make sure the neighborhood of the contraction maintains connectivity Recalculate the contraction targets and errors of all the edges that have been affected by the current contraction, i.e.: all edges that were previously connected to one of the endpoints of the edge that has just been contracted Output Copy internal data to generic output mesh
