Hierarchical Polygon Tiling with Coverage Masks

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 512 × 512 resolution, the algorithm tiles 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 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 4096 × 4096 grid as rapidly as hierarchical z-buffering [Greene-Kass-Miller93] tiled a 512 × 512 grid, and it effectively antialiased scenes containing hundreds of thousands of visible polygons. The algorithm requires strict front-toback 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