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, Quadric-Based 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.

1.0 Mesh concepts and data structures

The algorithm being described is concerned with polygonal simplification; therefore all familiar concepts of polygonal meshes apply. The models being simplified contain face and vertex lists, as well as face corner properties. The only restriction is that the meshes must be triangular, therefore any polygons with more vertices must be tessellated into triangles prior to simplification.

 

Input meshes can be manifold or non-manifold surfaces (see Figure 1. for examples), but the algorithm will not generate non-manifold structure in a previously manifold region during simplification. Triangular manifold surfaces have some nice properties. They tend to have an even tessellation on average, where a vertex is shared by 6 faces and 6 edges, and each edge is shared by two adjacent triangles. Since a triangle has three vertices, a closed manifold such as a sphere or torus will have twice as many faces as vertices. An open manifold surface has some edges that are not shared by two triangles, only one. Therefore, some vertices are shared by less than 6 triangles. Open manifolds with many edges will have less than twice as many faces as vertices; in fact they might even have more vertices than faces. Non-manifold surfaces might have somewhat more than twice as many faces as vertices. This information will be useful for understanding and debugging the input and output models, as closed manifold surfaces are the best candidates for simplification by the Okino Polygon Reducer. The table below shows typical relative vertex-to-face counts.

 

	Closed Manifold	Open Manifold	Non-Manifold
#vertices	x	x	x
#faces	~2x (~x for quads)	<2x	>2x

 

 

 

Figure 1: Manifoldness of different areas on a model

 

Because of the complex mesh operations that are necessary during simplification, there is additional connectivity information associated with faces and vertices. For example all face edges are stored in an array, and they are shared by adjacent faces. Each edge also has pointers to all of the faces it is a part of, and each vertex has pointers to all of the edges that use it. An edge is composed of two end vertices conceptually. In practice, however, they are implemented as two twin edges that point to each other. One has the first end vertex as its origin, while the other uses the second. The destination of one edge is the origin of its twin and vice versa. The reason for all these peculiarities in implementation are to ease and speed up certain mesh operations necessary during simplification, for example the finding of neighbors, easy elimination of faces, edges and vertices while maintaining mesh coherence, etc.

 

Another issue with mesh processing is the storage and processing of material properties, such as normals, texture coordinates, etc. To allow for proper flexibility in models that can be handled, material discontinuities at the vertex level must be accounted for. Storing all properties at every face corner would waste memory and make it harder to keep continuity intact. The solution was to adopt the wedge concept introduced by Hoppe.

 

A wedge is a structure that holds all surface properties at one point on the surface. To save memory, it only holds properties that are in use on the current model. In the interest of compactness, all property vectors are packed into one dynamically sized vector, and unpacked as needed. For example, if the mesh has normals and vertex colors, the property vector of each wedge will have 6 coordinates: the first three being the (x,y,z) values of the normal, while the remaining three would be the (r,g,b) values of the color. The property vector would look like so: (x, y, z, r, g, b). Therefore the property set of a wedge is a single multidimensional vector. Properties of a wedge are manipulated all at once.

 

Each face (triangle) points to three wedges, which contain the appropriate properties at the three corners. This implies that several faces can point to the same wedge if they have the same properties at the vertex they share (see Figure 2). This fact provides the space savings, since with most meshes, properties are mostly continuous across the surface, therefore all faces sharing a vertex will point to the same wedge, rather than replicating the data 6 times or more. Above that the flexibility is still there to handle discontinuities, in which case two or more different wedges will be created with the given properties, and each face points to the one that contains the exact set of properties of its corner.

 

 

Figure 2: Visualizing the wedge concept (image Copyright © 2001 Hugues Hoppe)

 

One drawback in this concept is that if even one of the properties is different between the faces, different wedges have to be created. So if all the faces around a vertex have the same normal but half of them are blue and the other half red, two wedges are needed, yet the normal data will be replicated. As an example, the property vectors might look like this: {(0,1,0),(1,0,0)} and {(0,1,0),(0,0,1)}, where the replication is obvious. There are other drawbacks associated with this concept that will become apparent in later parts of this report, but the advantages of memory savings, speed and ease of implementation make it the optimal solution. The two extremes of storing only one set of properties per vertex, or a separate set for every face corner are obviously deficient. An alternative would be to have separate pointers to each property at each face corner, but that would also be space inefficient (having to store a separate pointer for each property), slower, and harder to implement. The speed and ease of implementation of the wedge concept comes from the fact that all of the property vectors can be handled as one big vector – all operations affecting every property at once. There’s no need for trying to detect exactly which property is shared by which faces and processing them separately. This is especially useful if properties are calculated via quadrics, which will be explained below.

2.0 The Algorithm

The core of the PR algorithm is based on the technique described by Michael Garland in his Ph.D. thesis. 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 an edge, a vertex, and one, two, or more faces from the model, depending on the mesh neighborhood, as seen in Figure 3.

 

 

Figure 3: One, two, or more faces may be removed during a single edge contraction,

depending on the mesh neighborhood

 

When this contraction 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.

2.1 A Summary of Quadric Error Metrics

To better understand how contraction error is calculated, a summary of Michael Garland’s Quadric Error Metric idea is helpful. In essence the “quadric” name comes from the fact that squared distances are being calculated via quadric equations, which are noted as (A, b, c), where A is a matrix, b is a vector, and c is a scalar. The most useful quadric is the plane quadric. It can be defined by the plane equation of any face in the model. When any 3D point is plugged into the quadric equation, the minimum squared distance from the point to the plane is obtained. The equation is as follows:

 

Distance from point v to face plane f: Q^f(v) = vAv^t + 2b^tv + c

 

When plane quadrics are simply added up, the total distance from a point to all the planes can be obtained. Therefore the quadrics Q^fi obtained from all the faces sharing a vertex are added up, and the sum will be the vertex quadric Q^v. The distance of the model vertex to all of its quadric planes will be 0, since the vertex is a part of each plane; in fact it is at the intersection point of all face planes. Therefore Q^v1(v1) = 0 always. However, during contraction, the vertex v1 will be moved a certain distance from these planes to the target location v’ (unless the planes were all coplanar), hence the error of contraction. See Figure x for a visualization.

 

 

Figure 4: A 2D visualization of an edge contraction: a target vertex can not lie on

all face planes of the two original vertices at once

 

The target location v’ is at the minimum distance to all face planes of v1 and v2. This is obtained by adding up the face quadrics of both vertices to get Q = Q^v1+Q^v2, and minimizing the quadric equation Q:

 

The optimum vertex is: v’ = -A^-1b and its error is Q(v’).

 

The bulk of the runtime is used in inverting the matrix A and calculating Q(v’), and this is where optimization has to focus. These calculations have to be redone for all affected edges at each iteration (which comes out to about 6), not just for the one contraction being performed, because the errors of the new edges have to be updated and replaced in order in the contraction heap.

 

Even though the optimal distance to planes is an accurate notion of the way the algorithm chooses the order and target of contractions, Garland has an even more intuitive visualization of the concept. It is known that quadric equations can be graphed as three-dimensional isosurfaces, such as planes and ellipsoids. It turns out that graphing a plane quadric results in parallel planes with different error values, while adding several non-coplanar plane quadrics results in ellipsoidal isosurfaces. Figure 5 shows the conceptual shape of areas of equal error and the location of minimum error.

 

 

Figure 5: 2D crossectional visualization of typical quadrics

 

As mentioned above, the isosurfaces signify areas of equal error. What this means intuitively is that a point has more freedom of motion in the direction in which the quadric ellipsoid is widest. So if a given quadric is shaped as the one pictured above, the respective vertex has more freedom of motion side to side than upwards, without incurring too much error in the process. This translates directly to the visual fidelity of an approximation to the original model: the closer the target vertex is to all of the original face planes (by minimizing the distance function), the less the contraction will change the appearance of the overall model. Also, the contraction with the lowest error should obviously be done first, as it affects the appearance of the model the least. These are the main principles that the algorithm takes into consideration to guide its choices.

 

Figure 6a shows a 3D visualization of quadrics on a real world surface. It is visible that the quadrics in areas of low curvature, such as the side of the rabbit labeled “a”, are round and flat, allowing motion of those vertices in the approximate plane of the surface. Other areas that are longitudinally curved, such as areas of the ears labeled “b”, exhibit cigar shaped quadrics, which allow longitudinal freedom, but very little motion side to side. Other sharply curved areas, such as the chin of the rabbit labeled “c”, are constrained by tight spherical quadrics, so that these vertices stay more or less stationary, preserving the general shape of the model. Figure 5 b) shows a crossectional view of how quadrics are influenced by neighboring faces, and how the two quadrics at the ends of the edge being contracted contribute to the target vertex and its quadric. As mentioned above, the target quadric is the sum of the vertex quadrics of the edge endpoints, and the target vertex is calculated as the minimal point of this quadric.

 

 

Figure 6: 3D visualizations of error quadrics on a surface (Copyright © 2001 Michael Garland)

 

 

Figure 6a. 2D visualizations of error quadrics on a surface

 

In summary, quadric error metrics measure the curvature of the surface at specific points. They are used to gauge what areas of the mesh should be optimized, and which areas or vertices need to be left intact in order to preserve the general shape of the object. The quadric error metric also provides the optimal target vertex of any edge contraction. The reduction algorithm uses the values provided by the error quadrics to determine the order and targets of contractions. Below is a rough pseudocode outline of the algorithm as described above.

2.2 Summary of the algorithm in pseudocode

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

2.3 Handling Material Properties

Handling material properties is essential in Okino’s implementation of the Polygon Reducer, since most models that users in the entertainment business deal with are richly textured, while CAD users demand support for correct vertex normals. Michael Garland extended the QEM idea to encompass material properties along with geometry. Hugues Hoppe described a more efficient way of representing quadrics that encompass material properties, and he also introduced the wedge concept to ease the processing of meshes with properties, therefore his methods are implemented as an extension to Garland’s plain geometry reducer.

 

All property vectors are handled in exactly the same way as vertex vectors, since they are all three-dimensional in NuGraf; therefore normals will be used for illustration below.

The purpose of including properties in the quadric evaluation is firstly to have the control to trade off property accuracy versus geometrical accuracy in the approximated model, and secondly to obtain the correct property values at the target vertex of a contraction. It can be argued that in some instances a reduced model with accurate material properties can look more similar to the original model than one with the most optimal geometry but decreased property accuracy. Consider a long thin notch in a mostly planar surface. This is low amplitude detail that may be totally removed through reduction, since it has minor impact on the object’s overall shape. However, to the user, it may be an important visual feature. If normals are factored into the error quadric, this crease will be better preserved, since removing it would cause a large error in the normal field. The error would be high, and the quadrics would be tight, because the normal gradient in that area is large, in other words, the normals are changing fast. This applies to all other properties. Areas of sharp color gradient, like the edge of a shadow on a wall, would also be preserved, as the algorithm would leave more geometry there to preserve that detail.

 

A natural consequence of including properties in the error quadrics is that the properties of any target vertex can be calculated by minimizing the quadric equation, just like getting the position of the vertex itself. The resulting properties will correspond to the actual properties of the surface at the target vertex’s location.

 

Property discontinuities are handled through the “wedge” concept, as described earlier. Each wedge of a vertex pertains to a different set of surface properties; therefore they have to be described by individual property quadrics. It only makes sense for quadrics of like material regions to be interpolated, and unified into a target wedge quadric. Figure 7 illustrates the mechanics of the algorithm for different cases of material discontinuities. In this case color is the differentiating factor between the various material regions, while all other properties are continuous within these regions.

 

 

Figure 7: Illustrates how wedge quadrics are interpolated

and unified around material discontinuities

 

In the above diagram there are sharp material discontinuities along four edges, and these features need to be preserved. In fact, if the different colors signified different textures, it would make absolutely no sense to interpolate the properties of any but the like textured wedges. Therefore Q¹ and Q² are interpolated to obtain the unified wedge and quadric Q^1’, while Q⁴ and Q⁵ are interpolated to obtain Q^5’. These two operations are done at the same time by packing two wedges plus the geometry component into one larger quadric, and solving it. The wedge defined by Q³ is exceptional because it has no partner to interpolate with on the current contraction edge. For this reason, its property values can only be extrapolated by plugging the target vertex’s position into the Q³ equation and solving for the material properties that would exist at that point, based on the data present in Q³.

 

From the above demonstration it is evident that no material discontinuities will ever be removed from the model. This can be beneficial in most circumstances, as material discontinuities are generally determining factors in an object’s overall appearance and fidelity. For example, the boundary between a red and a blue region on a surface should be conserved. However, it may become a drawback on objects that have a lot of such discontinuities. This can happen if, for example, normals, texture coordinates, UV tangents, or a combination thereof, are not shared very nicely between faces. Every discontinuity results in splitting a wedge, and that can proliferate over the surface, causing a lot of duplication, which results in wasted storage and less than optimal simplification and interpolation of properties. These types of troublesome models can usually be improved by running a combination of the polygon processing routines already implemented in NuGraf.

2.4 Boundary Constraints

As stated above, discontinuity boundaries are determining factors in the appearance of an object, and the fidelity of an approximation, therefore they should be preserved. These can be surface boundaries (like the edge of a disc), color boundaries, normal discontinuity creases, etc. During simplification, the location of these discontinuities may get displaced, creating jagged boundaries in the place of straight ones. For this reason boundary constraints are introduced, to roughly lock the location of these discontinuities. A constraint is placed on any model edge that only has one polygon sharing it – a surface boundary, or an edge whose adjacent faces have different material properties – a material boundary. The weight of model and material property constraints is separately adjustable. A high weighting value will strongly restrict the vertices on a given boundary, while a lower weighting value will allow for more simplification at the expense of fidelity. The algorithm allows for three types of constraints: planar constraints, vertex constraints, and vertex locking.

 

A planar constraint effectively places a virtual plane on a polygon edge that is perpendicular to the neighboring surface. In QEM terms, summing this perpendicular plane into the quadrics of the given region tightens the isosurfaces, such that motion of vertices along the edge is allowed, while motion away from the edge is restricted. This way, boundaries remain in their original locations and don’t become jagged.

 

A vertex constraint simply restricts the motion of a vertex in every direction, also preserving boundaries. It can be used in instances when a given vertex may get too many plane constraints attached to it because of bad material property coherence (too many different wedges on the same vertex). Too many constraint planes can cause undesired artifacts after simplification, as they force the model out of shape, especially when using high weightings. A vertex constraint will restrict the vertex, but it won’t force it to move away from the original surface.

 

Vertex locking does exactly what its name implies, it absolutely locks any vertex that is on a boundary, such that it is never touched and displaced by edge contractions. This can be useful if a very large mesh is broken apart, simplified in pieces, then stitched together again. It avoids any visible seam whatsoever and can be vertex welded later. Edge constraints restrict seams too, but not perfectly, and the seams will not weld properly, since vertices will be at least longitudinally displaced from each other. Vertex locking on material boundaries is not as important, but may be desired in certain situations.

 

As mentioned above regarding wedge splitting, objects with too many discontinuities can be very troublesome to simplify. If even after various polygon-processing routines the mesh becomes littered with constraints, it will not be simplified optimally, and it may even be deformed by the virtual constraints. If excessive deformation is observed, the constraint weighting values should be decreased, until an optimal tradeoff is obtained between geometric and material fidelity. High boundary constraint weights and vertex locking also work against high object simplification, as too much detail is concentrated at boundaries, while leaving few polygons to represent the continuous areas. Understanding the implications of the different constraints and weightings is very useful in tweaking and optimizing the appearance of the simplified object along with the actual simplification percentage. It is largely a trial and error procedure, but it is learned intuitively with practice.