Abstract

1
Introduction
Many computer graphics applications require complex, highly de- tailed models to maintain a convincing level of realism.  Conse- quently, models are often created or acquired at a very high reso- lution to accommodate this need for detail. However, the full com- plexity of such models is not always required, and since the compu- tational cost of using a model is directly related to its complexity, it is useful to have simpler versions of complex models. Naturally, we would like to automatically produce these simplified models.  Re- cent work on surface simplification algorithms has focused on this goal. As with most other work in this area, we will focus on the simpli- fication of polygonal models. We will assume that the model con- sists of triangles only. This implies no loss of generality, since every polygon in the original model can be triangulated as part of a pre- processing phase. To achieve more reliable results, when corners of two faces intersect at a point, the faces should be defined as sharing a single vertex rather than using two separate vertices which happen to be coincident in space. We have developed an algorithm which produces simplified ver- sions of such polygonal models. Our algorithm is based on the iter- ative contraction of vertex pairs (a generalization of edge contrac- tion). As the algorithm proceeds, a geometric error approximation is maintained at each vertex of the current model.  This error approx- imation is represented using quadric matrices. The primary advan- tages of our algorithm are: ● Efficiency: The algorithm is able to simplify complex models quite rapidly.  For example, our implementation can create a 100 face approximation of a 70,000 face model in 15 seconds. The error approximation is also very compact, requiring only 10 floating point numbers per vertex. ● Quality:  The approximations produced by our algorithm maintain high fidelity to the original model. The primary fea- tures of the model are preserved even after significant simpli- fication. ● Generality: Unlike most other surface simplification algo- rithms, ours is able to join unconnected regions of the model together, a process which we term aggregation. Provided that maintaining object topology is not an important concern, this can facilitate better approximations of models with many dis- connected components.  This also requires our algorithm to support non-manifold 1 models. 2
Background and Related Work
The goal of polygonal surface simplification is to take a polygonal model as input and generate a simplified model (i.e., an approxima- tion of the original) as output.  We assume that the input model ( M n ) has been triangulated.  The target approximation ( M g ) will satisfy some given target criterion which is typically either a desired face count or a maximum tolerable error.  We are interested in surface simplification algorithms that can be used in rendering systems for multiresolution modeling — the generation of models with appro- priate levels of detail for the current context. We do not assume that the topology of the model must be main- tained. In certain application areas, medical imaging for example, maintaining the object topology can be essential. However, in appli- cation areas such as rendering, topology is less important than over- all appearance.  Our algorithm is capable of both closing topological holes as well as joining unconnected regions. Many prior simplification algorithms have either implicitly or ex- plicitly assumed that their input surfaces were, and ought to remain, manifold surfaces.  Let us stress that we do not make this assump- tion. In fact, the process of aggregation will regularly create non- manifold regions.
2.1
Surface Simplification
In recent years, the problem of surface simplification, and the more general problem of multiresolution modeling, has received increas- ing attention. Several different algorithms have been formulated for simplifying surfaces. Those algorithms which are most relevant to our work can be broadly categorized into 3 classes: Vertex Decimation.   Schroeder et al. [9] describe an algorithm which we would term vertex decimation. Their method iteratively selects a vertex for removal, removes all adjacent faces, and retri- angulates the resulting hole. Soucy and Laurendeau [10] described a more sophisticated, but essentially similar algorithm. While they provide reasonable efficiency and quality, these methods are not re- ally suited for our purpose.  Both methods use vertex classification and retriangulation schemes which are inherently limited to mani- fold surfaces, and they carefully maintain the topology of the model. While these are important features in some domains, they are restric- tions for multiresolution rendering systems. Vertex Clustering.   The algorithm described by Rossignac and Borrel [8] is one of the few capable of processing arbitrary polygo- nal input. A bounding box is placed around the original model and divided into a grid. Within each cell, the cell's vertices are clustered together into a single vertex, and the model faces are updated ac- cordingly.  This process can be very fast, and can make drastic topo- logical alterations to the model. However, while the size of the grid cells does provide a geometric error bound, the quality of the out- put is often quite low. In addition, it is difficult to construct an ap- proximation with a specific face count, since the number of faces is only indirectly determined by the specified grid dimensions. The exact approximation produced is also dependent on the exact posi- tion and orientation of the original model with respect to the sur- rounding grid.  This uniform method can easily be generalized to use an adaptive grid structure, such as an octree [6]. This can improve the simplification results, but it still does not support the quality and control that we desire. Iterative Edge Contraction.  Several algorithms have been published that simplify models by iteratively contracting edges (see Figure 1). The essential difference between these algorithms lies in how they choose an edge to contract.  Some notable examples of such algorithms are those of Hoppe [4, 3], Ronfard and Rossignac [7], and Guéziec [2]. These algorithms all seem to have been de- signed for use on manifold surfaces, although edge contractions can be utilized on non-manifold surfaces.  By performing successive edge contractions, they can close holes in the object but they can- not join unconnected regions. If it is critical that the approximate model lie within some dis- tance of the original model and that its topology remain unchanged, the simplification envelopes technique of Cohen et al. [1] can be used in conjunction with one of the above simplification algorithms. As long as any modification made to the model is restricted to lie within the envelopes, a global error guarantee can be maintained. However, while this provides strong error limits, the method is in- herently limited to orientable manifold surfaces and carefully pre- serves model topology.  Again, these are often limitations for the purposes of simplification for rendering. None of these previously developed algorithms provide the com- bination of efficiency, quality, and generality that we desire. Vertex decimation algorithms are unsuitable for our needs; they are careful to maintain model topology and usually assume manifold geometry. Vertex clustering algorithms are very general and can be very fast. However, they provide poor control over their results and these re- sults can be of rather low quality. Edge contraction algorithms can not support aggregation. We have developed an algorithm which supports both aggrega- tion and high quality approximations. It possesses much of the gen- erality of vertex clustering as well as the quality and control of itera- tive contraction algorithms. It also allows faster simplification than some higher quality methods [3].
3
Decimation via Pair Contraction
Our simplification algorithm is based on the iterative contraction of vertex pairs; a generalization of the iterative edge contraction tech- nique used in previous work. A pair contraction , which we will write (V1, V2) → V, moves the vertices V1 and V2 to the new posi- tion v, connects all their incident edges to v 1 , and deletes the vertex v 2 . Subsequently, any edges or faces which have become degenerate are removed. The effect of a contraction is small and highly local- ized. If (V 1 , V 2 ) is an edge, then 1 or more faces will be removed (see Figure 1). Otherwise, two previously separate sections of the model will be joined at v (see Figure 2). This notion of contraction is in fact quite general; we can con- tract a set of vertices into a single vertex:  (V 1 , V 2 , . . . , V k ) → V. This form of generalized contraction can express both pair contractions as well as more general operations such as vertex clustering. How- ever, we use pair contraction as the atomic operation of our algo- rithm because it is the most fine-grained contraction operation. Starting with the initial model M n , a sequence of pair contractions is applied until the simplification goals are satisfied and a final ap- proximation M g is produced. Because each contraction corresponds to a local incremental modification of the current model, the algo- rithm actually generates a sequence of models M n , M n –1, . . . , M g . Thus, a single run can produce a large number of approximate mod- els or a multiresolution representation such as a progressive mesh [3].
Aggregation
3.1
The primary benefit which we gain by utilizing general vertex pair contractions is the ability of the algorithm to join previously uncon- nected regions of the model together. A potential side benefit is that it makes the algorithm less sensitive to the mesh connectivity of the original model.  If in fact two faces meet at a vertex which is dupli- cated, the contraction of that pair of vertices will repair this short- coming of the initial mesh. Figure 3: On the left is a regular grid of 100 closely spaced cubes. In the middle, an approximation built using only edge contractions demonstrates unacceptable fragmentation.  On the right, the result of using more general pair contractions to achieve aggregation is an approximation much closer to the original. In some applications, such as rendering, topology may be less im- portant than overall shape. Consider a shape such as that shown in Figure 3 which is made up of 100 closely spaced cubes in a regu- lar grid. Suppose we wanted to construct an approximation of the model on the left for rendering at a distance.  Algorithms based on edge contraction can close holes in objects, but they can never join disconnected components.  In an algorithm using only edge con- traction, the individual components are individually simplified into nothing, as in the model in the middle. Using pair contraction, the individual components can be merged into a single object, as in the model on the right. The result is a much more faithful approxima- tion. Allowing aggregation also requires us to support non-manifold surfaces.  At the instant when two separate regions are joined, a non- manifold region is quite likely to be created. It would require a great deal of care and effort to ensure that a contraction never created a non-manifold region without severely limiting the kinds of contrac- tions that we could perform.
3.2   Pair Selection
We have chosen to select the set of valid pairs at initialization time, and to consider only these pairs during the course of the algorithm. Our decision is based on the assumption that, in a good approxima- tion, points do not move far from their original positions. We will say that a pair (v 1 , v 2 ) is a valid pair for contraction if either: l. (Vi, V2) is an edge, or 2.  ||V1 − V2|| < t , where t is a threshold parameter Using a threshold of t = 0 gives a simple edge contraction algo- rithm. Higher thresholds allow non-connected vertices to be paired. Naturally, this threshold must be chosen with some care; if it is too high, widely separated portions of the model could be connected, which is presumably undesirable, and it could create O(n2) pairs. We must track the set of valid pairs during the course of iterative contraction. With each vertex, we associate the set of pairs of which it is a member.  When we perform the contraction (v 1 , v 2 ) → v , not only does V 1 acquire all the edges that were linked to V 2 , it also merges the set of pairs from v 2 into its own set. Every occurrence of v 2 in a valid pair is replaced by v 1 , and duplicate pairs are removed.
4
Approximating Error With Quadrics
In order to select a contraction to perform during a given iteration, we need some notion of the cost of a contraction.  To define this cost, we attempt to characterize the error at each vertex. To do this, we associate a symmetric 4×4 matrix Q with each vertex, and we define the error at vertex v = [ v x v x 1] T to be the quadratic form ∆(v) = v T Q v. In Section 5, we will describe how the initial matrices are constructed. Note that the level surface ∆(v) = ϵ , which is the set of all points whose error with respect to Q is ε , is a quadric surface. For a given contraction (v 1 , v 2 ) → v , we must derive a new ma- trix Q which approximates the error at v. We have chosen to use the simple additive rule Q = Q 1 + Q 2 . In order to perform the contraction (v 1 , v 2 ) → V, we must also choose a position for V. A simple scheme would be to select either V 1 , V 2 , or (V 1 + V 2 )/2 depending on which one of these produces the lowest value of A(¥). However, it would be nice to find a po- sition for v which minimizes Δ(¥).  Since the error function Δ is quadratic, finding its minimum is a linear problem. Thus, we find ν by solving ∂Δ /∂x = ∂Δ /∂y = ∂Δ /∂z = 0. This is equivalent² to solving:
for v. The bottom row of the matrix is empty because v is an homo- geneous vector — its w component is always 1. Assuming that this matrix is invertible, we get that
If this matrix is not invertible, we attempt to find the optimal vertex along the segment V 1 V 2 . If this also fails, we fall back on choosing V from amongst the endpoints and the midpoint.
4.1
Algorithm Summary
Our simplification algorithm is built around pair contractions and error quadrics. The current implementation represents models us- ing an adjacency graph structure: vertices, edges, and faces are all explicitly represented and linked together. To track the set of valid pairs, each vertex maintains a list of the pairs of which it is a mem- ber. The algorithm itself can be quickly summarized as follows: 1. Compute the Q matrices for all the initial vertices. 2. Select all valid pairs. 3. Compute the optimal contraction target v for each valid pair (V 1 , V 2 ).  The error V 1 (Q 1 + Q 2 )V of this target vertex becomes the cost of contracting that pair. 4. Place all the pairs in a heap keyed on cost with the minimum cost pair at the top. 5. Iteratively remove the pair ( V 1 , V 2 ) of least cost from the heap, contract this pair, and update the costs of all valid pairs involv- ing V1. The only remaining issue is how to compute the initial Q matrices from which the error metric △ is constructed. 2 You can verify this for yourself by taking partial derivatives of
+ 2q23yz + 2q24y + q33z2 + 2q34z + q44 Figure 4: A sequence of approximations generated using our algorithm. The original model on the left has 5,804 faces. The approximations to the right have 994, 532, 248, and 64 faces respectively. Note that features such as horns and hooves continue to exist through many simpli- fications. Only at extremely low levels of detail do they begin to disappear.
5
Deriving Error Quadrics
To construct our error quadrics, we must choose a heuristic to char- acterize the geometric error. We have selected a heuristic which is quite similar to the one given by Ronfard and Rossignac [7]. Fol- lowing [7], we can observe that in the original model, each vertex is the solution of the intersection of a set of planes — namely, the planes of the triangles that meet at that vertex. We can associate a set of planes with each vertex, and we can define the error of the vertex with respect to this set as the sum of squared distances to its planes:
where p = [ a b c d ] T represents the plane defined by the equation ax + by + cz + d = 0 where a 2 + b 2 + c 2 = 1. This approximate error metric is similar to [7], although we have used a summation rather than a maximum over the set of planes. The set of planes at a vertex is initialized to be the planes of the triangles that meet at that vertex.  Note that if we were to track these plane sets explicitly, as [7] did, we would propagate planes after a contraction (V 1 , V 2 ) → V us- ing the rule:  planes( ī ) = planes( V 1 ) U planes( V 2 ). This can require a sizeable amount of storage that does not diminish as simplification progresses. The error metric given in (2) can be rewritten as a quadratic form: where K p is the matrix:
This fundamental error quadric K p can be used to find the squared distance of any point in space to the plane p. We can sum these fun- damental quadrics together and represent an entire set of planes by a single matrix Q. We implicitly track sets of planes using a single matrix; instead of computing a set union (planes( V i ) U planes( V 2 )) we simply add two quadrics (Q1 + Q2).  If the sets represented by Q1 and Q2 in the original metric are disjoint, the quadric addition is equivalent to the set union.  If there is some overlap, then a single plane may be counted multiple times. However, any single plane can be counted at most 3 times since each plane is initially distributed only to the vertices of its defining triangle. This may introduce some impreci- sion into the error measurement, but it has major benefits: the space required to track a plane set is only that required for a 4 × 4 symmet- ric matrix (10 floating point numbers), and the cost of updating the approximation is only that for adding two such matrices. If we are willing to sacrifice some additional storage, it would even be possi- ble to eliminate this multiple counting using an inclusion-exclusion formula. Thus, to compute the initial Q matrices required for our pair con- traction algorithm, each vertex must accumulate the planes for the triangles which meet at that vertex.  For each vertex, this set of planes defines several fundamental error quadrics K p . The error quadric Ω for this vertex is the sum of the fundamental quadrics. Note that the initial error estimate for each vertex is 0, since each vertex lies in the planes of all its incident triangles.
5.1
Geometric Interpretation
As we will see, our plane-based error quadrics produce fairly high quality approximations. In addition, they also possess a useful geo- metric meaning 3 . The level surfaces of these quadrics are almost always ellipsoids. In some circumstances, the level surfaces may be degenerate. For instance, parallel planes (e.g., around a planar surface region) will produce level surfaces which are two parallel planes, and planes which are all parallel to a line (e.g., around a linear surface crease) will produce cylindrical level surfaces. The matrix used for find- ing optimal vertex positions (Eq. 1) will be invertible as long as the level surfaces are non-degenerate ellipsoids. In this case, v will be at the center of the ellipsoid.
Additional Details
6
The general algorithm outlined so far performs well on most mod- els. However, there are a few important enhancements which im- prove its performance on certain types of models, particularly planar models with open boundaries. Preserving Boundaries. The error quadrics derived earlier do not make any allowance for open boundaries.  For models such as terrain height fields, it is necessary to preserve boundary curves while simplifying their shape. We might also wish to preserve dis- crete color discontinuities.  In such cases, we initially label each edge as either normal or as a "discontinuity".  For each face sur- rounding a particular discontinuity edge, we generate a perpendic- ular plane running through the edge.  These constraint planes are then converted into quadrics, weighted by a large penalty factor, and
added into the initial quadrics for the endpoints of the edge.  We have found that this works quite well. Preventing Mesh Inversion.   Pair contractions do not neces- sarily preserve the orientation of the faces in the area of the contrac- tion. For instance, it is possible to contract an edge and cause some neighboring faces to fold over on each other. It is usually best to try to avoid this type of mesh inversion. We use essentially the same scheme as others have before ([7] for example).  When considering a possible contraction, we compare the normal of each neighboring face before and after the contraction. If the normal flips, that con- traction can be either heavily penalized or disallowed.
Evaluating Approximations
6.1
In order to evaluate the quality of approximations produced by our algorithm, we need an error measurement which is a bit more rig- orous than the heuristic error measurement employed by the algo- rithm itself. We have chosen a metric which measures the average squared distance between the approximation and the original model. This is very similar to the E dist energy term used by Hoppe et al. [4]. We define the approximation error E i = E ( M n , M i ) of the simplified model M j as: where X n and X i are sets of points sampled on the models M n and M i respectively. The distance d(v, M) = min ρε M ‖ ν − p ‖ is the mini- mum distance from ν to the closest face of M (|| · || is the usual Eu- clidean vector length operator). We use this metric for evaluation purposes only; it plays no part in the actual algorithm.
Results
7
Our algorithm can produce high fidelity approximations in fairly short amounts of time. Figure 5 summarizes the running time 4 of our current implementation using the models shown in this paper. Figure 4 shows a sample sequence of approximations generated by our algorithm.  This entire sequence of cows was constructed in about a second. Notice that features such as horns and hooves re- main recognizable through many simplifications. Only at extremely low levels of detail do they begin to disappear. As described earlier, our algorithm attempts to optimize the placement of vertices after contractions.  Figure 6 summarizes the effect of this policy on approximations for a representative model (the cow model of Fig.  4).  At extremely low levels of detail, the
effect is modest. However, at more reasonable levels of detail the effect is substantial; optimal vertex placement can reduce the over- all error by as much as 50%.  In our experiments, we have also found that using optimal vertex placement tends to produce more well- shaped meshes. Figures 8–13 demonstrate the performance of our algorithm on much larger models.  Figure 9 represents a significant simplifica- tion (1.4%) of the original, but notice that all the major details of the original remain. In particular, notice that the contours on the in- terior of the ear and the large contours around the rear leg have been preserved. Figure 10 presents an even more drastic approximation: 100 faces or 0.14% of the original size. While most of the detail of the model has disappeared, the basic structure of the object is still intact; the major features such as the head, legs, tail, and ears are all apparent, albeit highly simplified. Figure 12 shows a very densely tessellated terrain model, and Figure 13 shows a highly simplified version. While the small scale texture of the terrain has largely dis- appeared, all the basic features of the terrain remain. Also note that the open boundary has been properly preserved.  Without the bound- ary constraints described earlier, the boundary would have been sig- nificantly eroded. Figure 11 illustrates the nature of the error quadrics accumulated during simplification. The level surface v T Ω v = ε is shown for each vertex. Each level surface is an ellipsoid centered around the corre- sponding vertex. The interpretation of these ellipsoids is that a ver- tex can be moved anywhere within its ellipsoid and have an error less than ε . The significant feature of the ellipsoids is that they con- form to the shape of the model surface very nicely. They are large and flat on mostly planar areas such as the middle of the hind leg, and they are elongated along discontinuity lines such as the contours through the ear and along the bottom of the leg.  In some sense, these ellipsoids can be thought of as accumulating information about the shape of the local surface around their vertex. Figures 14–17 demonstrate the real benefits which aggregation via pair contractions can provide. The original model consists of the bones of a human's left foot.  There are many separate bone segments, some of which even interpenetrate (obviously an error in model reconstruction). Three approximations are compared: one built by uniform vertex clustering, one built with edge contractions alone, and one built with pair contractions.  When edge contractions alone are used, the small segments at the ends of the toes collapse into single points; this creates the impression that the toes are slowly receding back into the foot. On the other hand, using the more gen- eral pair contractions allows separate bone segments to be merged. As you can see in Figure 17, the toes are being merged into single long segments. Figure 19 shows some of the pairs initially selected as valid. Notice how they span the gaps between bone segments. Finally, Figure 18 shows another illustration of the level surfaces of the error quadrics accumulated during simplification (this is the model seen in Figure 16). The benefits of aggregation are not solely visual.  Aggregation can also produce objectively lower approximation error.  Figure 7 shows the error E 250 for 250 face approximations of the foot model using various values of t . A fairly wide range of values all produce objectively better approximations than are achieved by the edge contraction only approximation ( t = 0). Notice, however, that in- creasing t does not always improve the approximation. This is due to the nature of our quadric error metric. Locally, the distance to a set of planes is a reasonable approximation of the distance to a set of faces. However, because planes have infinite extent and faces do not, the error metric becomes less reliable as we move farther away.
8
Discussion
Our algorithm provides a mix of efficiency, quality, and generality not found in earlier algorithms. While certain other algorithms are faster or generate higher quality approximations than ours, they typ- ically do not meet the capability of our algorithm in all three areas. The only algorithm capable of simplifying arbitrary polygonal mod- els, vertex clustering [8], does not reliably produce high quality ap- proximations. None of the higher quality methods available [2, 7, 3] support aggregation.  Both [2] and [3] seem to be significantly more time consuming than our algorithm.  The results of [7] are most sim- ilar to our own because we use a very similar error approximation. However, our system uses a more efficient means to track plane sets, and it incorporates some enhancements such as boundary preserva- tion. There remain various aspects of our algorithm that could be im- proved upon.  We have used a fairly simple scheme for selecting valid pairs.  It is quite possible that a more sophisticated adaptive scheme could produce better results. We have not addressed the is- sue of surface properties such as color. One possible solution is to treat each vertex as a vector (x, y, z, r, g, b), construct 7×7 quadrics, and simplify. We believe this could work well, but the added size and complexity make it less attractive than the basic algorithm. Although it generally performs well, our algorithm has a couple of clear weaknesses. First, as mentioned earlier, measuring error as a distance to a set of planes only works well in a suitably local neigh- borhood.  Second, the information accumulated in the quadrics is es- sentially implicit, which can at times be problematic.  Suppose we join together two cubes and would like to remove the planes associ- ated with the now defunct interior faces. Not only is it, in general, difficult to determine what faces are defunct, there is no clear way to reliably remove the appropriate planes from the quadrics. As a re- sult, our algorithm does not do as good a job at simplification with aggregation as we would like. 9
Conclusion
We have described a surface simplification algorithm which is capa- ble of rapidly producing high fidelity approximations of polygonal models. Our algorithm uses iterative pair contractions to simplify models and quadric error metrics to track the approximate error of the model as it is being simplified. The quadrics stored with the fi- nal vertices can also be used to characterize the overall shape of the surface. Our algorithm has the ability to join unconnected sections of models while still maintaining fairly high quality results.  While most previous algorithms are also inherently limited to manifold surfaces, our system is quite capable of handling and simplifying non-manifold objects. Finally, our algorithm provides a useful mid- dle ground between very fast, low-quality methods such as vertex clustering [8] and very slow, high-quality methods such as mesh op- timization [3].