Dustin Horne

Developing for fun...

UPDATE:  If you've been following this terrain series you have probably seen some bugs and a few things that I've overlooked.  I spent the last few days following my own tutorial, updating the series text, and fixing and refactoring the code.  If you don't want to start the tutorial over just to find the few changes I've made, you can download the complete solution for parts 1 through 4 here: Terrain Solution Parts 1 through 4

In the first three parts of this tutorial we examined creating the basic data structures to hold our terrain data and structuring our QuadTree.  In this part of the tutorial I'm going to show you how to activate different depths of the terrain and draw it based on which vertices are active.  We won't get into dynamic LOD until the next section, but when we do you'll have a good idea of how we're going to output our indices and draw our specific triangles.  If you haven't already read the first three sections of this tutorial, please visit the table of contents page and check them out.

The first thing we're going to do is prepare our QuadTree for drawing.  We're going to initiaze a BasicEffect with a blank texture and add the relevant Draw and Update methods to our QuadTree.  We'll then update the BasicEffect to use a texture we choose.  To start, let's go ahead and add a BasicEffect to our QuadTree.cs file.  Go ahead and add a new field to the top of the class:

`public BasicEffect Effect;`

Next we're going to set the starting effect parameters, so navigate to the QuadTree constructor and add the following:

```Effect = new BasicEffect(device);
Effect.EnableDefaultLighting();
Effect.FogEnabled = true;
Effect.FogStart = 300f;
Effect.FogEnd = 1000f;
Effect.FogColor = Color.Black.ToVector3();
Effect.TextureEnabled = true;
Effect.Texture = new Texture2D(device, 100, 100);
Effect.Projection = projectionMatrix;
Effect.View = viewMatrix;
Effect.World = Matrix.Identity;```

We've created a new BasicEffect, enabled default lighting and distance fog, and initialized it with a new blank texture and the current view and projection matrices.  We've also set the World matrix to the Identity matrix.

Now let's go ahead and create our basic Update method.  We'll continue to update this method as we progress.  It will be responsible for firing off the update process in our terrain across our quad nodes.  Go ahead and create the Update method as follows:

```		public void Update(GameTime gameTime)
{
//Only update if the camera position has changed
if (_cameraPosition == _lastCameraPosition)
return;

Effect.View = View;
Effect.Projection = Projection;

_lastCameraPosition = _cameraPosition;
IndexCount = 0;

_rootNode.SetActiveVertices();

_buffers.UpdateIndexBuffer(Indices, IndexCount);
_buffers.SwapBuffer();
}```

You'll notice that we don't have a definition for IndexCount.  Arrays are reference type objects and creating and destroying an array each round would generate garbage.  The approach we're taking is to keep track of the number of indices and specify that count later when we update the IndexBuffer.  Go ahead and add a new private field to your QuadTree class:

`internal int IndexCount { get; set; }`

We're also missing the SetActiveVertices method from our QuadNode class.  We'll get to that in a moment, but for now let's go ahead and create our Draw method:

```		public void Draw(GameTime gameTime)
{
device.SetVertexBuffer(_buffers.VertexBuffer);
device.Indices = _buffers.IndexBuffer;

foreach (EffectPass pass in Effect.CurrentTechnique.Passes)
{
pass.Apply();
device.DrawIndexedPrimitives(PrimitiveType.TriangleList, 0, 0, _vertices.Vertices.Length, 0, IndexCount / 3);
}

}```

Now that we have the basic drawing framework in place, we can add the functionality to update the index buffer.  First, let's add a method to the QuadTree class to add an item to the Indices array so we can update it from the QuadNode instances.

```		internal void UpdateBuffer(int vIndex)
{
Indices[IndexCount] = vIndex;
IndexCount++;
}```

With the drawing and indice updating capabilities created, let's move on to the QuadNode.  Go ahead and open QuadNode.cs.  Here we're going to add a method to set the active vertices for the active QuadNodes.  SetActiveVertices() will be responsible for traversing the tree and adding indices for all active vertices.  We're not yet splitting the terrain so for now we're only going to add the vertices for the top level node.  Each triangle is defined in clockwise order starting from the center vertex.  If only the 5 default vertices are active, this method will draw 4 triangles (Top, Right, Bottom and Left), however if the top, left, right, and bottom vertices are active, 8 triangles will be drawn.

```		internal void SetActiveVertices()
{

//Top Triangle(s)
_parentTree.UpdateBuffer(VertexCenter.Index);
_parentTree.UpdateBuffer(VertexTopLeft.Index);

if (VertexTop.Activated)
{
_parentTree.UpdateBuffer(VertexTop.Index);

_parentTree.UpdateBuffer(VertexCenter.Index);
_parentTree.UpdateBuffer(VertexTop.Index);
}
_parentTree.UpdateBuffer(VertexTopRight.Index);

//Right Triangle(s)
_parentTree.UpdateBuffer(VertexCenter.Index);
_parentTree.UpdateBuffer(VertexTopRight.Index);

if (VertexRight.Activated)
{
_parentTree.UpdateBuffer(VertexRight.Index);

_parentTree.UpdateBuffer(VertexCenter.Index);
_parentTree.UpdateBuffer(VertexRight.Index);
}
_parentTree.UpdateBuffer(VertexBottomRight.Index);

//Bottom Triangle(s)
_parentTree.UpdateBuffer(VertexCenter.Index);
_parentTree.UpdateBuffer(VertexBottomRight.Index);

if (VertexBottom.Activated)
{
_parentTree.UpdateBuffer(VertexBottom.Index);

_parentTree.UpdateBuffer(VertexCenter.Index);
_parentTree.UpdateBuffer(VertexBottom.Index);
}
_parentTree.UpdateBuffer(VertexBottomLeft.Index);

//Left Triangle(s)
_parentTree.UpdateBuffer(VertexCenter.Index);
_parentTree.UpdateBuffer(VertexBottomLeft.Index);

if (VertexLeft.Activated)
{
_parentTree.UpdateBuffer(VertexLeft.Index);

_parentTree.UpdateBuffer(VertexCenter.Index);
_parentTree.UpdateBuffer(VertexLeft.Index);
}
_parentTree.UpdateBuffer(VertexTopLeft.Index);
}```

Drawing our Tree

We should now have everything we need for the QuadTree to draw the terrain.  All we need now is a height map, a texture, and a camera to view the terrain with.  Let's start by creating a basic camera.  This camera will move front to back, left to right, and up and down.  It will also pitch (tilt front to back).  Go ahead and add a new class to your game project and call it Camera.cs.  For simplicity, I've added mine to my Pyrite.Terrain project.  Update it with the following code:

```using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;

namespace Pyrite.Terrain
{
public class Camera
{
//Move speed for camera
private float _moveScale = 4f;

private Vector3 _position;
private Vector3 _target;
private Matrix _view;
private Matrix _projection;
private GraphicsDevice _device;

public Matrix View { get { return _view; } }
public Matrix Projection { get { return _projection; } }
public Vector3 Position { get { return _position; } }

public Camera(Vector3 position, Vector3 target, GraphicsDevice device, float farDistance)
{
_device = device;
_position = position;
_target = target;

UpdateCamera();

_projection = Matrix.CreatePerspectiveFieldOfView(MathHelper.PiOver4, _device.Viewport.AspectRatio,
1.0f, farDistance);
}

public void Move(Vector3 translation)
{
_position.X += translation.X * _moveScale;
_position.Y += translation.Y * _moveScale;
_position.Z += translation.Z * _moveScale;

//Move the target with the camera as well
_target.X += translation.X * _moveScale;
_target.Y += translation.Y * _moveScale;
_target.Z += translation.Z * _moveScale;

UpdateCamera();

}

public void Pitch(Vector3 translation)
{
//Move the target with the camera as well
_target.X += translation.X * _moveScale;
_target.Y += translation.Y * _moveScale;
_target.Z += translation.Z * _moveScale;

UpdateCamera();
}

private void UpdateCamera()
{
_view = Matrix.CreateLookAt(_position, _target, Vector3.Up);
}

}
}```

Now that we have our camera in place, we can start setting up our Game project to display our terrain.  But first, you'll need a heightMap and a texture to display on your terrain.  I've put together a 641 x 641 height map and a jigsaw texture that you can use below.  Don't worry if it's not pretty right now, we'll use some better textures later on.  Once you've downloaded the following textures, add them to your Game's Content project.

Now let's make our changes to Game.cs.  If you don't already have it open, open your Game.cs file.  We're going to start by adding some new methods to our Game class.  In part 1 we started by adding references to our Graphics Device Manager and the Graphics Device itself.  We also added the world matrix, a DateTime and an integer to hold the frames per second as we'll be calculating this later on, as well as a BackgroundWorker to do terrain updates asynchronously.

First we're going to implement our constructor and the Initialize method.  Here we're simply creating our reference to the graphics device and turning off IsFxedTimeStep.  This will allow our game to run at arbitrary speeds and make our frames per second calculations more accurate later on.  Make sure you've added "using Pyrite.Terrain;" to the top of your Game.cs file. Replace Pyrite.Terrain with whatever you named your terrain project.  If you can't locate the namespace, make sure you've added the terrain project to your game projects references.

```		//The camera we created earlier.
Camera _camera;

//The quad tree for our terrain

public Game()
{
_graphics = new GraphicsDeviceManager(this);

}

protected override void Initialize()
{

this.IsFixedTimeStep = false;

base.Initialize();
}```

Now we're going to implement our LoadContent method.  Here we're going to be initializing some graphics settings and loading our terrain as well as setting up our camera.  Make sure you've downloaded the heightmap and texture above and placed them in the content project, then update your LoadContent method as follows:

```		protected override void LoadContent()
{
_graphics.PreferredBackBufferWidth = 1024;
_graphics.PreferredBackBufferHeight = 800;
_graphics.ApplyChanges();

_device = _graphics.GraphicsDevice;

Content.RootDirectory = "Content";

this.Window.AllowUserResizing = true;
this.IsMouseVisible = true;

_camera = new Camera(new Vector3(320, 100, 630), new Vector3(320, 0, 0), _device, 700f);

}```

So what have we done in the LoadContent method above?  We set our window to 1024 x 800 and added our reference to our graphics device.  We set our default content directory and a few other miscellaneous graphics settings.  We loaded our height map to be used for our terrain generation.  Then we got into the real meat and potatoes of the setup.

First we created an instance of our camera class.  The first parameter in our camera class is the position, or location of the eye of the camera.  The second is the target or the point we want to be looking at.  The third is our device instance, and the fourth is the max view distance which will define our projection's far clipping plane.

Next we initialized our quad tree for terrain.  The first parameter is the location of the top left corner of the terrain.  In our case we're putting the top left corner at the identity position of 0,0,0.  Next we're passing in the initial camera view and projection matrices.  We'll see those in action later when we implement view frustrum culling.  Finally we pass a reference to our graphics device and a scale factor that will determine the final physical size of our terrain.  For example, the above code uses a scale factor of 1.  This means that the top left corner of the terrain is at 0,0,0.  Our height map is 641 pixels wide so our terrain is 640 units wide.  This means our top right corner will be at 640, 0, 0.  If we apply a scale factor of 2, the top right corner will actually be at 1280, 0, 0.  For now let's leave this unscaled.

Finally, we've set a texture to the quad tree.  This texture will be used by the quad tree's basic effect to put a texture onto the terrain.  When you're ready to build your own terrain engine in production you will likely want to use something much more robust.

Updating and Drawing

With our base terrain setup and loaded, let's take care of updating and drawing the terrain.  Every frame we're going to pass in the camera's View and Projection matrices as well as call update on our terrain.  This ensures that the terrain is drawn correctly if the view and/or projection of the camera change.  We'll also update the camera position on the terrain.  For now, the camera will just be fixed but later we'll add code to allow for movement of the camera.

Go ahead and replace the Update method in Game.cs with the following:

```		protected override void Update(GameTime gameTime)
{

base.Update(gameTime);
}```

Now all that's left is to call Draw on our terrain.  Go ahead and replace the Draw method in your Game.cs with the following:

```		protected override void Draw(GameTime gameTime)
{
_device.Clear(Color.Black);

base.Draw(gameTime);
}```

The Results are In

It's time to see the results of all our hard work so far.  Go ahead and press F5 or run your project.  You should see a window with an amazing terrain... well not quite.  So far we're not actually splitting any geometry so the only node we have active is the top level node and its 5 vertices.  You should see a flat terrain something like the image below:

In order to see more detail, we need to add extra depth to our terrain.  To do this, we're going to need to activate nodes and vertices further into our terrain.  Let's start by specifying a minimum depth to use.  Go ahead and add a new public field to the QuadTree class.  We're going to use this variable for now to specify a minimum depth to activate.  Add the following to the top of QuadTree.cs:

`public int MinimumDepth = 6;`

Now, we're also going to need the ability to determine which nodes are active.  Save your QuadTree.cs file and open your QuadNode.cs file where we'll make the bulk of our remaining changes.  Let's start by adding a couple new fields to the top of our QuadNode.cs class:

```bool _isActive;
bool _isSplit;
```

We also need a way to activate the node, so create a new method called Activate as follows:

```		internal void Activate()
{
VertexTopLeft.Activated = true;
VertexTopRight.Activated = true;
VertexCenter.Activated = true;
VertexBottomLeft.Activated = true;
VertexBottomRight.Activated = true;

_isActive = true;
}```

Now we need a way to ensure we're split to the minimum split depth.  We're going to add a new method called EnforceMinimumDepth as below:

```		public void EnforceMinimumDepth()
{
if (_nodeDepth < _parentTree.MinimumDepth)
{
if (this.HasChildren)
{
_isActive = false;
_isSplit = true;

ChildTopLeft.EnforceMinimumDepth();
ChildTopRight.EnforceMinimumDepth();
ChildBottomLeft.EnforceMinimumDepth();
ChildBottomRight.EnforceMinimumDepth();
}
else
{
this.Activate();
_isSplit = false;
}

return;
}

if (_nodeDepth == _parentTree.MinimumDepth || (_nodeDepth < _parentTree.MinimumDepth && !this.HasChildren))
{
this.Activate();
_isSplit = false;
}
}```

Now we need to update our SetActiveVertices() method.  Instead of blindly setting active indices, it now needs to traverse the tree and set the active vertices for the children.  Let's return to the SetActiveVertices method in our QuadNode class.  Currently this is iterating through the vertices of the current quad and calling _parentTree.UpdateBuffer for each of the vertices.  Before we start doing this, we need to check see if this quad has been split and if it has children.  Add the following code to the TOP of the SetActiveVertices method (before any calls to _parentTree.UpdateBuffer):

```if (_isSplit && this.HasChildren)
{
ChildTopLeft.SetActiveVertices();
ChildTopRight.SetActiveVertices();
ChildBottomLeft.SetActiveVertices();
ChildBottomRight.SetActiveVertices();
return;
}```

This will now first perform the check to see if we need to look deeper in the tree for active nodes.  Now all we need to do is enforce this minimum depth.  Open QuadTree.cs again and look at your QuadTree class.  Let's go down to the Update method and find the line:  _rootNode.SetActiveVertices();.  We need to add a line just above that, so it will now look like this:

```...

_rootNode.EnforceMinimumDepth();
_rootNode.SetActiveVertices();

...```

And that's it.  Now run your project again and you should get a terrain that looks like this:

Part 4 Conclusion

Up to this point we haven't done anything too exciting.  We've generated a basic terrain from a height map and shown how to display it at different depths from a quad tree.  Go ahead and play around with different MinimumDepth levels but beware, setting a value too high will cause an exception as our IndexBuffer currently isn't large enough to hold all of our indices.

In Part 5 of this series we'll address this issue by creating a larger index buffer to hold the index data.  We'll also add some movement to allow you to traverse the terrain.  Most importantly, we'll start adding level of detail to the terrain, making the terrain progressively less detailed as it moves away from the camera.