Re: [Algorithms] BSP tree, or what?

[Willem H. de B. <wi...@wh...>]

There was one project that I worked on which featured both indoor
as well as outdoor scenes. These scenes were pretty much given to
me as 'polygon soup' and then collected together into fairly big
'chunks' of geometry that did not have any real restrictions on them
in terms of how much volume (or area) it would take up in the world.
The world was essentially static.

The approach I ended up taking was to create a kD-tree (splitting
at the midpoints of the subtree's AABB's) and then essentially
subdivide 'into' the chunks until I reached a certain threshold number
of triangles, and then make the rest into a leaf in the tree, to
be preprocessed so that these could be fired off to the GPU.

IIRC (and this is 3 years ago), there was a reasonable amount of
culling going on, and so the kD-tree approach worked quite
well. There is some benefit in balancing the tree. I remember an
old Graphics Programming Methods article that goes into some
depth on how to balance a kD-tree, which worked rather well.

Then I experimented with occlusion. This is where we ended
up not gaining much in terms of performance. Since these were
outdoor and indoor scenes I took a general approach and
1) got artists to place 'occluder meshes' at appropriate parts
of the scene, and 2) tried my hand at building occluders
from buildings and then fusing these together. I remember this
being quite messy and there being lots of ugly special cases.

Neither of these occluder approaches were really worth the effort
in retrospect.

The idea of using AABB trees and people's positive experience
with them sounds quite interesting - something to try next time. :)

Cheers,
Willem

----- Original Message ----- 
From: "Eric Haines" <eri...@gm...>
To: "Game Development Algorithms" <gda...@li...>
Sent: Wednesday, June 04, 2008 2:35 PM
Subject: [Algorithms] BSP tree, or what?


> 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
>
>
> -------------------------------------------------------------------------
> Check out the new SourceForge.net Marketplace.
> It's the best place to buy or sell services for
> just about anything Open Source.
> http://sourceforge.net/services/buy/index.php
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>