| Hierarchical Polygon Tiling with Coverage Masks |
| Author |
Ned Greene |
| Book |
Proceedings of SIGGRAPH 96 |
| Publisher location |
New Orleans, Louisiana |
| Publish date |
August 1996 |
| Editor |
Holly Rushmeier |
| Caption |
|
| Govt order number |
ISBN 0-201-94800-1 |
| Header |
|
| Publisher |
ACM SIGGRAPH, Addison Wesley |
| Journal |
|
| Keywords |
|
| Language |
SIGGRAPH.1996.06 |
| Label |
Greene:1996:HPT |
| Math review number |
|
| Volume number |
|
| Other |
|
| Pages |
65-74 |
| Corporate author |
|
| Type |
|
| Series title |
Computer Graphics Proceedings, Annual Conference Series |
| Notes |
|
| Volume |
|
| Location |
|
| Abstract |
We present a novel polygon tiling algorithm in which recursive subdivision of image space is driven by coverage masks that classify a convex polygon as inside, outside, or intersecting cells in an image hierarchy. This approach permits Warnock-style subdivision with its logarithmic search properties to be driven very efficiently by bit-mask operations. The resulting hierarchical polygon tiling algorithm performs subdivision and visibility computations very rapidly while only visiting cells in the image hierarchy that are crossed by visible edges in the output image. Visible samples are never overwritten. At 512x512 resolution, the algorithm tiles as rapidly as traditional incremental scan conversion, and at high resolution (e.g. 4096x4096) it is much faster, making it well suited to antialiasing by oversampling and filtering. For densely occluded scenes, we combine hierarchical tiling with the "hierarchical visibility" algorithm to enable hierarchical object-space culling. When we tested this combination on a densely occluded model, it computed visibility on a 4096x4096 grid as rapidly as hierarchical z-buffering tiled a 512x512 grid, and it effectively antialiased scenes containing hundreds of thousands of visible polygons. The algorithm requires strict front-to-back traversal of polygons, so we represent a scene as a BSP tree or as an octree of BSP trees. When maintaining depth order of polygons is not convenient, we combine hierarchical tiling with hierarchical z-buffering, resorting to z-buffering only in regions of the screen where the closest object is not encountered first. |
| TOC |
|
| Total pages |
|
| Price |
|
| Copyright |
Copyright (c) 1996 Association for Computing Machinery |
| Extra |
|
|
