## Stackless MBVH Traversal for CPU, MIC and GPU Ray Tracing

mpeterson
Posts: 56
Joined: Fri Jan 06, 2012 3:09 pm

### Re: Stackless MBVH Traversal for CPU, MIC and GPU Ray Tracin

jbikker wrote:On CPU, the fastest practical approach is straight MBVH traversal. For first bounce diffuse rays, Tsakok's MBVH/RS is optimal. I presented a paper with an approach that outperforms both (by ~20%), but it's a complex algorithm:
http://arauna2.ompf2.com/files/cgf_article.pdf
it goes even much faster then this. stay tuned...

voxelium
Posts: 15
Joined: Fri Apr 27, 2012 11:10 am
Contact:

### Re: Stackless MBVH Traversal for CPU, MIC and GPU Ray Tracin

Paper/code or it didn't happen!

I'm also using single-ray MBVH on CPU & MIC, but for me it's better than MBVH/RS even for first bounce rays: http://www.cs.ubbcluj.ro/~afra/publicat ... _mbvh8.pdf

A ~20% speedup sounds perfectly reasonable (what about multi-threaded perf though?), but I would be really surprised if we could improve this by an order of magnitude for incoherent rays.

voxelium
Posts: 15
Joined: Fri Apr 27, 2012 11:10 am
Contact:

### Re: Stackless MBVH Traversal for CPU, MIC and GPU Ray Tracin

joedizzle
Posts: 21
Joined: Sat Dec 03, 2011 5:08 pm
Location: Nairobi, Kenya
Contact:

### Re: Stackless MBVH Traversal for CPU, MIC and GPU Ray Tracing

This is an excellent paper, I'll use it for my GPU tracer. One thing that I've noted, it seems the pseudo-code for BVH2 might lead to infinite loops for a novice implementer who might use the code as it is. I tested the code for a simple square plane which is made up of 2 triangles, meaning all nodes have same bounding box properties. This scenario will force the ray to intersect both leaf bounding boxes and do necessary intersection test, for a properly defined bvh (one node, 2 leaves i.e. 2n-1 property). As a result using the code in the paper, the ray traversal never enters the second leaf. Analysis of the code points to the problem of the leaf node code below.

Code: Select all

// Leaf node
if (!isInner(nodeId)) {
...
}

which should be

Code: Select all

// Leaf node
if (!isInner(nodeId)) {
// do necessary intersection first
...

// update parent and sibling status
parentId = nid.x;
siblingId = nid.y;
}

the above modified section of the leaf node code, resolved the issue. After a strenuous week of debugging. Lol

Has anyone encountered the similar problem?

mpeterson
Posts: 56
Joined: Fri Jan 06, 2012 3:09 pm

### Re: Stackless MBVH Traversal for CPU, MIC and GPU Ray Tracing

again: this is 10 years old crap. go with state of the art -> google is your friend !

joedizzle
Posts: 21
Joined: Sat Dec 03, 2011 5:08 pm
Location: Nairobi, Kenya
Contact:

### Re: Stackless MBVH Traversal for CPU, MIC and GPU Ray Tracing

I will definitely, in my TODO list of latest algorithms, https://github.com/joedizzle/CLTracer (I will properly organize the repository soon).

- But if you're dealing with platforms that have limited capability in dealing with stacks, the latest algorithm that I found, but with limited public available information is... "Efficient stackless hierarchy traversal on GPUs with backtracking in constant time"... http://research.nvidia.com/publication/ ... -hierarchy.

- This is well implemented in "RadeonGPU Raytracer"... https://github.com/GPUOpen-LibrariesAnd ... onRays_SDK. I might implement it once I understand the algorithm.

- The final accelerator to implement for GPU is "GPU Ray Tracing using Irregular Grids" (solves teapot in a stadium problem) - https://graphics.cg.uni-saarland.de/index.php?id=939 which seem to be quite superior.

My previous comment was just a simple identification of a problem that I haven't seen it been discussed anywhere in the internet.