Re: [Algorithms] BSP tree, or what?

[Stefan S. <kef...@gm...>]

If you're talking software rasterization, a bsp coupled with a pvs is 
probably the most efficient means to render static geometry, as proven 
by quake, I guess..
But that's not a great solution for current state of the art in gpu 
rasterization, you'd probably be better off with a portal solution 
guided by occlusion queries..

As far as frustum culling is concerned, early out is the way to go..

(what do you mean when you say 'large models', do you mean a 1M poly 
dragon, or indoor fps style level, or crysis style world?)

Eric Haines wrote:
> 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
>
>