In a world where everything is made out of cubes (that computer guys like to call voxels!), it is important to be able to display a lot of them efficiently. This post describes how the game Castle Defender does it and why it needs to be optimised!
Now that we know how the cubes in the world are stored (if you don't, then go read part1 now!), we can talk about how they are displayed.
First of all, I should mention that there are already a few articles out there on how to generate a mesh for a voxel geometry, so I'm not going into too much detail here. I personally recommend this article, which comes with a really nice javascript demo.
Let's have a look at the new castle model for the game menu screen.
This model is stored as a 25x64x32 voxel grid, thus a total of 51200 voxels! However, a lot of them are empty and in the end, the castle, the ground and the clouds are made out of only 7194 voxels. (This shows that more than 85% of the voxels are empty, so maybe it would be interesting to find a better storage technique after all! But that's for another day.)
To display these voxel, the first method that comes to mind is to display a cube for each non-empty voxel, at the position of the voxel. The empty voxels don't need to be displayed, since we can't see them! So the first basic (and stupid!) algorithm will look like something like this:
Listing 1: stupid algorithm
for each voxel in array
if voxel is not empty then
display cube at voxel position
end if
end for
Using this algorithm, the castle is displayed as 7194 cubes, and as each cube is made of 6 square faces (also called quads) it uses a total of more than 43000 quads. The following image shows us the same castle using the stupid algorithm. The faces are displayed in "wireframe mode" so the hidden ones (the ones that are behind other ones) can be seen.
As you can see, it's a huge mess! This is because the stupid algorithm creates a lot of faces that will never be seen by the player. For example, all the cubes inside the two towers (and that's not a reference to the Lord of the Rings!) are not visible as they are hidden by other cubes on the surface of the towers.
To improve the algorithm, we'd like to display only the faces that we can see. This can be a bit tricky, but the first way to reduce drastically the number of quads is to notice that only the voxels in contact with empty voxels have faces that can be seen by the player. In fact, only the faces that are in between an empty voxel and a solid voxel can be seen, the others are either buried underground or stuck inside a structure. The following algorithm only display the faces that can potentially be seen by the player, by culling the ones that are inside the structure.
Listing 2: culling algorithm
for each voxel in array
if voxel is not empty then
if voxel above is empty then
display top face
end if
if voxel under is empty then
display bottom face
end if
if voxel on the right is empty then
display right face
end if
if voxel on the left is empty then
display left face
end if
if voxel on the front is empty then
display front face
end if
if voxel on the back is empty then
display back face
end if
end if
end for
As you can see, the algorithm is a little longer (just a little!) and contains a lot of if conditions. But let's see how efficiently it reduces the number of quads.
As you can see when comparing with the previous image, the number of quads is significantly reduced. A counter on the number of faces shows that the castle is now displayed using 7626 faces. The number of faces was almost reduced by 6!
The culling algorithm is more or less what Castle Defender uses at the minute. It could still be improved. For instance the faces that point in the opposite direction of the camera are always hidden by the faces that point towards the camera, so the algorithm could be aware of the relative camera position in order to further select the visible faces.
Another optimisation would be to combine adjacent quads into a single bigger quad. This is what this article calls the "greedy meshing". For instance, if you look at the ground, you can see that it's mainly flat, so it could be displayed by using only a few large quads that would merge all the smaller quads. Careful however, as the ground is made of voxels with different colours, limiting the merging of the quads. But one could imagine still merging the quads together and dynamically building a texture based on the voxel colours that would be applied on the top...
In the end, my opinion is that it's not worth the hassle. And there are also lots of other techniques that I don't have the time to talk about: occlusion culling, voxel resampling... !
That's all for today!
To sum up, only the faces of a voxel that are in contact with an empty voxel are displayed, which is fairly easy to program, and reduces the number of quads efficiently. But still... at each frame thousands of faces are computed, their coordinates are sent to the graphic card one by one, where they are rendered then discarded. Wouldn't it be better if we could store them on the graphic card, and simply ask only for them to be rendered at each frame? Wouldn't this provide a huge speed-up?
The answer is simple: yes we can and indeed it does!
And also, that's what we'll talk about in part 3!
Cheers,
Nick
Part 2/ The Display
Now that we know how the cubes in the world are stored (if you don't, then go read part1 now!), we can talk about how they are displayed.
First of all, I should mention that there are already a few articles out there on how to generate a mesh for a voxel geometry, so I'm not going into too much detail here. I personally recommend this article, which comes with a really nice javascript demo.
Let's have a look at the new castle model for the game menu screen.
 |
| A nice voxel castle! |
To display these voxel, the first method that comes to mind is to display a cube for each non-empty voxel, at the position of the voxel. The empty voxels don't need to be displayed, since we can't see them! So the first basic (and stupid!) algorithm will look like something like this:
Listing 1: stupid algorithm
for each voxel in array
if voxel is not empty then
display cube at voxel position
end if
end for
Using this algorithm, the castle is displayed as 7194 cubes, and as each cube is made of 6 square faces (also called quads) it uses a total of more than 43000 quads. The following image shows us the same castle using the stupid algorithm. The faces are displayed in "wireframe mode" so the hidden ones (the ones that are behind other ones) can be seen.
 | |
| Too many quads! |
To improve the algorithm, we'd like to display only the faces that we can see. This can be a bit tricky, but the first way to reduce drastically the number of quads is to notice that only the voxels in contact with empty voxels have faces that can be seen by the player. In fact, only the faces that are in between an empty voxel and a solid voxel can be seen, the others are either buried underground or stuck inside a structure. The following algorithm only display the faces that can potentially be seen by the player, by culling the ones that are inside the structure.
Listing 2: culling algorithm
for each voxel in array
if voxel is not empty then
if voxel above is empty then
display top face
end if
if voxel under is empty then
display bottom face
end if
if voxel on the right is empty then
display right face
end if
if voxel on the left is empty then
display left face
end if
if voxel on the front is empty then
display front face
end if
if voxel on the back is empty then
display back face
end if
end if
end for
As you can see, the algorithm is a little longer (just a little!) and contains a lot of if conditions. But let's see how efficiently it reduces the number of quads.
 |
| Not so many quads! |
The culling algorithm is more or less what Castle Defender uses at the minute. It could still be improved. For instance the faces that point in the opposite direction of the camera are always hidden by the faces that point towards the camera, so the algorithm could be aware of the relative camera position in order to further select the visible faces.
Another optimisation would be to combine adjacent quads into a single bigger quad. This is what this article calls the "greedy meshing". For instance, if you look at the ground, you can see that it's mainly flat, so it could be displayed by using only a few large quads that would merge all the smaller quads. Careful however, as the ground is made of voxels with different colours, limiting the merging of the quads. But one could imagine still merging the quads together and dynamically building a texture based on the voxel colours that would be applied on the top...
In the end, my opinion is that it's not worth the hassle. And there are also lots of other techniques that I don't have the time to talk about: occlusion culling, voxel resampling... !
That's all for today!
To sum up, only the faces of a voxel that are in contact with an empty voxel are displayed, which is fairly easy to program, and reduces the number of quads efficiently. But still... at each frame thousands of faces are computed, their coordinates are sent to the graphic card one by one, where they are rendered then discarded. Wouldn't it be better if we could store them on the graphic card, and simply ask only for them to be rendered at each frame? Wouldn't this provide a huge speed-up?
The answer is simple: yes we can and indeed it does!
And also, that's what we'll talk about in part 3!
Cheers,
Nick
No comments:
Post a Comment