Ray Tracing Acceleration

There are a number of ways to accelerate ray tracing which mostly fall into two categories: (a) Reduce the number of rays we trace. (b) decrease the number of intersection tests

Of course you can also increase the efficiency of your ray / object intersections but as that problem is largely solved and optimized it can be ignored.

For (a) a subsampling method is often used which operates on the primary rays. The problem is that it can produce artifacts especially with lots of small objects.

For (b) a variety of space partitioning methods exist which reduce the number of objects a ray is intersected with, the most popular being the kd tree.



Both a and b methods do work very effectively in standard ray tracing on single or multiple core cpu's. Although the benefits of subsampling decrease rapidly with scene complexity. On a scene with a lot of moving objects the kd tree needs to be recalculated every frame.

Implementing these acceleration structures for my simple scene on a cuda device resulted in some interesting results.  My fps dropped by about 8 for the standard scene with 75 objects but as I increased the object count the fps did not drop off as quickly as the brute force ray tracing method used before. This is to be expected as the number of ray / intersect tests is kept down.  I think the drop in initial frame rates is a result of the warps diverging as we traverse the tree. This can clearly be optimized and just fitting an acceleration structure to my current implementation is a very poor method of using the devices parallel processing capabilities.

The biggest single improvement in speed has come from using the kdtree on the shadow rays. As every intersection results in 2 shadow rays (in my scene)  the amount of shadow rays in the scene quickly explodes. Remember for shadow rays you dont have to determine where on the object surface the ray intersects just if it intersects at all.

While I've been playing with kdtrees I cant help thinking there is a better way. I have a couple of ideas - so watch this space :)