Archive for August, 2008

Britonia so Far …

Seeing as this is the first article on, I think it’d  best to get you up to speed on the current status of the project.

The name of the project, as you might have already guessed is Britonia, and in case you haven’t guessed from the web site theme, it is to be a ‘Medieval Trading and Combat Simulation’ game.
I came up with the name randomly, and as for the genre, I picked just what ‘theme’ most interested me at the start.  The main target of the project is not however, to make a fully working title, but rather a ‘playground’ of sorts where I can try all the interesting bits of code and tutorials found on the net or in books.

So far I have mainly been concentrating on the terrain.  As this is to be a trading game, one would (quite rightly) expect the game world to be large, with varying resources, factions, people and economies.  To that end, for the last couple of months, I have been trying several methods of programming terrain.

Brute Force Method: A good starting point for terrain one might argue, simply create a large static mesh from a heightmap, and throw it all at the graphics card.  This obviously didn’t work very well, but it is good practise for beginners to learn about using heightmaps to create terrains.  The problem with this method, is that, especially for large worlds, with richly detailed terrains, there are simply to many vertices/triangles.  Imagine you are standing on the edge of the corner of the map. looking off the side of the terrain, you are still sending all the vertices for the entire terrain to be drawn, even though 95% of the terrain is behind the camera; not good. To remedy this, we need some sort of spatial partitioning.  read on.

QuadTree / Octree :  I next looked to quadtrees.  Quadtrees are a way to partition space, so that we only update/render what is seen by the camera (  The quadtree works by first creating one large parent ‘node’.  This this node, in turn creates 4 child nodes, each child is half the size of its parent.  This continues along down each child node, until the node reaches some restriction which we have set (such as maximum levels or a certain size).  When the restriction is met, we create a terrain ‘patch’ (a mesh) which we will eventually draw.  Now, when we render the terrain we call Draw() on the parent node, the node will first check if it is visible or partilly visiable by the camera, if it is, we call draw() on each of it’s children.  If it is not visible, we skip the node, and thus we skip rendering it and all of its child nodes.  When we get down the the leaf nodes (the last children, which should all be visible by this point), then we render it.  As you can imagine this saves alot of draw calls and processing time.  This was good, but not nearly good enough for what I needed.  Imagine now, standing on the corner of the terrain, looking inwards towards the centre.  Every node in front of the camera will be drawn, even the nodes which are on the far reaches of the camera visibility.  This is correct behaviour, the problem is however that they are drawn with exactly the same amount of detail as the node you standing on.  So if you want the terran around the camera to look nice ( which is a must really ), you are forced to render triangles in the distance which you most likely cannot see, because they too have an equally large triangle count.  I needed to change this.

Chunked Quadtree :  Next I tried to implement Chunked Quadtrees.  This is a LOD algorithm in which at every node in the Quadtree, we create a mesh with an equal amount of vertices.  For example, say all nodes are 8×8 vertices.  The parent node creates a mesh of the entire terrain, using just the 8×8 vertices.  Just like the normal quadtree, this node then creates four children, which also create a mesh using just 8×8 vertices.  Now for each of the children, the area of which the 8×8 vertices represent is 50% smaller, so it has 50% more detail than it’s parent.  This continues down until the restrictriction we mentioned in the last paragraph is meet.  So now we have lot’s of different meshes with different LODs (Level of Detail).
Now when we call the Draw() method of the parent node, instead of just checking to see if the node is visibile, we check also the amount of Screen Space Error in the node.
This wasn’t easy to understand at first, but basically imagine 2 points of varying heights.  When the node creates the mesh, the vertices will be created on these two points.  Now when a child is created of this node, we need to create 50% more detail.  We do this by creating an extra vertices in between the parents vertices.  so now the two previous points are at positions 1 and 3 in the child mesh.  The child will then create the vertex in between these points at position 2.  The Error of the mesh is taken to be the distance between point 2, and the (previous) line between points 1 and 3.  The mesh error is then the highest error found in the mesh.
So now, if the node in the quadtree is visible, and if the error is less than a set tolerence, we can go ahead and render this node at this level, thus eliminating the need to draw only the leaf nodes.  If the error is higher than the tolernce and the node is visible, we can call Draw() on all the children, who’s error will be less.
This seemed a good way to implement the terrain at first, but it quickly became apparent that, with large terrains, and the need to create meshes at each level of the Quadtree, the memory requirements were just too high.  I wanted big terrains.

Plantary Bodies : I’ve been following another project for a while now, at least the bits of it which interest me.  It is called ‘Infinity: the Quest for Earth‘, which is a space simulation.  In Infinty, whole planets are generated procedurally, and they look amazing.  This was something that definitly interested me.  So I scoured around the internet for a bit and found a paper by Jochen Winzen.  Although I haven’t used the majority of the implementation outlined in the paper, it did help me understand how a full planet could be made.  And that is where I am today.
I am still using quadtrees, but this time I have 6 of them forming a cube.  Then using a method from the infinity engine, I project these quadtree vertices into a sphere.  All the quadtrees use normal frustrum culling, and they create new LODs when required, depending on the distance of the camera from the terrain.  Currently, I am creating 6 heightmaps at run-time and storing them into textures of size 1025×1025, one for each face of the ‘cube’.  The heightmaps are used for the height data for the LODs, as long as the resolution of the textures is still ok.  When the resoltion of the textures is not high or good enough, I use midpoint displacement to generate new height information.
This is not even nearly finished.  Currently I’m just concentrating on the mesh.  I still need to do texturing, vertex and texture morphing, mesh skirts (to hide seems between nodes of differrent LODs), GetHeight() method, which should return the height of a point on the terrain (currently this returns the height of the point above sea level) and the midpoint displacement doesn’t look very good.  This is all only for the terrain, the sky and other things I’ll look at in the future.

The biggest problem of all for me at the minute is scale.  Somehow you just don’t get the feeling that the world is huge ( which it is ).  The only way to see this was to set the run speed to 3 metres per second, and try to run to the first mountain I see.  I think this is just the bad heightmap generation and the texturing at the minute; which is extremely bad, also terrain scattering should help bring a bit of depth to the terrain.

So there you have it.


Leave a comment