Archive | Procedural Moonbase RSS for this section

Procedural Moonbase: 30 Seconds to Launch

Mere hours from the deadline, the project comes to its conclusion. However, some sacrifices had to be made. Andrew tried valiantly to get the procedural city generation working, but it was a lost cause. Instead he implemented shadow mapping.

Honestly, I think this works better for our concept. I was a bit worried that the scene might be a bit too busy with the city, but I think the addition of shadows really works, and gives the trees the last little bit of “oomph” that they needed. The “Octopus” tree especially casts a nice ominous shadow over the landscape, and it all plays quite nicely with the orbiting light.

One Last Push

On the eve of the deadline, work continues at a feverish pace…

Procedural Terrain and L-systems

Work on procedural terrain generation and crystal formations was mostly done for last Friday’s post. A bit of polish work has occurred since then. Most notably, I’ve smoothed out the terrain of the real world moon heightmap data. The result is much more moon-like:


Also, I’ve tweaked the shader for the crystal growths. I’ve used a technique similar to what is done in cel shading to recognize the silhouettes of the growths. At first I was planning on implementing actual cel shading, but it did not look good. However, I discovered that I could favor the external shell portion of the texture in the silhouette area, much like how if you look at a transparent object from an extreme angle, you see more of the surface material. I find the result to be quite satisfying:


… compared to last week:


Procedural Cities and Buildings

This weekend, Andrew added functionality to render the smaller heightmap for the city on top of the buildable area of the larger heightmap.

The main C++ program invokes a Python script to generate the heightmap and road network, then reads the data into a new LandscapeModel at the appropriate location. The program then renders the road network using a solid color shader for now. By rendering only a portion of the road network at a time, it’s possible to animate the process, showing how the network grows from the population centers and intersects with itself.


The more significant challenge has been extracting buildable areas from the road network. Implementing the road network growth required hacking together a spatially indexed graph database. The generated graphs are subtly broken – some roads cross without an intersection, so the graph is not necessarily planar.

Andrew need to resolve this issue before he can reliably extract cycles, and he needs to extract buildable plots before he can place and generate buildings. He will be working on that tonight.

Where the graph is sensible, he is able to extract a cycle:


But in a case where the edges intersect somewhere besides an intersection point, this fails:



There is an additional requirement that all procedural elements be able to be regenerated at runtime. I’ve implemented the plumbing to ensure that this happens. At the press of a button, the terrain can be regenerated, the crystals can be regenerated and the real world heightmap data can be toggled on and off. Additionally, when the city generation is complete, the plumbing is in place for that as well.

All this regeneration happens much faster than I’d thought it would, which was nice. There was no need to optimize the regeneration or implement asynchronous regeneration.

Onwards To The Moon

As the deadline looms, work continues at a feverish pace. Much has happened, and much remains to be done.

Procedural Terrain Generation

The terrain generation is basically done. We are generating random landscape heightmaps using the Diamond-Square algorithm. After generating the heightmaps, we carve out a flat space for the city, and then place various mineral deposits and crystal growths. After the features are set, we tessellate the landscape.


We are also capable of reading in external heightmap data, and I’ve located a heightmap of the surface of the moon, which we are capable of turning into a 3D surface.

As you can see, the lunar surface is much rougher than one would think.


Crystalline Structures

New this week are the crystalline structures seen in the screenshots above. These are generated using L-systems, with the following grammar:

V = { D(len, topScale, bottomScale, topLen, bottomLen), C(len, topScale, bottomScale, topLen, bottomLen), S(scale), T(minSegs) } S = { F(theta), K(theta), A(r, s) } ω1 = { A(C(6,1,1,1,1), D(1.0f, 3.0f, 2.5f, 0.5f, 1.0f)) } ω2 = { A(C(6,1,1,1,1), A(F(1), S(1))) } ω3 = { A(S(1), A(K(1), T(3)) } P = { D -> A(D, A((K(1), C(2,1,1,1,1)))), C -> A(C, A(F(0.75), T(3))), T : final iteration -> A(T, S(0.5)), T : otherwise -> A(T, T(1)), S : -> A(S, D(3,2,1,1,1)) }

There is a basic crystal building block, represented by D and C. These are the same shape, but D has 5 branching points, and C has 1 (the center.) To build on a mounting point, one uses the A rule, which states “For all mounting points produced by r, build s on it.”

Rounding out the bunch, are S a “scepter” shaped crystal, F, which fans out in three directions, and K, which forks in two directions. Last but not least is the “angry tentacle” formation T.

Here we see ω1:


… ω2:


…and ω3:


Procedural City Generation

We’ll be placing a procedurally generated moon base on the flat build site carved out of the terrain. The moon’s surface is very rough, so we can only place the base on the flat area.

However, the area under the city isn’t completely flat; we are using a technique called spectral synthesis to generate a smoother heightmap underneath the city. The edges of this heightmap will coincide smoothly with the surrounding terrain to ensure a natural transition.


After generating the heightmaps, we generate a population density map using a similar procedure, attenuating it where the terrain is steepest (it’s difficult to build on the side of a hill!). Then we sample the density map and place population centers using k-means clustering. Finally, we triangulate the set of population centers to generate a connectivity graph for road generation.


Once we have a connectivity graph, we draw adaptive highways between population centers using the technique described in Citygen: An Interactive System for Procedural City Generation, using a heuristic combining Least Elevation Difference, population density, and the degree to which the road would deviate from its current direction. As these are drawn, we create additional perpendicular roads in areas of high population density. These roads are extended using the same heuristic until they reach a less populated area.


So far, we’ve implemented the above in Python so we can leverage the performant array operations from NumPy and SciPy, in addition to the spatial indexing functionality from Rtree. We’ll need to use the Python C API to call into our Python code and store the resulting road graph in a buffer for rendering.

The Way Ahead

Much work remains to be done. For terrain and L-systems, there remains polish work. I’ve implemented the required algorithms, and it technically “works.” However, it’s still a bit rough. I hope to refine the shaders of the crystals to make them appear more 3-dimensional. Additionally, I’d like to increase the density of “trees” on the landscape as I think it looks a bit sparse. I hope to have this work wrapped up by tomorrow night.

For city generation, the road graph needs to be converted to buildable cells, and subdivided/populated with buildings. Andrew plans to have this done by tomorrow night. By Sunday, he plans to have the rendering set up for this, with basic buildings. Then by Monday, more elaborate buildings will follow.

Additionally, we need the capability to regenerate the various procedurally generated components at runtime. This is a simple matter of plumbing, and should not be difficult. Time allowing, I’d like to do this asynchronously, so there is no frame hiccup during regeneration. The user will press a button, and a few seconds later, the change will be reflected.

Procedural Moonbase

Having reached the end of UCSD’s Intro to Computer Graphics course, I have been tasked with creating a real-time demo that implements a subset of features covered in the class. Today is the first of three posts about the progress of this project.

For this project myself (Chris Tetreault) and my partner Andrew Buss will be implementing 4 features:

  • Procedurally modelled city
  • Procedurally modelled buildings
  • Procedurally generated terrain
  • Procedurally generated “plants” with L-systems

With all of these, we’ll be creating a procedurally generated moon base. First, we will generate a landscape, and carve out a flat spot for the base. Next, we will generate a city, which consists of a procedurally generated layout populated by procedurally generated buildings. Finally, we will procedurally generate doodads to be placed on the landscape throughout the undeveloped portion of the terrain.

All of this will be implemented in modern C++ with modern OpenGL.

Terrain and “Plants”

This portion of the project is coming along nicely. We are currently generating the landscape, with the exception of textures. We currently have the surface normals set as the pixel color in the fragment shader.

Procedurally Generated landscape

At some elevation lower than the city, I plan to add lava. Additionally, I plan to have two land based-textures that I will select between based on the elevation gain. Likely, this will be a smooth rock texture for steep hills, and gravel for flatter areas.

After completing this, I will use L-systems to generate stuff to put on the landscape. This will likely take the form of geological formations, such as rocks or lava flows as one isn’t likely to find trees on a blasted lunar wasteland.

Cities and Buildings

For the city portion, we’ll be procedurally generating moon base buildings. We decided to go with the moon base, as opposed to a traditional city because we felt this could give us more creative freedom to do what we want. After all; if the task is to procedurally generate a “City”, how many urban downtown areas are you likely to see?

This portion of the project is still in the planning phase, so expect to see more on this next week.

%d bloggers like this: