Decade Engine

How to generate a procedural sphere.

2011-11-01T10:58:00.000Z

I have received an email asking to explain how I generate a procedural sphere as per this post. Rather than respond to emails personally, I have decide in future to answer the questions on the blog, presenting the information to a wider audience for comment, correction, improvement and perhaps a little learning.

The base of my generated sphere is a cube. Depending on how smooth the generated sphere needs to be, I recursively split each side into 4 equally sized children. This is achieved my finding the center of the face, popping that point out so that it is the correct radius from the center, then making 4 faces using the original points and this new point. (There is some ASCII art showing this in the code below)

void CSphere::Initialize(float p_fRadius, int p_iMaxDepth)
{
        //     TLB----TRB
        //        /|           /|
        //      / |   / |
        //    TLF----TRF    |
        //    |     BLB--|BRB
        //    |   /        | /
        //    | /          |/
        //    BLF----BRF

        //Putting the Vertices of the initial Cube at p_fRadius is not correct as the distance of
        //p_fRadius, p_fRadius, p_fRadius from the Origin is greater than p_fRadius.

        CVector3 l_Vertices[8];
        l_Vertices[TOP_LEFT_FRONT] = MoveToRadiusDistance(CVector3(-p_fRadius, p_fRadius, -p_fRadius), p_fRadius);
        l_Vertices[TOP_RIGHT_FRONT] = MoveToRadiusDistance(CVector3( p_fRadius, p_fRadius, -p_fRadius), p_fRadius);
        l_Vertices[BOTTOM_RIGHT_FRONT] = MoveToRadiusDistance(CVector3( p_fRadius, -p_fRadius, -p_fRadius), p_fRadius);
        l_Vertices[BOTTOM_LEFT_FRONT] = MoveToRadiusDistance(CVector3(-p_fRadius, -p_fRadius, -p_fRadius), p_fRadius);
        l_Vertices[TOP_LEFT_BACK] = MoveToRadiusDistance(CVector3(-p_fRadius, p_fRadius, p_fRadius), p_fRadius);
        l_Vertices[TOP_RIGHT_BACK] = MoveToRadiusDistance(CVector3( p_fRadius, p_fRadius, p_fRadius), p_fRadius);
        l_Vertices[BOTTOM_RIGHT_BACK] = MoveToRadiusDistance(CVector3( p_fRadius, -p_fRadius, p_fRadius), p_fRadius);
        l_Vertices[BOTTOM_LEFT_BACK] = MoveToRadiusDistance(CVector3(-p_fRadius, -p_fRadius, p_fRadius), p_fRadius);

        //Initialize the faces of the cube (The face structure just stores the vertices for the face corners and has render functionality, not applicable to this explanation, and its depth in the face tree)
    m_pFaces[FRONT].Initialise(FRONT, l_Vertices[TOP_LEFT_FRONT], l_Vertices[TOP_RIGHT_FRONT], l_Vertices[BOTTOM_RIGHT_FRONT], l_Vertices[BOTTOM_LEFT_FRONT], DEPTH0);
        m_pFaces[RIGHT].Initialise(RIGHT, l_Vertices[TOP_RIGHT_FRONT], l_Vertices[TOP_RIGHT_BACK], l_Vertices[BOTTOM_RIGHT_BACK], l_Vertices[BOTTOM_RIGHT_FRONT], DEPTH0);
        m_pFaces[BACK].Initialise(BACK, l_Vertices[TOP_RIGHT_BACK], l_Vertices[TOP_LEFT_BACK], l_Vertices[BOTTOM_LEFT_BACK], l_Vertices[BOTTOM_RIGHT_BACK], DEPTH0);
        m_pFaces[LEFT].Initialise(LEFT, l_Vertices[TOP_LEFT_BACK], l_Vertices[TOP_LEFT_FRONT], l_Vertices[BOTTOM_LEFT_FRONT], l_Vertices[BOTTOM_LEFT_BACK], DEPTH0);
        m_pFaces[TOP].Initialise(TOP, l_Vertices[TOP_LEFT_BACK], l_Vertices[TOP_RIGHT_BACK], l_Vertices[TOP_RIGHT_FRONT], l_Vertices[TOP_LEFT_FRONT], DEPTH0);
        m_pFaces[BOTTOM].Initialise(BOTTOM, l_Vertices[BOTTOM_LEFT_FRONT], l_Vertices[BOTTOM_RIGHT_FRONT], l_Vertices[BOTTOM_RIGHT_BACK], l_Vertices[BOTTOM_LEFT_BACK], DEPTH0);

        //Subdivide each patch to the lowest resolution
        m_pPatches[FRONT].SubDivide(p_fRadius, p_iMaxDepth);
        m_pPatches[RIGHT].SubDivide(p_fRadius, p_iMaxDepth);
        m_pPatches[BACK].SubDivide(p_fRadius, p_iMaxDepth);
        m_pPatches[LEFT].SubDivide(p_fRadius, p_iMaxDepth);
        m_pPatches[TOP].SubDivide(p_fRadius, p_iMaxDepth);
        m_pPatches[BOTTOM].SubDivide(p_fRadius, p_iMaxDepth);
}

where

bool CSphereFace::SubDivide(float p_fRadius, int p_iMaxDepth)
{
        if (m_iDepth >= p_iMaxDepth)
            return false;

        //Create the Additional Vertices
        //
        //    NW---------------D-------------NE
        //    |          |                  |
        //    |                      |                  |
        //    |                      |                  |
        //    |                      |                  |
        //    A--------------Center-----------C
        //    |                      |                  |
        //    |                      |                  |
        //    |                      |                  |
        //    |                      |                  |
        //    SW----------------B-------------SE
        //
        //

        g_vAdditionalVertices[A] = m_vBaseVertices[eNorthWest] + ((m_vBaseVertices[eSouthWest] - m_vBaseVertices[eNorthWest]) / 2.0f);
        g_vAdditionalVertices[B] = m_vBaseVertices[eSouthWest] + ((m_vBaseVertices[eSouthEast] - m_vBaseVertices[eSouthWest]) / 2.0f);
        g_vAdditionalVertices[C] = m_vBaseVertices[eNorthEast] + ((m_vBaseVertices[eSouthEast] - m_vBaseVertices[eNorthEast]) / 2.0f);
        g_vAdditionalVertices[D] = m_vBaseVertices[eNorthWest] + ((m_vBaseVertices[eNorthEast] - m_vBaseVertices[eNorthWest]) / 2.0f);

        //Create Child Nodes
        m_pChildren = new CSphereFace[4];
        m_pChildren[eNorthWest].Initialise(eNorthWest, m_vBaseVertices[eNorthWest], g_vAdditionalVertices[D], m_vBaseVertices[eCentre], g_vAdditionalVertices[A], m_iDepth + 1);
        m_pChildren[eNorthEast].Initialise(eNorthEast, g_vAdditionalVertices[D], m_vBaseVertices[eNorthEast], g_vAdditionalVertices[C], m_vBaseVertices[eCentre], m_iDepth + 1);
        m_pChildren[eSouthWest].Initialise(eSouthWest, g_vAdditionalVertices[A], m_vBaseVertices[eCentre], g_vAdditionalVertices[B], m_vBaseVertices[eSouthWest], m_iDepth + 1);
        m_pChildren[eSouthEast].Initialise(eSouthEast, m_vBaseVertices[eCentre], g_vAdditionalVertices[C], m_vBaseVertices[eSouthEast], g_vAdditionalVertices[B], m_iDepth + 1);

        m_pChildren[eNorthWest].SubDivide(p_fRadius, p_iMaxDepth);
        m_pChildren[eNorthEast].SubDivide(p_fRadius, p_iMaxDepth);
        m_pChildren[eSouthWest].SubDivide(p_fRadius, p_iMaxDepth);
        m_pChildren[eSouthEast].SubDivide(p_fRadius, p_iMaxDepth);

        return true;
}

and

CVector3 MoveToRadiusDistance(CVector3 p_Vector, float p_fRadius)
{
       //Get the Normalized Vector, of this vertex from the origin (center of the sphere) and pop it out to the correct radius,
        return p_Vector.Normalize() * p_fRadius;
}

That is pretty much the basics of how I create the sphere from recursively subdividing a cube. If I overlooked anything please comment and I will correct the post to reflect any gap in information or any mistake.

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

2011-05-07T16:53:00.001+01:00

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

Easier to implement
Less code
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

Remove back facing patches before the render pipeline.

2011-03-28T12:39:00.002+01:00

In a previous post, Procedural Planet - Subdividing Cube I mentioned how I remove complete patches which are facing away from the camera before the API culled their polygons in the render pipeline.

"Using frustum culling is not enough to remove any unrendered polygons from the planet. When close to a planet it can look like a flat terrain, just like the earth does for us as we stand on it, but from height it can be seen that the planet is in-fact spherical. With this knowledge it is possible to mathematically remove allot of the planet patches which are on the opposite side of the planet. With Back face culling the API would remove these anyway, however it would be very wasteful to pass these invisible faces down the render pipeline. By using a DotProduct with the LookAt vector of the camera and the Normal of the planet patch translated to model space, it is very simple to ignore these patches."

This code was part of what was lost from Decade with the recient SVN blooper, and therefore had to be rewritten. Despite having implemented the functionality about 18 months ago it took me some time to grasp the idea. I feel that a more technical post would be useful and will hopefully help anyone else when implementing similar functionality.

Anyone with experience in graphics programming will be familar with the concept of backface culling. As each polygon is passed down the rendering pipeline, it is tested to see if it is facing torwards or away from the camera. Since polygons facing away from the camera cannot be seen there is no need to render them. This concept can be applied when rendering a planet, however instead of just testing on a polygon by polygon basis, I test patch by patch. This allows me to ignore large collections of polygons with 1 test instead of the previously described polygon test.

How is this achieved?

Two pieces of information are required in order to test if a patch is facing towards or away from the camera.

1) The camera look-at vector. This is maintained by the camera object and updated as the camera moves and rotates around the world.
2) The normal vector of the patch. I calculate this when the patch is created by doing a CrossProduct of the vectors of 2 sides of the patch.

If the values of A,B,C and D in the above image are

l_vA: X=-11.547007 Y=11.547007 Z=-11.547007
l_vB: X=-6.6666670 Y=13.333334 Z=-13.333334
l_vC: X=-8.1649666 Y=8.1649666 Z=-16.329933
l_vD: X=-13.333334 Y=6.6666670 Z=-13.333334

The normal of the patch can be calculated using the following code.

m_vNormal = CalculateNormal(l_vB, l_vA, l_vC);

where

CVector3 CalculateNormal(CVector3 p_vOne, CVector3 p_vTwo, CVector3 p_vThree)
{
    CVector3 l_vA = p_vTwo - p_vOne;
    CVector3 l_vB = p_vThree - p_vOne;
    return Normalize(CrossProduct(l_vA, l_vB));
}

CVector3 CrossProduct(CVector3 p_vVectorOne, CVector3 p_vVectorTwo)
{
    CVector3 l_vResult;

    l_vResult.X = p_vVectorOne.Y * p_vVectorTwo.Z - p_vVectorOne.Z * p_vVectorTwo.Y;
    l_vResult.Y = p_vVectorOne.Z * p_vVectorTwo.X - p_vVectorOne.X * p_vVectorTwo.Z;
    l_vResult.Z = p_vVectorOne.X * p_vVectorTwo.Y - p_vVectorOne.Y * p_vVectorTwo.X;

    return l_vResult;
}

The calculated normal would be X=0.44721335 Y=-0.44721335 Z=0.77459687

With this information, as each patch is rendered, a simple DotProduct of these 2 pieces of information returns a floating point value. If this value is less than 0, the patch is facing away from the camera and therefore it and all its child patches can immediately be discarded.

float l_fDotProduct = DotProduct(m_vNormal, p_pCamera->get_LookAt());
if (0.0f > l_fDotProduct)
    return;

where

float DotProduct(CVector3 p_vVectorOne, CVector3 p_vVectorTwo)
{
    return p_vVectorTwo.X * p_vVectorOne.X + p_vVectorTwo.Y * p_vVectorOne.Y + p_vVectorTwo.Z * p_vVectorOne.Z;
}

One more issue must be dealt with before we have a complete solution. The above works well for static objects where all vertices are relative to the origin. However what will happen if the object is rotating?
The answer of that question is shown in the following image.

It may not be obvious from an image instead of a realtime demo so I will try and explain. The above implemented patch culling is processed on
the raw sphere data. This is equilavent to removing back-facing patches (anything from the back of the sphere, relative to the camera, is removed), then rotating the sphere on the Y axis (in the image above
the sphere is rotated by 130 degrees) and then rendering with the API culling all back-facing polygons. This order is obviously incorrect.

The more correct sequence would be to rotate the sphere, remove all back-facing patches, then render remaining patches and allow the API to remove any back-facing polygons in the front-facing patches. Since rotation occurs in the render pipeline it isn't possible for us to rotate before we remove the back-facing patches.

The solution is to multiply the camera look-at vector by the modelview matrix. This is equilavent to transforming the camera by the same values that will be applied to the sphere, resulting in the correct back-facing patches being removed, regardless of what rotation/translation/scaling is applied to the sphere.

float l_fDotProduct = DotProduct(m_vNormal, p_pCamera->get_LookAt() * p_pGraphics->get_Matrix(eModelView));
if (0.0f > l_fDotProduct)
return;

(Note: Since p_pCamera->get_LookAt() * p_pGraphics->get_Matrix(eModelView) will yield the same value for every patch, it would be better to calculate this once per frame for each planet that is being rendered. This value can then be used within the test on each patch in the planet.)

Two steps forward, three steps back

2011-03-22T08:56:00.002Z

In order to not admit what was probably a result of my own stupidity, I'm going to blame SVN. Regardless of what happened, it has now become apparent to me that the version of Decade Engine Source that I have isn't the latest version. It is missing my implementation of GPU planet generation. I've checked my online repository, backup disks etc .....

This means that I have to recode those sections. A chore, but on a positive side, I know the pit-falls and issues I encountered the last time, and can hopefully design around these and end up with better solution.

As per my previous post, I have also started IPhone and Android development. I shall be working on multiple projects at the same time, and rather than mix it all up on this blog, I have created a sister blog to this for Decade Mobile. Any updates which are specific to the mobile platforms shall be posted there.

Back online in Sydney

2011-03-08T10:34:00.000Z

Hello again. Its been far to long! I am now settled and living in Sydney and have decided that the time to resume Decade is far overdue.

Development of Decade shall continue as before with procedural planery bodies, but over the past few months I have started to program IPhone/IPad and Android, therefore I think it would be fun to create a mobile Decade Engine and try to make some simple but fun phone games.

Let the adventure begin (yet again!)
Ciarán

Moving to Australia

2010-06-26T15:29:00.000+01:00

Decade Engine will be on hold for a short while as I immigrate to Australia. Thank you to everyone who has emailed questions and support regarding my blog and development. I shall be back online and back in development 'DownUnder'.

Ciarán

GPU Procedural Planet

2010-03-16T22:31:00.004Z

This example does not use any textures to colour the terrain, and is therefore 100% procedurally generated. In basic terms it means that no media is loaded. Everything is 100% generated in the engine.

Let’s take some time to recap what needs to be procedurally generated in order to render the planet (shown in the video below).

Permutations Texture
The topography of the planet is created using noise algorithms. This example uses Multi Ridged Brownian Fractal Motion. At runtime this noise is created using a series of permutations which are stored in a texture so that it can be accessed by in a shader. The texture data doesn’t make allot of visual sense, however here is an example of what it looks like.

1 Vertex buffer
The planet is rendered as a series of patches. It is this patch nature which allows the recursive sub-division resulting in the increased/decreased level of visible detail. Whereas the CPU Planet generates a unique vertex buffer for each patch (because the noise is calculated when the patch is created and applied to height data in the vertex buffer), the GPU Planet only uses 1 vertex buffer of X * X vertices, generated procedurally, which are displaced in a shader at runtime for each patch to be rendered.

16 Index Buffers
An index buffer is used along with a vertex buffer to render some geometry. In allot of cases 1 vertex buffer is used with 1 index buffer. As described in previous posts a terrain requires 16 index buffers, generated procedurally, so that there are no terrain cracks. It must be possible for the edges of terrain patches, with different levels of detail, to join together seamlessly.

In the video above shows a basic GPU Planet. There is quiet an obvious bug visible as the camera moves. Because all noise is generated on the GPU, the Decade Engine running on the CPU has no knowledge of how much a vertex is displaced. All distance checking from the camera to the planet is calculated from the camera position to the underlying sphere of the planet (vertex displaced to radius of the planet but not with height noise applied). This is ok when the camera is high above the terrain however as the camera moves close to the surface, especially if this ground is at a high altitude, the sphere position may still be some distance beneath and therefore terrain subdivision do not occur properly.

I am considering 2 possible techniques to over come this

Generate the same noise values on the CPU as is generated on the GPU. Since all (pseudo) random data is stored in the permutations texture, it should be possible.
Render the height data to a texture instead of generating it as required each frame, then use this texture for shader vertex displacement as well as calculating the height of key vertices on the CPU.

Concentric LOD Areas

2010-02-24T22:48:00.004Z

Not really any new functionality, however small but important modifications. In the previous posts and video of the planet each patch was independent and updated when it thought correct regardless of the state of its neighbours. This resulted in a non-uniform patch pattern and multiple terrain cracks. A more detailed explanation of terrain cracks can be seen here.

Instead of a patchwork quilt on the planet surface, the terrain LOD (Level of Detail) decreases in concentric circles with its origin at the camera. All patches which neighbour a patch with lower LOD render the corner edge downgraded to the lower LOD preventing any terrain cracks appearing.

In the above pictures the radius of the LOD circle is set to 6.0. This means that the LOD circle has a radius of the length of the patch at this level of detail multiplied by 6.0. This value can be changed at runtime if desired resulting in a higher or lower detail of terrain.

Another change in the example, although not obvious from the pictures is that the planet is no longer updated/rendered from the root node. Now, during the first frame the lead patch is found. This is the patch that is directly below the camera at the correct LOD. Each frame when the planet updates the lead patch moves to one of its neighbours, children or its parent if required. This requires a little more code than simply recursively moving across the patch tree each frame, but should be faster as it removes the processing on many invisible patches (those which are closer to the root of the patch tree but are too low level of detail to meet our needs).

Procedural Planet - Subdividing Cube

2010-01-15T18:08:00.068Z

At long last I have returned to what was the growing focus of Decade Engine in the latter stages of 2008. A previous post showed the most basic functionality of Decade's planet generation. I hope to give more details here.

The below video has 3 sections.

Run-time cube subdivision and application of noise to create planet structure. Patch size is 10x10 quads. To give decent minimum resolution, the lowest possible level of subdividing in this example is 3, with the highest being 16. As the camera moves towards a patch, and gets within range (configured to radius of patch * 5 in this example) the patch subdivides into 4 children which are rendered instead of the parent when the camera is within range.
Similar to section 1, except when the camera moves away from the patch, the level of detail which is rendered does not reduce. This would allow users to see the size of patches at every allowed level on screen at once, however when far away the patches at level 15 and/or 16 are smaller than 1 pixel so not really visible. Some very basic math will tell us that if the planet in view was earth size (i.e. radius of 6378km) the length of a patch at level 1 would be 7364.67km. At level 16 the patch length is only 0.1123km and with 10 quads per patch length, the max resolution of the planet is just above 1m. By increasing the max allowed depth rendered, or the resolution of each patch, this maximum planet resoultion could be increased to cm level.
Using frustum culling is not enough to remove any unrendered polygons from the planet. When close to a planet it can look like a flat terrain, just like the earth does for us as we stand on it, but from height it can be seen that the planet is in-fact spherical. With this knowledge it is possible to mathematically remove allot of the planet patches which are on the opposite side of the planet. With Back face culling the API would remove these anyway, however it would be very wasteful to pass these invisible faces down the render pipeline. By using a DotProduct with the LookAt vector of the camera and the Normal of the planet patch translated to model space, it is very simple to ignore these patches.

Terrain Editor - Version 2

2009-12-09T20:26:00.003Z

Last week I received a request from a reader of DecadeBlog for access to the terrain editor. What little pride I have kicked in and in an effort to supply something a little more usable than Version 1 I set aside a little bit of time to add some features.

Version 2 is representitive of a more traditional editor, showing multiple views of the subject. 3 independent views of the terrain can be seen in the video below. Each view maintains its own render state. It is, for example, possible to show one view in wireframe, while the others remain solid or are shown in point form. There is also correct "Screen to World Projection" for each view.

Version 2 also contains some erosion filters. I noticed when editing that the old issue of terrain steps was occuring. By giving the ability to erode or filter the terrain any rough edges are smoothed out.

All application level in the above example is again scripted. On startup the DecadeEngine Sandbox calls the script init function and each frame the HandleInput, Update, Render3d and Render2d functions are called in the script. If anyone is interested in having the script please mail me or comment to this post. Its a little long and boring to publish here.

CPU v GPU Procedural Terrain Texture Generation

2009-11-25T19:39:00.006Z

Its been an interesting week. Having programmed graphics for some time, having read allot about shaders and having used them briefly I know they are powerful tools for the graphics programmer, but I am still slightly in awe of how quick they are.

It should be noted before reading any further that this is the first shader I have ever written. I've used and modified shaders before such as Sean O'Neil's atmospheric scattering (there is a post below somewhere) and some bumpmapping, but all code in this shader is mine and therefore possibly with some rookie mistakes.

Lets first refresh on the very simple texture generation technique currently implemented. The user specifies a list of terrain regions. Each region has texture data, an optimal, min and max height associated with it. For each pixel in the texture being generated the terrain height at that position is queried, interpolated if required (if the texture is higher resolution than the terrain mesh). This height is then compared to all terrain regions and a colour of the pixel is based on the strength of this height within the regions. There are many examples of the results of this algorithm elsewhere in the blog if you have not already seen.

Above can be seen the times used to generate the textures in software. 2048x2048 taking almost 1 minute! My code in this area isn't by any means heavily optimised, but is well written. Its a relatively simple algorithm of iterating though a list and comparing the height value against the region. Previously when procedurally generating a planet at run-time the texture size of choice was 256x256. This provided average detail but with the generation time of about 1 second, a freeze in movement was very obvious.

Now on to the better news....

What a difference? These times include the full process of using a the shader

Binding the Frame buffer so that the texture can be rendered off screen,
Enabling the Vertex and Fragment shader, binding the textures required.
Rendering the texture
Unbinding/disabling everything used during this sequence.

To get a better approximation on the time used to generate this texture in hardware the times above are also an average of 5000 iterations (that applies only to the GPU times as it would take over 3 days waiting for 5000 2048x2048 CPU textures to be generated).
Here is the fragment shader, which does all the work. The vertex shader just passes the vertex down the render pipeline.

struct vOutput
{
    float4 color : COLOR;
};

struct TextureRegion
{
    float2 startTextureCoord;
    float2 endTextureCoord;

    float optimalHeight;
    float minHeight;
    float maxHeight;
};

vOutput Main(float2 texCoord : TEXCOORD0,
            uniform sampler2D heightMap : TEX0,
            uniform sampler2D terrainTexture : TEX1,
            uniform int terrainTextureRepeat,
            uniform sampler2D detailTexture : TEX2,
            uniform int detailTextureRepeat,
            uniform float blendingRatio,
            uniform TextureRegion regions[4])
{
    vOutput OUT;

    //Get the Height
    float4 bytes = tex2D(heightMap, texCoord);
    float height = ((bytes[0] * 16777216.0f) + (bytes[1] * 65536.0f) + (bytes[2] * 256.0f)) / 1000.0f;

    //Strength of this Terrain Tile at this height
    float strength = 0.0f;

    //Color for this Pixel
    OUT.color = float4(0, 0, 0, 1);

    int colorset = 0;

    //For Each Terrain Tile Defined
    for (int loop = 0; loop < 4; loop++)
    {
        //If the Current Terrain Pixel Falls within this range
        if (height > regions[loop].minHeight && regions[loop].maxHeight > height)
        {
            colorset = 1;

            //Work out the % that applies to this height
            //If Height = Optimal, then its 100% otherwise fade out relative to distance between optimal and min/max
            if (height == regions[loop].optimalHeight)
            {
                strength = 1.0f;
            }
            else if (height > regions[loop].optimalHeight)
            {
                float temp1 = regions[loop].maxHeight - regions[loop].optimalHeight;
                strength = ((temp1 - (height - regions[loop].optimalHeight)) / temp1);
            }
            else if (height < regions[loop].optimalHeight)
            {
                float temp1 = height - regions[loop].minHeight;
                float temp2 = regions[loop].optimalHeight - regions[loop].minHeight;
                strength = temp1 / temp2;
            }

            if (strength != 0.0f)
            {
                float2 tileTexCoord;

                //Tile the Texture Coordinates
                tileTexCoord[0] = fmod((texCoord[0] * terrainTextureRepeat), 1.0f);
                tileTexCoord[1] = fmod((texCoord[1] * terrainTextureRepeat), 1.0f);

                //Recalculate the Texture Coordinates so that they are within the Specified Tile
                tileTexCoord = regions[loop].startTextureCoord + ((regions[loop].endTextureCoord - regions[loop].startTextureCoord) * tileTexCoord);

                //Get the Color at this Terrain Coordinate
                OUT.color += (tex2D(terrainTexture, tileTexCoord) * strength);
            }
        }
    }

    if (0.0f == colorset)
    {
        //Make Pink so that its obvious on the terrain (only for debugging)
        OUT.color = float4(1, 0, 1, 1);
    }
    else
    {
        //Scale the Texture Coordinate for Repeating detail and get the Detail Map Color
        texCoord *= detailTextureRepeat;
        float4 detailColor = tex2D(detailTexture, texCoord);

        //Interpolate Between the 2 Colors to get final Color
        OUT.color = lerp(OUT.color, detailColor, blendingRatio);
    }

    return OUT;
}

This week I have been using this shader in 2 ways.

Use as described above, to generate a texture once per terrain patch (will get generated in higher detail when the patch subdivides) and this texture is then used when rendering.
Use and bind every frame which gives per-pixel texture generation. This has the obvious disadvantage of requiring that the texture data for the terrain is generated each frame, but obviously does so for only the onscreen terrain. It has the nice advantage of not taking up any graphics memory, no need for frame buffers, rendering off screen, etc.... I was getting between 200 and 600 fps using this method.

I dont know how I will ultimately use this shader in the future. I will have to experiment and see which is the preferred method.

All the above results were generated on my laptop which has the following.

Renderer: ATI Mobility Radeon HD 3670
Vendor: ATI Technologies Inc.
Memory: 512 MB
Version: 3.0.8599 Forward-Compatible Context
Shading language version: 1.30

Max texture size: 8192 x 8192
Max texture coordinates: 16
Max vertex texture image units: 16
Max texture image units: 16
Max geometry texture units: 0
Max anisotropic filtering value: 16
Max number of light sources: 8
Max viewport size: 8192 x 8192
Max uniform vertex components: 512
Max uniform fragment components: 512
Max geometry uniform components: 0
Max varying floats: 68
Max samples: 8
Max draw buffers: 8

As always comments are welcome and appreciated.

Higher Detail Heightmap Textures

2009-11-19T09:26:00.003Z

When originally creating height maps, most of the tutorials store this information in grey-scale, therefore at the time this is what was implemented in decade. Limited to 256 different heights (as only 1 byte is used per value) it may be acceptable for demo's with small terrain patches, but is inadequate for anything larger with a more realistic topography.

To overcome this a terrain file format was created for decade. This allowed the saving of height data to a binary or text file using multiple bytes per value. With the introduction of shaders into Decade terrain engine, this too has become inadequate. I need to send the height information to the shader, along with the source tiles so that the procedural terrain texture can be created. The only feasible way to send this height information to the Graphics Card is in a texture, but the grey-scale implementation did not have high enough detail.

Solution? Combine the texture implementation with the multi-byte file format. To do this I split the floating point height position across the 3 color bytes using some simple bit shifting.

Using 3 bytes it is possible to represent 16777216 unique values (256x256x256). In the following example I want to maintain 3 digits after the decimal separator. This allows me to have terrain heights from 0.000 to 16777.216 which should be suitable for most procedural planets. It is of course possible to make the number of decimal digits configurable.

To convert a floating point height into 3 bytes (used in the texture rgb).

//Get the Height at the current Terrain Position
float l_fHeight = get_HeightAtPoint(l_iXPosition, l_iYPosition);

//Convert to an int. Multiply by 1000 to keep 3 decmial places.
int l_iColor = (int)(l_fHeight * 1000);

//Seperate into 3 Bytes
l_ucRed = ((l_iHeight >> 16) & 0xFFFF);
l_ucGreen = ((l_iHeight >> 8) & 0xFF);
l_ucBlue = l_iHeight & 0xFF;

and to convert 3 bytes back into a float, with 3 decimal places is as easy as

l_fHeight = ((l_ucRed << 16) | (l_ucGreen << 8) | l_ucBlue) / 1000.0f;

Above is a sample showing grey-scale height maps and their equivalent 24bit height maps. When I first saw the new maps, I thought there was a bug, and there would be rough edges in the terrain, due to the sudden color changes within the texture, however it loads correctly and terrain detail is maintained.

Winter is returning and I'm back again.

2009-11-10T11:42:00.003Z

Yet again the summer months have been a slack time for Decade. As a solo hobby project I find it very difficult to sit at my PC after a long day in the office when the sun is shining outside. Now that the cold, wet and dark nights are back I feel the urge to return to Decade and complete some of my long standing wishlist features.

Over the past week or two I've been researching shaders. I have decided to add support for CG and CGFX to Decade. My first task with this will be to move the procedural texture generation to the GPU. This should hopefully vastly speed up this area of the engine allowing much smoother planet generation.

Having reviewed the Decade code with a fresh mind, some housekeeping is first required. Cleaning up interfaces and improving segments before building upon. Within the next week I hope to have some comparisons between generating the textures on the CPU and the GPU. Not having much experience using the GPU for this type of processing I am unsure what to expect but from reading other blogs regarding Planet and Terrain generation I am confident that it is the right approach to take.

Basic Terrain Editor

2009-02-23T07:44:00.002Z

This update in itself probably does not deserve a full blog update however its been too long since I have reported any Engine Progress and some nice features have been added.

The video below shows my sandbox terrain editor. This is running in Engine Real time. By changing the size of the target area and using the mouse wheel it is possible to raise or lower segments of terrain. As the terrain changes the terrain texture is recalculated (for modified areas).

Key features:

Dynamic Vertex Buffer Object updating when terrain is updated
Dynamic Texture Updating when terrain is updated (from a set of source textures and height values (Optimal, Min, Max)
Screen to World projection allowing Decade to know where in the world the user is selecting with the mouse.
High level functionality of demo is 100% scripted (which calls Engine functions bound to script engine)

A GUI system is also in development. This system is based on my experience of C#. It is possible to register events for each GUI component on the engine or script level. These events are fired under the specified circumstances. e.g. Mouse Enters, Mouse Leaves, MouseLeftClicked etc...

Version 2 of the Terrain Editor should make use of this GUI system and also support features such as

Adding areas of Water
Adding areas of vegetation
Erosion Filters on selected area or whole terrain
Texture splashing for better terrain details. (Roads, coast line etc...)

Would you like to use Decade?

2008-10-29T22:13:00.000Z

Over the past few months I have received a number of requests from people wishing to use Decade in their personal probjects and also a possible commercial venture (with alot more work to be completed on Decade before this is possible). If you would like to use Decade in any of your project or have any questions which wouldnt suffice asking in the comments section of this blog then please email me at decadeengine@ymail.com

Its been a long time

2008-10-26T20:02:00.001Z

I truly cannot believe that it has been 4 months since I've updated this blog. The summer months have sped past. There was a period of quiet time for Decade with me taking time out for holidays and then some personal time to relax and pursue other projects. A number of weeks ago I approached Decade again and have since given it a complete overhaul.

No longer is Decade contained within 1 project. Logically dividing the sections up into DecadeUtilities, DecadeScript, DecadePhysics, DecadeInput, DecadeOnline, DecadeGraphics and DecadeEngine, a DLL has been created for each resulting in a complete game engine. Another advantage of this is that each of the components resides behind an "Abstraction Layer" therefore allowing me to change individual components such as graphics API, physics engine without having to recompile and deliver the whole game.

The names of the components descript pretty well what functionality is contained however for clarity I will give a brief overview starting at the bottom.
DecadeUtilities contains random functionality which does not meet the criteria of the other DLL's as well as functionality which is common to many of the DLL's higher up the chain. e.g Math, I/O

DecadeScript contains methods for loading and executing scripts at run time. As well as Decade calling functions within the script, most of the objects in the Decade suite of DLL's have been bound to the script engine allowing powerful control of the game engine from the script level. In the long term this will allow allot of customisation and add on capability to games made with the Decade Engine. Supported script engines are Game Monkey with LUA support currently being added.

DecadePhysics as the name suggests contains a physics engine. In keeping with the other DLL's in the Decade Suite all the physics engine functionality is contained within an "Abstraction Layer" which will allow support for other physics engines to be added quickly and easily. ODE is the current 3rd party physics engine supported by Decade.

DecadeInput contains functionality for all input methods. Keyboard, Mouse and Joystick/Joypad support are easy to add to your game project and with simple bindings to the script engine it takes a matter of minutes to map your keypress's or mouse moves to your desired functionality.

DecadeOnline is the encapsulation of online communication methods for multi-player online games. Offering you the possibility to create a server or client with ease and communicate over TCP or UDP.

DecadeGraphics contains all the graphics API functionality required in a 2D or 3D game, from creating an index or vertex buffer, loading a texture to graphics memory, executing a vertex or fragment shader. DecadeEngine currently uses OpenGL however a DirectX version of this DLL should be available in the near future.

DecadeEngine is the main interface to the Decade suite. This layer contains all the 2D and 3D engine functionality such as loading a texture, loading a mesh, creating a terrain or planet, lights, shadows etc....

Procedural Planet - Texture Generation

2008-06-16T21:49:00.002+01:00

Texture Generation for procedural planet was a simple step up from generating height based texture for a flat terrain. Because the underlying structure of each planet is a cube, 6 textures are required for each planet. The height is calculated from the distance of the vertex to the centre of the planet, minus the base radius of the planet. This method allows 100% re usage of the normal terrain height map and texture generation functionality.

In the above video the planet is made up of 125x125x6 vertices's and the moon from 65x65x6 faces. There is currently no complete LOD functionality. When fully implemented each face recursively subdivides into 4 faces of equal area, resulting in the level of detail of each face increasing by a level of 4 with each divide.

With some clean programming, a vertex should never have to be calculated more than once (unless the player moves a distance away and the section is deleted from memory). The parent will populate each of its children with the relevant subset of its data, and only the unknown sections calculated, resulting in lower memory usage as well as faster run time higher LOD generation.

Procedural Planet

2008-05-23T19:17:00.001+01:00

In continuation to the Procedural Sphere entry I made a few months ago, and from inspiration by the ongoing work of Jelly Edwards I decided to look into further developing the sub-dividing cube with procedural noise in order to make a planet.

The noise algorithm used is Fractional Brownian motion (fBm) which is a form of Perlin Noise.

A good article about fBm in relation to procedural planets can be seen here. This work was carried out by Sean O'Neill who has also contributed allot to atmospheric scattering.

Very early and basic attempts at a procedural planet can be seen below. For the purpose of illustrating the deformation of the sphere I have magnified the hills and valleys on the planet, which results in what looks like an asteroid or moon.

There are some key failings with this version. It is slow to render as the vertex and index buffers and built each frame. The whole planet is the same Level of Detail (LOD). This is ok for distance viewing, however as the camera approaches the surface of the planet, rendering the entire scene at a high LOD would cripple even the most powerful of computers.

Many of the techniques learned when researching and implementing my terrain system will be used here.

Dividing the planet surface into patches
Each Patch manages their own LOD (through subdivision and creation of child patches) based on distance from the camera.
Each Patch maintains its own Vertex Buffer, while sharing a group of Index Buffers (to cover neighbour patches with different LOD's)

Allot of my terrain modules can be reused, with perhaps a little added functionality, so I hope that, time permitting, adding these features will not take too long.

MD5 Mesh and Animation

2008-04-25T20:00:00.000+01:00

Two young and very talented modelers from Sweden have started making some game content to be used in Decade. MD5 was their format of choice for doing animations so I used this requirement as an opportunity to research the format.

A good explanation of the .md5mesh file format can be found here and a similar explanation of .md5anim can be found here.

After reading the two file format descriptions specified above as well as a refresher on quaternions it was not too difficult to parse the files and create the mesh and animations.

In order to make Decade's MD5 support as complete as possible it supports multiple loading methods which are specified through a flag parameter in the Load function. One can build hardware/software vertex and index buffers for each specified frame at load time or they can be populated when required.

If an animation does not have a high enough count of frames per second, Decade can calculate additional frames using the mesh/anim data along with quaternions and slerp.

Terrain Precalculated Shading Techniques

2008-04-05T13:04:00.003+01:00

After adding slope lighting and seeing how simple it was to make a terrain look better with no run time cost I decided to extend this method to more realistic looking shadow/shade.

Above is a non shaded, non shadowed terrain. This is the control image to which the next 2 results can be compared. In this normal method a height map is procedurally generated and the terrain texture is then created from this height map and a set of layer textures.

For slope lighting an extra step is added during the terrain texture generation.
For each vertex of the terrain, the neighbour vertex in a specified direction is checked. If it is higher than the current vertex shade is applied. This is a relatively fast technique. In a height map of 512x512 the number of comparisons is 262144.

Shadow texture generation is an extension of the slope shading technique. Instead of checking the immediate neighbour a ray is cast from the current vertex to a specified light position. For every step along the ray the height of the terrain at this point is checked, and if it is higher than the ray shadow is applied to the original vertex. (i.e. there is no direct line of light between the light source and the vertex). In my opinion this produces more realistic results and will combine well with shadow maps or shadow volumes but it is allot slower than the previous methods. To calculate the shade applied to each vertex in the shown 512x512 terrain 45556293 checks were required, which took 27 seconds.

This could probably be improved so that the terrain is checked at a lower resolution, with an approximate shade applied to the "in-between" vertices. This would allow the light source (probably the sun in an outdoor scene) to move.

Decade Blog is 1 year old today. 10% of the way through its life!

Slope Lighting

2008-04-02T19:14:00.003+01:00

Back at the dawn of procedural texture terrain generation in Decade I decided to skip slope lighting. My reason for this was that I have always planned on adding real lighting effects with shadow maps or shadow volumes.

Reciently my long time friend and arch nemisis Jelly Edwards, who is also now my blog enemy, has started a DX10 terrain engine and his slope lighting effect was impressive especially considering the ease at which it can be added and the free cost of this effect.

Slope lighting is calculated during texture generation therefore has no cost during runtime. Each vertex in the height map is checked against its neighbour in the direction from which the light is coming. If the neighbour is higher than the current vertex shade is applied based on the difference in height (how much the terrain is facing away from the light).

I am hoping that this effect will not be used in the majority of cases, however it is a nice addition to enhance the terrain on computers which do not have the power to do real time shadows.

Terrain Cracks Revisited

2008-03-31T17:35:00.007+01:00

In August of last year I posted a blog entry about terrain cracks. Despite having a theory back then about how to fix this problem I never got around to fixing the issue. A new feature was always more exciting and overtook this development.

Long overdue I have fixed the problem. I will briefly try and recap the issue. Segments of the terrain which are further away from the camera are rendered at a lower level of detail than those which are closer. When a patch gets a distance from the camera the level of details halves. Since every second vertex in the lower level of detail is missing this can result in cracks in the terrain. The image below shows this up close. This situation is not realistic because the patch joins will be a distance away from the camera however even at distance it is possible that artifacts would be visible.

In order to overcome this problem I have removed every second vertex along the edge of a patch which has a higher level of detail. This is all calculated during load time. At run time each neighbour of a patch being rendered is examined and a bitmask is calculated accurately describing the surrounding area. This bitmask is then used to offset into an IndexBuffer array, using the correct buffer with no run time calculation required. A more complete description of this can be found in the previous blog entry.

As can be seen above, there are now no visible joints between patches of differing detail, resulting in a more natural terrain.

General Update

2008-03-25T15:47:00.002Z

Time flies by again. Its been a busy year so far, allot of projects approaching deadlines at the office and I also worked allot on a 2D fluid dynamics tech demo. Development on Decade still continues, however currently at a slow pace.

In the past month I haven't had allot of time to complete 'Parallel Split Shadow Maps', so this is still in a limbo state. They sort of work however sometimes the scene is a mess and other times there are unknown artifacts.

While making the 2d fluid dynamics demo, with the PlayFirst SDK, I was impressed with their usage of LUA scripting. I have researched this topic a little and feel that I will add support for Game Monkey to Decade. As with the graphics and physics layers the script engine will also be extrapolated away so I can, at a later date, add support for another script engine.

I have also added joypad support to Decade to avoid always having to use the keyboard and mouse. DirectInput was used for this so this functionality will not be added to the Ubuntu version any time soon, or until I at least figure out how to do this in Linux.

I am delighted to announce that a friend has at last got on the game engine band wagon and started his own terrain engine called Jelly Engine. His ultimate goal is to generate a procedural universe. Please have a look at this blog and give him grief on how bad his engine is, even though it would be a lie.

Shadows

2008-02-18T17:01:00.001Z

Having past experience with Shadow Volumes in DirectX I could see a potential issue in using this technique in Decade so I therefore focused my attention on Shadow Maps.

Before giving some detail on my shadow map implementation I will briefly describe why I have bypassed Shadow Volumes for now. Shadow Volumes are created by calculating a silhouette of the mesh from the lights point of view. This silhouette is generated from the raw mesh data. The low poly trees currently used in Decade consist of colour keyed faces. The resulting Shadow Volume generates a shadow of the full face and not just the visible (non blended area). Below is a faked image which shows the shadow that would be generated using the Shadow Volume technique. Notice that the shadow for the tree remains the same regardless if colour keying is enabled or not.

Shadow Maps generate shadows by rendering the scene from the lights point of view and saving the depth buffer to a texture. This texture is then used to shadow the scene. The advantages that Shadow Maps have over Shadow Volumes are

No colour keying issues
Complex geometry does not affect the performance of the algorithm. The scene rendering should be efficient as it must be rendered 3 time per light
The complexity of the geometry is of much higher importance in Shadow Volumes because as mentioned previously the silhouette is generated from the raw mesh data

Due to the limited resolution of the texture map holding the depth/shadow data Shadow Maps can and usually do result in very aliased shadows. In the image below the light is only 75 units from the scene however it is very evident from looking at the car shadow that the shadow quality is very low. The right image shows the depth buffer from the lights point of view which is used to render the shadows.

Below can be seen how the Shadow Mapping technique becomes unusable as the light source moves further away from the scene or as the scene boundary grows. With less shadow map pixels used to represent the shadow of the same area of space the shadow loses form and any relationship with the casting object.

These issues make the Shadow Mapping technique inappropriate for rendering any large outdoor scene. Further research has shown that Shadow Mapping has some advanced friends such as Parallel Split Shadow Mapping. (PSSM). The PSSM method involves splitting the frustum into several parts along the eye vector, and rendering a separate Shadow Map for each split. This allows the area closest to the camera to use higher resolution shadow maps and with the resulting Shadow Map stretched over a much smaller area, less aliased shadows are possible.

Car Physics

2008-01-12T22:28:00.000Z

Using Joints in ODE basic car physics has been added to Decade. This consists of a car body and 4 wheels. Each wheel is connected to the car body by a combination of 2 joints. These emulate the suspension, steering and the axle.

A known issue with ODE is that when assigning a mass to a rigid body, the center of mass must be (0,0,0) relative to the body’s position. This results in the center of gravity of the car being much to high causing frequent rolls when turning at speed. Top Gear would have a great time comparing the car to some American sports car which has great straight line speed but corners with the grace of a giraffe.

If you note in the video at time 30 seconds, the car is represented to the physics engine as a box. Even when this box is reduced to tightly surround the car the center of mass will still be too high. I feel that if I create a thin box at the bottom of the car, which has 90% the mass of the car, to which the wheels are attached, and connected to this by a fixed joint is the light car body, driving should be allot smoother and realistic.

A fixed Joint is defined as "The fixed joint maintains a fixed relative position and orientation between two bodies, or between a body and the static environment."

As well as this representation working well in Decade it also closely copies real life, with the thin box being the chassis and the larger box, being the much lighter body.

Car model was downloaded from Turbo Squid which as well as selling an excellent range of models, also offers a selection of models for free.

Ubuntu

2007-12-23T18:10:00.001Z

In an effort to use OpenGL to its full potential, and a feature that is unique to OpenGL over its main competitor DirectX, I have decided to create a non windows version of Decade. Over the weekend I downloaded Ubuntu which is a free community developed, linux-based operating system.

Instead of making my desktop dual boot, I decided to try and use Microsoft Virtual PC, which is also free to download. It was a very easy to create the virtual PC, virtual hardisk and install Ubuntu. I can now access my Ubuntu installation from within my windows environment getting the benefits of both systems.

It took a little effort to get networking enabled, my router requiring some setting changes however once this was complete it was again a simple process to connect over the local network and access the shared drives on my Windows PC. With this setup I hope to use the same source base for Win Decade and Ubuntu Decade.

My first job after leaving university was in a HPUX environment however being a number of years ago I have forgotten allot of the basics. This morning I created the obligatory "Hello World" C++ program, but am having problems building OpenGL and SDL projects.

Decade Meets ODE

2007-12-15T11:47:00.000Z

Time yet again ticks by. No matter now much I try I can't stop it. As you can see Novermber was a quiet month in the life of Decade. Due to personal reasons I did not have much if any time to program, however last week I returned to Decade and decided that it was long overdue to add some physics to the engine.

Having messed around with ODE (Open Dynamics Engine) a few years ago I decided that I would start with this free physics engine. I am trying to use the same approach in adding the physics as I did with the graphics. I have implemented an extrapolation layer between the game engine and the physics engine with the hope that in the future I can add support for other physics engines without having to change too much of the game code.

Refreshing myself with the theory of ODE last week I have now started to modify Decade. Up to now all transformations, rotations etc.. in Decade were stored as Eulars. ODE rotations are matrix based so rather than have converter functions to change between Eular->Matrix and Matrix->Euler I modified the Decade core so that each object builds its own Model View Matrix. The Projection and View matrices are also build and handled by Decade. Although a little more complicated to code and read this approach does have some advantages. For an object which is static in the world its matrix can be built once, reused time and time again and doesn't have to be updated until the object moves. Using the glRotate, glScale and glTranslate functions this matrix was built for each object every frame.

Now that the basics of ODE have been added I will continue on this course building my Physics Layer. I will create some simple rag doll physics or a vehicle which will introduce me to the topic of joints.

After basic physics is added to Decade I really must invest some time to complete my to do list of improvements on current features. This includes

Properly fixing cracks in terrain
Priority Rendering Queue
Octree V Quadtree
ROAM Terrain
Finish Shadow Volumes and Parallel Split Shadow Maps

and after that I need to continue with my future to do list

Scriptable Particle System and Editor
Planet Generation
Some small tech games (Golf, racing etc...)

Atmospheric Scattering

2007-10-30T20:29:00.000Z

At long long last I have got a grip of atmospheric scattering. Decades implementation of atmospheric scattering is based on Sean O'Neill's amazing research. In the video below you can see the sun rising in the sky as the camera moves around the planet. The word planet is used with grace as the planet is simply a smooth sphere which was procedurally generated with recursive subdivision. (See Post below). Close to the end of the video the rendering switches to wire frame and you can see the planet subdividing by another level.

As always there is a list of improvements to make. The planet is currently rendered in software, each face rendered separately. There is also no culling. Adding hardware acceleration and efficient culling should greatly improve performance. The subdivided implementation of the sphere allows easy culling of vast numbers of faces with a few checks.

I am also going to look more detailed at realtime fractal terrain generation, possibly with Perlin Noise so as I dubdivide the planet as the camera gets closer the result will be a details, rich looking terrain.

Procedural Sphere

2007-10-24T20:46:00.000+01:00

While implementing my Sky Dome for atmospheric Scattering a number of issue quickly became noticeable. A sphere generated using the OpenGL function gluSphere or loaded from a mesh file had vertex compression at the poles. This usually causes texture compression/distortion which is naturally very undesirable.

To maintain Decade's procedural capability and to remove the issues with the previous implementation I created my own Sphere function by recursively subdividing a cube until the required resolution was achieved.

Below the two solutions can be seen side by side. On the left is the Sphere created with gluSphere or loaded from a file. The vertex compression is immediately obvious. The size of the face depends on which segment it exists, with faces getting smaller closer to the poles. On the right is my procedurally generated sphere. As you can see there is no vertex compression at the pole. In fact no pole is visually obvious. Due to the subdividing nature of the algorithm each face in the sphere is the exact same size.

I believe I may have achieved allot more than just creating a sky dome with this implementation. Creating a universe with procedural planets has always been on the wish list for Decade but I never knew where to begin. The recursive subdivision appears to be an ideal solution for this. It has level of detail and efficient culling properties automatically built in.

The level of the quad tree rendered defines the level of detail of the planet. Since the root of the planet is 6 quads, it is easy to bounds check these against the frustum and quickly remove unseen areas of the planet and the same process can be repeated for each of the child levels of the quad tree.

By using the above algorithm along with some height maps I believe rendering a full planet should be possible. I look forward to the day when I can roam a planet in Decade then jump in a space ship, fly away and land on another planet.

Oil Painting

2007-10-21T23:09:00.000+01:00

For another personal project (web based) I have worked on some image processing, hence the lack of updates this month. Rather than let the new code go to waste I have applied it to Decade too see the results. Here is a normal screen shot of Decade

and here is Decade as an Oil Painting.

I am happy with the results, although now a little unsatisfied that the manipulation is not real time. I'm not sure of the possibility of writing a Pixel Script to do this in real time because it requires sampling multiple pixels in order to create the smudged Oil Paint effect. Despite this I still plan to at least try and implement an Oil Painting script sometime. It would be nice to make a game where it appears that the whole world is painted, and perhaps the levels of the game could be based on classic painting by Da Vinci, Picasso etc.

I have also been working on Atmospheric Scattering this month but because of my other commitments have not yet fully integrated with Decade. I will try and get a video update soon to at least give a taster of my progress.

The other day I found a shortcut to my old website. It has been almost 3 years since it was updated. Hosted on an Irish telecoms provider, I do not seem to be able login to my account from outside Ireland so it has remained static since I left. It has some fond memories for me. This was my start in game programming as a hobby. The host where my game demos were stored is no longer active so you cannot download anything. If you would like to try anything leave a comment and let me know. I will then find the game in my archive and upload it.

Underwater Caustics

2007-09-24T13:32:00.000+01:00

Caustics are defined as "The light patterns generated on a surface by reflected or refracted light rays." Imaging that you are in a swimming pool and swimming beneath the water. The sides of the pool are not evenly lit. As the light enters through the surface of the water it is refracted and causes areas of shadow to appear on any surface beneath the water line.

This implementation of caustics is physically fake. I do not represent light beams entering and refracting on the water surface. This effect is achieved by tiling a sequence of textures on the terrain for the area under the surface of the water.

Sequence of textures which are tiled over the terrain

This does require the graphics card to support a 3rd texture unit. If you remember from previous blog entries, the terrain already requires 2 texture units, 1 for the terrain texture and 1 for the detail map to add more realism to the scene. From some quick research it looks as though most modern graphics cards support at least 4 texture units so this should not be a problem.

Water Comparison

2007-09-22T15:33:00.000+01:00

With both my planned implementations of water nearing completion it seemed appropriate to run some comparisons.

CPUWater was coded so that Decade could render a terrain with water on PCs which do not support the relevant OpenGL Extensions required for GPUWater. Decade will automatically detect which it can use.

The main surprise to come from running this comparison is non technical. After a few friends and programming peers viewed my comparison video (below) approximately 80% if them commented on how good CPUWater looked and that they thought it looked more realistic than GPUWater.

Scene Rendered with CPU Water

Scene Rendered with GPU Water

The main reason for this is because CPU water moves. Its height at each point varies depending on the tessellation of the mesh therefore it looks like waves lapping the shore. Since GPU water is comprised on only 1 quad and the waves are simulated using bump mapping the shore line is static.

Perhaps I should write a CPUGPUWater. The water will comprise of a tessellating mesh like CPU water, but it will be rendered using bump mapping like GPU water. This might achieve a nice result of having water which moves naturally however also appears to be highly tessellated despite its low poly count.

GPU Water

2007-09-21T23:29:00.000+01:00

My second attempt at water rendering uses a vertex/pixel shader along with normal and dudv map's. Using the normal and dudv map's along with the reflection texture, which is dynamically generated each frame, the final effect is achieved.

The image above is the normal map. Instead of using each pixel for a color, the nomal map stores a normal (between -1 and 1). The normals naturally give the image a purple, pink and blue color. What we do with this image is basically use it to bump map our water to give it the appearance of being highly tessellated and realistic. This realism comes when we use per-pixel lighting on the water. If we didn't have a normal map we would just depend on the normal of the water surface, which is pointing straight up, the water would look like a flat mirror.

The image above is the dudv map. It is called that because it's actually the derivative of a normal map. In mathematics the notation for a derivative is du/dv. What this texture does is give us a way to calculate refraction and how the light will react and bend on the water. Notice how the dudv map looks like waves of water.

The image above is the reflection texture. This is caculated each frame by inverting the scene, setting up a clipping plane and rendering the reflective data. Projective texture mapping is then used to apply this texture to the water.

Although I am happy with this implementation there are a few changes that need to be made. Memories of my first implementation of CPU water are coming back. My lake again looks like a mirror. It is too bright and too reflective. It should be possible to see some way under the surface of the water. I have tried to implement the simple changes which were required by CPU water, after I changed to using a reflection texture rather than drawing the inverted scene to the screen, however there is no differnce. Adding Alpha Blending with a fixed function does not seem to make any difference when the pixel shader is used. If I remove the shader from the rendering, a correct flat blue alpha blended quad is rendered. Since the GPU water is effected by per pixel lighting prehaps I need to modify the pixel shader in some way. I have read a few tutorials on OpenGL shaders, however I feel that I need to complete a few more before I have the confidence to say for sure.

CPU Water

2007-09-19T06:39:00.000+01:00

As all can see its been a while since I updated the blog so yesterday I recorded a small video of decade. You can now see the engine in motion rather than just static screenshots.

Unfortunately YouTube has really lowered the quality of the video when it was uploaded but it should still give a rough idea about Decade.

The video shows a simple terrain with random trees and my CPU water with vertex projected reflections.

Other features that I am still working on are

GPU Water
Shadow Maps, Parallel Split Shadow Maps, Shadow Volumes
Atmopheric Scattering
Priority Rendering Queue
Octree
Scriptable Particle System

Random Issues

2007-08-24T07:12:00.000+01:00

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

2007-08-20T19:15:00.001+01:00

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

2007-08-09T18:34:00.000+01:00

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

2007-08-05T19:55:00.000+01:00

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.

C++ to C#

2007-07-06T07:40:00.000+01:00

I have written many programs in C++ and many in C# before but this is the first time I have tried to convert a full C++ program in C#. Since both languages have a very similar structure and share allot in common I thought this would be a simple matter but I was very wrong.

Its by no means an impossible task, however the small but significant differences require some rethinking and restructuring of Decade. (Managed Code, stronger typecasting, delegates etc...) I have allot of the core graphics components complete and am now on the File Parsers. It has taken a short while to get a grasp of Regex instead of using sscanf and such functions, but now progress is moving again. Hopefully by next week I will have some screenshots from Decade.NET.

Panorama

2007-07-01T17:38:00.000+01:00

As conversion continues, and there isn't really anything new to show, I thought I would upload these these test images. They show randomly generated scenes in Decade (hence why there are trees growing in the water) in panorama form,

June is almost over already!

2007-06-26T22:34:00.000+01:00

July has been a quiet month with posts, however development continues. Holidays. Being busy at work. Having custom work to complete outside work etc.... the month has just disappeared.

Deciding that my own custom GUI components wasn't the best way to spend my time, I started development on Decade in C# using Tao for OpenGL. Development is slow but steady. I am currently adding in the file parsers for the 3D file formats and then terrain loaders/generators. With this complete it will be on par with Decade and I can begin working on my Sandbox Editors.

There are no screenshots to show, because I am using the same media as Decade and the screenshots look identical. Hopefully I will get some more spare time soon and can get the rest of the current in development work completed.

Decade .NET

2007-06-07T13:40:00.000+01:00

For the past number of days I have been contemplating moving Decade to .NET. Programming the GUI Interface has raised this issue. I am currently spending allot of time programming a GUI System so that I can make Level Editors and a range of other tools for Decade.

Drawing and managing the controls myself was inspired by Unreal Tournament, however my results are nothing like this. I don't have the artwork or the time to match these results. In truth my rendered buttons do not look much different to those I created almost 10 years ago when making simple Mode13h Dos Games. In short, with this method I am spending allot of time with little gain and not really learning anything.

Another possibility would be to make the GUI in WIN32, therefore keep the engine as C++. This would save time in now requiring me to rewrite the engine, however I find GUI work in WIN32 to be hideous.

Although requiring the most work and the most time, I think that converting Decade to C# is the best course of action. With this I get to refresh my C#, learn some more .NET and have a nice and simple way to create good Gui's for my tools. To help me with this I have found The Tao Framework. This will help allot in using OpenGL with C#.

If anyone has any comments or ideas on this plan I would like to hear them.

Thanks

Update

2007-06-04T13:52:00.000+01:00

Decade Engine is still alive. It has been about 10 days since I worked on it. Last week I had holidays and I also got a new acoustic guitar so was distracted from programming for a short while. In the few hours that I did work on the engine focus was on making GUI Components and the GUI Manager. I hope that buttons, combo boxes, list boxes, edit boxes etc... will all be supported soon and I can start work on mesh and level editors.

Hopefully I will have some screenshots soon, but so far development in this area has been allot of functional stuff so nothing nice to show.

Let there be Light

2007-05-23T21:10:00.000+01:00

Basic lighting has been added to Decade. This adds another slight layer of realism to the scene. In my opinion the screenshot below does not do Decade Justice. The moving water being effected by light and shade creates an impressive effect. I have tried to create a video to upload to YouTube so I can show here but so far the quality hasn't been worth showing.

Patch Culling and Node Tree has been added to Brute Force Terrain. This now exceeds the frame rate of software rendered Geomipmapping, however Geomipping will soon be Hardware Rendered too and will hopefully increase in frame rate.

Other in progress work are Scriptable Particle Systems and GUI Components such as buttons, combo boxes etc...

Software Water

2007-05-18T19:11:00.003+01:00

Although I hope that some day Decade is a high end 3D engine supporting the most advanced technologies and rendering techniques, at present I want to make sure that almost anyone can play my games.

My full blown water will be rendered using Bump Maps and Stencil Reflections, which not all Graphics Cards support therefore I have first implemented a simple alpha blended tessellating mesh with a sphere mapped texture. Results are not very realistic however give the impression of water with semi-realistic movement.

In Wire frame one can see the mesh clearly. As the water mesh is constantly moving and is alpha blended it does not have to be as high a resolution as the terrain. The terrain is the images shown is 512x512 whereas the water mesh is only 60x60.

Multiple View Ports

2007-05-16T07:30:00.000+01:00

To take a little break from terrain programming I decided to try something else last night. While watching a Formula 1 Grand Prix over the weekend it reminded me of playing racing games and being able to turn on or off the rear view. Having always wanted to implement this I decided that now was the time.

I was amazed at how easy it is in OpenGL to achieve multiple view ports. After 10 minutes of reading an online document I realised that I already had all the code from my OpenGL setup functions so only a little reorganisation was required.

Decade can now support 1 t0 X view ports (I haven't tested an upper limit) and each view port is independently controlled, updated and rendered. They can share scene data or use entirely separate data.

Uses for this within my plans for Decade are currently limited. It was implemented for my enjoyment rather than for a real need, however it should become useful for rear view when in a car, split screen multiple players etc..

The Sky's the Limit

2007-05-12T13:15:00.000+01:00

Sky Boxes have been added to Decade, and as a friend has commented they give the scene atmosphere in more than 1 sense. The sky boxes used were taken from Hazel Whorley who offers his creations free for use in non-commercial projects. They are some of the best free sky box textures I have ever seen.

I will use sky boxes for a while with Decade however I want to soon implement sky domes. They have many advantages over sky boxes. Due to the cube nature of the sky box it is very difficult to animate the sky without the cube structure becoming obvious to the user. The dome removes this and will allow me to set the time of day and add procedural clouds.

Erosion Filters

2007-05-10T13:23:00.000+01:00

Having put the issue raised in blog entry If a man owns land, the land owns him on the to "Fix It Later" pile I continued development of Decade. All my documented issues are always on my mind as I research and develop, so yesterday while searching through random Terrain documents I found a Box Filtering Height Maps for Smooth Rolling Hills tutorial and immediately thought it might be useful. Even though I am not always going to want to have rolling hills I thought that such a method might enable me store the terrain in its original 1 or 2 byte format instead of using 4 byte floats.

Terrain with height values stored in 1 byte

Terrain with height values stored in 4 bytes

Terrain with height values stored in 1 byte and modified with Erosion Filter of Box Size 3 and 1 Iteration

As you can see, running the Erosion Filter on the terrain greatly improves the quality of the 1 byte height field. (When I say 1 byte height field I mean that the data in the .raw file was stored in bytes. The height field is still stored in 4 bytes (float) within Decade). There is a little loss of detail compared to the 4 byte terrain however depending on the game and environment this may be acceptable.

Terrain with height values stored in 1 byte and modified with Erosion Filter of Box Size 11 and 5 Iteration

Care has to be taken when using the Erosion Filter. As you can see above running with too large a box size over many iterations starts to remove allot of the detail from the terrain resulting in a flowing rolling landscape. Again, this may be desirable in certain instances and not in others.

What this has thought me is that there is no right answer to the question I am asking. It all depends on personal preference and the requirements of the game at that time. To accommodate this I am going to allow a broad range of options. My custom height map file will be modified to allow the user specify how the data is stored.

Currently the simple file type is
Width (2 Bytes)
Length (2 Bytes)
Data (Width * Length * 4 Bytes)

so by adding in a type field the user can save and load as they desire

Width (2 Bytes)
Length ( 2 Bytes)
Type (1 Byte)
Data( Width * Length * Type Bytes)

I hope that this,along with the box and any other Erosion Filters added later, will allow Decade deal with a large variety of requirements when rendering/storing its terrain.

A little forrest.

2007-05-09T07:21:00.000+01:00

As I mentioned in a previous post, I really wanted to add trees and other vegetation to my terrain engine. I believed that this would greatly add to the atmosphere. My first desire was to create all these trees and plants procedurally. After searching online for a while I found a few good tutorials on how to achieve this but have decided to place that idea on hold for a while. Eventually I would love to do this. It would be great to have procedural plants on a procedural planet in a procedural solar system within a procedural universe. :)

For now I have decided to use mesh's for the plants. Again, rather than waste my time trying to model them myself or look for appropriate free models online (any I found either looked wrong or were to complicated) I choose to purchase the tree packs from Loopix These are decent quality, low poly trees which are ideal for my needs.

Currently a small selection of the available trees are just placed at random on the terrain. Already I think they add a whole new feeling to the demo.

Procedural Texture Mapping

2007-05-04T19:20:00.000+01:00

Decade can now generate its terrain textures procedurally. This is a big step as each terrain created automatically gets textured based on its unique attributes. Instead of just showing you a screenshot I will briefly explain how the textures are created.

A set of base textures is gathered. These are plain textures of all the environments which will exist in the terrain. e.g. sand, grass, rock, mud, snow etc...

Each of these environments is given

optimum height (The best height at which this environment exists)
min height (The minimum height at which this environment exists)
max height (The maximum height at which this environment exists)

By cross referencing these values with the height map, the textures assigned to each terrain which exits at the given height are blended together with higher preference going to the more optimal terrain.

The result is the above texture which is then applied to the terrain. For my first implementation of this algorithm I am happy with the results, however as always there are many improvements which need to be added.

Tiling textures instead of stretching them
Add support for applying the detail texture to the terrain texture at this stage to cards which do not support multi-texture can still have detail at no extra cost.
Some better logic for texture blending instead of just checking the height. The environment in a valley is different to that of a cliff face at the same height, or rocky outcrops on a snow covered mountain etc...
Add lighting so that features are enhanced.
Add vegetation to add more realism.

Bitter Sweet Success

2007-04-30T23:05:00.000+01:00

Having quickly modified Decade, to store saved/generated terrains using floating point values rather than unsigned chars, I am happy and disappointed with the result.

As you can see above the smoother gradient makes the terrain looks allot more natural. It has been commented that the staired terrain looks cool, like contour farming, and perhaps it does in unique circumstances but it will not work for the terrain in general. Despite this success the loading/saving time and file size has been affected even more than predicted. Huge Height Map files and long loading times are not acceptable.

Some more research needs to be done for terrain storing and loading. Different possibilities which instantly come to mind which may or may not work are

Split the terrain over many files and load the segments coming into view on another thread
Store the terrain in the original .raw file and use some logic to smooth the vertices's

If a man owns land, the land owns him - Ralph Waldo Emerson

2007-04-30T19:54:00.000+01:00

Just back from a weekend break in London so I did not program for the past few days. Coming home yesterday we were delayed in the train station for 7 hours so while sitting around I had plenty of time to think about what I wanted to achieve with the terrain segment of the Decade Engine. Here are some improvements. (I know I said in my last post that I was just going to add Vertex Arrays and VBO's but after some consideration I believe that the following additions are also required.)

1) Change from using a .raw file to using my own custom format. The .raw file used 1 byte for each value. This limits the range of values from 0 to 255 and only whole numbers are included. I didn't notice any issue with this when I was rendering small terrains (up to 512x512) however now that much larger terrains are being rendered 8192x8192 (134,217,728 faces) a very undesirable stair case effect is emerging. Take a look at the attached screenshots. As the values of the terrain are rounded the terrain grows in increments making it look unnatural. I am going to create my own file format which will use floats instead of unsigned chars. This has the advantage of being correctly able represent the terrain however will result in a larger file size and a longer read/write time for the file. I believe the advantage greatly outweighs the problems.

Stepped Terrain caused by .raw file data storage

2) Now that larger terrains are being rendered some more intelligent culling of patches is required. Simply checking if each patch is visible to the camera (by checking collision with the viewing frustum) is not enough. The mentioned 8192x8192 terrain segment is made up of 232,324 patches. With the current implementation this results in 232,324 frustum checks per frame. By adding a simple node tree most of these checks can be bypassed.

A node tree is a method of subdividing the mesh (terrain in this instance) into smaller sections. For instance, with the terrain I would divide it horizontally and vertically through the centre resulting in 4 segments, top right, top left, bottom right and bottom left. These segments would then be recursively divided until the required tree depth is reached. When doing frustum checks the terrain algorithm would first check collision with the node tree. If the Top Right Segment (or any other segment) was not visible by the frustum all of its children could immediately be ignored as not visible. If the Tree Node is visible by the frustum each of its children would be checked etc..etc... I expect that this will give a huge performance increase when used with large terrains for both geomipmapped and brute force terrains.

Stepped Terrain caused by .raw file data storage

3) Add support for Vertex Arrays and VBO's in geomipmapped terrains.

Patch Culling

2007-04-27T08:22:00.000+01:00

Brute Force Terrain. 32258 Polygons Rendered

As a further addition to the Geomipmapped terrain I have added Patch Culling.

In my original implementation of Geomipmapping the distance from the camera to the terrain patch was calculated and from this the level of detail deciphered. If you remember your maths from school you will know that getting the distance between two points always returns a number which is greater than or equal to zero. Because of this no spatial relation between the objects is known so we still rendered patches which were out of view of the camera, although at its correct Level of Detail.

Geomipmapping with no Patch Culling. 5757 Polygons Rendered

With Patch Culling we simply check if the current patch is inside the Fustrum of the Camera. A fustrum is like a pyramid on its side, the pointy part at the lens of the camera extending out into the world. By doing some simple plane tests we can quickly and easily see if a point is inside this pyramid and therefore immediately ignore it if it is not. This does not only help us ignore faces to render, but we can also ignore patches to update so is useful for the GPU and the CPU.

Geomipmapping with Patch Culling. 2192 Polygons Rendered

The final addition to my Geomipmapped Terrain (for now) is to add support for Vertex Arrays and VBO's. I hope that this will increase the fps but it will also keep the render code separate from the terrain code therefore keep me on track for an engine which should be easier to update to DX.

Geomipmapping

2007-04-24T08:04:00.000+01:00

Geomipmapping my first implementation of a CLOD algorithm, is working in its most basic form. The images below show the different outputs from the algorithms. To render a segment of terrain which is 128x128 Brute Force renders 32510 faces while Geomipmapping only has to render 1240 in this instance (this varies depending on camera position).

Brute Force and Geomipmapped Terrains Rendered in Wire Frame

Brute Force and Geomipmapped Terrains. (Very little visual difference)

Even at this stage I am happy with the frame rate increase. In the images shown you can see that Geomipmapping achieves 72fps whereas Brute Force gets 67.7fps. This may not seem like much of an increase but please remember how the Brute Force vertices are stored and rendered. VBO (Vertex Buffer Objects) are used therefore the vertices are stored and rendered by the Graphics Card. My Geomipmapping implementation currently renders all faces with individual software calls. If I do the same for Brute Force for the selected terrain its fps drops to about 54.

By implementing Vertex Arrays or VBO's for Geomipmapping, which is also maintain my desire of keeping the algorithms and graphics API calls separate, I expect to see a frame increase. Also by adding Frustum Culling on each of the terrain patches in the Geo terrain I can further reduce the number of vertices to be rendered.

Memory feeds imagination - Amy Tan

2007-04-22T15:02:00.000+01:00

Problems with Vertex and Index buffers are fixed. It took a long round-about way to get there. To isolate the issue I created a software renderer for the Vertex and Index Buffers. This involved parsing the vertex and index data during the render loop and using individual glTexCoord2f, glVertex3 etc... calls to render each face. This immediately showed that the vertex data was correct however the index data was only half populated.

ASE Mesh incorrectly rendered with Index Buffers

Terain Segment incorrectly rendered with Index Buffers

e.g. In a terrain segment of of 8x8 there are 64 vertices, 128 faces and 384 indices. During the software rendering of the vertex and index buffers Decade engine crashed when the offset into the index buffer reached 147. It caused incorrect rendering or an Access violation because the value of the index buffer was 52685, but the vertex array has only 384 elements. Further investigation showed this to be an error with the memory copy functionality in the index buffer create function.

Instead of
memcpy( this->m_pusIndices, p_pusIndices, p_iNumberOfIndices );
it should have been
memcpy( this->m_pusIndices, p_pusIndices, p_iNumberOfIndices * sizeof(unsigned short) );

Problem fixed.

Fontastic

2007-04-17T17:50:00.000+01:00

After some research and help from the good people at GameDev I have found out there there is in fact no problem with the Vertex Arrays or VBO's. The problem lies in the Font Object.

A few days ago I wanted to show the Camera Position and Rotation so I quickly followed a Font Tutorial in order to display this info on screen. I didn't really pay attention to what I was doing as I planned on rewriting this anyway so I fell victim to Copy and Paste.

Upon review I found that the font class used switches from 3D to 2D mode every time a string is rendered, so when I was rendering 6 lines of text this involved 6 Switches to 2D and 6 Switches back to 3D. When I changed this so that it switches to 2D, renders all text and then switches back to 3D I did find some improvements.

Running on a lower end system

Os : Windows XP Pro SP 2
CPU : Intel(R) Pentium 4 3.00GHz
GPU : Intel(R) 82915G/GV/910GL Express Chipset Family (Driver Version 6.14.10.4410)
Ram : 1GB

I get the following results

107fps when rendering in a nested Loop.
128fps when rendering using Vertex Arrays.
130fps when rendering using VBO.

I will now add in Index Buffers and see what results I get, as well as running on my home computer which has a good graphics card.

Vertex Buffer Objects and still no JOY

2007-04-16T08:05:00.000+01:00

Yesterday I implemented Vertex Buffer Objects (VBO's) into Decade Engine. Although I am still very happy with the code and the future portability to DX, I am again disappointed with the performance results. There is limited increase in frame rate compared to software rendering and no increase compared to Vertex Arrays.

For those interested in a more in depth description as well as any possible fixes, you can check out here.

Vertex Arrays

2007-04-14T10:40:00.000+01:00

Vertex and Index Arrays have been added to the Decade Engine. The Brute Force Terrain is now rendered using a Vertex Array as a Triangle Strip.

Previously the Terrain was rendered in a nested loop, rendering X Triangle Strips, where X is the length of the terrain. Now when the terrain is created/loaded 1 Triangle Strip is created and loaded into a Vertex Array. At render time I simply ask OpenGL to render this Vertex Array. Sample source for Vertex Arrays can be found at here

Sadly this did not give me the frame rate increase I was hoping for. I will have to investigate if there is a reason for this, and I will also implement Vertex Buffer Objects. Despite the disappointing results the code is now allot more readable, allot more maintainable and the Terrain Object is API independent. I will easily be able reuse the Object as-is when I code my DirectX version of Decade. (if only things were ever that easy)

Many areas of the engine are still in development

CLOD Terrain Renders
Terrain Texture Generation
Terrain Lighting
Applying Vertex and Index Buffers to Mesh Renders

Terrain with Texture and Detail Map

2007-04-10T20:32:00.000+01:00

The issue with the Terrain Texture has been fixed, or at least bypassed for now. I have stopped using IPicture to load my textures and have written code to load the different file types. Currently TGA and BMP are supported. the jpeg lib file causes errors as it was built in VS 2003 and I am using 2005. This can be reviewed later.

As well as fixing the terrain texturing I have added detail mapping. This uses multi texturing to tile another "detail" texture over the terrain. I was quiet surprised to see what a huge difference such a simple technique could make to the realism of the terrain.

Terrain without Detail Map

Terrain with Detail Map

Terrain Engine

2007-04-07T23:37:00.000+01:00

Development today focused on Terrain Rendering. Decade can now load a terrain from a .raw file and can also generate terrain using the Fault Formation and Mid Point Displacement Algorithms.

Terrain is rendered using Brute Force. This means that all the the vertices are rendered regardless of how far they are from the camera. On a small terrain like this that doesn't really matter however when the terrain grows larger it would slow then rendering to render all vertices in this way. ROAM and CLOD will be added soon.

I also tried to add a texture to the terrain however there seems to be some problem. The texture is not complete even though the texture vertices appear to be correct. I am using the IPicture interface to load the textures so maybe there is a problem with this. Tomorrow I will try and manually load the textures and see if this fixes the problem.

My First Entry

2007-04-05T20:19:00.000+01:00

My very first blog and my very first entry. I never thought I would be a blogger. I find the whole idea strange and didn't think I would have anything worth the bother of blogging, however after being very impressed by a development blog of a friend of mine I thought that a similar idea would be a good motivation and diary for my personal project.

The Decade Engine is my new OpenGL graphics engine with which I hope to create 3D games. It is so called because this year it has been 10 years since I first started programming, and with a personal project like this I wouldn't be surprised if it took 10 years to finish.

I hope to use this blog to publish regular updated on the development and features of the engine and then details on the subsequent games made with Decade.

It starts. (Timon : The Lion King)

First Images

2007-04-05T16:03:00.000+01:00

ASE and 3DS models with Alpha Blending and Bounding Spheres

ASE and 3DS models with Alpha Blending and Bounding Rects

Here are the first images from the Decade Engine. Nothing impressive to see as they are just tech demo's for my testing purposes. Current features of the engine are

ASE Model Loading
3DS Model Loading (with animations)
MD2 Model Loading (with animations)
MD3 Model Loading (with animations)
Camera with Fustrum Culling
Object Hierarchy
Alpha Blending and Color Keying
Bounding Rect and Bounding Sphere

In progress

Terrain Rendering with Level of Details
Integration of the Open Dynamics Engine (http://www.ode.org/)
Scriptable Particle System