Posts Tagged Terrain

Multi-texturing and Biomes

One of the priorities for 0.5.0 (the environmental update) has been to overhaul the multi-texturing system.

In 0.4.1 the best the engine could do was 4 textures (desert, grass, forests and cliffs), and those textures were placed at world-start, never changing. The end result was a very static map, very boring environment: basic tree loss/growth was the entire extent of environmental dynamics.

All this changes in 0.5.0. The design plan calls for a dynamic, responsive environment, and by crikey that’s what we’re going to have. (Crikey is Australian for… something. I dunno. Honestly I don’t even know what the word means, but it’s a stipulation of citizenship that we all say it at least once a week)

The first thing to add is more biomes. Desert/grass/forest works well as a basic, semi-tropical biome set, but what about colder biomes? Or warmer ones? Or wetter ones or drier ones? My current biome map concept has more than 20 different biomes drawn on a temperature/fertility map, including some hilariously extreme ones

If you can’t survive in a lava lake you’re simply not trying hard enough.

But that many biomes means a whole different approach to multi-texturing… or at least, I thought it did. This was when development started to go bad…

In 0.4.1 I used a multitexturing method called ‘texture splatting’. Imagine you’re painting the ground texture on a blank canvas. What texture splatting does is gives you a ‘stencil’ for each texture: so you can paint forest through the red stencil, grass through the green stencil and desert through the blue one, and by the time you’ve used all the stencils you’ve painted the entire terrain. All these stencils are nicely wrapped up into a single texture, called the blend texture.

Unfortunately, this only works for a limited number of textures per draw call: you can’t load more than a set limit of textures onto the GPU without it having a fit. So in order to render an unlimited number of textures, I’d need to change how I was approaching it.

My first attempt at a replacement system was sort of like an extremely complicated colouring book, where each grid square is numbered 1,2,3,4,etc and our hypothetical artist fills in the grid with grass/desert/forest from a colour key. Since we can include as many numbers as we like in the key, we can have as many biomes as we want.

Quick! Chop down a tree with your fists!

Once that’s done, our artist is faced with a problem: (s)he has to blur these colours together smoothly without pixilation or sharp edges. And since it’s going to be animated, a simple linear interpolation just isn’t going to cut it.

As it turns out, this is HARD. My own approach was to sample the biome-legend multiple times to give each pixel *four* biomes, each with a weighting value, which I then folded into the same channel as the key
(effectively, I designated the first digit of the channel as the key, and the remaining digits as the weight).

Honestly, the most surprising thing about this ridiculously complicated strategy is that it worked… mostly.

The grid is meant to be there.

But “works in general”, doesn’t mean “works well enough to use”. On closer inspection, the system produced artifacts all over the terrain. (not a typo: graphical glitches are “artefacts”, ancient relics are “artifacts”. I read that somewhere and internalised it, so it must be true) I actually got it working perfectly wherever 2 biomes met, but that was the limit: at any intersection with more than 2 it produced hard edges and odd colours, and the moment it was animated these artefacts started jumping about and generally making themselves easy to spot.

How many artefacts can you count?

So I ended up scrapping the idea entirely, and starting over with a new strategy, one requiring less math and more art.

This new strategy was much simpler: we go back to using the ‘stencil painting’ system, but this time once we’re done painting with the first 4 stencils (biomes), we put a new, transparent canvas over the existing canvas and keep on painting on that with a new set of stencils. Rinse and repeat.

This method turned out to have it’s own set of pitfalls, chief among them, alpha-blending and redrawing the entire terrain multiple times, with different textures each time. For an item which takes up as much of the screen as the terrain, this is a large graphics cost, and in a GPU-bound game probably would have spelled the end of this strategy. But Species is CPU-bound: it has GPU cycles to spare. So full-steam ahead.

“Everlasting pure darkness” will not be a biome in the full game. (Unless someone mods it in).

The artefacts of this method also turned out to be quite different to the ones I faced with the other method. The other method loved to produce singular, localised artefacts: hard edges and biome colours where they shouldn’t be. This method’s artefacts usually affected the entire terrain. I’d say two in particular are worthy of noting here, mainly because I haven’t actually managed to fix them: double rendered polygons and biome-set edges.

Biome-set edges were where one transparent layer tried to fade out into another. I never had any trouble with the inter-set blending, but proper alpha blending is a temperamental thing. In this case, because the biome colour fades out at the same time as the opacity does, the end result was a faded-but-noticeable black ‘border’ between different blend-sets.

Oh so that’s what wars are fought over.

I managed to ‘fill-in’ the majority of these borders by extending the colour to the very edge, but there is still a faint one around the first draw pass. Thankfully it’s subtle, and dealing with it had some odd side effects, so I’m going to leave that one alone. It’s not hugely noticeable.

Double-rendered polygons, on the other hand, are a problem.

It’s zombie-triangle apocalypse! Only trigonometry geeks will survive.

This isn’t actually a problem with the rendering method: it’s a problem with the QuadTerrain itself, which I didn’t know about until the rendering method made it visible. See, when the terrain is completely opaque, rendering a polygon twice has no effect. The colour from both renderings is the same, so it’s an invisible artefact. But when you render a *transparent* object, like, say… one of the 4-biome passes of the terrain… *then* it becomes quite visible, as you can see above.

But fixing it means re-familiarising myself with the QuadTerrain class, which I haven’t touched in quite some time. I’ve already made a little progress, eliminating about half of the artefacts above with one fix. Hopefully the next fix will get the rest, but I doubt it: bugs like this are often inversely exponential. You might be able to fix the majority of them easily, but there are always one or two subtle, extremely well hidden ones that you have next-to-no chance of ever finding.

Oh well, best I can do is to make sure I get most of them.

Currently, I have 23 biomes defined as rough shapes on a temperature/fertility axis. This includes ‘extreme’ biomes, like lava and salt-plains, and a number of underwater biomes that will only be found… err, underwater. (Fertility will at least partly be determined by height: everything below the water plain will be water).

So far everything is coming together as planned. Biomes are done, 3d trees are done (I’ll do a proper post on them later), I’m midway through tying the two together, and soon the nanozombies will be unleashed on the unsuspecting… oh wait wrong blog. You didn’t hear that.

Qu

“Other stipulations of Australian citizenship include:

– Must defend vegemite no matter personal opinion of taste. (sticky salty gunk)
– Must be willing to throw foreign tourists in front of a croc to save yourself. (Or was that the other way around?)
– Must know how to defend against drop-bears (trick question: there is no way to defend against drop bears)”

Advertisements

, , , , , , , , ,

Leave a comment

Terrain! from the Past!

Written July 2008

In 3 dimensional graphics, a computer can only render so many triangles before it suffers death by framerate. This is a problem in most games: the artists can never put as much detail into their 3D models as they would like.

With games where you can see and walk to the horison and beyond, this is especially awful. How can a computer render every triangle on a terrain so many kilometers wide, and still get a decent framerate?

The answer is fairly simple: it can’t. But the computer can reduce the number of triangles to be rendered on the graphics card. A distant mountain doesn’t need to have the same level of detail as the ground under the players feet, after all.

This is the point of Level of Detail (LOD) Algorithms: render fewer triangles, but get a visual result very similar to what you would have had you rendered them all. There are many different styles of LOD Algorithm. Species uses a QuadTree.

A Quadtree is a structure where each node is subdivided into 4 children nodes, each child node subdivided into 4 grandchildren nodes, etc. In the context of a terrain, this means that the ‘root’ node would have a low detail mesh, the children would have a higher detail mesh, the grandchildren have higher detail still, etc…

As the camera moves about the terrain, therefore, you can sink deeper into the quadtree and render high detail squares for nearby objects, and not sink anywhere near as far for distant objects, thus rendering them at a much lower detail.

[Present me says: this is where I seamlessly stitched in further detail from a more technically orientated post. You may not be able to follow much of the following without a background in graphics programming and/or wikipedia]

Stitching

Of course, nothing is perfect. Two same sized quadnode meshes next to each other will fit seamlessly, but imagine a high detail node next to a low detail node. The result will be artifacts known as gaps.
This can be fixed by ‘stitching’, where you either add or remove edge vertices from the nodes so that they match each other. In this case, I removed vertices from the higher detail node, creating a triangle pattern which connects to the lower detail node. In this screenshot, you can see it applied to every edge of every quadnode. In this one, it is applied correctly.

Of course, this isn’t as simple as it sounds: each quadnode is now accompanied by 9 meshes, 1 for no stitching, 4 for a single edge stitched, and another 4 for two stitched edges. Since these are generated at runtime, however, they aren’t a problem. [Present me says: well, they’re less of a problem than they would be if I tried to save them in memory. This is a case of putting up with longer loading times to reduce the memory footprint of the game]

Bounding Frustrums

It isn’t only distant objects need to be LODd. Nearby nodes which are not in view because you are looking in the opposite direction need not be rendered at all.

By doing a collision test between the camera’s “Bounding Frustrum” (a 3d shape representing the cameras viewport) and a quadnodes bounding box, we can determine which nodes are outside the view and quickly cut a whole heap of geometry from the render. By combining this with the distance testing, we can stop that from sinking further into off-screen nodes as well!

Multiple Vertex Buffers

One of the things I spent a lot of time on was converting the terrain to run with more than one vertex buffer.
The vertex buffer contains all the vertices read off of the heightmap. In general, it’s best to use a single buffer, because each buffer must be rendered with a separate Draw call. Unfortunately, there is a maximum limit to the number of vertices that can be rendered at once on the graphics card, and going above this limit will force the call to be rendered on the CPU (resulting in death by frame rate).

This limit varies, but on my home computer over a million vertices (a 1024×1024 terrain) is just a bit too much.

So, I implemented a nasty and complex algorithm to separate the terrain into a number of vertex buffers, based on the idea that each quadnode could be entirely contained within a parent vertex buffer if we split it correctly. This (eventually) came out well: it is now possible to split your terrain based on a size value. A 1024×1024 terrain split by 512 vertex buffers will come out as 4, 512×512 vertex buffers, with a fifth for all quadnodes which cover an area greater than 512 (only the root node, in this case).

It’s worth noting that I may have managed this whilst drunk, tired or otherwise incapacitated, as I cannot remember actually coding it, and have no really idea how or why it works. But it does, and seems to be bug free. [Present me says: Yes, that’s right. Apparently, the Ballmer Peak actually exists]

Global Normal Map

This shader was my first attempt at HLSL (High Level Shader Language), and came out brilliantly in my opinion. [Present me says: Hah! Oh you poor naive fool]

Dynamically changing the geometry can have a nasty effect: although the shape of a low detail node may be very similar to that of a high detail node, the shading can result in a fairly large difference in appearance if done per vertex.
To solve this, I took advantage of the power of HLSL, and told the terrain shader to use a global normal texture rather than per vertex normals. The advantage was twofold: My vertex buffers halved in size, and more importantly shading no longer changes between high and low detail quadnodes.

Detail Normal Map

Initially, I didn’t understand the mathematics behind normal mapping, and thought that by simply adding a detail normal map value to my global value in the shader I could create detail normal mapping. The result looked OK, but it wasn’t accurate: the detail normal ‘pulled’ the global normal upwards. When I tested with a high strength value for the detail normal, this was instantly apparent: the entire terrain was shaded as if it was a lot flatter than it truly was.
It wasn’t until after I’d finished the multitexturing that I worked out how to fix this, but when I did the difference was apparent (see below).

Multitexuring

Using a single texture for the entire terrain has two problems: the terrain is too big to be covered with a single texture with a high enough resolution, and tiling the same ground texture over the entire terrain is very bland. Therefore, I went for a multitexturing approach that made use of a blend texture.
In short, mutitexturing is using more than one texture on the same object, and a blend texture uses it’s red, green and blue channels to define the amount of each texture to show. In the sample, Blue represents sand, Green – grass, Red – Foliage and Black displays as Rock.
Quickly back on the subject of Detail Normal Mapping: you can see the difference between my original method, and my final method.

Distance Sorting

“Overdraw” is a term used when the pixel shader renders a distant object, then renders a closer object which completely obscures the distant object. Obviously, rendering the distant object was unnecessary: it didn’t end up being drawn on the screen, and rendering it simply hurt the fill-rate.
The GPU can overcome this if the near object is drawn first: when rendering the distant object, the fact that an object with a smaller Z-Buffer value has already been rendered will be detected, and the rendering process will be skipped.
Therefore, it is to our advantage to render the near quadnode before the far ones. Since a list of Quadnodes to be drawn is built seconds before the quadnodes indices are compiled into the index buffer, it’s a relatively easy fix to add a sort function in between.


Isn’t snarking in italics supposed to be my job?”
Qu.

, , ,

Leave a comment

Terrain!

Mid 2008

So, the first thing one needs do when beginning to code an evolution simulator is… what?

There’s no right answer to that question, but in my case I went for “make a world”. The creatures would need a ground plane to walk around on, and I wasn’t about to give them a featureless, boring surface. I wanted a world, with hills and cliffs and such-like. So, after optimistically trying “import Terrain“, I came to the conclusion that I was going to have to build my own system for consturcting and rendering the ground geometry. And you know what? I wasn’t going to settle for a sub-standard terrain system. I was going to built the BEST. DAMN. TERRAIN RENDERING SYSTEM. EVER.

Spoiler: some time after I was done, I went and started another, EVEN. BETTER. TERRAIN RENDERING SYSTEM because the one I built for Species was substandard and my comments at the time about it ‘looking awesome’ were kinda pathetic. Live and learn.

Okay, in the interests of full disclosure: at this point I’m going to cheat and shoehorn in a few posts from an old blog I made (now deleted) under another account (now redundant) when I was a young whippersnapper (now less acne’d). If you notice a change in the quality of writing, blame that on past-me, who is slightly less insane and nowhere near as awesome as present-me.

So here goes, over to the me from July 2008…

Also, future-him is kind of a dick.
Qu

Leave a comment