My last implementation of DDA grid traversal primitives had some very tricky aliasing issues, that I was not really ever able to mitigate in a meaningful way. There were a couple of suggestions I never tried, there was the 27x more expensive local neighborhood search version which would try to look a 3x3 region at each grid step, or the idea of using multiple superimposed grids of varying scale factors. Both of these might be interesting directions to explore, but I have not felt a a lot of motivation to follow up on them.
Something I found actually pretty recently - these aliasing issues are actually an acknowledged phenomenon called Euclid's Orchard, which deals with a viewer standing at one edge of a discrete grid and defining occlusion of sight lines to the integer gridpoints. It's an interesting phenomenon but it caused issues in that implementation, because due to the fact that the primitive needed to be fully contained in the cell, you would be able to see down between rows unless you were very, very careful about placing the camera. Some efforts that helped with this were a deterministic or non-deterministic jitter on the primitive - deterministic would lead to a solid primitive, offset within the cell, and non-deterministic would be in a different location in the cell, every query... this eventually accumulates to something like the random scattering that happens in volumetric media.
In any event - this implementation grew out of my recent efforts to implement GPU sphere packing, reusing 2/3 of the primary data structure for the "dart throwing" algorithm. I got thinking about this as a potential option, when I started messing with using a deterministic hash for placing the sphere centers. I think it's an interesting way to trade some computation for bandwidth, it's effectively a form of compression.
The texture for the traversal is extracted from the sphere packing process, with the "distance" term removed. This could be kept for raymarching usage, but I haven't tried it. It's somewhat redundant, since we have the other two values to get radius and position for a more exact and robust ray-sphere test.
There's 2x 4-byte values which need to be kept for each voxel. I just have these interleaved and written out to a PNG that is twice the width wide, and the height times the depth tall. Each pixel is 4 bytes, losslessly encoded - two pixels side-by-side is able to store all the information we need for a voxel. This way, I can basically trivially load and save these models, only knowing one dimension out of three - the width can be taken from half the image width, since we have two pixels per, and you can get the other from the relation that the height of the image is the product of one known value and an unknown value. The textures themselves have a strong resemblance to a voronoi diagram.
The outer loop of the traversal is lifted directly from the prior implementation. The per-voxel test that happens inside, however, now changes quite a bit. Before, where you would hash the grid index to get the material parameters, now you use a seed value which is stored in a 3D texture. I explained more about how that process works in the post on GPU sphere packing, but the key aspect is that that process uses 32-bit uint seeds to place a sphere. We extract and store the uint seed value from earlier in the process, which was subsequently used with the wang hash to generate a sphere's center point location. The seed is only stored in the case that the test passes during the "dart throwing", so we don't have a tremendous amount of redundant testing.
The key aspect, however, is what we're loading from the texture, and how we use it. The read consists of 2 unsigned integers, one gets uintBitsToFloat'd to a radius, and the second takes the place of the current wang hash seed value. After restoring the RNG state with the seed from the texture, calling the 0..1 uniform RNG hash function once, times the grid x dimension, again, times the grid y dimension, and again, times the grid z dimension, we are using a deterministic process that will net you an exact value for the center point of that sphere. With those two pieces of information, you can now perform a ray-sphere test for intersection. You can even continue hashing from this state to get more, random, deterministic per-sphere material properties (albedo, roughness, IoR, etc).
And I think this is very cool. I'm not sure if this has further implications, or applications in other usecases. 4 bytes become 12+ bytes, losslessly, with a minimal amount of global information. I shared some thoughts in the Future Directions section of that post, but there's actually a very cool mapping you could do to make this a more general method for drawing spheres. Essentially my idea is to construct a LUT of hash keys that would land you in any given voxel. This could be used as input to the sphere packing process, to steer the placement of the next sphere. Even without full coverage of every voxel, you would have substantially more control than a fully random sampling process like what happens now.
This might seem like a kind of an odd and sloppy approach. I'm kind of surprised it works so well. I've only noticed a few small artifacts, where I've seen kind a pattern that I assume is grid cell boundaries where there was somehow a discontinuity. It looks like a stepped, hard break in an otherwise smooth sphere surface, like you cut through it with a voxel cookie cutter. It's not at all common to see this, though, and I haven't had an opportunity to figure out exactly what is happening when it does.
Much more visible, however, is the discontinuities that arise from spheres being placed too close to the boundary. In this case, entire sections of the sphere will be chopped off. You can easily mitigate this during the generation step, you need to constrain the radius for a given point so that it can't expand beyond the distance to the closest face. It's also not critical that you eliminate this, because it does give you some interesting surfaces to look at, as well.
I would also like to characterize the performance of the traversal under grazing conditions. This is a weak point for iterative processes like SDF raymarching, and in this project as well, I think it could be a bit of a pathological case where you do the same ray-sphere test many times without ever successfully intersecting with it. I'm not sure that there's much you can do here, unless you keep track of the hash keys you have already tried, something along these lines. Indexing through a list of already-encountered keys during the traversal, though, seems inefficient compared to just doing the test again, would need to profile the methods against one another under different circumstances.
I do think I'm going to try to implement the reverse-key LUT, because I think it will provide some interesting opportunities. I think it's actually a pretty simple computation, but you may have to evaluate a significant portion of the 4 billion possible keys to get good coverage. I think it would be interesting to track how this progresses over time, as well, keeping some stats on how it converges. It may well be an overnight computation to cover a 10243 volume, but with the scale of the problem, I think it is not intractable to just use a brute force approach and evaluate the initial keys sequentially.
Last updated 9/26/2025