Color pass
Here you can see both the original algorithm's render as well as the optimized render
Summary
The goal of this challenge was to improve a template ray marching algorithm that rendered procedurally generated terrain using Fractional Brownian Motion (FBM). The template featured a naive ray marching implementation that took step lengths proportional to the ray's height above the terrain at each step.
I improved this algorithm by implementing a K-Lipschitz bound signed distance function. The K-Lipschitz bound provides the upper bound on the maximum slope of the terrain calculated from the provided FBM function used in the height map calculation. I then use this bound combined with the current height above the terrain to determine the minimum bound of the distance to the surface.
The K-Lipschitz bounds effectiveness was improved also by an implementation of level of detail scaling on the terrain generation. Since the terrain was generated by summing different scales of FBM maps, I stopped adding the smaller scale maps at larger distances since these fine details would not be visible. This meant the lower bound for the signed distance function increased as the ray got further away from the camera.
My final improvement to the algorithm was adding an Illinois trigger method to detect collisions with the surface which significantly improved rays that march close to the surface. Rays that graze the surface must take many steps because the distance to the surface is so small so the step size remains small as long as the ray is close to the surface. The illinois method gets around this by searching for collisions with the surface in a bracket similar to the bisection method.
The total step count of the original template algorithm was 1.73e8 steps and the total step count of my final implementation was 1.07e8 steps. Improving the step count by nearly 40%!
Render comparisons
Cost map
The gradient renders represent the cost of each rendered pixel. The brightest pixels are the most expensive while the darker ones are the least expensive to compute. The original render shows a white rim above furtherest mountains because these were very expensive. Those are nearly all gone in the optimized implementation.