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 DataTriangle 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 2x = 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 1x = 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...