Saturday, May 07, 2011

Can I claim progress even if I am behind where I used be?

I am the first to admit annoyance at having to redo functionality which I have previously implemented, however with the experience and lessons learned when coding procedural planets the first time, my implementation this time is smaller (in code) and more efficient than before.

I shall try and highlight an area which is
  1. Easier to implement
  2. Less code
  3. More efficient
From the centre of LOD (Level of Detail) every patch within a certain distance is rendered at the same LOD. The previous version of Decade calculated the distance from the centre of the patching being tested to the centre of LOD. The length between two positions in 3D space is calculated as

#define SQUARE(x)                ((x)*(x))

float Length(CVector3* p_pvOne, CVector3* p_pvTwo)
{
    return (float)(sqrt(SQUARE(pvTwo->X - p_pvOne->X) + SQUARE(pvTwo->Y - p_pvOne->Y) + SQUARE(pvTwo->Z - p_pvOne->Z)));
}

(The sqrt function has been traditionally considered slow and avoided if possible. I am unsure of its performance on modern hardware however the above could be optimised by not calculating the sqrt in the length function, and comparing it to the expected value squared.)

An better optimisation is to remove the requirement for calculating the distance from each patch to the centre of LOD completely. Instead of using the distance from the centre, I now recursively step from the centre to each neighbour, then onto each of their neighbours while incrementing the 'distance' with each step. When the 'distance' reaches a predefined value, the edge of the LOD area has been reached. In the following images 'distance limit' is set to 3.



The results above are not as desired. Some analysis showed that the east and west neighbours of the centre of LOD are within 3 recursive steps from the north neighbour (which is processed first). Because of this the east and west patches are marked as processed and will not be processed again when directly updated from the centre patch.

To overcome this, when processing a patch, if it is already flagged as processed, I compare its distance in steps from the centre of LOD. If the current distance is less than the stored distance I process again. Reading that sounds a little confusing so I shall try and explain in some steps. (only key steps are listed)
  • Move from the centre patch to the north. Its distance is stored as 1
  • Move from the current patch (north) to the east. Distance is stored as 2
  • Move from the current patch (north->east) to the south (this is the centres east neighbour). Distance is stored as 3.
  • Move from the centre patch to the east. This patch is flagged as processed at a distance of 3. The current distance is 1 therefore ignore previous processing and process again.

That looks better. It is a uniform area around the centre of LOD. However, it is still not correct. To render the next area of lower LOD I step 1 level up the patch tree and render outwards from here. Patches are not rendered if any of its children have been rendered as this would cause an unacceptable overlap and possible onscreen artifacts. This results in huge holes in the terrain.


A simple rule of "if one of my siblings is being rendered at a specific LOD, I must also render at that LOD even if I am not within range of the centre of LOD" fixes this problem.




The above example has resulted in code which is smaller, simpler to understand and faster to run than the previous version based on actual distance.

Planet rendered from orbit showing LOD
Same planet rendered from atmosphere, again showing LOD