Invisible wrote:
> Presumably, the BSP algorithm would go
> 
> + Test ray against the left and right halfs of the top-level box.
> 
> + If either is hit, recurse into sub-boxes (as with BVH).

There are numerous optimizations available when traversing a BSP tree. Each
node is either a splitting node or a leaf node. Leaf nodes contain a list of
all objects that could potentially occupy the volume the node represents,
whilst splitting nodes contain an axis (X, Y or Z), the plane (float), and
references to two child nodes. It's important to note here that it does *not*
contain a bounding box - the only spatial information is the splitting plane
and axis.

Given a specific node, and its two children ('left' and 'right' in BSP
parlance), the traversal algorithm knows the following:

  a) any object whose bounding box, on the active axis, ends on or before
     the splitting plane, will be found by traversing the left node.
  b) any object whose bounding box straddles the splitting plane will be
     found by traversing either node.
  c) any object whose bounding box, on the active axis, starts after the
     splitting plane, will be found by traversing the right node.

Objects are listed as an index in a list, not by a pointer. The list index is
also used as an index into a bitmap (aka 'mailbox'); whenever, in the process
of traversing a BSP tree, it is necessary to perform an intersection test on
an object (recalling that an object can be listed in multiple nodes), its bit
is set. This bit is checked before attempting an intersection test and thus
repeating the test is avoided during the same traversal.

As you can see, one of the advantages of a BSP is that at each splitting node
you only have to determine if the origin of the ray is before or after the
splitting plane, and if the end point within the volume of the node is on the
left or right of the splitting plane. Thus iteration can be quite efficient.

To assist even further, two of the three values (distance from ray origin to
splitting plane, distance to bounding volume start, and distance to bounding
volume end) needed to make the iteration decision are available from the
previous level, thus (with the exception of comparisons) there is only one
floating-point calculation needed at each splitting node.

Another significant advantage worth mentioning is that it is possible to
trivially iterate the tree in a loop rather than using a recursive algorithm.

-- Chris

N.B. the volume occupied by each node is known despite the fact that no
bounding boxes are stored in the tree; it is derived from the top-level scene
bounding box - which is passed to the traversal algorithm - and the splitting
planes, which as the tree is traversed are used to iteratively reduce the volume.

Post a reply to this message