One of the most interesting topics for me is the way terrain is
generated and the feeling of outdoor scenes. What I am going to do
today is refactor my terrain engine but as an added bonus is I am going
to list the terrain generation algorithm here for future references for
anyone that wants to do a quick lookup and understand it. In Direct3D
all counter clockwise created triangles are culled. This means that if
you specify a triangle creation in counter clockwise order by default
Direct3D will not render it. This is just a little information before
we continue ;)
So what do we need to do?
We need to create a triangle mesh that will be used for a base of our
terrain. Right now we aren't really concerned about the heights as that
will involve another post but let's continue...
Well here is a little image that will probably make things a little more clear.
Do you notice anything out of place? Notice that I have specified
triangles in the counter clockwise order, from what I said earlier
Direct3D culls counter clockwise triangles. Why did I choose it? Well
it's because the algorithm I have generates the triangles in that order
and it's easy to read. You could probably go further and work out an
algorithm that will generate your triangles in a clockwise ordering but
it's just 2 renderstates that I need to set so that's not really going
to bother me.
Device.RenderState.CullMode = Cull.Clockwise;
//Render my terrain
Device.RenderState.CullMode = Cull.CounterClockwise;
The Algorithm
Let's first look at the vertices. For performance reasons we will use a
vertex and buffer setup. Index buffers are basically indices that show
direct3d how different vertices are connected to form primitives. So we
just need 1 set of non-duplicated vertices and the index generation
method will be the real challenge here.
Vertex Generation
So the vertex generation is simple.
Example
ArrayList vertices =
new ArrayList();
for (
int y = 0; y < height; y++)
{
for (
int x = 0; x < width; x++)
{
vertices.Add(
new Point(x, y));
}
}
This will just generate vertices based on the width and height of the terrain, very clean and simple.
Index Generation
The index generation is a bit tricky and the easiest way to solve these
problems is to take some test data and write them down. So let's take
some test data.
As you can see the data is exactly what we wanted and now we can start
to notice some cool things about the data and working out algorithms
are really fun. So let's match these up with the indices that we want
created... to see how we can work out this algorithm.
For a 3 x 3 terrain we have the following data set.
Vertex Data
(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)
Index Data
Triangle 1 : 0, 1, 4
Triangle 2 : 0, 4, 3
Triangle 3 : 1, 2, 5
Triangle 4 : 1, 5, 4
Triangle 5 : 3, 4, 7
Triangle 6 : 3, 7, 6
Triangle 7 : 4, 5, 8
Triangle 8 : 4, 8, 7
How interesting is this? We can now figure out what's going on here...
So let's take a though pattern step and look at x and y in each iteration of our nested for loop.
Iteration 1
x = 0; and y = 0;
Iteration 2
x = 1; and y = 0;
Iteration 3
x = 1; and y = 0; and so on....
The Complete Algorithm
One thought is that we might be able to generate a complete primitive
in each iteration... Yep that's a good idea so let's work on that.
Iteration 1
x = 0; and y = 0;
Triangle 1 : 0, 1, 4
Triangle 2 : 0, 4, 3
We need to get 0, 1, 4, 0, 4, 3 in order.
So how does this look?
ArrayList indices = new ArrayList();
for (
int y = 0; y < height - 1; y++)
{
for (
int x = 0; x < width - 1; x++)
{
indices.Add(y * width + x);
indices.Add(y * width + x + 1);
indices.Add((y + 1) * width + x + 1);
indices.Add(y * width + x);
indices.Add((y + 1) * width + x + 1);
indices.Add((y + 1) * width + x);
}
}
That works and so I carry on to explore the deeper meaning of terrain generation and tommorow I will post some screenshots...
Till then...