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: enter image description here

  • 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.

enter image description here

  • $\begingroup$ I don't know about SVO but the fastest idea is just to use 3D texture, memory is less and less a concern. $\endgroup$
    – mdkdy
    Commented Jan 16, 2022 at 12:25
  • $\begingroup$ You will run out of memory almost instantly, you cannot hold a 4096 res texture in memory in most systems. $\endgroup$
    – Makogan
    Commented Jan 16, 2022 at 19:35
  • $\begingroup$ Well yes if voxel size is very small, I managed to fit in few hundred megabytes with nice quality though smaller voxels would help with light leak. $\endgroup$
    – mdkdy
    Commented Jan 16, 2022 at 20:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.