∗∗××××cover-age masksAbstract1 INTRODUCTIONCR Categories:Keywords:Ned GreeneApple ComputerHierarchical Polygon Tiling with Coverage MasksContact author at [email protected],Apple Computer, 1 Infinite Loop, Cupertino, CA 95014We present a novel polygon tiling algorithm in which recur-sive subdivision of image space is driven by coverage masksthat classify a convex polygon as inside, outside, or inter-secting cells in an image hierarchy. This approach permitsWarnock-style subdivision with its logarithmic search prop-erties to be driven very efficiently by bit-mask operations.The resulting hierarchical polygon tiling algorithm performssubdivision and visibility computations very rapidly whileonly visiting cells in the image hierarchy that are crossedby visible edges in the output image. Visible samples arenever overwritten. At 512 512 resolution, the algorithmtiles as rapidly as traditional incremental scan conversion,and at high resolution (e.g. 4096 4096) it is much faster,making it well suited to antialiasing by oversampling andfiltering. For densely occluded scenes, we combine hierarchi-cal tiling with the hierarchical visibility algorithm to enablehierarchical object-space culling. When we tested this com-bination on a densely occluded model, it computed visibilityon a 4096 4096 grid as rapidly as hierarchical z-buffering[Greene-Kass-Miller93] tiled a 512 512 grid, and it effec-tively antialiased scenes containing hundreds of thousandsof visible polygons. The algorithm requires strict front-to-back traversal of polygons, so we represent a scene as a BSPtree or as an octree of BSP trees. When maintaining depthorder of polygons is not convenient, we combine hierarchicaltiling with hierarchical z-buffering, resorting to z-bufferingonly in regions of the screen where the closest object is notencountered first.I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism - Hidden line/surfaceremoval; I.3.3 [Computer Graphics]: Picture/Image Gener-ation.tiling, coverage mask, antialiasing, visibility,BSP tree, octree, recursive subdivision.Polygon tiling algorithms have been an important topic incomputer image synthesis since the advent of raster graph-ics some two decades ago. Their purpose is to determinewhich point samples on an image raster are covered by thevisible portion of each of the polygons composing a scene.Currently, polygon tiling software running on inexpensivecomputers can render point-sampled images of simple scenesat interactive rates. The fastest tiling algorithms have beencarefully tuned to exploit image-space coherence by usingincremental methods wherever possible. However, they failto exploit opportunities for precomputation and they wastetime tiling hidden geometry. There is a need for more effi-cient tiling algorithms that effectively exploit coherence andprecomputation to enable efficient culling of hidden geome-try and efficient tiling of visible geometry.The dominant polygon tiling algorithm in use today is in-cremental scan conversion. Typically, raster samples on apolygon’s perimeter are traversed with an incremental line-tiling algorithm. Edge samples on each intersected scan-line define spans within a polygon, which are then traversedpixel-by-pixel, permitting incremental update of shading pa-rameters and, in the case of z-buffering, depth values. Vis-ibility of samples can be determined by a) maintaining az-buffer and performing depth comparisons [Catmull74], b)traversing primitives back to front and writing every pixeltiled [Foley-et-al90], or c) traversing primitives front to backand overwriting only vacant pixels [Foley-et-al90]. With in-cremental scan conversion, the cost per pixel tiled is verylow because incremental edge and span traversal effectivelyexploits image-space coherence.One problem with traditional incremental scan conver-sion is that it must tile every sample on every primitive,whether or not it is visible, and so it wastes time tiling hid-den geometry. This is not a big problem for simple scenes,but for densely occluded scenes it severely impairs efficiency.Ideally, a tiling algorithm should cull hidden geometry effi-ciently so that running time is proportional to the visiblecomplexity of the scene and independent of the complexityof hidden geometry.The Warnock subdivision algorithm [Warnock69] ap-proaches this goal, performing logarithmic search for visibletiles in the quadtree subdivision of a polygon. If scene prim-itives are processed front to back, only visible tiles and theirchildren in the quadtree are visited. Although Warnock sub-division satisfies our desire to work only on visible regions ofprimitives, the traditional subdivision procedure is relativelyslow and consequently, this approach is slower than incre-mental scan conversion, except for densely occluded scenes.Neither traditional incremental scan conversion nor Warnocksubdivision is well suited to tiling scenes of moderate depthcomplexity.A second shortcoming of incremental scan conversion isthat it spends most of its time tiling edges and spans, travers-ing these features pixel by pixel, even though all possi-ble tiling patterns for an edge crossing a block of samplescan be precomputed and stored as bit masks called. Then the samples that a convex polygon coverswithin a block can be quickly found by compositing the cov-erage masks of its edges. Previously, this technique has beenANDING××ק§§§§§§§§×2 PREVIOUS WORK2.1 Warnock Subdivision2.2 Coverage Masks3 TRIAGE COVERAGE MASKStriagecoverage masks in-side outside intersectingoccupieddepth-priority Warnock algorithmarea samplingused to estimate coverage of polygonal fragments within apixel to accelerate filtering [Carpenter84, Sabella-Wozny83,Fiume-et-al83, Fiume91].Here we present a polygon tiling algorithm that combinesthe best features of traditional algorithms. The key innova-tion that makes this integration possible is the generaliza-tion of coverage masks to permit their application to imagehierarchies. The generalized masks, which we call, classify cells in the image hierarchy as, , or an edge. This enables them todrive Warnock-style subdivision of image space. The resultis a hierarchical tiling algorithm that finds visible geometryby logarithmic search, as with the Warnock algorithm, thatexploits precomputation of tiling patterns, as with filteringwith coverage masks, and that also uses incremental meth-ods to exploit image-space coherence, as with incrementalscan conversion. The