December 2015
This program allows you to walk and fly through a 3D fractal. Hit Esc to toggle the mouse cursor and the menu. When the menu is closed, use the mouse, W, A, S, D and space to look around, move and jump. You can change your size and speed with the mouse wheel. Increasing your size can easily get you stuck. Hold left shift to temporarily disable collisions and gravity.
This project's starting point was a so-called distance estimator (DE) for the Mandelbox family of 3D fractals. A DE is a function, which for any point in space gives you the approximate distance to the surface of the fractal. You can use it for ray tracing by iteratively advancing the ray's current end point by the end point's distance estimate until the returned distance is below some threshold.
The DE doesn't consider the ray's direction, so any piece of fractal near the ray will decrease the estimate and slow down the advancement of the ray, even if no collision is imminent. The rays also get slowed down whenever the DE, which is only an approximation, underestimates the distance to the fractal.
The DE is a computationally expensive function and a naive ray tracing implementation would evaluate it on every step for the complete ray of every pixel on every frame. My intuition told me, that there's lots of room for optimization there, so I started optimizing.
I tried to speed up the rendering by first generating a low-resolution approximation, which then gets refined into a full-resolution image. This approach does reduce the total number of DE evaluations per frame, but it's not enough. Adding an even coarser approximation pass doesn't help either. The bottleneck is the full-resolution pass, which can still require hundreds of DE evaluations per pixel to converge.
The Mandelbox DE contains an iterative function, which "folds space". In theory one would have to go through infinitely many folding iterations to get a fractal in the mathematical sense. Using increasingly many iterations gives us an increasingly accurate approximation with more, finer details, but at about 30 iterations the additional details just drown in rounding errors. Decreasing the number of folding iterations saves processing power, but it also makes the scene very smooth and visually uninteresting.
By using the world position of each pixel as its uv-coordinate, I can easily add textures to the fractal. If the ray tracing happens at a low resolution (to reduce the number of DE evaluations) and the texturing happens at full resolution, the result will look mostly as if the ray tracing happened at full resolution. There are some artifacts along sharp edges, which become particularly obvious, when the camera is moved.
I removed the texturing later on, when a new rendering technique allowed me to increase the number of folding iterations to a point, where any texture would just distract from the intricate details of the fractal's surface.
This is the rendering technique, which finally let me render the fractal with a high level of detail in full-screen at decent frame rates: I only do a fixed number of DE evaluations per ray each frame and store the result in a floating point texture for further refinement during the next frame. This means that some rays will take multiple frames to hit the fractal. During that time, the previous frame's image gets recycled.
For minimal artifacting I'd have to re-render the previous frame as a kind of height map, which would take too much time, so I just do a rough approximation: By sampling the previous frame I get an estimate for the distance between the fractal and the camera. Using that distance I can get a slightly more accurate sample, which then gets fed into the refinement iteration loop.
When the camera isn't moving, the image converges perfectly, but any kind of motion causes artifacts.
I handle collision detection by ray tracing thrice per tick: towards the floor, towards the ceiling and in the direction of the current velocity. If the latter detects a collision, I do a few additional DE evaluations to estimate the fractal's normal and modify the velocity to have the player slide along the surface.
I noticed that enabling collisions and gravity, and always having the same size made exploring the fractal much less fun. Maybe the fun can be regained by adding mobility gimmicks like grappling hooks or jet packs. If I end up revisiting this project, those would probably be the next things I implement.
The renderer is good enough for me to enjoy flying around the fractal. Depending on the settings it seems either too slow or too ugly to be used in a commercial game. Some other class of fractal might be faster to render.
It's possible to make the renderer fill the depth buffer to combine the fractal with traditionally rendered elements, but placing entities in the world would be tricky: The fractal is too vast to populate it manually and too irregular for simple procedural placement. Games of many different genres could take place on a fractal, but I can't think of a game that would actually benefit from it.