Tuesday, March 16, 2010

GPU Procedural Planet

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
  1. 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.
  2. 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.

Wednesday, February 24, 2010

Concentric LOD Areas

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).

Friday, January 15, 2010

Procedural Planet - Subdividing Cube

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.
  1. 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.

  2. 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.

  3. 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.

Wednesday, December 09, 2009

Terrain Editor - Version 2

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.

Wednesday, November 25, 2009

CPU v GPU Procedural Terrain Texture Generation

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.

  1. 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.
  2. 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.

Thursday, November 19, 2009

Higher Detail Heightmap Textures

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.

Tuesday, November 10, 2009

Winter is returning and I'm back again.

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.

Monday, February 23, 2009

Basic Terrain Editor

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...)

Wednesday, October 29, 2008

Would you like to use Decade?

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

Sunday, October 26, 2008

Its been a long time

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....

Monday, June 16, 2008

Procedural Planet - Texture Generation

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.

Friday, May 23, 2008

Procedural Planet

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.

Friday, April 25, 2008

MD5 Mesh and Animation

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.

Saturday, April 05, 2008

Terrain Precalculated Shading Techniques

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!

Wednesday, April 02, 2008

Slope Lighting

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.

Monday, March 31, 2008

Terrain Cracks Revisited

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.

Tuesday, March 25, 2008

General Update

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.

Monday, February 18, 2008

Shadows

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
      From Lights point of view. Depth Buffer saved to Texture
      From Cameras point of view with only ambient lighting.
      From Cameras point of view with light enabled and Shadow Map applied.



    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.

Saturday, January 12, 2008

Car Physics

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.

Sunday, December 23, 2007

Ubuntu

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.

Saturday, December 15, 2007

Decade Meets ODE

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...)

Tuesday, October 30, 2007

Atmospheric Scattering

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.

Wednesday, October 24, 2007

Procedural Sphere

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.

Sunday, October 21, 2007

Oil Painting

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.

Monday, September 24, 2007

Underwater Caustics

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.



Saturday, September 22, 2007

Water Comparison

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.

Friday, September 21, 2007

GPU Water

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.


Wednesday, September 19, 2007

CPU Water

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

Friday, August 24, 2007

Random Issues

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

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

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

Monday, August 20, 2007

Resistance is Futile

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

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

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

Improvements made this week are....

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

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

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


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


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


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


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

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

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

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

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

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

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

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

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

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