DDA Grid Traversal Primitives in Daedalus
This is another project that was inspired by discussions with gelamisalami on the GP discord. I really liked the grid traversal demos they were doing, and I wanted to try something similar, following my own messing around with trying to simulate opal microstructure. I had hit some limitation there, with the number of spheres that I was able to handle in a reasonable amount of time. With the explicit primitive list, numbers like 100k became pretty unfeasible. With the DDA approach, I've been able to do a cube bounding volume with 1024 cells to an edge, which could contain on the order of one billion primitives, before performance started falling off significantly like I was seeing with the explicit sphere list.
This algorithm is mostly used for voxel rendering. It can be used to walk through a uniform grid, and touch all the grid cells that the ray passes through. This can be made very efficient, using a form of BVH/hierarchical traversal - using mipmaps containing occupancy information at varying levels of detail, informing whether you can safely take larger steps. I haven't messed with this very much, but I know Teardown does something along these lines. If you wanted to do some of the more mainstream cubic voxel rendering, this is a cool approach that may make a lot of sense.
But I was more interested in this approach, by jt. This adds another test inside each step of the DDA traversal, where you can test against a primitive contained inside of the grid cell. I did this mostly with spheres, but also tried cubes and oriented disks. What's cool is, you can do additional tests where you take a texture read or a sample of an SDF, at a position or texel associated with that grid cell index. This can inform material, what primitive you test against, etc.
Using a hash function like pcg3d, which takes the grid cell index as input and gives some deterministic output, you can do more high frequency things like assigning materials or colors that vary between neighbors. By using a deterministic hash here, you can reliably and exactly get this information back, whenever you are doing a grid traversal through this particular cell.
This is all very cool, but it has some limitations. I mentioned that the primitive has to be contained inside the grid cell - if you accept that the primitives can span across neighboring grid cells, your traversal becomes 27x more expensive, or else your intersections become directionally dependent and unreliable. This is because at each step, you're going to have to check against neighboring cells, or you will only incidentally hit the larger primitive when traveling in certain directions. You won't always hit the bounding grid cell during the traversal. I haven't tried implementing this neighborhood search, but it may still be a viable approach for smaller grid dimensions.
Related to this limitation, there are some interesting grid aliasing issues. Because of the boundaries, for spheres (less so, for cubes that fill the grid cell) there is almost always a gap between the primitives contained in neighboring grid cells. Even if they are touching, assuming the primitive fits in the grid cell, it's only at a single point at the boundary. The aliasing pattern looks pretty crazy, but it's actually correct - you can cross reference this with the phenomena that you see in highly organized rows of headstones, like they do in military cemeteries. The headstones are a 2d analog, in the DDA traversal you see it manifest in 3d. When you can see down rows it can create some interesting artifacts, when your view aligns with the divisions between grid cells.
I explored a couple different approaches, to counter these artifacts. You can very carefully align your view, so that you don't see down these divisions, but that's not a very general solution, and you may not be able to get that for a particular scene that you're trying to render with it. I tried breaking up this uniform grid pattern, a couple of different ways.
First, using this same pcg3d hash, to get a deterministic random offset and radius for each grid cell. This way, you can place the spheres with a little less regular pattern, and you can more easily find a view direction that will not show the aliasing, quite as bad. But it's not a magic bullet, I found that it does not fully solve the problem, and pretty often your view direction will line up with the grid enough that the aliasing patterns show up again.
My second approach to this problem, was to use a per-sample, non-deterministic hash to offset the primitive. This means that it will be in a different location in the grid cell, each sample - and over multiple samples, this really becomes more of a distribution of positions. It's actually quite interesting, the way it converges to something like a volumetric effect. I don't think this is really that good a solution - there are better ways to get this type of volumetric effect, but it's interesting.
Gelamisalami proposed another solution, using a rhombic dodecahedral traversal, which has a bit more complex grid pattern. I think this is also another very attractive direction to explore, and I do want to circle back to this, eventually.
This folds into the discussion of usage for the opal microstructure idea that I had been playing with, at the end of last year. Like I said, I was hitting an upper limit on primitive count, much lower than I wanted. It was workable, and you did see some pretty cool Tyndall effect scattering of the colors from the sky. But in order to move towards something larger scale, like I had seen in Alia's work, this kind of grid cell traversal was a very solid solution. It requires a lot of bounces, but it also resolves to some pretty nice subsurface scattering, as well.
Something I messed with pretty extensively, I really liked this - the disk primitives, in particular. I really liked this idea of masking them with an SDF, and then also orienting them with the gradient of that same SDF. It creates this extremely interesting surface appearance when the disks are small relative to individual pixels, almost becomes pearlescent. Couple examples, here. The red one looks interestingly like the end grain of meat fibers, and the green one has an interesting kelp-like look. Really interesting stuff, where it starts to act like more of a type of material than a model.
Using textures also proved to be an interesting approach. I tried Brent Werness' Voxel Automata Terrain that I ported to C++ a while ago, to populate a 3d texture (this is the same thing that was used for the clouds at the top of the page).
Also messed with putting a 2d texture into a heightmap, and checking the y axis of the grid cell, against the height value. These were pretty cool, particularly when using colored glass spheres inside each grid cell. These are just attenuating at surfaces, they are not doing the distance-based attenuation that they should be, based on Beer's law - that will be something to pursue soon.