David Luebke, Carl EriksonDepartment of Computer ScienceUniversity of North Carolina at Chapel Hill
1. ABSTRACT
Hierarchical dynamic simplification (HDS) is a new approach tothe problem of simplifying arbitrary polygonal environments.HDS operates dynamically, retessellating the scene continuouslyas the user’s viewing position shifts, and adaptively, processingthe entire database without first decomposing the environmentinto individual objects. The resulting system allows real-timedisplay of very complex polygonal CAD models consisting ofthousands of parts and hundreds of thousands of polygons. HDSsupports various preprocessing algorithms and various run-timecriteria, providing a general framework for dynamic view-dependent simplification.
Briefly, HDS works by clustering vertices together in ahierarchical fashion. The simplification process continuouslyqueries this hierarchy to generate a scene containing only thosepolygons that are important from the current viewpoint. Whenthe volume of space associated with a vertex cluster occupies lessthan a user-specified amount of the screen, all vertices withinthat cluster are collapsed together and degenerate polygonsfiltered out. HDS maintains an active list of visible polygons forrendering. Since frame-to-frame movements typically involvesmall changes in viewpoint, and therefore modify the active listby only a few polygons, the method takes advantage of temporalcoherence for greater speed.
CR Categories: I.3.5 [Computer Graphics]: Computational Geometry andObject Modeling - surfaces and object representations.
Additional Keywords: polygonal simplification, level of detail, viewdependent rendering.
2. INTRODUCTION
2.1 Polygons In Computer Graphics
Polygonal models currently dominate the field of interactivethree-dimensional computer graphics. This is largely becausetheir mathematical simplicity allows rapid rendering of polygonaldatasets, which in turn has led to widely available polygon-rendering hardware. Moreover, polygons serve as a sort oflowest common denominator for computer models, since almostany model representation (spline, implicit-surface, volumetric)can be converted with arbitrary accuracy to a polygonal mesh.
In many cases the complexity of such models exceeds thecapability of graphics hardware to render them interactively.Three approaches are used to alleviate this problem:
• Augmenting the raw polygonal data to convey more
visual detail per polygon. Gouraud shading and texturemapping fall into this category.
• Using information about the model to cull away large
portions which are occluded from the currentviewpoint. The visibility processing approach of Tellerand Sequin is an excellent example [Teller 91].
• Polygonal simplification methods simplify the
polygonal geometry of small or distant objects toreduce the rendering cost without a significant loss inthe visual content of the scene. HDS is one suchmethod.
2.2 Polygonal Simplification
Polygonal simplification is at once a very current and a very oldtopic in computer graphics. As early as 1976, James Clarkdescribed the benefits of representing objects within a scene atseveral resolutions, and flight simulators have long used hand-crafted multi-resolution models of airplanes to guarantee aconstant frame rate [Clark 76, Cosman 81]. Recent years haveseen a flurry of research into generating such multi-resolutionrepresentations of objects automatically by simplifying thepolygonal geometry of the object. This paper presents a newapproach which simplifies the geometry of entire scenesdynamically, adjusting the simplification as the user movesaround.
2.3 Motivation
The algorithm presented in this paper was conceived for verycomplex hand-crafted CAD databases, a class of models forwhich existing simplification methods are often inadequate.Real-world CAD models are often topologically unsound (i.e.,non-manifold), and may entail a great deal of clean-up effortbefore many simplification algorithms can be applied.Sometimes such models even come in “polygon-soup” formatswhich do not differentiate individual objects, but insteaddescribe the entire scene as an unorganized list of polygons. Noexisting algorithm deals elegantly with such models.
Even when the model format delineates objects, simplifyingcomplex CAD datasets with current schemes can involve manyman-hours. To begin with, physically large objects must besubdivided. Consider a model of a ship, for example: the hull ofthe ship should be divided into several sections, or the endfurthest from the user will be tessellated as finely as the nearbyhull. In addition, physically small objects may need to becombined, especially for drastic simplification. The dieselengine of that ship might consist of ten thousand small parts; aroughly engine-shaped block makes a better approximation thanten thousand tetrahedra. Finally, each simplification must beinspected for visual fidelity to the original object, and anappropriate switching threshold selected. This can be the mosttime-consuming step in the simplification of a complicated modelwith thousands of parts, but few existing techniques addressautomating the process.1
These considerations led to a new approach with threeprimary goals. First, the algorithm should be very general,making as few assumptions as possible about the input model.The algorithm must therefore deal robustly with degenerate and 1
Notable exceptions include work by Cohen et al, and by Shirley and Maciel[Cohen 96, Maciel 95].
non-manifold models. Second, the algorithm should becompletely automatic, able to simplify even a polygon-soupmodel without human intervention. This implies that thealgorithm must simplify the entire scene adaptively rather thanrelying on simplifying objects within the scene. Third, thealgorithm should be dynamically adjustable, supplying thesystem with a fine-grained interactive “dial” for trading offperformance and fidelity. This final requirement implies that thealgorithm must operate at least partially at run time.
2.4 Hierarchical Dynamic Simplification
Hierarchical dynamic simplification has some novel features.Rather than representing the scene as a collection of objects,each at several levels of detail, the entire model comprises asingle large data structure. This is the vertex tree, a hierarchy ofvertices which is queried dynamically to generate a simplifiedscene. The vertex tree contains information only about thevertices and triangles of the model; manifold topology is notrequired and need not be preserved. Each node in the vertex treecontains one or more vertices; HDS operates by collapsing all ofthe vertices within a node together to a single representativevertex. Triangles whose corners have been collapsed togetherbecome redundant and can be eliminated, decreasing the totalpolygon count. Likewise, a node may be expanded by splittingits representative vertex into the representative vertices of thenode’s children. Triangles filtered out when the node wascollapsed become visible again when the node is expanded,increasing the polygon count.
The entire system is dynamic; nodes to be collapsed orexpanded are continuously chosen based on their projected size.The screenspace extent of each node is monitored: as theviewpoint shifts, certain nodes in the vertex tree will fall belowthe size threshold. These nodes will be folded into their parentnodes and the now-redundant triangles removed from the displaylist. Other nodes will increase in apparent size to the user andwill be unfolded into their constituent child nodes, introducingnew vertices and new triangles into the display list. The userselects the screenspace size threshold and may adjust it duringthe course of a viewing session for interactive control over thedegree of simplification. Nodes will be folded and unfolded eachframe, so efficient methods for finding, adding, and removing theaffected triangles are crucial.
3. STRUCTURES AND METHODS3.1 Active Triangle List
The purpose of the active triangle list is to take advantage oftemporal coherence. Frames in an interactive viewing sessiontypically exhibit only incremental shifts in viewpoint, so the setof visible triangles remains largely constant. The active trianglelist in its simplest form is just a sequence of those visibletriangles. Expanding a node appends some triangles to the activetriangle list; collapsing the node removes them. The active list ismaintained in the current implementation as a doubly-linked listof triangle structures, each with the following basic structure:
struct Node *Tri {
Node * cornersproxies[3];};
Tri*prev, *next;
[3];The corners field represents the triangle at its highestresolution, pointing to the three nodes whose representativevertices are the original corners of the triangle. The proxies fieldrepresents the triangle in the current simplification, pointing tothe first active ancestor of each corner node [Figure 1].
Before SimplificationAfter Simplification(a) Arrows point at corners(b) Arrows point at proxiesFigure 1: A triangle’s corners reference the initial vertices; itsproxies point to the current simplification of each corner.Clustering vertices to the representative vertex of their quadrant(circled) collapses all but the darkened triangle.
3.2 Vertex Tree
Created during a preprocessing stage, the vertex tree controls theorder in which vertices are collapsed and stores data necessary tocollapse and uncollapse these vertices quickly. Unfolded nodesin the vertex tree are labeled active, and folded nodes are labeledinactive; the active nodes of the vertex tree comprise acontiguous region called the active tree. Active nodes with noactive children are a special case; these nodes form the boundaryof the active tree and are labeled boundary nodes[Figure 2].
Active TreeBoundary NodesVertex TreeFigure 2: The vertex tree, active tree, and boundary nodes.Each node in the vertex tree includes the basic structuredescribed below (explanations of the individual fields follow):
struct BitVec Node {
Byte
id;NodeStatusdepth;CoordCoordrepvertlabel;floatcenter;Triradius;Tri*tris;;Node * *subtrisByte
parentnumchildren;
;};
Node ** children;
;• id: a bit vector which labels the path from the root of
the vertex tree to the node. In a binary vertex tree,each bit specifies the left or right branch at that level ofthe tree. For the vertex octree described in section 7.1,each 3-bit triple denotes the correct branch at thatlevel.
• depth: the depth of the node in the vertex tree. The
depth and id together uniquely identify the node.
• label: the node’s status: active, boundary, or inactive.
Figure 4: Showing the subtris of three nodes. These are thetriangles which appear and vanish as the nodes fold and unfold.Here the subtris of each circled node are darkened.
• repvert: the coordinates of the node’s representative
vertex. All vertices in boundary and inactive nodes arecollapsed to this vertex.
• center, radius: the center and radius of a bounding
sphere containing all vertices in this node.
• tris: a list of triangles with exactly one corner in the
node. These are the triangles whose corners must beadjusted when the node is folded or unfolded.
• subtris: a list of triangles with two or three corners
within the node, but no more than one corner withinany child of the node [Figure 4]. These triangles willbe filtered out if the node is folded, and re-introducedif the node is unfolded.
• parent, numchildren, children: the parent and
children of this node in the vertex tree.
The fundamental operations associated with nodes in thevertex tree are collapseNode() and expandNode(). Thesefunctions add or remove the subtris of the specified node fromthe active triangle list and update the proxies of the node’s tris:
collapseNode N->label = (Node *N)
foreachboundary;// label all children inactive child C of N
if (C->label == active)
foreachC->label = collapseNode(C);inactive;
// update triangle T in N->tris
foreachtri proxies
T->proxies[c] =
corner c of {1,2,3}
firstActiveAncestor(T->
foreachcorners[c]);
// remove triangle T in N->subtris
removeTri(T);subtris from active listexpandNodeforeach (Node *N)
N->label = C->label = child C of N
boundary;foreachactive;
// update triangle T in N->tris
foreachtri proxies
T->proxies[c] =
corner c of {1,2,3}
firstActiveAncestor(T->
foreachcorners[c]);
// add triangle T in N->subtris
addTri(T);
subtris to active list4. VIEW-DEPENDENT SIMPLIFICATION
The data structures and methods described so far provide aframework for dynamic view-dependent simplification. Anycriterion for run-time simplification may be plugged into thisframework; each criterion takes the form of a function to choosewhich nodes are folded and unfolded each frame. The currentimplementation incorporates three criteria: a screenspace errorthreshold, a silhouette test, and a triangle budget.
4.1 Screenspace Error Threshold
The underlying philosophy of HDS is to remove triangles whichare not important to the scene. Since importance usuallydiminishes with size on the screen, an obvious run-time strategyis to collapse nodes which occupy a small amount of the screen.To formulate this strategy more precisely, consider a node whichrepresents several vertices clustered together. The errorintroduced by collapsing the vertices can be thought of as themaximum distance a vertex can be shifted during the collapseoperation, which equals the length of the vector between the twofarthest vertices in the cluster. The extent of this vector on thescreen is the screenspace error of the node. By unfolding exactlythose nodes whose screenspace error exceeds a user-specifiedthreshold t, HDS enforces a quality constraint on thesimplification: no vertex shall move by more than t pixels on thescreen.
Determining the exact screenspace extent of a vertex clustercan be a time-consuming task, but a conservative estimate can beefficiently obtained by associating a bounding volume with eachnode in the vertex tree. The current implementation usesbounding spheres, which allow an extremely fast screenspaceextent test but often provide a poor fit to the vertex cluster. Thefunction nodeSize(N) tests the bounding sphere of the node Nand returns its extent projected onto the screen. The recursiveprocedure adjustTree() uses nodeSize() in a top-down fashion,evaluating which nodes to collapse and expand:
adjustTreesize = (Node *N)
if (size >= threshold)
nodeSize(N);if (N->label == active)
foreachelse
adjustTree(C);
child C of N
// N->label == Boundaryelse
expandNode(N);
if (N->label == active)
// size < thresholdcollapseNode(N);
4.2 Silhouette Preservation
Silhouettes and contours are particularly important visual cuesfor object recognition. Detecting nodes along object silhouettesand allocating more detail to those regions can thereforedisproportionately increase the perceived quality of asimplification [Xia 96]. A conservative but efficient silhouettetest can be plugged into the HDS framework by adding two fieldsto the Node structure: coneNormal is a vector and coneAngle isa floating-point scalar. These fields together specify a cone ofnormals [Shirman 93] for the node which conservatively boundsall the normals of all the triangles in the subtree rooted at thenode [Figure 5]. At run time a viewing cone is created thatoriginates from the viewer position and tightly encloses thebounding sphere of the node [Figure 6]. Testing the viewingcone against the cone of normals determines whether the node iscompletely frontfacing, completely backfacing, or potentially lieson the silhouette. If any normal in the cone of normals isorthogonal to any direction contained within the viewing cone,the node is potentially on the silhouette [Figure 7]:coneNormal(Nview)
coneAngle (α)
Figure 5: On the left, a node containing four triangles plus itsbounding sphere. On the right, the node’s cone of normals.
viewConeAngle (β)
θviewConeNormal (Nview)
Figure 6: The viewing cone on the left originates from the viewerand tightly encloses the bounding sphere of the node. The anglebetween Ncone and Nview is denoted θ in the pseudocode below.
testSilhouetteα(Node *node, Coord eyePt)
N = node->coneAngle;
βconeN = calcViewConeAngle( = node->coneNormal;
eyePt, node);
θview = calcViewConeNormal(eyePt, node);if ( = cos-1θ - α(N - viewβ > • Ncone);if (return θ + α + FrontFacing;π/2)
β < π/2)
returnreturn OnSilhouette;
BackFacing;Silhouette preservation dovetails nicely with the screenspaceerror metric approach presented above: the testSilhouette()operation determines which nodes may be on the silhouette, andthese nodes are then tested against a tighter screenspace errorthreshold than interior nodes [Plate 2]. The adjustTree()operation is easily modified to incorporate this test:
adjustTreesize = (Node *N)
if (testSilhouette(N) == nodeSize(N);
elsetestThreshold = OnSilhouette)
Ts;if (size >= testThreshold = // testSilhouette(N) == Interior
TI;
if (N->label == active)
testThreshold)
foreachelse // N->label == Boundary
adjustTree(C);
child C of N
elseexpandNode(N);
if (N->label == active)
// size < testThreshold
collapseNode(N);
Note that hierarchical backface culling falls out of thesilhouette preservation test if polygons of backfacing nodes arenot rendered [Kumar 96].
4.3 Triangle-Budget Simplification
The screenspace error threshold and silhouette test allow the userto set a bound on the quality of the simplified scene, but often abound on the complexity (and rendering time) is desired instead.Triangle budget simplification allows the user to specify howmany triangles the scene should contain. HDS then minimizesthe maximum screenspace error of all boundary nodes within thistriangle budget constraint. The intuitive meaning of this processis easily put into words: “Vertices on the screen can move as faras t pixels from their original position. Minimize t.”
The current system implements triangle budget simplificationas a priority queue of boundary nodes, sorted by screenspaceerror. The node N with the greatest error is unfolded, removingN from the top of the queue and inserting the children of N backinto the queue. This process iterates until unfolding the top nodeof the queue would exceed the triangle budget, at which pointthe maximum error has been minimized. The simplificationcould further refine the scene by searching the priority queue forthe largest nodes which can still be unfolded without violatingthe triangle budget, but this is unnecessary in practice. Theinitial minimization step works extremely well on all modelstested, and always terminates within twenty triangles of thespecified budget. Pseudocode for this procedure isstraightforward:
budgetSimplify// Initialize Q to (Node *rootnode)Heap *Q(rootnode);
rootnodeNode *topnode = rootnode;
Q->initialize(root);
while (topnode->nsubtris < topnode = Q->removeTop();tribudget)
expandNode(Q->insert(topnode);
tribudget -= topnode->children);topnode->nsubtris;
5. OPTIMIZING THE ALGORITHM
A straightforward implementation of the HDS algorithm runswith adequate speed on small models, no larger than 20,000triangles or so. Three kinds of optimizations together increasethe speed of the dynamic simplification by almost two orders ofmagnitude: exploiting temporal coherence, using visibilityinformation, and parallelizing the algorithm.
5.1 Exploiting Temporal Coherence
HDS assumes a high degree of frame-to-frame coherence in theposition of the viewer. The design of the active triangle list inparticular is based on the assumption that relatively few triangleswill be added or removed to the scene each frame. Oneespecially frequent operation that can also take advantage ofcoherence is the firstActiveAncestor() function, used heavily bycollapseNode() and expandNode(). FirstActiveAncestor(N)searches up the vertex tree for the nearest ancestor of node Nwhich is tagged Active or Boundary. Storing the result of eachsearch as a field of N and going up or down from that nodespeeds up the next search considerably. The id field of the Nodestructure provides the information necessary to traverse down thetree along the correct path.
5.2 Visibility: Culling the Active Triangle List
The active triangle list as described exploits temporal coherencebut does not lend itself to efficient culling of invisible triangles.View-frustum culling techniques clump polygons together, oftenusing a spatial hierarchy to quickly reject clumps which lieoutside the view frustum, but clumping is hard to maintain in theever-changing active list. A different approach for HDS wouldbe to distribute the active triangles across the vertex tree,associating each triangle with the smallest node which containsall three of the triangle’s corners. Rendering the scene wouldthen consist of a top-down traversal of the vertex tree, evaluatingeach node’s visibility and rendering the associated triangles ofvisible nodes. While enabling efficient visibility culling, thisscheme loses the advantage of temporal coherence, since everyvisible active node must be visited every frame. On complexmodels the overhead of traversing a deep active tree underminesthe benefit of rendering fewer triangles.
In practice a hybrid approach works well: the active trianglelist is split into several lists, each associated with a high-levelnode of the vertex tree. Nodes with an active list are termedcullNodes; triangles added by expandNode() are appended to theactive list of the smallest cullNode containing the corners of thetriangle. Restricting cullNodes to the high levels of the vertextree results in a coarse-grained culling without the overhead of afull active tree traversal, thus exploiting both visibility cullingand temporal coherence.
5.3 Visibility: Avoiding Irrelevant Nodes
Distributing the active list across multiple nodes speeds uprendering, since invisible nodes are not visited. HDS may stillneed to examine such nodes, however, since the tris and subtrisof an invisible node may still be visible [Figure 8]. Some nodes
are not only invisible but irrelevant, that is, expanding orcollapsing the node cannot possibly affect the scene. Aninvisible node is irrelevant if it does not contain a corner of anypotentially visible triangle; the simplification traversal can savetime by not visiting these nodes. In an interactive walkthroughsession, the vast majority of invisible nodes are usuallyirrelevant, so testing for irrelevance provides a significantspeedup. An exact test is difficult, but a conservative test forirrelevant nodes is easily constructed by adding a container fieldto each node in the vertex tree. The container node C of a nodeN is the smallest node which contains every tri and subtri of Nand N’s descendants. C thus contains every triangle which mightbe affected by operations on the subtree rooted at N. If C isinvisible, N is irrelevant and can be safely ignored by thesimplification traversal.Irrelevant
InvisibleFigure 8: Invisible nodes are completely outside the viewfrustum. Irrelevant nodes are invisible and contain no verticesof visible triangles.
5.4 Asynchronous Simplification
An important strategy for speeding up any algorithm is toparallelize it, distributing the work over multiple processors.Computer graphics applications most commonly accomplish thisby parallelizing the major stages of the rendering computation ina pipeline fashion. A traditional level-of-detail system might bedivided into SELECT and RENDER stages: the SELECT stagedecides which resolution of which objects to render and compilesthem into a display list, which the RENDER process thenrenders. Meanwhile, the SELECT process prepares the displaylist for the next frame [Funkhouser 93, Rohlf 94]. If S is thetime taken to select levels of detail and R is the time taken torender a frame, parallelizing the two processes as a pipelinereduces the total time per frame from R+S to max(R,S).
HDS also divides naturally into two basic tasks, SIMPLIFYand RENDER. The SIMPLIFY task traverses the vertex treefolding and unfolding nodes as needed. The RENDER taskcycles over the active triangle list rendering each triangle. Letthe time taken by SIMPLIFY to traverse the entire tree be S andthe time taken by RENDER to draw the entire active list be R.The frame time of a uniprocessor implementation will then beR+S, and the frame time of a pipelined implementation willagain be max(R,S). The rendering task usually dominates thesimplification task, so the effective frame time often reduces toR. The exception is during large shifts of viewpoint, when theusual assumption of temporal coherence fails and many trianglesmust be added and deleted from the active triangle list. This canhave the distracting effect of slowing down the frame rate whenthe user speeds up the rate of motion.
Asynchronous simplification provides a solution: let theSIMPLIFY and RENDER tasks run asynchronously, with theSIMPLIFY process writing to the active triangle list and theRENDER process reading it. This decouples the tasks for a totalframe time of R, eliminating the slowdown artifact associated
with large viewpoint changes. When the viewer’s velocityoutpaces the simplification rate in asynchronous mode, theSIMPLIFY process simply falls behind. As a result the scenerendered for the viewer is somewhat coarse in quality until theSIMPLIFY process catches up, at which point the scenegradually sweetens back to the expected quality. This gracefuldegradation of fidelity is less distracting than sudden drops inframe rate.
A straightforward implementation of asynchronoussimplification is relatively easy to code on a shared-memorymultiprocessor system, but care must be taken to avoid“dropouts”. Characterized by triangles that disappear for aframe, these transient artifacts occur when the RENDER processsweeps through a region of the active list being affected by theSIMPLIFY process. For example, the collapseNode() operationremoves triangles and fills in the resulting holes by adjusting thecorner positions of neighboring triangles. If those neighboringtriangles have already been rendered during the frame whencollapseNode() adjusts their corners, but the triangle to beremoved has not yet been rendered, a hole will appear in themesh for that frame.
Dropouts are fundamentally caused by failure to maintain aconsistent shared database in an asynchronous system. They aredifficult to eradicate with simple locking schemes. Locking thetriangles to be affected before every collapseNode() andexpandNode() operation will not suffice, since the triangles maynot be near each other in the active triangle list. Since the activetriangle list is divided among the high-level nodes for cullingpurposes, another possibility would be to lock all nodes affectedby the collapse or expand operation.2 This strategy preventsdropouts, but proves prohibitively expensive in practice.
The update queue provides one solution to the dropoutproblem. The update queue was motivated by the observationthat the time spent performing collapseNode() and expandNode()operations is a small fraction of the time taken by the SIMPLIFYprocess to traverse the vertex tree and determine which nodes tofold and unfold. Rather than actually performing the updates, theSIMPLIFY process accumulates them into the update queue,marking the node Dirty and placing a Collapse or Expand entryin the queue. The update queue acts as a buffer: at the beginningof every frame the RENDER process performs the first n updatesin the queue, collapsing or expanding each node before markingit Clean again.3 All changes to the active triangle list take placeas a batch before any triangles are rendered; the shared databaseis thus kept consistent and dropouts are eliminated.
6. PREVIOUS WORK
6.1 Constructing the Vertex Tree
Many excellent polygonal simplification algorithms have beendescribed in the recent literature [Cohen 96, Hoppe 96, Eck 95].HDS is not a competing algorithm, but a framework into whichmany existing algorithms can be incorporated. Any algorithmwhich can be expressed in terms of vertex collapse operationscan be used to create the vertex tree. The construction of thevertex tree determines the order in which vertices are collapsed,which in turn determines the quality of the simplification HDScan create. In addition, the construction of the vertex tree affectsthe run-time performance of HDS, since a well-balanced tree will 2
This turns out to be the subtree rooted at the container node of the nodebeing collapsed or expanded.
3
As with any buffer, care must be taken to empty the update queue fastenough; n was set to 1000 for all models tested.
reduce the traversal time of the SIMPLIFY task. Possiblealgorithms form a spectrum, ranging from fast, simpleapproaches with moderate fidelity to slower, more sophisticatedmethods with superb fidelity. The choice of algorithm forconstructing the vertex tree is heavily application-dependent. Ina design-review setting, CAD users may want to visualize theirrevisions in the context of the entire model several times a day.Preprocessing times of hours are unacceptable in this scenario.On the other hand, a walkthrough of the completed model mightbe desired for demonstration purposes. Here it makes sense touse a slower, more careful algorithm to optimize the quality ofsimplifications and prevent any distracting artifacts.
6.1.1 Simplest: Spatial Subdivision
One of the simplest techniques is to classify the vertices of themodel with a space-partitioning structure such as an octree. Anadaptive version of the spatial binning approach introduced by[Rossignac 92], the spatial subdivision method was firstintroduced for view-dependent simplification by [Luebke 96].Vertices are ranked by importance using local criteria such asedge length and curvature. Beginning at the root of the octree,the most important vertex within each node is chosen as thatnode’s representative vertex. The vertices are then partitionedamong the node’s eight children and the process is recursivelyrepeated. In this way vertices are clustered roughly according toproximity. Neighboring vertices are likely to get collapsedalmost immediately, whereas distant vertices tend to merge onlyat high levels of the tree.
Unless the vertices of the model are uniformly distributed,the straightforward approach just described will result in highlyunbalanced octrees. CAD models are often locally dense butglobally sparse, consisting of highly detailed componentsseparated by areas of low detail or empty space. In this situationa more adaptive partitioning structure such as a K-D tree willproduce a more balanced tree, yielding better run-timeperformance. An even simpler structure is the tight octree, inwhich each node of the octree is tightened to the smallest axis-aligned cube which encloses the relevant vertices before the nodeis subdivided. This approach seems to adapt very well to CADmodels, and most results presented in this paper used tight-octreespatial subdivision to cluster vertices.
Top-down spatial subdivision clustering schemes possessmany advantages. Their simplicity makes an efficient, robustimplementation relatively easy to code. In addition, spatialpartitioning of vertices is typically very fast, bringing thepreprocess time of even large models down to manageable levels:preprocessing the 700,000 polygon torpedo room model, forexample, takes only 158 seconds [Table 1]. Finally, spatial-subdivision vertex clustering is by its nature very general. Noknowledge of the polygon mesh is used; manifold topology isneither assumed nor preserved. Meshes with degeneracies (suchas cracks, T-junctions, and missing polygons) are unfortunatelyquite common. Spatial-subdivision vertex clustering schemeswill operate despite the presence of degeneracies incompatiblewith more complex schemes.
6.1.2 Prettiest: Simplification Envelopes,Progressive Mesh Algorithm
On the other end of the spectrum, some very sophisticated recentsimplification algorithms could be used to build the vertexcluster tree. Cohen et al present Simplification Envelopes, offsetsurfaces of a polygonal mesh modified to prevent self-intersection and bounded to a distance ε of the mesh. Bygenerating a simpler triangulation of the surface withoutintersecting the simplification envelopes, the authors guarantee a
simplification which preserves global topology and varies fromthe original surface by no more than ε [Cohen 96].Simplification envelopes could be used to construct the vertextree in HDS by applying successively larger values of ε, at eachstage only clustering those vertices which do not cause the meshto intersect the envelopes. The value of ε used to generate eachcluster would then become the error metric associated with thatnode in the vertex tree, resulting in an HDS simplification withexcellent fidelity. Unfortunately, it is not clear how to extendsimplification envelopes to allow merging between differentobjects, or to allow drastic topology-discarding collapseoperations at high levels of the tree.
Hoppe describes an optimization approach which creates aseries of edge collapses for the Progressive Meshesrepresentation [Hoppe 96]. Each edge collapse corresponds to anode in HDS with two children and one or two subtris. Thestream of edge collapse records in a progressive mesh containsan implicit hierarchy that maps directly to the HDS vertex tree.A progressive mesh may thus be viewed without modification inan HDS system, though this has disadvantages. A progressivemesh never collapses more than two vertices together at a time,which may result in an unnecessarily deep vertex tree. Amodified optimization step which could collapse multiplevertices seems possible, and would address this problem. Also,progressive meshes collapse only vertices within a mesh, soseparate objects never merge together. Finally, restricting edgecollapses to those which preserve the manifold topology of themesh limits the amount of simplification possible.4 For thesereasons, a direct embedding of a progressive mesh is not optimalfor the drastic simplification necessary to visualize very complexmodels.
Along with progressive meshes, Hoppe introduces a very niceframework for handling surface attributes of a mesh duringsimplification. Such attributes are categorized as discreteattributes, associated with faces in the mesh, and scalarattributes, associated with corners of the faces in the mesh.Common discrete attributes include material and textureidentifiers; common scalar attributes include color, normal, andtexture coordinates. Hoppe’s method of maintaining discrete andscalar attributes as vertices are collapsed extends directly toHDS, and is used without modification in the currentimplementation.
6.1.3 A Hybrid Approach
Both the simplification envelope and progressive meshapproaches can be combined with top-down spatial subdivisionto allow drastic simplification and merging of objects. The resultof either approach on a collection of objects in a scene is acollection of vertex trees. When the vertex tree for each object isadequate, the spatial subdivision algorithm unifies this “vertexforest” into a single tree. A tight octree or similar structuremerges nearby vertices from the same or different object, withoutregard to topology. The final vertex tree exhibits both highfidelity (at low levels of the tree) and drastic simplification (athigh levels).
The sphere and bunny simplifications in the color plates weregenerated with this type of hybrid approach. Since this modelwas intended to illustrate silhouette preservation as a run-timecriterion, it was important to merge vertices so as to minimizethe normal cones of the resulting vertex cluster. Also, thecurvature of a non-manifold mesh is not well defined, so onlyadjacent vertices in the mesh could be collapsed. These 4
For example, our implementation could not reduce the 69,451-trianglebunny model beyond 520 triangles.
considerations led to a two-stage clustering algorithm. First, aprogressive mesh representation of the model was created, inwhich the edge collapse order was chosen to minimize normalcones and to maintain a balanced tree. Edge collapses whichresulted in normal cone angles greater than 135o weredisallowed. When the model could be simplified no further withthese restrictions, a tight octree was applied to the remainingvertex clusters to produce a single HDS vertex tree.
6.2 Other Related Work
Xia and Varshney use merge trees to perform view-dependent
simplifications of triangular models in real-time [Xia 96]. Amerge tree is similar to a progressive mesh, created off-line andconsisting of a hierarchy of edge collapses. Selective refinementis applied based on viewing direction, lighting, and visibility.Xia and Varshney update an active list of vertices and triangles,using frame-to-frame coherence to achieve real-timeperformance. In addition, extra information is stored at eachnode of the merge tree to specify dependencies between edgecollapse operations. These dependencies are used to eliminatefolding artifacts during the visualization of the model, but alsoconstrain the tessellation to change gradually between areas ofhigh simplification and areas of low simplification. Thisrestriction limits the degree of drastic simplification possiblewith a merge tree, as does the inability of merge trees to combinevertices from different objects. Xia and Varshney also assumemanifold models, which together with the limited simplificationavailable makes their approach less appropriate for large-scaleCAD databases.
The error bounds described in Section 4 provide a usefulindicator of the simplification fidelity, but screenspace error andsilhouette preservation are only two of the many criteria thatdetermine the view-dependent perceptual importance of a regionof a scene. Ohshima et al. [Ohshima 96] investigate a gaze-directed system which allocates geometric detail to objectsaccording to their calculated visual acuity. Objects in the centerof vision have a higher visual acuity than objects in the peripheryand are thus drawn at a higher level of detail. Similarly,stationary objects are assigned a higher visual acuity than rapidlymoving objects, and objects at the depth of the user’s binocularfusion are assigned a higher visual acuity than objects closer orfarther than the distance at which the user’s eyes currentlyconverge. These techniques show promise for further reducingthe polygon count of a scene in immersive rendering situations,and could be integrated into the HDS framework as additionalrun-time simplification criteria.
7. RESULTS
HDS has been implemented and tested on a Silicon GraphicsOnyx system with InfiniteReality graphics.
The models tested span a range of categories. Bone6 is amedical model created from the Visible Man volumetric dataset.Sierra is a terrain database originally acquired from satellitetopography. Torp and AMR are complex CAD models of thetorpedo and auxiliary machine rooms on a nuclear submarine,each comprised of over three thousand individual objects. Bunnyis a digitized model from a laser scanner. Finally, Sphere is asimple procedurally-generated sphere created to illustratesilhouette preservation and backface simplification. Table 1details the size of each database along with the preprocessingtime for the tight-octree algorithm of Section 6.1.1 and the hybridalgorithm of Section 6.1.3. Polygon counts and error thresholdsfor specific views of each model are provided with the colorplates.
Preprocessing TimeModelCategoryVerticesTriangles(Tight Octree) (Hybrid) Bone6 Medical 3,410,391 1,136,785 445 seconds — Sphere Procedural 4,098 8,192 1.2 seconds 2.5 minutes Bunny Scanned 35,947 69,451 12 seconds 20 minutes Sierra Terrain 81,920 162,690 33 seconds — AMR CAD 280,544 504,969 121 seconds — Torp CAD 411,778 698,872 158 seconds 87 minutesTable 1: Sizes and preprocessing times of models pictured incolor plates. Note that the hybrid vertex clustering algorithm(described in Section 6.1.3) is not optimized for speed.
8. REMARKS
Polygonal simplification is a process of approximation. As withany approximation, a simplification algorithm taken to the limitshould recover the original object being approximated. Thisholds true for the HDS algorithm: as the screenspace areathreshold approaches subpixel size, the visual effects ofcollapsing vertices become vanishingly small. Note that thepolygon counts of large and complex enough scenes will bereduced even under these extreme conditions. This is important;with complex CAD models, finely tessellated laser-scannedobjects, and polygon proliferating radiosity algorithms all cominginto widespread use, databases in which many or most visiblepolygons are smaller than a pixel are becoming increasinglycommon.
View-dependent simplification is inherently an immediate-mode technique, a disadvantage since most current renderinghardware favors retained-mode display lists. Experiments on anSGI Onyx with InfiniteReality graphics, for example, indicatethat Gouraud-shaded depth-buffered unlit triangles render two tothree times faster in a display list than in a tightly optimizedimmediate mode display loop [Aliaga 97]. Relatively smallmodels will prove more efficient to render using existing staticmultiresolution techniques, since the levels of detail for eachobject can be precompiled into a display list. As scenes approachthe size and complexity of the AMR and Torp datasets, thespeedups possible in an adaptive view-dependent frameworkbegin to exceed the speedups provided by display lists. For verylarge, complex CAD databases, as well as for scenes containingdegenerate or polygon-soup models, HDS retains the advantageeven on highly display-list oriented hardware.
9. SUMMARY AND FUTURE WORK
HDS provides a framework for the dynamic view-dependentsimplification of complex polygonal environments. Thisframework is robust, operating solely at the level of vertices andtriangles and thus insensitive to topological degeneracies, andadaptive, able to merge objects within a scene or even operate onpolygon-soup databases. Any simplification method reducible toa series of vertex clustering operations can be used by thepreprocessing stage of HDS. The tight-octree spatial subdivisionmethod described in section 7.1 and the two-stage hybridapproach described in section 7.3 have been implemented anddemonstrate two such preprocessing strategies. Different run-time criteria for collapsing and expanding vertices may also beplugged into the HDS framework; the current system supports ascreenspace error tolerance, a triangle budget, and silhouettepreservation. Many optimizations of the HDS run-timealgorithm have been incorporated, including an asynchronoussimplification scheme which decouples the rendering andsimplification tasks.
Many avenues for future work remain. HDS in its currentform is limited to static scenes; even the fast spatial subdivisionschemes for vertex tree construction cannot keep up with a modelthat changes significantly in real time. An incremental algorithmfor creating and maintaining the vertex tree might allowsimplification of truly dynamic scenes. More sophisticated run-time criteria are certainly possible. The bounding spheres in thecurrent implementation can be a poor fit for the vertices of acluster, resulting in unnecessarily conservative error estimates.More sophisticated bounding volumes such as ellipsoids ororiented bounding boxes would complicate the nodeSize()operation, but could provide a much better fit. Nodes might alsobe unfolded to devote more detail to regions containing specularhighlights in the manner of [Cho 96] and [Xia 96], or toperceptually important regions using the gaze-directed heuristicsdescribed in [Oshima 96].
10. ACKNOWLEDGMENTS
Special thanks to Fred Brooks, Greg Turk, and Dinesh Manochafor their invaluable guidance and support throughout this project.Funding for this work was provided by DARPA ContractDABT63-93-C-0048, and Lockheed Missile and Space Co., Inc.Additional funding was provided by National Center forResearch Resources Grant NIH/NCCR P4RR02170-13. DavidLuebke is supported by an IBM Cooperative Fellowship; CarlErikson is supported by an NSF Graduate Fellowship.
11. REFERENCES
[Aliaga 97] Aliaga, Daniel. “SGI Performance Tips” (Talk). For moreinformation see: http://www.cs.unc.edu/~aliaga/IR-perf.html.
[Cho 96] Cho, Y., U. Neumann, J. Woo. “Improved Specular Highlightswith Adaptive Shading”, Computer Graphics International 96, June, 1996. [Clark 76] Clark, James H. “Hierarchical Geometric Models for VisibleSurface Algorithms,” Communications of the ACM, Vol 19, No 10, pp 547-554.
[Cohen 96] Cohen, J., A. Varshney, D. Manocha, G. Turk, H. Weber, P.Agarwal, F. Brooks, W. Wright. “Simplification Envelopes”, ComputerGraphics, Vol 30 (SIGGRAPH 96).
[Cosman 81] Cosman, M., and R. Schumacker. “System Strategies toOptimize CIG Image Content”. Proceedings Image II Conference(Scotsdale, Arizona), 1981.
[Eck 95] Eck, M., T. DeRose, T. Duchamp, H. Hoppe, M. Lounsbery, W.Stuetzle. “Multiresolution Analysis of Arbitrary Meshes”, ComputerGraphics, Vol 29 (SIGGRAPH 95).
[Funkhouser 93] Funkhouser, Thomas, and Carlo Sequin. “AdaptiveDisplay Algorithm for Interactive Frame Rates During Visualization ofComplex Virtual Environments”. Computer Graphics, Vol 27(SIGGRAPH 93).
[Hoppe 96] Hoppe, Hugues. “Progressive Meshes”, Computer Graphics,Vol 30 (SIGGRAPH 96).
[Kaufman 95] Taosong He, L. Hong, A. Kaufman, A. Varshney, and S.Wang. “Voxel-Based Object Simplification”. Proceedings Visualization95, IEEE Computer Society Press (Atlanta, GA), 1995, pp. 296-303.
[Kumar 96] Kumar, Subodh, D. Manocha, W. Garrett, M. Lin.“Hierarchical Backface Computation”. Proc. Of 7th EurographicsWorkshop on Rendering, 1996.
[Maciel 95] Maciel, Paulo, and Shirley, Peter. “Visual Navigation of LargeEnvironments Using Textured Clusters”, Proceedings 1995 SIGGRAPHSymposium on Interactive 3D Graphics (Monterey, CA), 1995, pp. 95-102.
[Luebke 96] Luebke, David. “Hierarchical Structures for DynamicPolygonal Simplification”. University of North Carolina Department ofComputer Science Tech Report #TR96-006, January, 1996.
[Oshima 96] Ohshima, Toshikazu, H. Yamamoto, H. Tamura. “Gaze-Directed Adaptive Rendering for Interacting with Virtual Space.” Proc. ofIEEE 1996 Virtual Reality Annual Intnl. Symposium. (1996), pp 103-110.[Rohlf 94] Rohlf, John and James Helman. “IRIS Performer: A HighPerformance Multiprocessing Toolkit for Real-Time 3D Graphics”,Computer Graphics, Vol 28 (SIGGRAPH 94).
[Rossignac 92] Rossignac, Jarek, and Paul Borrel. “Multi-Resolution 3DApproximations for Rendering Complex Scenes”, pp. 455-465 in GeometricModeling in Computer Graphics, Springer-Verlag, Eds. B. Falcidieno andT.L. Kunii, Genova, Italy, 6/28/93-7/2/93. Also published as IBMResearch Report RC17697 (77951) 2/19/92.
[Schroeder 92] Schroeder, William, Jonathan Zarge and William Lorenson,“Decimation of Triangle Meshes”, Computer Graphics, Vol 26(SIGGRAPH 92)
[Shirman 93] Shirman, L., and Abi-Ezzi, S. “The Cone of NormalsTechnique for Fast Processing of Curved Patches”, Computer GraphicsForum (Proc. Eurographics ‘93) Vol 12, No 3, (1993), pp 261-272.[Teller 91] Teller, Seth, and Carlo Sequin. “Visibility Preprocessing forInteractive Walkthroughs”, Computer Graphics, Vol 25 (SIGGRAPH 91).[Turk 92] Turk, Greg. “Re-tiling Polygonal Surfaces”, ComputerGraphics, Vol 26 (SIGGRAPH 92).
[Varshney 94] Varshney, Amitabh. “Hierarchical Geometry
Approximations”, Ph.D. Thesis, University of North Carolina Department ofComputer Science Tech Report TR-050
[Xia 96] Xia, Julie and Amitabh Varshney. “Dynamic View-DependentSimplification for Polygonal Models”, Visualization 96.
因篇幅问题不能全部显示，请点此查看更多更全内容