Simplify the visibility task without necessarily solving it completely.

Assumes the presence of other visibility algorithms to resolve exact visibility

in practice, OpenGL's scan-conversion & Z-buffering

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

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

1)for each object

classify it as incident or out of the view frustum
 

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

hand off incident objects to another method (such as raycasting)

is in front of all the others AND
is convex AND
covers the frustum

DEMO

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

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

Setup

1. idea: divide the scene into cells

implementation: make a k-d tree by splitting along the occluders
2. 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?

static (preprocessing stage)
"what can you see from a given cell?"
• cell-to-cell
• cell-to-region
• cell-to-object
dynamic (dependent on view frustum)
"what can you see from the instantaneous viewpoint and view frustum?"
• eye-to-cell
• eye-to-region
• eye-to-object
 

cell B can see cell A iff there exists a "stabbing line" from a portal in cell A to a portal in cell B, unoccluded by any walls.

DEMO

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

clip the frustum by each successive portal; the remaining pyramidal region is the visible region for that cell.

intersect that object with the visible region of the cell
 

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

runtime
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:

• keep track of all the cells we drew in the previous frame
• re-scan-convert the cells; if they're totally behind, throw them out
• draw all the objects from the remaining cells and mark their cells as drawn
• now do the regular algorithm, avoiding marked cells

use: large data sets
preprocessing: create k-d tree
coherence:
    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

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

• criteria: size, rendering complexity, redundancy
• temporal coherence: use the last occluder list? [hand-waving]

 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

1)use the depth estimates to determine if  all or part of the object is in front of the occlusion map; if it's in front, just draw the object

2)otherwise, try to reject the object as occluded
Get the object's screen-space projection and read off its corresponding values in the HOM

for each pixel we need to check in the HOM:

if opacity > 1.0
    return occluded
else
    traverse to a lower level in the hierarchy

use: scenes with lots of occlusion from nearby objects
preprocessing: an occluder database (Coorg & Teller 96 compute this dynamically)
coherence:
    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