In this second part of the terrain series, we're going to build some of the data structures we'll be using for our terrain. If you haven't already done so, please read Part 1 of the terrain series.
The most imporant piece of our terrain project is the terrain data and more specifically the vertex data. Calculating all of the vertex data can be fairly CPU and time intensive and this is not something we want to do every frame. For this reason, we're going to setup some simple data objects to store our vertex data. Remember from part 1 of the series I said we're working with VertexPositionNormalTexture. This allows us to easily send vertex data to the BasicEffect class and draw a simple texture with little effort. You may decide you want to use a different vertex type and draw the data differently. This is entirely up to you, but I would recommend sticking with VertexPositionNormalTexture for the duration of this series.
This series is designed to help you easily understand how the terrain and LODing is working. I plan to follow this series up with a second one where we'll make enhancements and performance improvements to our terrain generation.
TreeVertexCollection
To keep things fairly simple, I'm using a TreeVertexCollection class to store all of my vertices for the QuadTree and some extra data that may be useful later. The TreeVertexCollection class keeps track of the position of the terrain as a Vector3, the size of the terrain, the total vertex count, an array of VertexPositionNormalTexture and the scale of the terrain. The width of the terrain is determined by the size of the supplied heightmap. This represents the initial unscaled width, not the final physical size of the terrain.
IMPORTANT:
A quick but important note on Height Map sizes... In order for the quad tree to properly divide the terrain, the size of the terrain needs to be a value divisible by 8. This is one less than the number of vertices. So for a terrain with a width of 256 x 256, your height map must be 257px x 257px. This will make more sense later in the series when we examine the layout of the vertices for each quad node.
To start, go ahead and open the new Windows Game solution you created in Part 1 of this tutorial. We're going to add a new project to the solution for our terrain. Go ahead and add a new project to the solution and choose Windows Game Library under XNA Game Studio 4.0. You can call your new project anything you'd like. I'm working on my own engine which I call Pyrite, so I've chosen Pyrite.Terrain as my project name. Once you're new project is added, delete Class1.cs.
Start by right clicking in your project, add new item, and add a new class. We're going to call this class TreeVertexCollection. As I stated earlier, we're storing an array for the vertices, the initial terrain size, the vertex count, and the scale. We are also going to store the "half size" of the terrain. This is to reduce calculations within a loop you will see soon. Your TreeVertexCollection class should look something like this:
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
namespace Pyrite.Terrain
{
public class TreeVertexCollection
{
public VertexPositionNormalTexture[] Vertices;
Vector3 _position;
int _topSize;
int _halfSize;
int _vertexCount;
int _scale;
public VertexPositionNormalTexture this[int index]
{
get { return Vertices[index]; }
set { Vertices[index] = value; }
}
public TreeVertexCollection(Vector3 position, Texture2D heightMap, int scale)
{
}
}
We've setup the constructor to take 3 arguments: position, heightMap, and scale. Position is going to represent the position of the top-left corner of your terrain in 3D space. The "Y" value of position will represent the absolute lowest position in our terrain, so if you'd like the lowest point in the terrain to be 0, just use 0 for your "Y" value. In my testing I just position the upper left corner of the terrain at the identity position: Vector3.Zero.
The heightMap is just a Texture2D loaded from an image, preferrably grayscale. Remember that the width of the heightmap must be a multiple of 8 plus one, so if we're developing a 1024 x 1024 terrain, the heightmap should be 1025 x 1025. If you're unsure if your terrain is a correct dimension, simply subtract 1 and divide by 8. If the result is not a whole number (i.e. there is a decimal place), your terrain is not a size that will work with this implementation. Also, avoid using heightMaps any larger than 1025 x 1025. This already results in a very high vertex count (1,050,625). Ideally, for large terrains a paging system should be implemented to only load the necessary pieces. How you determine the sizes to split really depend on the scale of your world, but keep this in mind: too small of chunks will result in a high number of vertex buffer changes and a lot of draw calls which will negatively affect performance, but larger chunks mean more calculations and more vertex data per "page", which would quickly consume a large amount of memory if loading more than one at a time, for instance if you're near the corner of 4 terrain chunks, then all 4 chunks would need to be loaded and processed.
Change your TreeVertexCollection constructor to look like this:
public TreeVertexCollection(Vector3 position, Texture2D heightMap, int scale)
{
_scale = scale;
_topSize = heightMap.Width - 1;
_halfSize = _topSize / 2;
_position = position;
_vertexCount = heightMap.Width * heightMap.Width;
//Initialize our array to hold the vertices
Vertices = new VertexPositionNormalTexture[_vertexCount];
//Our method to populate the vertex collection
BuildVertices(heightMap);
//Our method to calculate the normals for all vertices
CalculateAllNormals();
}
Now that we have our constructor created we can code out our methods to populate the vertice list and calculate the normals for all of the vertices. We'll begin by writing our BuildVertices method. We're going to build our vertices based on the dimensions of the heightmap. There are a couple of different approaches we can use here. We can use a two-dimensional array which makes populating easy, or we can transform the two-dimensional terrain data into a single dimension array. The latter lends better to our task as it makes lookups by index quicker and also results in an array this is already appropriate to use for a VertexBuffer later on.
We know there are heightMap.Width * heightMap.Width vertices and we've already initialized our array to this size. Our starting x, y and z positions will be those specified for the top left corner. We're going to calculate each vertex's Y position using the grayscale heightmap we supplied. In grayscale images the three color channels, Red, Green and Blue all contain the same value for each pixel. Equal amounts of Red, Green and Blue result in a gray color with exception of R:0, G:0, and B:0 which is black and R:255, G:255, and B:255 which is blue.
In our example we are using the value of the red channel as our height value. Depending on the transition between shades of adjacent vertices, this may result in some pretty dramatic or mellow height changes. We're going to write this to use a scale factor for the height, width and depth values. Using a value less than one, such as 0.25f, would result in softer height transitions and a lower maximum height. Using a value greater than one, such as 5.0f, would result in much more pronounced height changes. You could even designate ranges. So, let's say the Red value is less than 200. You could say all values less than 200 would be multiplied by a scale of 0.75f, making the height changes more subtle. But maybe values greater than 200 (i.e. 201 to 255) represent mountains and multiply these values by a higher factor, such as 2.0f. When you're playing with this, be creative.
For now, we're just going to scale the literal pixel value down by 5.0f for our Y value to reduce the change in height. We'll be adding that value to _position.Y since that is our base starting point, and when we construct our vertice, we will be multiplying each x, y and z value by our _scale factor. The reason for this is so we can achieve terrain that covers a much larger area without adding additional vertices, yet it will still have a reasonable level of detail. So let's say our heightMap is 1025 x 1025. That is the number of pixels, or vertices our terrain will contain. If we didn't use a scale factor, the terrain would be 1024 units wide by 1024 units long. If we use a scale factor of, say 2, our terrain will actually cover a larger physical area.
For instance, let's say you have a starting position of Vector3.Zero (which is X = 0, Y = 0, Z = 0). Setting height aside for now, let's assume you have a flat map. If your heightmap were all black and the size was 1025 x 1025, the top right corner vertex of your terrain would be {X = 1024, Y = 0, Z = 0} and the bottom right corner (closest to you) would be: {X = 1024, Y = 0, Z = 1024}. Now let's say you apply a scale factor of 2. Your bottom right corner would now become {X = 2048, Y = 0, Z = 2048}. You could even rewrite this to scale your x, y and z values separately.
So now let's code our BuildVertices method. In this method _maxX represents the maximum value of the X position before X is reset to the original position and Z is increased by 1. Look at it as though it were a grid of fixed size. You go through the cells one by one until you reach the last cell in the row, then you reset your position to the first cell and drop down to the next row. Here is the code for the BuildVertices method which takes the heightMap as a parameter:
private void BuildVertices(Texture2D heightMap)
{
var heightMapColors = new Color[_vertexCount];
heightMap.GetData(heightMapColors);
float x = _position.X;
float z = _position.Z;
float y = _position.Y;
float maxX = x + _topSize;
for (int i = 0; i < _vertexCount; i++)
{
if (x > maxX)
{
x = _position.X;
z++;
}
y = _position.Y + (heightMapColors[i].R / 5.0f);
var vert = new VertexPositionNormalTexture(new Vector3(x * _scale, y * _scale, z * _scale), Vector3.Zero, Vector2.Zero);
vert.TextureCoordinate = new Vector2((vert.Position.X - _position.X) / _topSize, (vert.Position.Z - _position.Z) / _topSize);
Vertices[i] = vert;
x++;
}
}
Now that we have our vertices constructed, we can move on to calculating the normals for each vertice in our terrain. For better visual effects, this could be done dynamically in the shader or by using a normal map, but for simplicity we're just calculating all of the normals ahead of time and storing them with our vertices. I won't get too in depth as to how the normals are being calculated here, but in general I've treated each set of vertices like a triangle fan. I'm starting with the second vertex in the second row and calculating the normals for the triangles it forms with adjacent vertices. Then I'm moving two vertices to the right and repeating until I reach the second to last vertice, at which point I'm moving down two rows and starting the process over until I've calculated the vertex normals for each possible triangle in our terrain. Here is the code for the CalculateAllNormals() method which traverses the array of vertices and the SetNormals() method which calculates the normal for each triangle. If this is an area where people would like more information, I can try to elaborate more later and possible include some diagrams to show the triangles being formed and calculated:
private void CalculateAllNormals()
{
if (_vertexCount < 9)
return;
int i = _topSize + 2, j = 0, k = i + _topSize;
for (int n = 0; i <= (_vertexCount - _topSize) - 2; i += 2, n++, j += 2, k += 2)
{
if (n == _halfSize)
{
n = 0;
i += _topSize + 2;
j += _topSize + 2;
k += _topSize + 2;
}
//Calculate normals for each of the 8 triangles
SetNormals(i, j, j + 1);
SetNormals(i, j + 1, j + 2);
SetNormals(i, j + 2, i + 1);
SetNormals(i, i + 1, k + 2);
SetNormals(i, k + 2, k + 1);
SetNormals(i, k + 1, k);
SetNormals(i, k, i - 1);
SetNormals(i, i - 1, j);
}
}
private void SetNormals(int idx1, int idx2, int idx3)
{
if (idx3 >= Vertices.Length)
idx3 = Vertices.Length - 1;
var normal = Vector3.Cross(Vertices[idx2].Position - Vertices[idx1].Position, Vertices[idx1].Position - Vertices[idx3].Position);
normal.Normalize();
Vertices[idx1].Normal += normal;
Vertices[idx2].Normal += normal;
Vertices[idx3].Normal += normal;
}
That wraps up our TreeVertexCollection class. Now we have the entire set of vertices and relevant information that we can send to the graphics card. The next class we're going to talk about is the BufferManager which is really a simple manager that takes care of initializing the vertex buffer with all of our vertex data and updating and swapping the active index buffer.
BufferManager
As stated, the buffer manager is responsible for managing the active vertex and index buffers. In our case, we only have a single VertexBuffer and two IndexBuffer's that are swapped out when updated. In production however, you may be using larger, more complex terrains and implementing paging in which this class could be restructured to account for multiples of each active terrain segment.
The BufferManager class holds three important pieces of data: An integer value representing which index buffer is active, a vertex buffer, and an array containing two index buffers. During initialization, the BufferManager accepts the array of vertices we created and a reference to the graphics device. It then sets the vertex data to the inactive vertex buffer. In this example, the index buffers are initialized large enough to hold 100,000 indices. Later in the series we will explore the drawbacks to this and how it can be improved.
Additionally, the BufferManager contains a property which returns the active index buffer, a method that updates the inactive index buffer, and a method that swaps the active and inactive index buffers. Here is the entire code for the BufferManager class.
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
namespace Pyrite.Terrain
{
internal class BufferManager
{
int _active = 0;
internal VertexBuffer VertexBuffer;
IndexBuffer[] _IndexBuffers;
GraphicsDevice _device;
internal BufferManager(VertexPositionNormalTexture[] vertices, GraphicsDevice device)
{
_device = device;
VertexBuffer = new VertexBuffer(device, VertexPositionNormalTexture.VertexDeclaration, vertices.Length, BufferUsage.WriteOnly);
VertexBuffer.SetData(vertices);
_IndexBuffers = new IndexBuffer[]
{
new IndexBuffer(_device, IndexElementSize.ThirtyTwoBits, 100000, BufferUsage.WriteOnly),
new IndexBuffer(_device, IndexElementSize.ThirtyTwoBits, 100000, BufferUsage.WriteOnly)
};
}
internal IndexBuffer IndexBuffer
{
get { return _IndexBuffers[_active]; }
}
internal void UpdateIndexBuffer(int[] indices, int indexCount)
{
int inactive = _active == 0 ? 1 : 0;
_IndexBuffers[inactive].SetData(indices, 0, indexCount);
}
internal void SwapBuffer()
{
_active = _active == 0 ? 1 : 0;;
}
}
}
Part 2 Conclusion
Now we've seen the two main data storage classes. These handle the data needed by the graphics card. In Part 3 of this series we'll look at how to structure the QuadTree and examine how it divides the vertex space. As always, please feel free to comment with questions or suggestions an how I can improve this tutorial series or my terrain implementation.
<< Go back to Part 1 Terrain Series Table of Contents Go to Part 3 >>