Resistance is Futile

It may not be futile, but it is very difficult to resist coding new features when some maintenance needs to be done on what has already been developed. The desire to implement the next big thing is tempting. However I have thus far succeeded in doing what I believe needs to be done in order to improve decade as it exists already.

Friends have told me that premature optimizations are the death of many projects; however I don’t feel that what I am doing now is really optimising. This has always been a learning project, not exactly made up as I went along, but that does have an element of truth. It was best implemented at the time based on what I knew, and through experience learned from my implementation, experimenting and reading I now see there are better and faster ways to do things. Further developments also rely on these better ways of doing the basic things therefore it is important that they are implemented now. e.g. Water will rely on geomipmapped terrain to

A) Reduce the Number of water polygons rendered and
B) Reduce the number of water vertices updated and projected to screen

Improvements made this week are....

Use triangle strips rather than triangle lists when rendering Terrain/Water patches.
I have been told in a forum that the more information passed to the GC (Graphics Card) the faster it can render so therefore triangle lists are the best for performance. I cannot find any information to back this up so I will test for myself, but I find it difficult to believe that this is true. Consider the amount of information that needs to be passed each frame....

Patch Size = 17
Triangle List would have 1734 Indices for Patch of highest LOD
Triangle Strip would have 644 Indices for Patch of highest LOD

and presume there are 1000 patches rendered a frame (in a 1024*1024 terrain there would be 3721 Patches) there is a huge difference in the amount of index data sent to the GC. 1764000 as opposed to 644000. Decade supports lists and strips for terrain patch rendering so I will at some stage benchmark the performance of both.


Remove Terrain Cracks.
In terrains which support Level of Details (LOD) artefact's called cracks can appear. These can caused when a terrain patch has another terrain patch with a lower LOD as its neighbour. In the image below you can see the cracks in the distance. I have removed the skybox because the black background highlights the cracks.

Below you can see an up-close image of the cracks. In reality it would not be possible to see a crack this close because as stated it is when a patch neighbours a patch with lower LOD, and that will always occur in the distance. The wire frame image should make it more apparent why these artefact's occur.

There are 2 methods to remove the crack. The 1st is "Vertex Insertion" into the patch with the lower LOD. This is not a difficult task; however it is the more complex of the 2 methods so we will ignore it. The 2nd and preferred method is "Vertex Removal" from the patch with the higher LOD. Decade presumes that a patch can only neighbour a patch with an LOD that is the same as its own, or has a difference of 1. (i.e. 1 Level Greater than or less than its own). With this being the case, to remove a vertex from a patch we simply navigate the index buffer to the indices relating to the side of the patch in the direction of its neighbour (North, South, East or West) and remove every 2nd index. And to make it even more simple, we don’t even have to "remove" the index. By setting the index equal to the next index in the array we visually remove the vertex from the patch, however it is still theoretically present, but rendered as a degenerate triangle (a triangle which has 2 vertices the same, hence no area) and apparently OpenGL and DX can recognise degenerate triangles and do not even send them to the GC.

To further improve the speed of Decade, all this is pre-calculated. For every LOD which the terrain supports 16 index buffers are created.

00 None Lower
01 West Lower
02 East Lower
03 East-West Lower
04 South Lower
05 South-West Lower
06 South-East Lower
07 South-East-West Lower
08 North Lower
09 North-West Lower
10 North-East Lower
11 North-East-West Lower
12 North-South Lower
13 North-South-West Lower
14 North-South-East Lower
15 North-South-East-West Lower

and during run time the correct index buffer is selected and applied to the associated vertex buffer. Many tutorials I have seen update the index information at run-time however I think this is unreasonable for high performance in a large terrain. In Decade a Nibble (Half a Byte) is used in order to select the required index buffer.

1000 = North Patch is Lower LOD
0100 = South Patch is Lower LOD
0010 = East Patch is Lower LOD
0001 = West Patch is Lower LOD

So the pseudo code for selecting the correct index buffer to use would be

byte IndexBuffer = 0x00;
if North Neighbour's LOD LessThan This Patch's LOD
IndexBuffer = IndexBuffer XOR 8 (1000 in Binary)
if South Neighbour's LOD LessThan This Patch's LOD
IndexBuffer = IndexBuffer XOR 4 (0100 in Binary)
if East Neighbour's LOD LessThan This Patch's LOD
IndexBuffer = IndexBuffer XOR 2 (0010 in Binary)
if West Neighbour's LOD LessThan This Patch's LOD
IndexBuffer = IndexBuffer XOR 1 (0001 in Binary)

For example presume that we had a Patch which had the following Neighbours. North and West = Same LOD as the Patch, South and East has a Lower LOD. Running through the above code we would hit the lines

IndexBuffer = 0x00;
IndexBuffer = IndexBuffer XOR 4
IndexBuffer = IndexBuffer XOR 2

which gives us IndexBuffer of 0110 or 6. Referencing the above array we see that index 6 provides the Index Buffer for a Patch with South and East having lower LOD's which is exactly what we required.

This has been my first attempt to make my posts a Little more technical. I hope I succeeded in explaining how I was achieving certain behaviour in Decade. I would be delighted to hear your questions or comments.