Screen Space Acceleration Structure

Screen Space Acceleration Structure

The paper “An Adaptive Acceleration Structure for Screen-space Ray Tracing” recently caught our attention. It promises up to 80% upspeed compared to a classic DDA single layer raymarching.


The raymarching is seen as an improvement to a classic DDA line rasterizer and uses a quadtree as an acceleration structure. The quadtree data is maintained in the MIP-Levels of an RG16F texture, making it really suitable for a common GPU implementation. The tracing itself is decoupled from the quadtree building step and traverses the octree from root to leafs. If necessary, the traversal steps upwards on higher quadtree levels to check for empty space skipping, which is done in a stackless and register-saving manner.

All in all, very elegant. Since it still was a bit of work to go from the GLSL pseudocode from their supplemental material to a working shader, I’d like to share it with you. All intellectual credits go to the team around D. Luebke at NVIDIA.

Our first quadtree level is constructed in the following fragment program. Note, that the depth is not linear and ranges from zero to one, which enables to save a few FPU instructions for converting them. Theoretically, the non-linearity should cause a problem at the plane compression. Practically, it doesn’t. The depth space bending is small enough to be catched by the subsequent merging thresholds.

We then build the quadtree bottom up:

Now, the tracing itself:

Please note that this code isn’t heavily optimized, there is still a lot of potential, but it outlines the general algorithm.

We came to the conclusion, just like Frostbite in their recent presentation about stochastic screen space reflections, that it’s a good idea to combine both stride-based raymarching and geometric exact tracing with an acceleration structure. For most cases however, we use the stride based because it scales a lot better to spontaneous needs thanks to the variation of step size and stride size.

Leave a Reply

Your email address will not be published. Required fields are marked *