Re: [Algorithms] BSP tree, or what?

[<gd...@er...>]

Hi Eric, 

We've been using various kind of AABB trees for static and dynamic triangle 
meshes (deformable objects), broadphase collision detection, view frustum 
culling. 

Static AABB trees with memory optimized layout that allow for fast stackless 
traversal in parallel on SPUs. It supports fast and cache-friendly local and 
global refit operations. 

Dynamic AABB trees: we have also implemented a very fast dynamic AABB tree, 
that rebalances itself, rather then a refit. For broadphase purposes, we 
keep two of those dynamic trees, and object can move from one to the other 
tree. 

We integrated this into Pierre Terdiman's CDTestBenchmark, and the dynamic 
AABB tree implementation outperforms OPCODE Box Pruning. All of this is 
available in latest open source Bullet 2.69 at http://bulletphysics.com 

Is your implementation exclusive to GPU, or do you consider a CPU 
implementation? Perhaps we can do some performance comparisons/benchmarks 
between BSP and other methods (AABB trees etc)? 

Thanks,
Erwin 

 


Eric Haines writes: 

> I should have been clearer: yes, I'm using the GPU. By BSP trees I mean 
> axis-aligned hierarchical trees, not the polygon-plane-aligned 
> old-school Doom stuff. By large I mean lots of objects, say 10K on up, 
> each object a mesh of say 20 to 20k polygons. Scene type is 
> "unpredictable", right now I'm just looking at general solutions for 
> large scenes: could be indoor architectural, or just "complex stuff". 
> I'm looking to see if there's a good "this scheme works for most data 
> sets in some reasonable way" choice. Certainly things like terrain 
> rendering have their own specialized solutions (CLOD, etc. - DICE's from 
> SIGGRAPH 2007 seems very cool, on a constrained quadtree), I understand 
> that. 
> 
> Eric 
> 
> 
> Stefan Sandberg wrote:
>> 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?)
>  
> 
> -------------------------------------------------------------------------
> 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