Review : Hmm, good ideas, but awful grammar.

--------------------------------------

Notes on the fast BeamTree algorithm
Charles Bloom
1-17-2000
--------------------------------------

The goal of the fast beamtree algorithm is for it to
be so lean that it can never ever possible slow down the
renderer.  The consequence is that full occlusion is not
done; eg. the beamtree does not contain all polygons, and
does not occlude all polygons wich could be occluded.
Let's examine this.  Once a beamtree has N polygons in it,
it has a cost of O( log(N) ) to test, the result is that
the bigger it gets, the more expensive it is to test a
polygon and see that it is visible (occlusion test that
report non-visibility can be O(1)).  So, the main thing we
can do is only add a few polygons to the beamtree, resulting
in a total cost off O( N ) instead of O( N * log(N) ).
In most interesting cases, only a few large polygons are the
primary occluders (for example, when you stand right in front
of a wall), so that if we can add only these few large
polygons, we will get most occlusion, while only having a
few polygons in the tree.

Now, when a beamtree contains all polygons and those polygons
are sorted front to back strictly, then the rendering algorithm
goes as follows :
	1. clip the polygon into the beamtree, cutting it against
		all old polygons
	2. for all of the new polygon pieces that land in an
		empty part of the beamtree:
	3. render the polygon piece
	4. add it to the beamtree.
(note that if the four edges of the screen are added to the
beamtree first, this does the clipping for you too).  This is
quite elegant and provides for full exact occlusion, but we
cannot use it, because we will only add a few polygons to the
screen, and our polygons will not be strictly front to back,
only roughly sorted front to back.

So, conceptually, our beamtree algorithm must be as follows :
For a given polygon, estimate if it is a good occluder.  If so,
add it to the beam tree. Associate a "Z" value with this polygon
equal to the farthest Z of any part of the polygon (we treat the
polygon as 2d in screen space with just one Z value for the whole
polygon).  Now, to test a polygon against the beamtree, we
simply find all the beamtree leaves that it lies in.  We check the
closest Z depth of the polygon against the value in the leaf : if
the Z of the polygon is closer than that in the leaf, it is
visible.  Note that if a polygon is visible, we can early out of
the beamtree tests quickly (once it is visible in any portion, we
render the whole thing), so that our beamtree is very fast when it
is failing to occlude anything.

We don't actually test all polygons to be rendered against the
beamtree, but rather test bounding boxes of groups of polygons
against the tree.  The test against the tree is typically not
worth the compuation unless we might occlude a large polygon or
quite a few polygons.  Note that if the front three faces of a
bounding cube are occluded, then everything inside is occluded.
(we actually just use the screenspace bounding polygon of the cube).

In practice, a 2d BSP is used to construct the beamtree, so that
adjacent polygons can abutt exactly (by sharing a node in the tree).
Also, polygons to be rendered are not actually checked against the
tree, but rather their bounding circle or bounding rectangle in
screen space is used for speed.

Let me say it again to try to make this clear:

imagine that you've already found the good occluders and added them to
the "occlusion structure" (OS) (the beamtree, or whatever). then,
descend the oct-tree:

take the AABB of the current oct-tree node and do the heirarchical
  test against the frustum; stop if it's all-out
if it's partially inside, render the contents of the node
if it's full inside, test the AABB against the OS and
  render the contents only if visible.

So, the only part that we need the front-3 faces for is this test
against the OS.  To do that we just project the corners of the AABB
to screen space, then take the quads that make up the 3 front faces
and see if any part of them is visible (eg. lands in an empty part
of the beam-tree).

----------------------------------------------------------
Unsolved issues :

1. Faster bounding cube test?  Currently requires transforming
the eight corners of the cube, more expensive than we'd like.

----------------------------------------------------------
(addendum Jun 6:)

The cool way to drive this "loose beamtree" is with a whole-scene
oct-tree.  You start with a camera frustum, with which you can
easily (heirarchically) tell which cubes off the octtree are in
the frustum; this gives you your first level of visibility culling.

Next, you visit all the visible octtree cubes near the camera (this
is a simply heirarchical descent).  In all those cubes, you tell
the objects that they may add beamtree occluders after they render.
(there are no beamtree tests).

For the rest of the visible octtree cubes, you test the three font
faces sides of the cube against the beamtree; if they are not all
occluded, then you render the objects contained in the cube.
You should use the "loose octtrees" of Thatcher Ulrich to make sure
that each object is wholy contained in one and only one octtree node.
(you can compute which three faces will be the front-facing ones
only once per frame, it's the same for every cube).  See
http://www.tulrich.com/geekstuff/partitioning.html

How do objects add to the beamtree?  Basically, they have a bunch
of OBB's (oriented bounding boxes) which are as large as possible
which being entirely enclosed by the polygons of the objects.  They
then simply add the front faces of these OBB's to the beamtree.

Note that if we do this, we don't even need depth comparisons in
the beamtree (eg. no Z's).  Instead, it's just a way of drawing 2d
regions that are a binary occlusion mask.  It's equivalent to
creating a very elaborate frustum for culling out the objects in
octtree cubes away from the camera.

----------------------------------------------------------