It is very important to have an efficient implementation for finding out which triangle each ray collides with (instead of a naive brute force approach). Just like a ray tracer or a physics engine, this is done with an acceleration structure.
Often programmers are keen to use bounding volume hierarchies or oct trees. In my PS3 Ray tracer, I used a BVH. Therefore for this project I wanted to use an oct tree, in order to learn something new (also see the other side of the fence).
Linear Oct Tree
An oct tree is a way of storing objects in a hierarchy. This allows hierarchical tests e.g. test the outer most cube, then test its sub cubes, test their sub cubes after that, and so forth. This makes a huge impact on performance. Several hundred of thousands of tests can be reduced to a mere few thousand.
Its arrangement is like so: one giant outer most cube contains all the objects (sub cubes). That giant cube is split into eight (thus its name) sub cubes. Each one of these sub cubes is also split into eight sub cubes. This pattern is repeated until the smallest cubes are of the desired size. The whole oct tree is stored in a tree like structure, thus it inherits linked list like performance.
This can be alleviated by storing it in a hash table instead. This seems to create a problem straight away. From a given point in space how do you access that sub cube / node? Well, our good friend maths has the answer; Morton Codes
Morton codes / Z-order curves are a way of mapping multidemsional data to a single dimension. Therefore, its possible to map our three dimensional points to a one dimensional key.
Morton Codes are integer numbers created from interleaving bits. Each bit indicates whether the point we are mapping is above or below the halfway line on a particular axis in an area.
Consider this two dimensional Morton code (in binary): 100. The very first 1 is a marker bit in order for us to work out the depth / where to start. The left most zero tells us our point is below halfway on the X axis. The right most zero tells us our point is below halfway on the y axis.
So, say this Morton Code was for a square that is 16 units in length on each side (doesn't have to be equal for the Morton key to work). Our example key of, 100 identifies a point that is less than 8 on the X axis, and less than 8 on the Y axis. Now, consider 110, it represents a point that is more than 8 on the X axis(first one from the right) and less than 8 on the Y axis (the 0). That's not very accurate at all. Using the marker bit (the very first 1) as a reference we can map even more accurate points / areas.
For example, 11101 maps to; X being more than 8, Y being more than 8 (the middle 11 to the left of 0), then in that sub square (8 to 16 on X and Y) X is less than halfway (12) and Y is more than halfway (the right most 01). Therefore 11101 maps to: X >= 8 && X <= 12 and Y >= 12 && Y <= 16.
Using this technique in the path tacer; we can convert our 3D point into a key, then ask the hash table for the data, then check for collisions only against primitives in that sub cube (opposed to all primitives).
Traversing a Linear Oct tree is semi top down; it's referred to as "Walking". The process is as follows:
• A primary ray is tested against the outmost cube (which is the only cube that doesn't contain primitives)
• Calculate the point at which the ray collides which the cube.
• Offset that point along the ray's direction vector by a very tiny amount.
• Obtain a list of primitives from the hash table look up (from the Morton Code of the offset point).
• Check for collision against them.
• If no collisions are found, use our earlier cube collision data (far collision point) to advance into the next sub cube (via offseting point by tiny amount).
The linear oct tree (including a hash table) and Morton codes are completed. I want to fine tune it so that the checksum of the images (from the linear oct tree) matches the checksum from the brute force approach.
However, I fear this may not be possible, since the algorithm seems ad hoc in places.
Realistic Ray Tracing, Second Edition by Peter Shirley, R. Keith Morley
An Introduction to Ray tracing edited by Andrew S. Glassner
Real-Time Collision Detection by Christer Ericson