Incoherent Ray Tracing without Acceleration Structures
At Eurographics 2012, I presented an efficient incoherent ray tracing method that does not use any acceleration structures, and is optimized for AVX. It is based on the algorithm introduced in the HPG 2011 poster Efficient Ray Tracing without Auxiliary Acceleration Data Structure by Alexander Keller and Carsten Wächter.
Incoherent Ray Tracing without Acceleration Structures
Attila T. Áfra
Eurographics 2012 Short Paper
Abstract
Recently, a new family of dynamic ray tracing algorithms, called divide-and-conquer ray tracing, has been introduced. This approach partitions the primitives on-the-fly during ray traversal, which eliminates the need for an acceleration structure. We present a new ray traversal method based on this principle, which efficiently handles incoherent rays, and takes advantage of the SSE and AVX instruction sets of the CPU. Our algorithm offers notable performance improvements over similar existing solutions, and it is competitive with powerful static ray tracers.
Paper (personal copy): PDF
Paper (definitive version): available at diglib.eg.org
Slides: PPTX (with notes, video), PDF
Voxelium 
Really cool! I’m going to implement this technique this weekend and see how it compares to my kD-tree and my BIH tree.
Thanks!
-= Dave
davidneubelt
May 2, 2012 at 6:55 pm
Really great work. I’m going to implement your technique this weekend and see how it compares to my optimized kD-Tree and BIH tree.
davidneubelt
May 2, 2012 at 6:56 pm
This is cool. I’ve been thinking along these lines myself since someone posted the original paper on my blog. Here’s a few things I’d like to try if I ever had the time:
* Don’t use SAH. SAH is meant to be an approximation that works well given that we don’t know which rays we will eventually try to cast against it. However, for an algorithm like this, we *do* know exactly which rays we’re tracing against the tree so we should be able to do much better.
* There’s a few things you could try to optimize. For example, optimize num_rays*num_tris for each half of the tree so that they’re as close as possible. Screen pixel rays have a nice distribution so it’s easy to analytically compute how many rays will on each half of a splitting plane. For triangles, just pick a small number and treat the distribution of triangles as piecewise linear in between the randomly selected ones.
* Maybe we can do something with triangle area/orientation here too? Seems like a shame if we couldn’t exploit the fact that we know where the camera is.
* Maybe on the first partition (after view and backface culling) we compute some kind of rough projected size estimate for each triangle? Just a few bits worht. Maybe then subdivision could happen so that the sum of rays*projected_triangle_area is roughly the same on each side?
* Don’t do AABB splitting, split along the screen space axes. This essentially becomes hierarchical frustum tracing, but with the bonus that you’re actually adaptively subdividing the inputs as you go.
sebastiansylvan
June 27, 2012 at 4:11 am
The original technique is patented in the US by Keller and Wächter (US 20090225081).
Were you aware of this patent, and do you have an opinion about whether your technique is covered by the patent?
laurent
August 30, 2012 at 9:13 pm
Yeah, I know. Well… I’m not exactly a huge fan of software patents. 🙂
Attila Áfra
September 5, 2012 at 2:47 pm
[…] of this paper) and Keller and Wächter. Some more work was done recently on the subject by Attila Áfra. Since DACRT is so new, only a little work has been done on it so far, but it strikes me as a […]
New Ideas in Raytracing – Nathan Reed's coding blog
September 30, 2012 at 12:29 am