Overall Goals

Interested by the modeling and mesh-generation parts of the class, we set out to create a terrain and city mesh generator. Our main goals were to:

  • Explore “Noise” and how it could play a part into mesh generation.
  • Create an algorithm that could infinitely generate terrain and city meshes using the previous noise system.
  • Wrap all of our code together into Unity3D to create a “playable” demonstration of our mesh generation.

To reach these goals, we constructed a simple flight simulator demonstration over infinite, procedurally generated terrain/city.

Noise

Mesh generation, of either buildings or terrain, requires an input source of data. This data describes the heights of the terrain (or buildings) at a specific point. For example, a noise function that always returned “1.5”, would create a terrain mesh that is exactly flat.

There are many different noise functions that could have been used to create this height map, but we specifically chose to use Simplex Noise for a variety of reasons. It is relatively computationally inexpensive, well defined, has a continuous gradient, and doesn’t have directional artifacts.

The method for computing this noise was described in Simplex Noise Demystified, by Stefan Gustavson.

Simplex Noise Visualized

The `SimplexNoiseLibrary.{c,h}` contains all of the code to generate a SimplexNoise map. We can visualize this noise system by creating a 2-dimensional array of noise and mapping the output value of this function to the gray scale value of a pixel. Here are a few examples of Simplex Noise maps at various frequencies.

Due to the asynchronous nature of infinite, procedural terrain generation, it is important to get a continuous and reproducible noise system. We use a Deterministic Random Number Generator in order to achieve this effect. Implementing the Simplex Noise system using this DRNG allows continuous, deterministic noise generation. This is shown below:

It's important to also note that these noises can be compounded on top of each other, generating a combined noise map. This is useful for generating realistic terrain. A "summed" image is shown below:

Terrain Mesh

To generate the terrain from the noise maps that we created, we simply overlay a grid of vertices over the noise map with their height dimension described by the value of the noise map. From here, we export this mesh of points to an OBJ file (OBJ file format spec). Some sample meshes are shown below:

Once again, since the underlying noise system is continuous, the resulting meshes are continuous, as demonstrated by the sequenced mesh in the following picture:

These are two adjacent meshes. The gap between them has been added manually to show the alignment of their edges.

Terrain Mesh LOD

It is important to be able to control the level of detail of the terrain. Our algorithm solves this problem by varying the amount of vertices projected on top of the noise map. In a reduced LOD mesh, less vertices are “laid over” the mesh, resulting in the same mesh shape as a full LOD mesh, but with a lower amount of vertices. This algorithm allows the changing of the LOD without adding any additional computational complexity.

These three images are all of the same mesh, at max LOD, 8x fewer vertices, and 16x fewer vertices

City Mesh

The city mesh was constructed in a similar manner to the terrain mesh. The primary difference was that instead of connecting each vertex to its neighbors, a rectangular prism was constructed at each vertex, with the height corresponding to the noise value of the vertex. Since a city should not look too smooth, a far choppier noise function, was combined with the smooth version used in the terrain to create a city that has higher and lower patches, but with sufficient variability in building height.

Below we have too smooth, too random, and just right.

Unity3D

Both the terrain and the city mesh generators were ported from C to Unity:JavaScript. Basic graphical additions such as a skybox, diffuse materials, lights, and fog were added to a simple scene. An airplane mesh was created using two cubes and a sphere. The procedural generation code was added to a script that checked the location of the plane and generated new code when the plane got to the edge of the loaded map.

Unity3D Controls

Each of the games has the exact same controls:

  • W/S or Up/Down arrows -> Pitch down and up, respectively
  • A/D or Left/Right arrows -> Roll/yaw left and right, respectively
  • Space Bar -> Fly faster

New terrain/city will load as you fly toward the edge of drawn terrain.

Difficulties and Reflections

Working on this project revealed a lot of insight into mesh generation and games. We were most surprised by the difficulty in working between formats and engines, and differences in the city vs terrain meshes. Specifically we had trouble:

  • Working with different file formats (i.e. Unity3D wants 0-indexed meshes, OBJ wants 1-indexed meshes)
  • Unity3D’s default coordinate system has the “ground” plane as the X-Z plane instead of the X-Y plane
  • Porting C-code to Windows Unity3D. (We tried compiling a Windows DLL on mac with MinGW, but we were ultimately unsuccessful. We had to resort to porting all of the code to Unity3D:JavaScript)
  • Dealing with off-by-one errors. One of our major bugs was a slight gap between adjacent meshes.
  • Adequetly building a city mesh from a noise function. Simply using one layer of noise resulted in a city that was either too smooth (think a choppy mountain) or too random.

Overall, we thoroughly enjoyed creating this project and learned a great deal about noise systems, different methods of mesh generation, and working with a commercial graphics engine.

Condensed Overview of Project

There are two main parts of our code: (1) C source and mesh/image functions and (2) Unity3D Executables. Simply run make all in order to compile and run (1). This will create a set of images and meshess.

  • noiseImages/freq*.pgm -> Simplex Noise Maps at various frequencies.
  • noiseImages/sequence*.pgm -> A series of images that show the linear, contiguous nature of the Simplex Noise Map.
  • noiseImages/SummedImage.pgm -> A special noise map that was generated using multiple different frequencies of noise. This is what the terrain generation is created from.
  • noiseMeshes/CitySeq*.obj -> A series of meshes that show the linear, contiguous nature of the City mesh generation. (The number in the filename refers to the x-position of each of the meshes. i.e. CitySeq1.obj should be moved 1 unit in the +x position from CitySeq0.obj)
  • noiseMeshes/TerrainSeq*.obj -> A series of meshes that show the linear, contiguous nature of the Terrain mesh generation. (The number in the filename refers to the x-position of each of the meshes. i.e. TerrainSeq1.obj should be moved 1 unit in the +x position from TerrainSeq0.obj)
  • noiseMeshes/TerrainLOD*.obj -> A series of meshes that show the different LOD settings that out mesh generation system can create.

The Unity3D Executables can be run on any Windows computer or Web browser with the Unity Plugin. Mac and Linux (experimental, not fully supported) binaries are available at Dropbox Link to Binaries. The full Unity3D source for each of these projects is also available at the previous Dropbox link.