The Editor - #1

Introduction #

First of all, let’s clear something up - I’m not a computer science student, rather I’m a mechanical engineer. Programming is something that became a hobby of mine and I started doing it in the year of 2015. My adventure started off with Python and later I came across Rust and stuck with it. Right now, along my studies, I’m making a game based on a Warcraft III mod called Island Defense, which I used to play back in 2008, and I’m using Amethyst engine written in Rust. Perhaps this project is a bit out of scope for my abilities as a game developer but I wanted to give it a try and see how far I can go. This also means I can’t make any promises game-wise, yet!

Now that we got that out of the way we can start talking programming (keep in mind that I won’t get into to much detail for some things).

Terrain Mesh #

I forgot to mention that I wanted to do something like this in a long time, but this part was always hard for me to grasp. All the tutorials I watched weren’t really helpful when it comes to the terrain mesh. I read a bit about graphics programming and rendering to get a better understanding of some basic concepts. 

For readers that are new to this kind of stuff you may ask yourself what is this terrain mesh and how do i create it? 

Well basically it’s a collection of connected triangles. Everything that you see in games nowadays - units, heroes, buildings, environment even the user interface is made up of triangles. In order to create such triangles you need, of course, three points, which in term are called vertices. These vertices can have different properties (attributes).

Let’s assume in pseudo code that a vertex struct looks something like this:

struct Vertex {
    position,
    color,
    . . .
}

Here the position and color field can be called attributes of the vertex.
You may be wondering now that I’ve got this Vertex struct what the heck do I do with it ? 

Good question! In order for us to make use of the Vertex we need to supply it to a shader, specifically the vertex shader. This shader will run for each instance of our Vertex struct it receives.

This is a bit of simplifying it, since with Amethyst you need to create another, let’s call it VertexArgs, struct which you actually send to the shader and need to implement AsVertex trait.

As far as Amethyst goes you start by creating a custom rendering pipeline. When creating this object you can set which shaders you want your pipeline to use, along with the type of the vertex and many other things - where perhaps the most important ones, for this chapter, are the primitive type: TriangleList, TriangleStrip.

You also need to bind your vertex buffer, which is just an array of your Vertex structs. Binding is actually supplying the vertex shader with the vertex buffer. The way you process each vertex in the buffer is done through the vertex shader.

NOTE: You also need to supply the transformation matrix to the shaders! Without it you won’t be able to render the vertices correctly.

Enough chitchat, let’s generate the vertex buffer:

let mut vertex_buffer = Vec::new();
for x in 0..x_size {
    for y in 0..y_size {
        let v0 = Vertex { . . . };
        let v1 = Vertex { . . . };
        let v2 = Vertex { . . . };

        let v3 = Vertex { . . . };
        let v4 = Vertex { . . . };
        let v5 = Vertex { . . . };

        vertex_buffer.extend(vec![v0, v1, v2, v3, v4, v5]); 
    }
}

Where x_size and y_size represent the number of tiles in the X and Y direction.

If you are a beginner like me you would end up with something like this:
blog_image_1.png

There are a couple of problems with this approach that I will talk about later.

Memory consumption #

This code actually generates a quad per iteration, where each quad is represented by two triangles ([v0, v1, v2] and [v3, v4, v5]). Let’s also assume (which in reality is completely plausible) that our vertex struct looks like this:

struct Vertex {
    position: [f32; 3],
    color:    [f32; 3],
}

This struct now takes 24 bytes of memory.

If we had a grid that is 3x3 tiles large we would have a total of 9 tiles (quads). Multiply this by 6 to get the number of vertices in your vertex buffer. We end up with the result of 54 vertices. The total size of the vertex buffer in bytes is 54*24 which is about 1 kilobyte of memory.

You may say that this isn’t impactful, but what if we had a grid of 100x100 tiles. This would result in 10000*6*24 which is about 1.4 megabytes of memory. Keep in mind that for some games 100x100 isn’t large at all.

The good thing is we can optimize it, and resolve the memory consumption - drastically!

Optimization #

The above example was using the primitive type called TriangleList. This primitive tells the shader how to sample the vertices you send it. If we had a list of vertices like [a, b, c, d, e, f], it would generate two triangles - [a, b, c] and [d, e, f].

Luckly for us a primitive called TriangleStrip exists. The way it generates the triangles using the same list of vertices [a, b, c, d, e, f], is like [a, b, c], [b, c, d], [c, d, e], [d, e, f] (It would also try to create a triangle with [e, f] but since there are only two vertices it will discard it.);

Now we can write the above snippet like this:

let mut vertex_buffer = Vec::new();
for x in 0..x_size {
    for y in 0..y_size {
        let v0 = Vertex { . . . };
        let v1 = Vertex { . . . };
        let v2 = Vertex { . . . };      
        let v3 = Vertex { . . . };

        vertex_buffer.extend(vec![v0, v1, v2, v3]); 
    }
}

Remember me saying that a terrain mesh it a collection of triangles, well the above example and picture for that matter show the a approach where they are not connected. The way you connect these triangles (vertices) is by using something called an index buffer. The index buffer just hold the indices into our vertex buffer! These indices can either be u16 or u32.
Depending on how much vertices you have you should set one or the other.

The above snippet is now reduces to just this:

let mut vertex_buffer = Vec::new();
for x in 0..=x_size {
    for y in 0..=y_size {
        let v = Vertex { . . . };

        vertex_buffer.push(v);  
    }
}

Notice that we take and extra index with ..= in order to generate vertices in the last lines of our grid.

The code i am using for generating the index buffer is:

        let mut ib: Vec<u32> = Vec::new();
        for y in 0..y_size as u32 {
            for x in 0..(x_size + 1) as u32 { 
                let mut nw = vec![
                        x + y * (x_size + 1) as u32,
                        x + (y + 1) * (x_size + 1) as u32,
                ];

                ib.extend(nw);
            }
        }

I won’t go into explaining here but this generates the indices for the vertex buffer. This might be different with anyone else but it needs to correspond to your vertex buffer and cannot have a bigger indice value than the size of your vertex buffer eg. vertex_buffer.len() - 1.

There is a bit of a setback with using the primitive TriangleStrip. As I’ve said if we supply it with the array that looks like this [a, b, c, d, e, f] it will generate [a, b, c], [b, c, d], [c, d, e], [d, e, f]. Now since we have a grid, and we iterate over each line of that grid we will get weird artifacts because our last triangles will not be connected properly!

This is best demonstrated with an example. Let’s assume we have a 2x3 grid.

The index buffer would look like this:

vec![0, 4, 1, 5, 2, 6, 3, 7, 4, 8,  . . .];

This would generate triangles as:

[(0, 4, 1), (4, 1, 5), (1, 5, 2), (5, 2, 6), (2, 6, 3), (6, 3, 7), (3, 7, 4), (7, 4, 8) . . .]

The problem at first isn’t really easy to notice! I thought this was all good and nice until i started changing the height of my terrain. Turns out the last two triangles in the above list are problematic - (3, 7, 4), (7, 4, 8). There triangles actually connect end of the last row to the start of the next row!

Fear not, there is a solution to this and these are deranged triangles! Basically we add additional vertices to fool the GPU, and this is the only setback that I’ve noticed with using the primitive TriangleStrip with the index buffer.

This is how a part of our list would look like now:

 [(0, 4, 1), (4, 1, 5), (1, 5, 2), (5, 2, 6), (2, 6, 3), (6, 3, 7), 
  (3, 7, 7), (7, 7, 4), (7, 4, 4), (4, 4, 8)] // Deranged triangles.
  . . .

The vertex buffer doesn’t change at all, so all that’s needed was to add extra 4 triangles per row of tiles. This doesn’t get in the way of further development of the editor.

If we take this effect into consideration, the index buffer snippet looks like this:

        let mut ib: Vec<u32> = Vec::new();
        for y in 0..y_size as u32 {
            for x in 0..(x_size + 1) as u32 { 
                let mut nw = vec![
                        x + y * (x_size + 1) as u32,
                        x + (y + 1) * (x_size + 1) as u32,
                ];

                // Adding derogatory vertices.
                if x == (x_size + 1) as u32 - 1 && y != y_size as u32 - 1 {
                    nw.push(x + (y + 1) * (x_size + 1) as u32);
                    nw.push((x + 1) * (y + 1));
                } 

                ib.extend(nw);
            }
        }

This is taking long enough so if you are a commited reader stay for one more paragraph!

Since the terrain I am trying to create only needs a heightmap (a collection of vertices that only hold the height of each vertex), our vertex struct can be additionally simplified and would look like this:

struct Vertex {
    height: f32
}

The size is only 4 bytes now, although we have to calculate the X and Y position of each vertex in our vertex shader, as well as our texture coordinates (if one needs this). We could also remove the color field since we don’t need it in this case.

To summarize with this approach the grid of 100x100 vertices would take total 118 kilobytes of memory (vertex buffer: 39KB, index buffer: 79KB ).

If you stuck till the end, thanks for reading! Unfortunately I do not have more pictures for this devlog but I assure you on the next one there will be more.

Cheers!

 
22
Kudos
 
22
Kudos