Random Issues

Not a list of random issues, as the name suggests, but an issue with Random Number Generation. Both my procedural terrain generation techniques (Fault Formation and Midpoint Displacement) use pseudo random numbers. The other day when comparing Decade with Decade.NET it was quiet obvious that 2 very different terrains were built even though the same seed and procedural algorithms were used.

Creating 2 basic programs, 1 in C++ and another in C#, I generated 10 random numbers using the seed '12345'. The C++ program generated "7584-19164-25795-22125-5828-23405-27477-5413-29072-23404" while the C# program generated "143337951-150666398-1663795458-1097663221-1912597933-1776631026-356393799-1580828476-558810388-1086637143". I then limited the C# number generation to be between 0 and RAND_MAX (32767) as the C++ rand() function does, but the results were still incorrect with "2187-2298-25386-46748-26131-27108-5437-24120-8526-16580" being generated.

The easiest way to over come this has been to create a Managed C++ DLL with members to seed and create random numbers. This DLL is added as a reference to Decade.NET and it is used to get a random number rather than the Random object. Now both Decade and Decade.NET produce the same random numbers for a given seed any procedural work based on random numbers will match.

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.

Vertex Projected Reflections

A new implementation was required in order to achieve better looking software water. It is slightly more complicated, a little more CPU expensive but I feel the results are allot more appealing and worth it. No hardware acceleration was used so this should hopefully work on any computer.

The differences are:

Previous

• Invert the scene so that it is upside down
• Setup the clipping plane so that only vertices above the water (those that will be reflected) are drawn
• Draw the scene
• Disable the clipping plane
• Render scene as normal

Now

• Invert the scene so that it is upside down
• Setup the clipping plane so that only vertices above the water (those that will be reflected) are drawn
• Render the scene to a texture to be used when rendering the water
• Project each of the water vertices to screen coordinates. Set these values as water texture coordinates
• Render scene as normal

Further optimizations are to be added for the water. Use a terrain approach to render the water by splitting it into patches and rendering with a level of detail therefore reducing the polygons drawn in the distance. As well as reducing the number of polygons rendered I should be able equally cut the number of water vertices updated and projected to screen.

I have just looked through this blog and feel a little dubious about it. I guess the first question is does anyone read it? If so can you let me know. I am going to update it as often as required regardless because it is a nice timeline of the Decade Engine for me, however if people read it and would like to learn something from it please let me know. I can start to make the posts more technical with sample source, comparisons etc... In essence start to build up a 3D engine tutorial.

Reflections

I find it hard to believe that its been almost a month since I last posted. I guess there just hasn't been much new to show since then, as I was converting Decade to Decade.NET. Progress is slow due to a busy life but its now almost there.

Today, for a change (which they say is as good as a break) I decided to implement reflections. A second render pass was needed. 1 to draw a clipped upside down scene which is used for the reflection and then the normal scene.



Unfortunately these images as usual do not do Decade justice. The water looks like a sheet of glass, however in Real Time with the water moving and light reflecting realism is better. I think I will finish software water soon and then add DUDV maps for hardware rendered water.