[Bf-committers] BIH progress update

[Joe Eagar]

Yves Poissant wrote:
> From: "Joe Eagar"
>
>   
>> I thought Altivec and SSE both used the same memory layout structure 
>> (though Altivec does have more SIMD registers then SSE)?  If I remember 
>> right, they both require the same 16-byte alignment in memory as well, 
>> though I could be wrong.
>>     
>
> I'm not an altivec specialist but as far as I know, they do use the same 16 
> byte alignment. You are right. But in order to be non architecture specific, 
> the abstraction should not assume that every SIMD use the same memory layout 
> structure right?
>   
Heh.  I was thinking we'd support Altivec and SSE, as that's 90% of our 
users (if not 99%).  I guess it would be a good idea to support *all* 
SIMD architectures, not just those two.  From personal experience 
though, in these sorts of things trying to make *everyone* happy is 
rarely possible without a lot of manpower.
>   
>>> Look at post #4 for the c source file. It is cool indeed. I may try it 
>>> just for my own education to see how well it can really accelerate the 
>>> ray to scene intersection process.
>>>
>>>       
>> I'd be interested to know how your tests work out.
>>     
>
> I will post my results but I don't plan to try that until I have a nice 
> really efficient BIH or BVH running.
>
>   
>>> If you are interested in SSE implementations, you should take a look at 
>>> Arauna : http://igad.nhtv.nl/~bikker/ and look at his kdtree.c source 
>>> code.
>>>
>>>
>>>       
>> I'll take a look, thanks.
>>     
>
> His kdtree source code is a bit of a misnomer. It actually have code for 
> traversing the kdtree or the BVH. One or the other are selectable. At one 
> point, he had a BIH but he scrapped it and implemented a SAH BVH. 
> Apparently, the BVH was 26% faster than the BIH. I still have the source 
> with the BIH but as you will see, it is so heavily SSE that it is not 
> usefull for my needs. It is still very interesting to look at though.
>
> Yves 
>   
I've not read about SAH BVH (just glanced at BVH once a while back).  
I'll have to read up about it.

Also, there are some common things about spatial trees that are often 
missed in implementations.  A common technique in any sort of search 
tree is links between branches; however this isn't done all that often 
in spatial trees (at least as far as I could tell).  In the case of 
spatial trees these links are basically pointers between adjacent nodes. 
The advantages of these "neighboring" links is they reduce the time 
spent traversing the tree.  The tree essentially becomes a cyclic graph, 
thus once you've identified the starting node of a ray you can trace 
that ray through the graph fairly quickly.  I once had the idea of even 
using a 3d grid to speed up finding the starting node of a ray, but 
never tried it (the idea being that each grid cell would have a 
reference to the smallest node that contained the entire cell).

My own tests with an octree I wrote appeared to show a massive speedup 
with this technique (I'm not an expert, so I'm not sure how valid my 
reference implementation was).  Links between nodes don't really give an 
asymptotic advantage, but they do nonetheless give significant practical 
benefits (at least in my somewhat amateurish tests :) ).  I think the 3d 
grid idea might be worth checking out, too (the idea being to reduce the 
tree traversal time to as far below the O(logN) upper bound as possible).

Joe