[Bf-committers] BIH progress update

[Joe Eagar]

Some very good information in your post, thanks.

Yves Poissant wrote:
>> 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).
>>     
>
> The current acceleration structure used in Blender renderer is called an 
> Octree but I think it is more like a regular grid because it uses a DDA. But 
> I haven't really took time to analyse it so I could be wrong.
>   
It's a flattened-out octree.  So the leaf nodes are forced to all be at 
the same depth level.  I'm not sure how it's actually traversed.
> The regular grid is very efficient for scenes where the primitives are well 
> distributed because traversing it, given a ray, amounts to doing a 3D 
> Digital Differential Analyser (DDA, the classic Bresenham line drawing 
> algorithm). It have trouble with large almost empty space. The so called 
> "teapot in the stadium" type of scene. In those scenes, the algorithm loose 
> a lot of time traversing empty spaces to end up in nodes that contain 
> hundreds if not thousands of primitives.
>
>   
I've read that DDA has some caveats though, in addition to what you've 
said.  One site said it has trouble with close-to-vertical (I assume 
this means close-to-z-axis) rays.  Is DDA or other uniform-grid 
techniques really better then a more flexible, adaptive octree 
approach?  In that case you have to use a ray-AABB test for traversing 
the tree, but I thought that didn't cause too many problems.
> IMO, Blender should keep the octree/regular grid but add at least another 
> acceleration structure for scenes for which the octree is not optimal. The 
> way I see it, the UI octree setting could sugest the octree resolutions 64, 
> 128, 256, 512 as we have now, and then another option that would be BVH. It 
> would actually be better if the name "octree" was changed for 
> "Accelleration" in that case. But the user could have a choice of using BVH 
> if that is more efficient for a given scene. 
>   
Seems like if the BVH consistently benchmarks better then the octree 
then it should replace it, otherwise having it as an option would be a 
good thing.

Joe