Original Post
Here's another optimization idea to chew on. In a recent paper by Havran (and others) he explains a way to get a modest speedup by 'shaft culling'. In this paper he also points to an older paper, 'Ray Shooting using Longest Common Traversal Sequences'. I checked out that paper, and it's quite interesting. Basically, what he proposes is this: If you shoot two rays in the scene, and these rays both traverse the same nodes, then it is guaranteed that a ray that sits inbetween these rays is also traversing these nodes (in a kd-tree). More generally: If the first n nodes traversed by the two rays are equal, then the first n nodes can be skipped for rays between these two rays. It can be made more efficient by using a 'shaft': A pyramid shape, where you test the 4 corner rays. All nodes traversed by the four corner rays can be skipped by the interior rays. The disadvantage: detecting how many nodes are traversed by all rays is quite expensive. Besides, starting the interior rays half way is a nightmare, since they will still need the full traversal stack that the corner rays produced up to the point where they entered different nodes. Now that was 2000. It's 2005 now, and there's SIMD packet tracing. This opens interesting possibilities: Suppose we put the four corner rays in a packet. As long as the entire packet travels through the same nodes (something that is already being tested in Wald's version of the kd-tree traversal), we know that all interior rays could also start there. Nice twist compared to the 2000 paper is that we have the stack handy. So as soon as the packet is not coherent anymore (i.e., some rays are disabled while traversing), the interior rays are turned into packets, and traced from that point on. The advantage of this approach is that in general, many rays will just skip open space. They will simply start where the detail starts. And shafts consisting of 16 rays is only the beginning: Imagine that we skip the large open areas by casting 16x16 rays. As soon as this shaft is no longer coherent, it is split in 4 8x8 shafts. These are split later on in 4x4 shafts, and finally we have 2x2 rays in a single packet. This could seriously bring down the rendering times. One catch: The interior rays need near and far values. These need to be calculated once the interior rays are fired. And, the stack needs to be copied for these rays (but that's just a few bytes). I still have to try this, and I do some other potential problems, but it sure looks nice. :) - Jacco.