Nerdy Inverse Network

The blog is moving to nerdy-inverse.biz !

The content will be moved this month and new articles will be available soon ! :)

Here’s basically how XNA applications are executing:

Initialization steps:

1. The application (entry point) calls the game class constructor.
2. The game class constructor creates the game components and call their constructors.
3. The game class Initialize method is called by the XNA framework.
4. The framework calls each game component’s Initialize methods.
5. The framework calls each drawable game component’s LoadGraphicsContent methods.

Processing steps:

1. The framework calls the game’s Update method.
2. The framework calls each game component’s Update methods.
3. The framework calls the game’s Draw method.
4. The framework calls each drawable game component’s Draw methods.

Device events:

If the device is lost (the application window is moving to another monitor, the screen resolution is changed, the window is minimized, etc..), calls to the game’s and drawable game components’ UnloadGraphicsContent are made by the framework.

If the device is reset, then the framework calls the game’s LoadGraphicsContent methods as well as each drawable game component’s LoadGraphicsContent methods.

Shutdown steps:

1. The game’s Exit() function is called.
2. The framework calls the game’s Dispose method.
3. The game’s Dispose method calls each of the game component’s Dispose methods.
4. The framework calls the game’s UnloadGraphicsContent method.
5. The framework calls each drawable game component’s UnloadGraphicsContent method.
6. The game now exits.

Now that you are aware of the basic flow, there’s one particular thing in the processing steps that differs from what you can probably expect when using XNA for the first time. This particular thing is the game loop timing.

The game loop timing can be either fixed steps or variable steps. By default, XNA sets the game class to use a fixed time step. This determines how often the Update and Draw methods will be called.

When using the variable step setting, the game calls its Update method as soon as the previous frame is done drawing. This setting forces you to implement the game logic and animation based on elapsed time between frames to ensure a smooth game experience. Because the Update function is called immediately, the delay between calls can vary a lot. Without taking the elapsed time into considerations, you would see that the game is oftenly going faster or slower.

When using the fixed step setting, the game tries to call its Update method on the fixed interval specified in its TargetElapsedTime property (60 by default). This allows you to use the Update call as a basic unit of time and assume it will be called at the specified interval. When an update runs slower than expected, the game will skip the Draw calls and try to keep up the target elapsed time pace. This ensures that Update will have been called the expected number of times when the game loop catches up from a slow down. Also, the GameTime class provides a IsRunningSlowly boolean flag indicating if the game loop is taking longer that the target elapsed time. This allows you to adjust the amount of work you do in the Update function by yourself to meet the desired pace.

You can read more on game time in XNA on Shawn Hargreaves’ Blog here.

In this part, we will add heightmask support as well as the multiply and add operations to the heightmap class. This new heightmask class works like a stencil. It has the same size than the heightmap and the mask values are all between 0.0f and 1.0f.

Since we also add the possibility of adding and multiplying heightmap together, we can make combination of different heightmap even more interesting. For example, you can use multiple terrain generation algorithms together and apply mask on them to blend the terrain from one type to another, like a volcanic area to an islands area. You might wonder what’s the difference between using a heightmap in the 0.0f - 1.0f range and a heightmask ? Well, the difference lies in the way we combine them:

Here’s the ApplyMask function of the Heightmap class:

You can see that the ApplyMask function assure you that the values will stay between the minimum height and the maximum height of the heightmap. If you want to use a heightmap like a mask, you can only multiply it with a heightmap having also 0.0f and 1.0f as respectively minimum and maximum height.

Here’s the MultiplyHeightmap function and the AddHeightmap function:

Here’s a few screenshots of a simple heightmask in use:

The heightmask applied to a heightmap at maximum height.

The heightmask applied to a random heightmap.

The heightmask applied to a random heightmap.

You can download the sample application here.

In this part, we add the possibility to combine two heightmaps together. This is pretty easy to do. For each heights of the destination heightmap, we take it’s height multiplied by (1 minus the ratio) and we add the other heightmap’s height at the corresponding coodinates which we multiply by the ratio. The ratio is the percentage of the heightmap passed as a parameter and it’s in the [0.0f;1.0f] range. Also, I added the noise size parameter to the perlin noise generation as well as another NormalizeHeightmap function with a minimum and a maximum parameter.

Here’s some screenshots to illustrate heightmap combination:

The base heightmap.

The base heightmap at 90% and a random heightmap at 10%.

The base heightmap at 50% and a random fault formation at 50%.

The base heightmap at 50% and a random fault formation at 50%.

The base heightmap at 50% and a random fault formation at 50%.

The base heightmap at 50% and a random mid point displacement at 50%.

The base heightmap at 50% and a random mid point displacement at 50%.

The base heightmap at 50% and a random mid point displacement at 50%.

The base heightmap at 50% and a random particle deposition at 50%.

The base heightmap at 50% and a random particle deposition at 50%.

The base heightmap at 50% and a random particle deposition at 50%.

The base heightmap at 50% and a random particle deposition at 50%.

The base heightmap at 50% and a random perlin noise at 50%.

The base heightmap at 50% and a random perlin noise at 50%.

The base heightmap at 50% and a random perlin noise at 50%.

Here’s the CombineHeightmap function:

Here’s an example on how we use it in the GameFOT class:

You can download the source code here.

Another way to create heightmaps is to generate them using perlin noise. Perlin noise was invented by Ken Perlin and is one of the most common ways of creating procedural noise. It works by adding together noise of different frequencies. To do this, we first need a number generator that returns the same random number for a specific seed. Here’s the one that we use:

This function returns a float value in the range -1.0f to 1.0f. Next, we need to be able to interpolate between two random values, with a smooth effect. Linear interpolation isn’t really good for heightmaps, so we will use cubic interpolation since it’s available in XNA in the MathHelper class. While being more accurate, it’s also more expensive. If we generate a bunch of random numbers using the noise function and if we create a curve with them thanks to the cubic interpolation, we get some nice random curves.

I said before that perlin noise was about adding noise together right ? In our case, we will add curves made of noise together. The frequency is the number of random numbers that we use to generate the curve. For each curve that we use, we double the number of random numbers. Each doubled frequency is called an octave. As frequency of each curve increases, we want that the amplitude (or influence) of each curve to decrease. We control how much the amplitude decreases per octave using persistence.

The formula is quite simple: Amplitude = Persistance ^ octave

The cool thing about perlin noise, is that we can do that in 2D, 3D, or any other number of dimensions as well.

Here’s some screenshots to illustrate perlin noise:

Seed = 1337, persistence = 0.75, octaves = 10

Same as above, in wireframe.

Seed = 1669, persistence = 0.8, octaves = 4.

Same as above, in wireframe.

Seed = 12345, persistence = 0.7, octaves = 8.

Same as above, in wireframe.

As you can see, the results don’t look very good. That’s because perlin noise based heightmaps are way better then we combine them by using a small noise size with medium persistence multiplied by a large noise size with high persistence for example. We will see how to combine heightmaps in the next part as well as how to control noise size.

Like before, we create a HeightmapPerlinNoiseSettings class to store the settings, the seed value, the persistence value and the octaves count.

Here’s the meat of the heightmap class that deals with perlin noise:

You can simply press the B button or the enter key to cycle through each heightmap types.

You can download the source code here.

In nature, volcanic mountain ranges and island systems like the Pacific Rim’s are generated by lava flow. In this part, I use a particle system borrowed from the field of molecular beam epitaxy to simulate lava flow. The original idea comes from Jason Shankel.

The idea behind this algorithm is to drop sequences of particles and simulate their flow across a surface composed of previously dropped particles. Dropping a sufficient number of particles will produce structures that look like the flow patterns of viscous fluid (like lava). We start with an empty heightmap, and we drop one particle on it at a random location. After that, we drop a second particle on top of the first and we shake the heightmap until it comes to rest (until none of its neighbors is at a lower altitude). We continue to drop particles until we have a decent size pile. If we keep the drop point in a single place, we will have a large peak, moving the drop point periodically will create chains of multiple small peaks.

Volcanoes have very distinctive mountaintops. Once the lava flow stops, the lava cools and recedes back into the earth, creating some kind of bowl called a caldera. To generate a caldera, we invert the heightmap value above a certain altitude about the horizontal plane defined by that altitude. To make it more realistic, we apply some erosion using the low pass filter that we have created for the fault line deformation algorithm. We implement the caldera inversion using a flood fill technique to avoid interference with other peaks.

Here’s some screenshots to illustrate particle deposition:

Caldera = 0.7, 1024 jumps, peak walk = 4, minimum particle drop = 128, 1024 for the maximum.

Same as above in wireframe.

Caldera = 0.5, 1024 jumps, peak walk = 2, minimum particle drop = 128, 1024 for the maximum.

Same as above in wireframe.

Caldera = 0.7, 1024 jumps, peak walk = 8, minimum particle drop = 128, 1024 for the maximum.

Same as above in wireframe.

Caldera = 0.5, 128 jumps, peak walk = 2, minimum particle drop = 128, 1024 for the maximum.

Caldera = 0.5, 1024 jumps, peak walk = 2, minimum particle drop = 128, 1024 for the maximum.

You can get all sorts of results with this algorithm. It looks even better when you have water.

Like before, we create a HeightmapParticleDepositionSettings class to store the settings. We have the caldera height, the number of jumps, the peak walk value, the minimum and the maximum particle drops.

Here’s the meat of the heightmap class that deals with particle deposition:

You can simply press the B button or the enter key to cycle through each heightmap types.

You can download the source code here.

Mountain ranges like the Himalayas are formed by a geological process called uplift. Lateral pressure from the movement of tectonic plates causes the surface of the Earth to wrinkle like fabric, pushing up mountain ranges. We can simulate this effect using the mid point displacement algorithm, also kown as the plasma fractal or the diamond square algorithm.

In one dimension, mid point displacement works like this. Take a line segment, pick the middle point and displace it by a random value in a small range (like -half length, +half length of the segment). After that, you reduce the range and you repeat the process for each new segments created this way.

In our algorithm, at each iteration, the offset range is multiplied by 2^-r, where r is the roughness constant.

When r > 1, the offset will decreases faster than the line segment length, so the terrain will look like a mountain or a valley, very smooth.

When r = 1, it’s where we have the best results, small regions will look like large regions.

When r < 1, we end up with a very chaotic result. The late iterations have a disproportionately large effect on the terrain.

In two dimension, instead of a line segment, we use a rectangle. Instead of one middle point, we now have five middle point, one for each side and the middle of the rectangle. In the diamond-square algorithm, the calculation of the rectangle’s mid point is called the diamond step, and the calculation of the side mid point is called the square step.

To do that, we start with a rectangle ABCD seeded with height values at the four corners. We calculate the height at the midpoint E by averaging the height of each corners A, B, C and D and we add a random value in the defined range (in our case, half the width length). This is the diamond step. Now, the square step, calculate the heights at the mid points of the line segments by averaging the corner values and the midpoints of the adjacent rectangles, and again, adding a random value in the defined range. You can repeat the process as much as you want.

Since the square step relies on the diamond values of neighbording square, we must first perform each diamond step before doing the square step.

Here’s some screenshots to illustrate mid point displacement:

Diamond step only with r = 1

Diamond step only with r = 0.25

Diamond step only with r = 4.0

Mid point displacement with r = 1.0

Mid point displacement with r = 1.0 in wireframe.

Mid point displacement with r = 0.25

Mid point displacement with r = 4.0

As you can see, with r close to 1.0, we get the best results.

Like what we did for the fault line deformation algorithm, we create a HeightmapMidPointSettings to store the algorithm settings (in my implementation, we only have one rough constant).

Here’s the meat of the heightmap class that deals with mid point displacement:

You can simply press the B button or the enter key to cycle through each heightmap types.

You can download the source code here.

In this part, we introduce the concept of fractal terrain generation. In this particular part, we will focus on fault line deformation. In nature, forces like tectonic plates, mass-wasting and shorelines erosion create terrain features like escarpments, mesas and seaside cliffs. Fault lines allow you to generate these kinds of terrain.

The idea behind this algorithm is to start with a flat heightfield. Then we compute a random line through it and add an offset value to each value on one side. After that, we decrease the offset value and we repeat the process until we are satisfied with the level of detail generated.

The formula used to decrease the offset value at each iteration is:

offset = maxOffset - ( ( maxOffset - minOffset )  * i ) / iterations

When we pick random lines to intersect with the heightfield, we pick two random points within the heightfield and we use them to determine the line.

Also, we add the concept of erosion by using a low pass filter on the heightmap. This filter reduce the noise (in this case, the variance of heights from one point to his neighbors). Because fault lines generate huge differences between neighboring heights, we provide a parameter to set the frequency of the filter as well as an erosion factor.

Here’s some screenshots to illustrate fault lines:

This heightmap is generated using random values.

This heightmap is generated using a few fault lines without filtering.

This heightmap is generated with more fault lines without filtering.

This heightmap is generated used a lot of fault lines without filtering.

This heightmap is generated used a lot of fault lines with average filtering.

The same heightmap as above in wireframe, notice the effect of the low pass filter.

This heightmap is generated with low filtering and few fault lines.

This heightmap is generated with more fault lines with heavy filtering.

As you can see, by playing with the fault generation settings, you can have a wide range of results.

Now let’s see how it works in the code:

First, I added a HeightmapFaultSettings class which is used as a container for the minimumDelta, maximumDelta (both used for the offset calculation), the number of iterations, the nomber of iterations per filtering, and the filter value (between 0.0 and 1.0).

Here’s the meat of the heightmap class that deals with fault generation:

You have probably noticed that I added a simple RandomHelper class to avoid rewriting the same code everywhere in the project.

In the GameFOT class, I have just added a few lines to display the current algorithm used for the terrain. You can press B or Enter to go from one heightmap to another.

You can download the source code here.

In this part, we add the support of terrain patches. Terrain patches are small part of the terrain geometry. Patches are used to cull the terrain efficiently and avoid to draw the whole terrain geometry at each frame. By reducing the number of patches to draw, we reduce the number of draw calls to make.

Here’s two screenshots of the terrain patches clearly visible:

In the wireframe screenshot, you can see that each patch is composed of the same amount of geometry. In later tutorials, we will introduce the concept of level of detail at the terrain patch level. Also, you can deduce from the screenshots that the patch size matters a lot in the efficiency of the culling. The best way to balance the patch size vs batching draw calls is by profiling the performance of the application.

How are we culling the terrain patches ? Simply by computing the bounding frustum of the camera then testing for each patch, if its bounding box is contained or not inside of the frustum. If the terrain patch is inside of the frustum, we simply draw it.

Here’s two screenshots of the final sample:

In the first screenshot, you can see that the whole terrain is drawn, therefore all terrain patches are inside of the bounding frustum of the camera. In the second screenshot, you can see that only a subset of the terrain is inside of the frustum. In this case, 37 patches are visible or partially visible.

In the fly camera class, we add a bounding frustum variable and we expose it using a public property. In the update function, we compute the bounding frustum by using its constructor. We pass to the constructor the multiplication of the view matrix by the projection matrix.

Here’s the new TerrainPatch class:

Most of the terrain patch code comes from the old terrain code.

Here’s the new terrain code:

In the GameFOT class, we simply add a sprite batch and a sprite font to display the patch count and the drawn patch count of the terrain.

That’s it !

Here you can download the source code.

A picture is worth a thousand words:

That’s what we’re making in this part. The terrain is textured using multiple textures, based on the height at each vertex. Also, we compute the normal at each vertex and use it to light the terrain with a directional source. Here’s the changes since part 105.

In the heightmap class, we remove all code related to the heightmask, and we add the following constructor:

The fly camera class is slightly updated to move faster because of the increased terrain size. The input manager is kept as before.

Most of the changes happen in the terrain class. First, we add four textures, one for the ground level, one for the mud level, one for the rocky level and one for the snow level. The ground is the lowest height and the snow the highest one. We change the old VertexPositionColor format used for the geometry to VertexPositionNormalTexture everywhere in the code.

The textures are loaded in the LoadGraphicsContent method:

The draw method is now also responsible of moving the directional light using a circle pattern. Also, we pass to the effect shader a vector3 called “g_vecHeights”. This vector contains the heights of each texture levels.

The BuildVertexBuffer method is updated to compute the vertex normal. We compute each vertex normal using the ComputeVertexNormal method.

Here’s the new function:

The TerrainEffect.fx shader have new uniform extern variables for the light direction, the terrain level heights, the four textures their samplers. The vertex shader transform the vertices, compute the diffuse color (which is uniform and used to light the terrain), the specular color for the snowy level. Also, it computes the ratio of each texture for each vertex and multiply it by the lighting value and it scales down the texture coordinates. The pixel shader simply apply the textures.

Here’s the effect shader:

In the GameFOT class, we add a simple flag to check if we just started the application in the LoadGraphicsContent method. We do that because we load the terrain geometry from a greyscale bitmap texture. The scene is initialized like this:

Here’s the source code of this part.