Re: [Algorithms] BSP tree, or what?

[Jon W. <hp...@mi...>]

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

For static stuff, a kd-tree might work just fine -- sounds like that's 
similar to the axis aligned plane tree you're using.

For moving stuff, if only a dozen things are moving, stuff them in a 
list/vector. If more things are (potentially) moving, then a loose 
octree has served us well.

For indoors scenes where you want PVS, cells with portals are usually 
the optimal way to go. No bounding hierarchy tree will be able to cull 
out walls behind walls behind walls (or valleys behind hills behind 
valleys...) and even with early Z tests, if you end up pseudo-filling 
the entire screen a dozen times, that will hurt your frame rate.

All of those mechanisms can be improved, from a rasterization point of 
view, by adding dynamic occluders (ideally with occluder fusion). I know 
that the IHVs say that their cards are efficient enough that you 
shouldn't bother, but that's only true for the "GTX" versions -- the 
64-bit versions that end up in the laptops that most of the buying 
public are buying, are still very fill rate sensitive.

Sincerely,

jw