<p>I have a working oct-ree raytracer and I am applying it to the sponza.</p>
<p>The algorithm I have designed works like this at a high level:</p>
<ul>
<li>Collide with the bounding box of the model, move your ray to that collision point</li>
<li>Add to a stack the largest BB and the point at which the ray collided with the box</li>
<li>while the stack is not empty</li>
<li>Check if this voxel is occupied, if it isn't continue</li>
<li>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</li>
<li>If we are at the lowest level and the voxel is occupied, return the found value</li>
</ul>
<p>To try to show a picture:
<a href="https://i.sstatic.net/tsHhD.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/tsHhD.png" alt="enter image description here" /></a></p>
<ul>
<li><p>Ray collides with box, we move to collision point.</p>
</li>
<li><p>We then calculate in which of the 4 children we currently are, push it to the stack.</p>
</li>
<li><p>We move along the ray  to the very next voxel, we add it to the stack.</p>
</li>
<li><p>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.</p>
</li>
<li><p>This box has something in it, so we check the children by doing the same traversal as before (we only add 2 of them).</p>
</li>
<li><p>We pop, box is empty, we skip.</p>
</li>
<li><p>We pop, box is full, this is a leaf node, we return the value.</p>
</li>
</ul>
<p>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.</p>
<p>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.</p>
<p><a href="https://i.sstatic.net/nLGor.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/nLGor.png" alt="enter image description here" /></a></p>

CC BY-SA 4.0
2022-01-16T12:25:43.893Z
I don't know about SVO but the fastest idea is just to use 3D texture, memory is less and less a concern.
mdkdy
CC BY-SA 4.0
2022-01-16T19:35:52.443Z
You will run out of memory almost instantly, you cannot hold a 4096 res texture in memory in most systems.
Makogan
CC BY-SA 4.0
2022-01-16T20:39:41.870Z
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.
mdkdy
<raytracing><performance><voxelization>
Sparse voxel oct tree tracing, optimization tricks?
Makogan
# Sparse voxel oct tree tracing, optimization tricks?

(Asked by: username_0 on 2022-01-14)

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](https://i.sstatic.net/tsHhD.png)](https://i.sstatic.net/tsHhD.png)

* 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](https://i.sstatic.net/nLGor.png)](https://i.sstatic.net/nLGor.png)

**Tags:** raytracing, performance, voxelization

> **Comments:**
> **username_1**: I don't know about SVO but the fastest idea is just to use 3D texture, memory is less and less a concern.  
> **username_0**: You will run out of memory almost instantly, you cannot hold a 4096 res texture in memory in most systems.  
> **username_1**: 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.  

---

## 0 answers

