Archive for category Technical

Billboard Trees

No, not like this. Well, sort of like this.

So, I had my fancy schmancy terrain. I could render the ground. Yay. Accomplishment of the century. So, the next task would be to put something on the ground. Ambitiousness!

I figured the best thing to start with would be a vegetation system. I’d need a cheap, plentiful food source for when I started putting creatures on the map, and plants were the obvious choise. In addition, they add detail and make the entire map more interesting than just a ground-plane. To render them, I decided to use billboards.

Who needs more practice with their drawing tablet? You do! Yes you do!

Billboards, in a computer-graphics sense, are one-dimensional shapes that always face the camera so you don’t [i]see[/i] that they’re only one-dimensional. They’re like other-dimensional monsters that always know where you are. They’re used all the time in games, but normally only to represent complex objects that are often some distance away from the camera (like trees), or are too numerous to represent more accurately (like grass). As of the time of writing this, Species is still using billboards for it’s vegetation. This may have to change, but at the moment it’s one of the lower-priority items on the development list: the sprites, tacky as they are, are functional.

It would have probably been best to configure the vegetation to render in tandem with the QuadTerrain system, but knowing I would have to continually update the vegetation based on how much energy any particular vegetation object had, and allow all the creatures on the map to interact with it, I realised that a QuadTree would be less than ideal. The QuadTree system relies on larger nodes being less detailed than smaller ones: for the creature interactions, if not the rendering itself, I would need the same amount of detail everywhere on the map. So I divided the terrain into a simple grid, with each grid-square being given a small number of tree objects to manipulate and render. Creatures more than 2 squares away from a vegetation square don’t process the trees in it at all, saving CPU.

One advantage of a grid is that it correlates exactly with real-world space. Rather than checking the grid square by square, or sinking down through parent nodes in a quad tree, I can simply divide the creatures position co-ordinates by a given value and plug the result into the array to tell me instantly which square they’re in.

Am I being too technical? I’m being too technical, aren’t I? Oh god, what if I’m swamping you with boring technical information? Here, have a picture instead!

Look at the picture! Ignore my crippling insecurities!

Trees!

Now, they’re not perfect. They blend in with the terrain, which I don’t actually want in this case since it should be easy for the player to spot and identify food-sources. And they’re unbelivably tacky-looking because I threw them together in Adobe Flash using a laptop touch-pad. And, of course, they’re billboards. They look okay from a distance, but get too close and the illusion stops being at all convincing.

But then again, hindsight is always 20-20, and even though there’s a lot of things I would/will/might change, the vegetation billboard grid works for now. And maybe that’s good enough. For now anyway.

Want to hear something worrying? I don’t think he was actually being sarcastic in that first sentence.
Qu.

5 Comments

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

Getting into 3D

Late 2007

So here’s me, late 2007. University wasn’t going well, and I was beginning to suspect I had chosen the wrong career path. On the other hand, my programming skills had been improving, and I had finally gone looking for a 3D game engine.

I found Blitz3D.

Blitz’s simple interface and use of the BASIC programming language lightened the learning curve going from 2D to 3D graphics, but it also removed from me some area’s of complexity, like collision managment, basic drawing concepts and terrain rendering. In hindsight, I really can’t tell if this was a good thing or a bad thing. On the one hand, it allowed me to build a few projects to near-completion very quickly: on the other, I only had a very shallow understanding of what it was I was actually doing. I remained enthused, but it slowly began to dawn on me that Blitz simply wasn’t powerful enough for my needs.

Losing interest in one project and looking for something else to occupy myself, I decided that I needed a different, more powerful engine. I found something even more powerful than that: the XNA framework.

According to a definition I found on the internet, which means it is absolutely infallible and anyone using any other definition is a blasphemer and a heretic, a game framework is a step above raw DirectX but a step below an actual game engine: it’s used to build the engine, which in turn is used to build the game. I had no idea at the time what this meant, but I saw normal mapping and bloom effects in an XNA project and, eyes shining with innocence, I happily ran after the graphical candy.

Sold his soul for Parallax Mapping,
Qu

, , , , ,

Leave a comment