I have a working oct-ree raytracer and I am applying it to the sponza.
The algorithm I have designed works like this at a high level:
- Collide with the bounding box of the model, move your ray to that collision point
- Add to a stack the largest BB and the point at which the ray collided with the box
- while the stack is not empty
- Check if this voxel is occupied, if it isn't continue
- move along the ray, colliding with up to the 4 children of the voxel, add each one, along with its collision point to the stack
- If we are at the lowest level and the voxel is occupied, return the found value
To try to show a picture:
Ray collides with box, we move to collision point.
We then calculate in which of the 4 children we currently are, push it to the stack.
We move along the ray to the very next voxel, we add it to the stack.
We would move outside the box if we kept going, so we stop here and pop from the stack. This box is empty, so we skip it.
This box has something in it, so we check the children by doing the same traversal as before (we only add 2 of them).
We pop, box is empty, we skip.
We pop, box is full, this is a leaf node, we return the value.
Some features of this algorithm that should make it efficient are, we never check all 8 children of a voxel we check at most 4 at any one time. We never need to sort them, because we are using a grid traversal to collide with them, so we know which one is closer and which one is furthest from the starting point of the ray.
Despite all of this and my best efforts, the algorithm is not running in real time. A 256 resolution SVO of the sponza is rendering at 200 ms per frame on a GTX 1070, I strongly believe there are mechanisms to get this working faster but I am somewhat out of ideas.
