Last time we saw several elegant object-precision or hybrid algorithms

However, difficult to justify superlinear processing when models get huge.

Let's review the visibility questions we posed last time:

• How can invisible scene primitives be eliminated efficiently? Or...
• How can visible scene primitives be identified efficiently? Or...
• How can hybrid/alternative versions of the problem be posed? (Later.)

Parameters:
  model size n, screen resolution r = w *h

Desiderata:

• Object precision (continuous)or screen precision (discrete framebuffer)?
• Running time
• Storage overhead (over and above model storage)
• Working set:
• memory locations referenced over interval delta t, worst case
• basically, how much memory is required to avoid excessive VM I/O
• Overdraw (also depth complexity):
• how many times a typical pixel is written by rasterization process

  

• Screen-space subdivision (Warnock's algorithm)
• Working set size: O(n)
• Storage overhead: O(n lg r)
• Time to resolve visibility to screen precision: O(n *r)
    (though lots of optimizations possible -- worth another look!)
• Overdraw: none
• BSP construction and traversal (ordering algorithm)
• Working set size: depends on definition: O(1), O(lg n)
• Storage overhead: O(n^2)
• Time to resolve visibility to object precision: O(n^2)
• Overdraw: maximum
• Z-buffering
• Working set size: O(1)
• Storage overhead: O(1)
• Time to resolve visibility to screen precision: O(n)
• Overdraw: maximum

The notion of conservative visibility oracles arose:
  Prefix pipeline with data structure & algorithm which efficiently
  discards invisible polygons, and/or identifies visible polygons
  Assume an ordinary z-buffered pipeline handles rendering
  (that is, resolves visibility at screen resolution -- no fragments)
  But: if oracle is to get the correct picture, what constraint
  must it observe? This is called conservative culling.

Example conservative visibility oracles:

• Report whole model visible every frame
• Cost?
• Satisfies superset criterion? By how much?
• Use analytic solution from last lecture(e.g.,
    report exactly the set of visible fragments)
• Cost?
• Satisfies superset criterion? By how much?
• BSPtree
• Is it a visibility oracle?

Early conservative visibility oracle: hierarchical frustum culling (Garlick et al., 1990)

Pseudocode:

Cull (Frustum F, Tree T) {
  if ( F^T != null ) { // if F and T are not spatially disjoint
  if ( T is a leaf )
  render portion of T's contents within F // how ?
  else { // examine subtrees (e.g., positive, negative halfspaces)
  Cull ( F, T->lochild )
  Cull ( F, T->hichild)
  }
  } // if F ^T ...
} // Cull

Reduces overdraw somewhat, on average (for example beyond far
  clipping plane) but does not detect occlusion of one polygon by another
  (For what kind of models/scenes would this algorithm
  be ideal -- about as well as you can do?)

... and there can be a whole lot of occlusion!

Previous Meeting .... Next Meeting ... Course Page

Last modified: Nov 1998