Conservative Visibility Algorithms

Simplify the visibility task without necessarily solving it completely.

Assumes the presence of other visibility algorithms to resolve exact visibility


View-frustum Clipping
input: any objects

if the object does not intersect the view frustum, throw it out!

use: when you can't see a lot of objects, this is worth it.
time: O(n) if used as preprocessor
preprocessing: none
coherence: object
scene footprint: total
memory footprint: one object and the view frustum
potential overdraw: occluded objects in the view frustum
clipping: partial - objects entirely outside the view frustum are clipped correctly
transparent objects: supported

Back-face Culling
input: facesets

idea: if a face of an object points away from the viewer, it must be occluded by some front-facing face.

for each face F of each object
    N = outward-pointing normal of F
    if N dot V > 0, throw away the face

GL generates normals based on the order of vertices
    glFrontFace (GL_CCW); //sets front-facing side to where vertices go counterclockwise

glEnable (GL_CULL_FACE);
glCullFace (GL_BACK);

use: lots of back faces.
time: O(f), where f is the # of faces
preprocessing: normals for each face
coherence: object
scene footprint: total
memory footprint: one face and the view vector
potential overdraw: occluded front faces
clipping: no
transparent objects: not supported

Screen-Space Subdivision  (Warnock, 1969)
input: objects that can be tested against a view frustum
    e.g., against planes.

1)for each object

now we have a list of objects incident upon the view frustum

2)if we have zero or one incident object
    we're done with visibility for this portion of the screen
    subdivide into smaller frusta, distribute our objects down to them, and recurse..
    ...unless we're at the pixel level already, in which case

we can finish a frustum if one incident object O(unknown)


use: scenes with little occlusion
preprocessing: none
coherence: image-space
scene footprint: total
memory footprint: requires an incidence list per frustum
potential overdraw: occluded objects within subfrusta
clipping: yes
transparent objects: supported

Cells and portals (Airey 91, Teller 92)
primary application/input: architectural scenes with axially-aligned walls that provide most of the occlusion.

scene divided into "occluders" (walls)  and "detail objects" (smaller objects within a room)


  1. idea: divide the scene into cells

  2. implementation: make a k-d tree by splitting along the occluders
  3. For each cell, create a list of potentially visible objects from any viewpoint in the cell
  1. determine cell of eyepoint and get its list of potentially visible objects
  2. cull down that list by clipping against the actual view frustum
  3. hand off the cell's walls and culled list to some other visibility method

How to determine the PVO's?

cell-to-cell visibility
reformulated problem: assume an algorithm to take a sequence of portals and determine whether such a line exists through them.


Find_Visible_Cells (cell C, portal sequence L, visible cell set V)
    V += C;
    for each of C's portals P
        if (Stabbing_Line_Exists (L + P))
            Find_Visible_Cells (C, L+P, V);

also store this in a "stab tree"

cell-to-region visibility

cell-to-obj visibility
for each visible region in the stab tree
    for each object in its cell not already deemed visible
        if the object intersects the region, associate it with the cell

eye-to-cell visibility
use the stab tree
if there exists a ray inside the view frustum through a portal sequence, that cell is visible

eye-to-region visibility
for each visible path in the stab tree

eye-to-object visibility
for each object visible from the source cell [hand-waving]

use: architectural walkthroughs, PhD topics
preprocessing: create k-d tree
coherence: none?
scene footprint: at runtime, the PVO for the current cell
memory footprint: the PVO list and stab tree structure for the current cell
potential overdraw: occluded objects within the PVO
clipping: dynamically, yes
transparent objects: detail objects, yes; walls, no

Selective k-d Tree Traversal (Greene & Kass, 93)
input: objects with bounding boxes that the rasterizer can handle
create a k-d tree of the data

Draw (cell) {
    scan-convert the cell's bbox
    if it's totally occluded or totally clipped, throw it out
    if we're a leaf node, draw our objects
    otherwise draw near child; draw far child

use temporal coherence:

G & K used scan conversion and their hierarchical Z-buffers for this algorithm, but it doesn't depend on them.
In their implementation, it began to win at around 45K polygons over a software implementation of traditional scan-conversion & Z-buffering

use: large data sets
preprocessing: create k-d tree
    temporal - as discussed
    image-space - scan converts objects
    object and world space - uses cells
scene footprint: objects within k-d cells within the view frustum
memory footprint: a k-d cell and its contents.
potential overdraw: occluded/clipped objects in visible cells
clipping: yes
transparent objects: supported

Hierarchical Occlusion Maps (Zhang 97)
input: whatever the rasterizer can handle
build up an occluder database  [hand-waving]

1)choose N objects as occluders (vary N according to occluder effectiveness in the previous frame)

2)draw the occluders in anti-aliased black & white
3)make a series of smaller maps using bilinear interpolation, down to 4x4 (steps 2 & 3 can be done with texturing h/w). Results in occluder fusion

 example of Hierarchical Occlusion Map
4)keep depth estimate - the farthest Z of any occluder, or farthest Z's for some screen-space subdivision
5)Get the set of potentially visible objects for this view frustum, somehow
6) For each object

- not conservative - could miss objects seen through little holes, but visually that's not so bad unless it's a bright object
- uses h/w Z buffer to actually draw everything

use: scenes with lots of occlusion from nearby objects
preprocessing: an occluder database (Coorg & Teller 96 compute this dynamically)
    temporal - supposedly uses occluders from last frame
    image-space - relies on occluder coherence to cover the scene
scene footprint: presumably traverses all the objects
memory footprint: the HOM's, an individual object to render
potential overdraw: occluded occluders; occluded objects in the view frustum have some work done to reject them
clipping: no
transparent objects: not supported