[Algorithms] BSP tree, or what?

[Eric H. <eri...@gm...>]

I've been surveying the literature for how best to display large models 
when using rasterization. Frustum culling, LOD, occlusion culling - 
sure. What I'm most interested in is what sort of efficiency structure 
is best to use for large models. I personally favor a BSP tree, with 
each object's bounding box getting inserted in one location in the tree 
(unlike ray tracing, which has different needs, where objects are often 
pushed towards the leaves and duplicated). BSPs can be used for frustum 
culling, the cells can be used with LOD (too small a cell, toss it out 
or approximate by drawing a box), and with the BSP providing front to 
back traversal, occlusion culling can also be folded in fairly 
effectively. Even without occlusion culling, front to back allows less 
pixel shader evaluation, etc.

My questions for the day:
1) Is there some other scheme I should be seriously considering? Spheres 
for bounding volumes are quicker to test for frustum culling, but the 
spheres themselves seem pretty inefficient for arbitrary groups of geometry.

2) Bounding box hierarchies might actually be better than BSP trees, but 
it's trickier to form them well. Really, I like using BSP tree formation 
algorithms that allow the creation of an efficient hierarchy, but for 
rasterization I can afford to let the two child boxes of a parent 
actually overlap - a strict front-to-back ordering is not required, it's 
more that you want the child bounding boxes to be as tight as possible. 
Efficient bounding volume creation for the purposes of rasterization 
seems underexplored, but maybe I'm missing out on someone's work here.

3) Memory locality is a big deal nowadays. Do people have any experience 
with van Emde Boas schemes to localize chunks of the tree, or other 
methods to improve locality (e.g. flattening the tree)? These seem good 
on paper, but I'd like to know before I spend a few days implementing 
and find no gain whatever (or, hopefully, large gains). The problem with 
BSP is that, if you want front to back traversal, the order of traversal 
does change depending on the view.

4) I'm favoring spending time making an efficient BSP because most of my 
data is static, not animated, so the time I put into making a BSP is 
paid back. However, the build cost of a BSP is noticeable. Animated 
objects I'm currently just putting in a list without any efficiency 
structure. For animations involving a lot of objects, I've wondered if 
something like loose octrees or some other "quick to create" efficiency 
structure would pay off in terms of time saved culling vs. time spent 
forming and maintaining them.

Anyway, I'm interested in anyone's practical experiences here. As usual, 
I suspect it's a case of "it all depends", but I'd love to know what 
people have found useful and useless.

The one cute little result I thought I'd share: for ray-tracing, the 
surface area heuristic (SAH) gets used in forming efficient BSP trees. 
That is, the efficiency of a split of a box is measured by taking the 
number of objects in a child box times the area of the child's box. The 
lower the summed value for the two children and for objects split by the 
cutting plane, the more likely the split is gaining you efficiency. 
What's interesting for rasterization is that frustum culling is a 
process of planes intersecting boxes, unlike ray tracing, where it's 
rays vs. boxes. When shooting rays, you want to use the surface area of 
the box for the relative probability a random ray hits the box. When 
testing planes, you want to use the mean width of the box. The mean 
width is proportional to the sum of the lengths of the sides of a box 
(or the radius of a sphere). Using the mean width to decide on the 
efficiency of a box gives me more what I would expect for a BSP tree for 
rasterization: the leaf nodes tend to have 10 children or so, as further 
splitting is less effective than with traditional SAH. This matches my 
own experience with forming such hierarchies by simple median-split 
schemes: the leaf nodes are less effective if you try to chop them too fine.

All for now,

Eric