Abstract A Topology Modifying Progressive Decimation Algorithm

William J. SchroederGE Corporate R&D Center

Abstract

Triangle decimation techniques reduce the number of trian-gles in a mesh, typically to improve interactive renderingperformance or reduce data storage and transmission

requirements. Most of these algorithms are designed to pre-serve the original topology of the mesh. Unfortunately, thischaracteristic is a strong limiting factor in overall reductioncapability, since objects with a large number of holes orother topological constraints cannot be effectively reduced.In this paper we present an algorithm that yields a guaran-teed reduction level, modifying topology as necessary toachieve the desired result. In addition, the algorithm isbased on a fast local decimation technique, and its opera-tions can be encoded for progressive storage, transmission,and reconstruction. In this paper we describe the new pro-gressive decimation algorithm, introduce mesh splittingoperations and show how they can be encoded as a progres-sive mesh. We also demonstrate the utility of the algorithmon models ranging in size from 1,132 to 1.68 million trian-gles and reduction ratios of up to 200:1.

1Introduction

Even with the increasing speeds of computer hardware,interactive computer graphics and animation remains anelusive goal. Model size keeps growing, partly because ofadvances in data acquisition, and partly due to ever moresophisticated computer simulation and modeling tech-niques. Laser digitizers can generate nearly one millionpolygons in a 30 second span, while iso-surface generationcan create 1-10 million polygons. Terrain models fromhigh-altitude sources such as satellites are even larger: morethan 10 million triangles is not uncommon.

To address this situation a variety of polygon reductiontechniques have been developed to reduce model size. Sig-graph ‘92 was a seminal year for polygon reduction withthe presentation of two papers. Schroeder et al. [1] pre-sented an algorithm called triangle decimation based onlocal vertex deletion followed by re-triangulation. Turk [2]described an algorithm based on dispersion of new pointson top of the original mesh, followed by global re-triangula-tion. At Siggraph ‘93 Hoppe et al [3] presented a mathemat-ically rigorous algorithm based on optimization techniques.Later that year Hincker and Hanson [4] described an algo-rithm based on merging regions of nearly co-planar poly-gons into a single large polygon, and then re-triangulating.Since that time other notable algorithms have been pre-sented including methods that are guaranteed accuratewithin a global error bounds [11] or within a simplificationenvelope [8].

All of the algorithms described above are designed topreserve the original topology of the mesh. While this maybe important for many applications (e.g., analysis or com-putational geometry), preserving topology introduces con-straints into the reduction process. For example,

ColorPlate1(a) shows a shell mesh with seven holes, andPlate1(b) shows the result of reduction where topology ispreserved. As shown in the figure, the topological con-straint introduced by the holes clearly limits the ability ofan algorithm to reduce the mesh.

In many applications, such as interactive navigation ofgeometric databases, preserving topology is not a criticalconstraint. Reduction algorithms are typically used toimprove rendering speed or to minimize data size or com-pression requirements. In such applications topology-pre-serving reduction schemes are often incapable of achievingdesired reduction levels. This results in unresponsive sys-tems or the use of crude bounding boxes or bounding hullsto represent objects. Removing topological constraint cancreate large gains in reduction factors and therefore, systemresponsiveness and interactivity.

Another important development in the field of polygonreduction is the progressive mesh [7] introduced by Hoppe.A progressive mesh is one in which the original mesh canbe decomposed into a simpler base mesh, where the basemesh is related to the original via a compact series of oper-ations. In Hoppe’s scheme, the single topology preservingoperationEdgeCollapse (and its inverseEdgeSplit) is suffi-cient to transform the full resolution mesh into a simplerbase mesh (and the base mesh back to the full resolutionmesh). Progressive meshes offer many attractive properties,including the ability to compactly store and incrementallytransmit and reconstruct geometry. Such capability isimportant for network based rendering and data transmis-sion.

In this paper we present a new algorithm that can modifythe topology of a mesh in order to guarantee a requestedreduction level. Moreover, the algorithm creates progres-sive representations by extending the pair of operationsEdge Collapse/Split with another pair of operators:VertexSplit/Merge. The algorithm is fast by virtue of a local deci-mation scheme similar to [1]. We begin by describingrelated background work, and then describe the algorithmfrom a high level, followed by a detailed look at each of itsparts. We conclude by applying the algorithm to five datasets and report times to reduce the meshes at various levelsof reduction.

2Objectives

The motivation for this work is to support interactive visu-

alization of large geometric databases. These databases typ-ically represent the design of industrial equipment such asaircraft engines or power generation equipment. Our

approach is based on building level-of-detail (LOD) modelsfor each part, ranging in complexity from full resolution toa bounding hull consisting of dozens of triangles. The sizeof our databases for a complete system may reach 100 mil-lion triangles and 25,000 separate parts, while an averagedatabase size is approximately 10 million triangles and10,000 parts. Also, in an active design environment it iscommon to have a dozen or more variations of the samedesign, or multiple designs ongoing simultaneously. Withthis application in mind, we formulated the followingobjectives for our reduction algorithm:

•Guaranteed reduction level: Building a LOD databaserequires generating meshes of the correct complexityrelative to every other level. In an automatic processwith thousands of parts, only using an algorithm with aguaranteed reduction level will reliably construct a con-sistent database.

•Modify topology: Arbitrary reduction levels implies theneed to modify topology. For example, to reduce a flat,square plate with a single hole that is represented by1000 polygons to two triangles forming a square with nohole requires the elimination of the hole.

•Progressive representation: The decimation processmust be encodable into a series of compact, incrementaloperations. This facilitates the transmission of the meshacross a network, and minimizes disk storage.

•Fast: We wish to construct an entire LOD database in asingle day, or rapidly process parts as they are designedand submitted to the database. From our statistics citedpreviously, this requires a triangle processing rate ofapproximately 100 million triangles per day. At this ratewe feel confident that we can manage a business-widedesign process.

•Robust: Since the LOD database is built completelyautomatically, the algorithm must run without humanintervention or error correction.

3Background

In this section we briefly describe some related work thatforms the basis of our progressive decimation algorithm.

3.1Topology Modifying Algorithms

We began our work by investigating two important polygonreduction algorithms that modify topology. Rossignac [9]uses a vertex merge technique, where local vertices can beidentified using an octree or 3D bin array. Vertices lyingclose to each other are merged into a single vertex, and thetopology of the affected triangles are then updated. Thismay consist of either triangle deletion (if two or three of thevertices are merged), or updating the connectivity list of thetriangle. He et al. [10] use a volume sampling approach,where the triangles are convolved into a volume to generatescalar values (e.g., scalar value may be distance from origi-

Classify

Simple

ComplexBoundaryInteriorEdgeCorner

Evaluate

Distance to planeDistance to line

ddTriangulateRecursive 3DSubdivide withtriangulationsplit planesFigure 1.Overview of the decimation algorithm.

nal mesh). Then an iso-surfacing technique such as marchingcubes can be used to extract a surface approximating theoriginal mesh.

Rossignac’s method is capable of generating representa-tions at any reduction level. Unfortunately, it is not amenableto a compact progressive operator. For example, if mergingneighboring vertices eliminates 1000 triangles, we need tokeep track of each triangle modified and its relationship tothe merged vertices, and do this for each merging step of thealgorithm. Another problem with this method is that pointscan be merged regardless of surface coherence. For example.points that lie close to one another (measured via Euclideandistance) but are far apart (via surface distance) or even onseparate surfaces may be merged.

The volume sampling technique can generate representa-tions at almost any level by judicious selection of the sam-pling (or volume) dimensions. Unfortunately, it is notpossible to recover the original mesh using this technique,since the extracted iso-surface has no direct relation to trian-gles in the original mesh. Also, there is no method to controlthe number of triangles produced by the method, and thenumber of triangles may vary unpredictably as the volumedimensions are changed.

3.2Decimation

The decimation algorithm has been widely used because ofits combination of desirable features:O(n) time complexity,speed, simplicity, and the ability to treat large meshes. Inaddition, it preserves high-frequency information such assharp edges and corners, and creates reduced meshes whosevertices are a subset of the original vertex set, thereby elimi-nating the need to map vertex information. However, as orig-inally presented the decimation algorithm is topology

preserving and provides no progressive mesh representation.The decimation algorithm proceeds by iteratively visitingeach vertex in the triangle mesh. For each vertex, three basicsteps are carried out. The first step classifies the local geome-try and topology in the neighborhood of the vertex. The clas-

sification yields one of the five categories shown inFigure1:simple,boundary,complex,edge, andcornervertex. Based on this classification, in the second step alocal planarity measure is used to determine whether thevertex can be deleted. Although many different criterionare possible, distance to plane (for simple vertices) anddistance to line (for edge and boundary vertices) hasproven to be useful. If this decimation criterion is satis-fied, in the third step the vertex is deleted (along withassociated triangles), and the resulting hole is triangu-lated. The triangulation process is designed to capturesharp edges (for vertices classifiededge andcorner) andgenerally preserve the original surface geometry. (See [1]for additional details.)

An attractive feature of the decimation algorithm is itsrelative speed. We used the decimation algorithm as thebasis on which to build our progressive algorithm.

3.3Progressive Meshes

A progressive mesh is a series of triangle meshesMi=Mi

(V,K) related by the operations

(M

ˆ=Mn

)→Mn–1

→…→M1→M

0

(1)

whereˆ andnandM0

MM represent the mesh at full resolution, is a simplified base mesh. Here the mesh is

defined in terms of its geometryV, or vertex set inR3

,andK is the mesh topology specifying the connectivity of themesh triangles.

It is possible to choose the progressive mesh operationsin such a way to make them invertible. Then the opera-tions can be played back (starting with the base meshM0

)

M0

→M1

→…→M

n–1

→M

n

(2)

to obtain a mesh of desired reduction level (assuming that

the reduction level isless than the base meshM0

).

Hoppe’s invertible operator is an edge collapse and itsinverse is the edge split (Edge Collapse/Split) shown inFigure5(a). Each collapse of an interior mesh edge resultsin the elimination of two triangles (or one triangle if thecollapsed vertex is on a boundary). The operation is repre-sented by five values

Edge Collapse/Split (vs,vt,vl,vr,A)

wherevsis the vertex to collapse/split,vbeing collapsed to / split from, andv andt is the vertexlvr are two addi-tional vertices to the left and right of the split edge. Thesetwo vertices in conjunction withvtriangles deleted or added. In Hoppe’s presentation,s andvt define the twoArepresents vertex attribute information, which at a mini-mum contains the coordinatesx of the collapsed / splitvertexvs.

A nice feature of this scheme is that a sequence of theseoperators is compact (smaller than the original mesh rep-resentation), and it is relatively fast to move from onereduction level to another. One significant problem is thatthe reduction level is limited by the reduction value of the

base meshM0

. Since in our application we wish to realizeany given reduction level, the base mesh contains no trian-gles

(M

ˆ=Mn)→Mn–1→…→M1→(M0=M(V,∅))(3)

(some vertices are necessary to initiate the edge split oper-ations). Thus our progressive mesh representation consistsof a series of invertible operations, without requiring anybase mesh triangles.

4Algorithm

Our proposed algorithm is based on two observations.First, we recognized that reduction operations (such asedge collapse) reduce the high-frequency content of themesh, and second, topological constraint can only beremoved by modifying the topology of the mesh. Theimplication of the first observation is that “holes” in themesh (see Plates1(a)-(c)) tend to close up during reduc-tion. The only reason they do not close completely isbecause topological modification is prevented. The secondobservation led us to realize that we could modify thetopology by “splitting” the mesh, i.e., replacing one vertexwith another for a subset of the triangles using the originalvertex. We also realized that any collection of triangles,whether manifold or non-manifold, could be simplified bysplitting the mesh appropriately. Thus we developed ouralgorithm to use topology-preserving operators wheneverpossible, to allow hole closing (or non-manifold attach-ments to form), and to split the mesh when further reduc-tion was not possible.

4.1Overview

The algorithm is similar to the decimation algorithm. Webegin by traversing all vertices, and classify each vertexaccording to its local topology and geometry. Based onthis classification, an error value is computed for the ver-tex. The vertex is then inserted into a priority queue,where highest priority is given to vertices with smallesterror values.

Next, vertices are extracted from the priority queue inorder. The vertex is again classified, and if of appropriateclassification, an attempt is then made to retriangulate theloop formed by the triangles surrounding the vertex.

Unlike the decimation algorithm, where the hole is formedby deleting the vertex and triangles, in our algorithm theretriangulation is formed by an edge collapse. Note that inthis process holes in the mesh may close, and non-mani-fold attachments may form.

If all allowable triangulations are performed and thedesired reduction level is still not achieved, a mesh split-ting operation is initiated. In this process, the mesh is sep-arated along sharp edges, at corners, at non-manifoldvertices, or wherever triangulation fails (due to no legaledge collapses). This process continues until the desiredreduction rate is achieved.

4.2Vertex Classification

Vertices are classified based on topological and geometriccharacteristics. Key topological characteristics arewhether the vertex is manifold or non-manifold, or

whether the vertex is on the boundary of the mesh. A man-

BoundarySimpleNon-manifold

type ofCrack TipInteriorEdgeCorner

Degenerate

Figure 2.

Vertex classification. Crack tip vertices showndisplaced to emphasize topological disconnect.

ifold vertex is one in which the triangles that use the ver-tex form a complete cycle around the vertex, and eachedge attached to the vertex is used by exactly two trian-gles. A boundary vertex is used by a manifold semi-cycle(i.e., two of the edges on the mesh boundary are used byonly one triangle). Note that a vertex with a single triangleattached to it is a boundary vertex. A vertex not fallinginto one of these two categories is classified non-mani-fold.

Geometric characteristics further refine the classifica-tion. A feature angle (angle between the normals of twoedge-connected triangles) is specified by the user. Thisparameter is used to identify sharp edges or corners in themesh, and guide the triangulation process. Whether a tri-angle is degenerate is another important geometric charac-teristic. A degenerate triangle is one that has zero area,either because two or more vertices are coincident, orbecause the vertices are co-linear. (Although not commonin most meshes, many CAD systems do produce them.)Proper treatment of degenerate triangles is necessary toimplement a robust algorithm.

Vertices are classified into seven separate categories asshown in Figure2. There are three base types: simple,boundary, non-manifold; and four types derived from thethree base types: corner, interior edge, crack-tip, anddegenerate. Interior edge vertices have two feature edges,and corner vertices have three or more feature edges (ifsimple), or one or more feature edges (if a boundary ver-tex).

Crack-tip vertices are types of boundary vertices, exceptthat the two vertices forming the boundary edges are coin-cident. These form as a side effect of some splitting opera-tions. These types must be carefully treated duringtriangulation to prevent the propagation of the crackthrough the mesh.

4.3Error Measures

The computation of vertex error is complicated by the factthat the topology of the mesh is changing. Researcherssuch as [8] and [11] have devised elaborate techniques tolimit the global error of a reduced mesh, but these meth-ods depend on the topology of the mesh remaining con-stant. When the topology changes, it is hard to build

useful simplification envelopes or to measure a distance tothe mesh surface. Because of these considerations, and

eError = eii + ejejΣekError = ei + ekError distributed toeisurrounding vertices

Figure 3.Computing and distributing error.

because of our desire for rapid decimation rates, we

choose to retain the distance to plane and distance to lineerror measure employed in the decimation algorithm

(Figure1). Our only modification to the process is to esti-mate the error of a vertex connected to a single triangledifferently. Instead of using distance to line that a bound-ary vertex would use, we compute an vertex erroreaibasedon the triangle areai

ei=

ai

(4)

which is an effective edge length. This error measure hasthe effect of eliminating small, isolated triangles first.One improvement we made to the process of error com-putation is todistribute andaccumulate the error of eachdeleted vertex. The idea is as follows: we maintain anaccumulated error valueevi for each vertexvvertexvi. When athe errorj connected toei is deleted via an edge collapse,j is distributed tovi using

ei=ei+ej

(5)

Thus the total errore(i.e., distance to plane or distance to edge measure)i is a combination of the local errorplusthe accumulated error value at that vertex. The error ateach vertex is initially zero, but as the mesh is reduced,regions that are non-planar will generate errors, and there-fore propagate the error to neighboring vertices. Figure3illustrates this process or a 1D polyline and 2D surfacemesh.

A nice feature of this is approach is that it is relativelysimple to compute a global error measure. As a vertex is

deleted and the hole re-triangulated, the actual errorˆe

the re-triangulated surface (versus the estimated errorj toeis computed. (The errore

j)

ˆthe minimum distance from the deleted vertex to the re-tri-j is computed by determiningangulated surface.) Then, the accumulated error is actuallya global error bounds. This global error measure is conser-vative, but it can be used to terminate the algorithm forapplications requiring a limit on surface error. (Note: set-ting a limit on maximum error may prevent the algorithmfrom achieving a specified reduction value.)

4.4Priority Queue

A central feature of the algorithm is the use of a priorityqueue. We use an implementation similar to that describedby [5], but modified to support theDelete(id) method,

Array treeIndex into treeimplementation

based on id

Root(ei,vi)0j(v0)=2Level 1(ei,vi)j(v1)Children

1(e0,v0)2j(v2)……(ei,vi)m–1j(vn–1)(ei,vi)mj(vn)Figure 4.Modified priority queue implementation.

whereid specifies a vertex not necessarily at the top of thequeue. The implementation is based on a well-balanced,semi-sorted binary tree structure, represented in a contigu-ous array. In addition, we have another array indexed byvertex id, that keeps track of the location of a particular idin the priority queue array. Figure4 illustrates the datastructure. (Note that the introduction of the priority queuemeans the time complexity of the algorithm isO(n log n)as compared to theO(n) of the decimation algorithm.)The addition of theDelete(id) method is necessarybecause of the incremental nature of the progressive deci-mation algorithm. When a vertex is deleted (via an edgecollapse), both the local topology and geometry surround-ing the vertex are modified. The effect is that the verticesdirectly surrounding the deleted vertex (i.e., those con-nected by an edge) have their topology and geometrymodified as well. Thus the error values of these verticesmust be recomputed. This means that the surrounding ver-tices are first deleted from the queue, the error is recom-puted, and the vertices are reinserted back into the priorityqueue.

4.5Triangulation

A vertex marked for deletion is eliminated by an edge col-lapse operation as shown in Figure5(a). We identify theedge to collapse (and the vertexvt) by identifying theshortest edge(vs,vt) that forms a valid split. If featureedges are present, we choose the shortest feature edge.This is not an optimal scheme, but when used with smallfeature angle values gives satisfactory results. We chosethis simple approach because of our requirements on tri-angle processing rate.

A valid split is one that creates a valid local triangula-tion (i.e., triangles do not overlap or intersect). The edgecollapse may modify the global topology of the mesh,either by closing a hole or introducing a non-manifoldattachment. Non-manifold attachments may occur, forexample, when a vertex at the entrance of a tunnel isdeleted, and the tunnel entrance collapses to a line. (SeeFigure5(c) and (d).)

We use a half-space comparison method to determinewhether an edge collapse is valid. To determine if a vertexvdefine the loop of vertices connected to1=vt forms (in conjunction withvs) a valid split, wevs as

Li=(v1,v2,…,vn). An edge collapse is valid when all

vr

Collapsevr

vsvvt

Splitvvll

t

a) An edge collapse and splitv4l3r=(vv1,v5,v4,v3)l4

Invalidv5r

3l4lv2vt=v1

l3l=(v1,v3,v2)

b) Valid and invalid splits

c) Closing a holed) Forming non-manifold attachment

Figure 5.Triangulation via edge collapse

planespj≤ni passing through the vertices(v–1and normal to the average plane normalt,vj) for

3≤Nseparate the vertex loopliloops. This comparison can be computed by creating thei into two non-overlapping sub-n–3 split planes and evaluating the plane equationpi=Ni⋅(vj–vt). The sub-loops are non-overlappingwhen all vertices in one sub-loop evaluate either positiveor negative, and all vertices in the other loop evaluate tothe opposite sign.

As we mentioned earlier, crack-tip vertices must becarefully triangulated to avoid propagating a crack

through the mesh. Crack-tip vertices are treated like sim-ple vertices by temporarily assuming that the two coinci-dent vertices are one vertex. Then, if a valid split can befound, the two coincident vertices are merged with aVer-texMerge, followed by anEdgeCollapse. Although thismay reverse a previousVertexSplit operation, it does elim-inate a vertex and two triangles and prevent the crack fromgrowing. Eventually changes in the local topology andgeometry will either force the crack to grow or to close up.The process will eventually terminate since the mesh willeventually be reduced to a desired level, or will be elimi-nated entirely.

4.6Vertex Splits

A mesh split occurs when we replace vertexvs with ver-texvoriginally used vertext in the connectivity list of one or more triangles thatvs (Figure6(a)). The new vertexvis given exactly the same coordinate value asvtintroduce a “crack” or “hole” into the mesh. We prefer nots. Splitsto split the mesh, but at high decimation rates this relievestopological constraint and enables further decimation.

vr

SplitvvrsvsMergevtvvla) A vertex split and mergelInterior EdgeCorner

Non-manifoldOther typesb) Splitting different vertex types

Figure 6.Mesh splitting operations. Splits are exaggerated.

Splitting is only invoked when a valid edge collapse is notavailable, or when a vertex cannot be triangulated (e.g., anon-manifold vertex). Once the split operation occurs, theverticesvDifferent splitting strategies are used depending on thes andvt are re-inserted into the priority queue.classification of the vertex (Figure6(b)). Interior edge ver-tices are split along the feature edges, as are corner verti-ces. Non-manifold vertices are split into separate manifoldpieces. In any other type of vertex splitting occurs by arbi-trarily separating the loop into two pieces. For example, ifa simple vertex cannot be deleted because a valid edgecollapse is not available, the loop of triangles will be arbi-trarily divided in half (possibly in a recursive process).Like the edge collapse/split, the vertex split/merge canalso be represented as a compact operation. A vertex split/merge operation can be represented with four values

Vertex Split/Merge (vs,vt,vl,vr)

as shown in Figure6(a). The verticesvl andvr define asweep of triangles (fromvr tov (we adopt a counter-clockwisel) that are to be separatedfrom the original vertexvordering convention to uniquely define the sweep of trian-sgles).

4.7Progressive Mesh Storage

The storage requirements for a progressive mesh aresmaller than the standard triangle mesh representationschemes. We estimate the storage requirements as follows.A mesh generally consists of aboutn vertices and2n tri-angles, for a total of9n words of storage using a standardscheme of three vertex indices per triangle, and threecoordinate values per vertex, each stored as one word ofinformation. Using a progressive mesh representation,each edge split requires at a minimum the coordinates andvertex indicesvs,vt,vl, andvr, and creates two trianglesand one vertex, at a cost of7n words of storage. A vertexsplit requires the four vertex indicesvs,vand typically no more thann⁄4t,vl, andvr,reduce the mesh toM0

splits are required to

. We can then estimate the storage

requirements to total8n words, for a savings of 11% overthe standard scheme. Note that even though the vertexsplit requires additional storage over edge collapse, it doesallow us to virtually eliminate the cost of representing thebase mesh.

Further savings are possible by carefully organizing theorder of the playback operations. For example, by renum-bering the vertices after the forward progression is com-plete, it is possible to eliminate the vertex indexvt.

As [7] describes, additional storage savings are possiblebased on the coherence of local topological operations,and by 16-bit quantization and compression of the coordi-nate values. We can also take into account the number ofbits required for a vertex index and use smaller word sizes,if appropriate.

4.8Error Inflection Points

An error inflection pointEerror is greater than a user-defined valuei occurs when the ratio of theEr

e---i--+e----1

->Er(6)

i

The importance of inflection points is that they mark

abrupt transitions in the error of the mesh, and often corre-spond to significant changes in the appearance of themesh. Thus, by tracking these inflection points, we canfind natural points at which to generate LOD’s for a par-ticular part. For example, the first error inflection pointalways occurs at the point in which non-zero error is intro-duced. Geometrically, this corresponds to the point whereall co-planar triangles have been removed from the inte-rior of the mesh, and all co-linear vertices are removedfrom the boundary of the mesh. This is an important pointin the reduction process, since at this point the reducedmodel is indistinguishable from the original mesh usingtypical surface-shading techniques.

We use error inflection points to build other levels in oursequence of LOD models. For a requested reduction levelLk, we use the meshMj with the closest inflection point

Mj:Ej–Lk≤Ei–Lkfor allk≤i,j≤n

(7)

Typical values ofEically determined.

r range from 10 to 100, and are empir-4.9A Variation In Strategy

We found a variation of our splitting strategy to work wellfor a certain class of problems. In this variation, wepre-split the mesh along feature edges, at corners, and at non-manifold vertices. This strategy works well for objectswith large, relatively flat regions, separated by thin, smallsurfaces. This is because splitting isolates regions fromone another, thereby preventing the distortion of the meshdue to errors from edge collapse across the thin surfaces.An example of this behavior can be seen in Color Plate 2,where the triangles forming the thin edges of the plate dis-appear before the much larger triangles forming the facesof the plate.

NumberTrianglesShell1132Plate2624Heat Ex.11,006Turbine314,393Blade1,683,472Figure 7.

ModelReduction 0.5timecollapsessplitsReduction 0.75timecollapsessplitsReduction 0.90timecollapsessplitsReduction 1.00timecollapsessplitsRate0.4631901.0765603.272759015898,40143,011747421,04200.6849401.4198404.4241390202157,87769,019825631,60600.7055700.76648089,3681.6812281691.73145722191,0065.3654479145.8663551160112,689229202,70283,214241232,28188,18478,272914758,05601042852,74324,50196,937Results for five different meshes. Times shown are elapsed seconds. Number of edge collapses and vertex splits are

also shown. The rate is the maximum number of triangles eliminated per elapsed minute.

5Results

We implemented the algorithm as a C++ class in theVisualization Toolkit (vtk) system [6]. The algorithm isrelatively compact requiring less than 2 KLines of code(including the priority queue implementation). No formaloptimization of the code was attempted other than theusual compiler optimization. All test results are run on a190 MHz R10000 processor (compiled and run in 32-bitmode) with 512 MBytes of memory.

We choose to test the algorithm on five different mod-els. The first two are shown in Color Plates 1 and 2, andare a shell mesh and plate with seven holes. The next twomodels are extracted from CAD systems. The first is aheat exchanger with 11,006 original polygons. The next isa turbine shell consisting of 314,393 polygons. Finally, thelast model is very detailed turbine blade consisting of 1.68million triangles originally. The data was obtained by gen-erating an isosurface from a 512 x 512 x 300 industrial CTscan of the part.

Figure7 shows elapsed wall clock time in seconds forthese five examples at reduction levels of 0.50, 0.75, 0.90,and 1.00 (elimination of all triangles). We also show thenumber of edge collapses and vertex splits required ateach level of reduction.

Color Plates 3(a)-(f) show results for the heat

exchanger. Plates 4(a)-(f) show results for the turbineshell. Plates 5(a)-(f) show the results for the turbine blade.Note that in each case the onset of vertex splitting isshown. In some of these color plates the red edges areused to indicate mesh boundaries, while light green indi-cates manifold, or interior edges.

The ability to modify topology provides us with reduc-tion levels greater than could be achieved using any topol-ogy preserving algorithm. ColorPlate4 clearly

demonstrates this since the maximum topology preservingreduction we could obtain wasr=0.404. We were able tomore than double the reduction level and still achieve areasonable representation.

At extreme reduction levels the quality of the mesh var-ied greatly depending on the model. In some cases a fewlarge triangles will “grow” and form nice approximations(e.g., the plate and shell). In other cases, the mesh is frag-mented by the splitting process and does not generatelarger triangles or good approximations. But in each casewe were able to recognize the part being represented,

which is sufficient for initial camera positioning and navi-gation. We were generally pleased with the results of thealgorithm, since the creation of non-optimal meshes iswell balanced by the algorithm’s speed, ability to processlarge meshes, and robustness.

6Conclusion

We have described a topology modifying decimation algo-rithm capable of generating reductions at any level. Thealgorithm uses the invertible progressive operatorsEdgeCollapse/Split andVertex Split/Merge to construct com-pact progressive meshes. The algorithm has a high enoughpolygonal processing rate to support a large scale designand visualization process. We have found it to be aninvaluable tool for creating LOD databases.

References

[1]W. J. Schroeder, J. A. Zarge, and W. E. Lorensen. Decimation oftriangle meshes.Computer Graphics 26(2):65-70, July 1992.[2]Turk, G. Re-Tiling of polygonal surfaces.Computer Graphics,26(2):55-64, July 1992.

[3]H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, W. Stuetzle.Mesh optimization.Computer Graphics Proceedings (SIG-GRAPH ‘93), pp 19-26, August 1993.

[4]P. Hinker and C. Hansen. Geometric optimization. InProc. ofVisualization ‘93. pages 189-195, October 1993.

[5]A. V. Aho, J. E. Hopcroft, J. D. Ullman.Data Structures andAlgorithms. Addison-Wesley, 1983.

[6]W. J. Schroeder, K. M. Martin, W. E. Lorensen.The VisualizationToolkit An Object-Oriented Approach To 3D Graphics. Prentice-Hall, 1996.

[7]H. Hoppe. Progressive Meshes.Proc. SIGGRAPH ‘96, pp 99-108,August 1996.

[8]J. Cohen, A. Varshney, D. Manocha, G. Turk, H. Weber, P. Agar-wal, F. Brooks, W. Wright. Simplification envelopes.Proc. SIG-GRAPH ‘96, pp 119-128, August 1996.

[9]J. Rossignac and P. Borel. Multi-resolution 3D approximations forrendering. InModeling in Computer Graphics, pp. 455-465,Springer-Verlag, June-July 1993.

[10]T. He, L. Hong A. Kaufma, A. Varshney, S. Wang. Voxel basedobject simplification. InProc. of Visualization ‘95, pp. 296-303,October 1995.

[11]R. Klein, G. Liebich, W. Strasser. Mesh reduction with error con-trol. InProc. of Visualization ‘96, pp. 311-318, October 1996.[12]

P. Heckbert and M. Garland. Fast polygonal approximation of ter-rains and height fields. Technical Report CMU-CS-95-181, Carn-egie Mellon University, August 1995.

a) Original model1,132 trianglesb) Topology unchanged

43 triangles

c) Topology modified

Plate 1 - Topological constraints prevent further reduction (shell with holes). Red edges are on the

boundary of the mesh, light green edges are in the interior of the mesh.

a) Original model2,624 trianglesb) Shortly after splitting

157 trianglesc) Final model4 triangles

Plate 2- Sharp edge splits and hole elimination (thin plate with holes). (b) is a close-up of the mesh

showing the how the hole triangles are disconnected from the top plate.

a) Original model11,006 trianglesb) Reduction 50%,5,518 trianglesc) Just after mesh splitting2,707 triangles, 75.4% reduction

d) Reduction 90%,1,100 trianglese) Reduction 95%,550 trianglesf) Reduction 98%,220 triangles

Plate 3- Heat exchanger at different levels of reduction. (c) shows the edges that are split at the onset of

edge splitting.

a) Original model314,39 trianglesb) Shortly before splitting187,449 triangles, reduction 40.4%c) 50% reduction,157,196 triangles

d) 75% reduction,78,598 trianglese) 90% reduction,31,439 trianglesc) 95% reduction,15,719 triangles

Plate 4- Turbine shell shown at various reduction levels. Shell has thickness, and many features requiring

vertex splitting.

a) Original model1,683,472 trianglesb) Close-up of edges

showing holes leading to interiorc) 75% reduction,420,867triangles

d) Shortly before splitting134,120 triangles, 92% reductione) 95% reduction,84,173 trianglesf) 99.5% reduction,8,417 triangles

Plate 5 - Turbine blade shown at various levels of reduction. Data derived from 5122 by 300 CT scan.