Thursday, April 26, 2018

Procedural Terrain Research Project

Rationale

In 2008 I decided that I wanted to build a game for simulating the development and sustainability of a colony on Mars.  I had high ambitions and a keen interest in the epistemic qualities of such an endeavor.  I started with terrain and wanted to ensure as realistic geology and geomorphology as possible because education and simulation was more important to me than entertainment.

I eventually shelved this project discouraged by gaming research suggesting that playing video games could be very bad for a young person's health including shrinkage of the hippocampus and impairment of the prefrontal cortex.  There were other factors involved in that decision as well, but that was definitely the final nail in the coffin.

Below I document my journey procedurally generating an impact crater with outflow channels meandering around it.  Each two-dimensional grayscale image illustrates the DEM (digital elevation model) resulting from each test (top-down view with lighter colors representing higher elevations and darker colors representing lower elevations).  I thoroughly enjoyed this project and hope to find a productive and practical application for these algorithms I have developed.

The Crater




At first I tried to simulate the particle physics of an impact crater as it unfolds in real-time, but this was much too computationally intensive even simulating large virtual particles.  So I started with an optical template with little more than an ejecta blanket.


Here I've elaborated on the template a bit and carved out a cavity in the while preserving the relative isostatic uplift in the center similar to the effect of a falling drop of water into a pool.  Some large craters have multiple concentric rings from the resulting impact (Mare Orientale and Schrödinger are stunning examples in particular) suggesting a corollary to ripples in a body of water.


The next thing I wanted to do was give it a realistic environment.  Here I employ brown noise and merge it with the template.  Brownian noise is particularly useful for synthesizing realistic terrain.  It is characterized by higher amplitudes at lower frequencies (as opposed to white noise which is uniform by comparison).  It tends to best model the appearance of mountains as it does the sound waves emitted by a water fall.


The smoothness of the impact crater was the first thing that bothered me and I was determined to resolve this before moving onto any other experiments.  This is one of the inherent disadvantages of using a template or decal approach offering less flexibility in crater shape perturbation.


This became an exercise of playing with a variety of aggregating mathematical operations until I produced something visually appealing.  I still think this is too simple and inherently too circular.

River Channels



Pleased with the crater I took a short break and moved-on to my next ambition: outflow channels.  Immediately I noticed I had to deal with these subtle rounding errors resulting in pixelated holes.  This is one of the problems inherent to reconciling partial non-integral values to an integral grid system.


This project kindled a love and appreciation for mathematics and linear algebra in particular.  Resolving these errors wasn't easy but it wasn't impossible either. Now I had a baseline established for synthesizing branches and making erosion channels more interesting and varied.


I played with the idea of parallelizing outflow branch computation, but decided that degree of fine-grained parallelism wasn't necessary.  Something didn't sit right with this channel bulldozing the impact crater.  The meandering of the branches also appears to be much too to haphazard, something was missing.


From observing Gold Crater on Mars I concluded that the walls of an impact crater were compressed and higher density than other terrain.  In fact terrain density varies a great deal in general.  So I added an additional density map companion to the height map model and used this to train branch synthesis.  This additional channel made it possible to enhance it further in the future using density generation algorithms.



Taming these meandering branches still proved to be as difficult as herding cats.  I used the pink dots here to help me trace exactly what the main branch was doing.  Was my algorithm ignoring the density values? was I making incorrect assumptions about the calculations?  While one branch broke through the crater wall the other did not.  This still marks an improvement.


Eventually I stumbled upon something that started to make sense.  I wasn't happy with it yet though, the outflow channels appeared too smooth for my liking.  But at least I had an iteration with plenty of outflow channel branches and not a single one breached the impact crater walls.


Finally I stumbled upon something that blew my mind.  There were some emergent effects I had not anticipated: riverine islands.  When I stumbled upon this iteration I was tremendously happy.  In fact that day marks one of my best days of coding experiments.

Here is a 3D rendering of the resultant height map model from three different perspectives.  Note the riverine islands in the last rendered image.  The spires here are the same residual pink / red dots I used for troubleshooting flow paths.


Going Forward

I am currently researching practical applications for the code I have produced for procedural terrain generation.  While the individual algorithms are not distributed / parallelized, the system that generates an environment with these features is (I opted to use OpenMP).  Procedural algorithms include impact cratering, outflow channels, volcanic spires & outflow, wind erosion and weathering. 

In particular the settlement of Mars in any capacity (whether an outpost or self-sustaining human colony) is tremendously exciting and suggests an apropos domain for this technology.

No comments:

Post a Comment