Optimized Ray-marching algorithm

Inspiration

I was inspired to tackle this challenger because it contained a unique intersection of 3D creativity and math which I both love.

What it does

This algorithm renders heightfield meshes that are generated using functional brownian motion.

How I built it

I improved upon Huawei's basic raymarching algorithm by making many adjustments.

1. Level of Detail optimizations: The functional brownian motion mesh generator creates a mesh by summing multiple noise maps. I altered the mesh generation to be dependent on the camera location so that smaller details and higher frequency noise maps were not added to the mesh at larger distances.
2. K-Lipschitz Bounded Sphere tracing: I knew I wanted to improve upon the height based ray marching iteration but struggled with finding out how to generate a signed distance function for each point. Instead I came across the K-Lipschitz equation which provides a bound on the distance function based on the fBm parameters.
3. Height Rendering cutoffs: I improved the sky rendering time by simply ending all rays if they reached a height greater than the maximum possible height of the mesh.
4. Illinois method: The most significant and novel method in this algorithm is the Illinois method implementation. To save time with raymarching while close to the height maps surface, the Illinois method checks wether there will be a hit in a certain window and skips this window if there is not a hit. This significantly reduces the number of small steps the algorithm takes by skipping these windows entirely.

Challenges I ran into

I ran into multiple challenges in this algorithm. The improvements such as the level of detail and height cutoffs seemed fairly obvious and were quite easy to implement. The Sphere tracing and Illinois method were not however. I suspected that the gradient would be useful in determining the distance function for sphere tracing but trying to devise a method before finding K-Lipschitz bound was extremely challenging. Luckily once I found the K-Lipschitz equation it was an obvious solution to my problem.

I was struggling thinking of ways to solve the grazing problem that ray marching has until I considered a root finding method that I was recently studying in a Computational Physics course, the bisection method. Since the height from the mesh is a signed function I realized that I could search for a sign change in a window significantly larger than the iterative step size and probably be able to detect wether a hit was in the window much faster than the brute force method.

Accomplishments that I am proud of

I am quite proud of my K-Lipschitz bound distance function as well as the Illinois method implementation. Combined I was able to reduce the step count by 37.8 percent which is far more than I thought I would be able to achieve with in the 48 hour period.

What I learned

I learned about ray marching and various ways to improve its performance.

What's next for me

I hope to continue working in 3D computer graphics and building impactful technology and software.

Built With

• glsl