Tech Feature: Noise and Fractals

Introduction
Now that I have a working algorithm for terrain rendering, I wanted to try making some of it procedurally. This would not be used in order to generate levels, but instead to help artists add some extra detail and perhaps for some effects. The natural world is very noisy and fractal place, so in order a to get a nice looking environment, these two features are crucial.

Noise
When doing noise for natural phenomena, one normally wants some kind of coherent noise. Normal white noise, when nearby pixels are not correlated in any way, looks like this:

This is no good when one wants generate terrain and the like. Instead the noise should have a more smooth feel to it. To get achieve this, one fades between different random values, creating smooth gradients. A way to do this is to generate a pseudo-random number (pseudo because a certain coordinate, will always return the same random value) for whole number points, and then let the fractional parts between these be interpolations. For example, consider the 1D point 5.5. To get the value for this coordinate the pseudo-random values for 5 and 6 are gotten. Lets say they are 10 and 15. These are then interpolated and since 5.5 lies right between them, it is given the value 12.5 ( (10+15)/2 ). This technique is actually very similar to image magnification, where the whole numbers represent the original pixels.

Generating random numbers this way, something like this is gotten:


This looks okay, but the interpolations are not very smooth and looks quite ugly. This can be fixed by using a better kind of interpolation. One way to to do this is using cosine-interpolation, which smoothen the transition a bit.

This looks a lot better, but the height map image still looks a bit angular, and not that smooth. However, we can smooth it even further by using cubic interpolation. This ties nicely into the image magnification analogy I made early as cubic is a common type of filter for that. It works by not only taking into account the two points to blend between, but the points next to them as well. In our above example this would be the points 4 and 7 (which are next to 5 and 6). It looks like this:


This gives a much smoother appearance, but it (as well as the other algorithms above) has some other problems. Because the height values for each whole pixel are completely random, it is gives a very chaotic impression. Many times one wants a more uniform look instead. To fix this something called Perlin noise is used. What makes this algorithm extra nice is that it based on gradients instead of absolute values for each pixel. Each whole pixel is assumed to have the value 0, and then a gradient determines how the value changes between it and a neighboring pixel. This allows it to be much more uniform look:


Because of it is based on gradients, it also makes it possible to take the derivative of it, which can be used to generate normal maps (something I am not using though). It is also quite fast, pretty much identical to the cosine interpolation. The cubic interpolation, which requires more random samples, is almost twice as slow.


Fractals
Now that a coherent noise function is implemented it can be used to generate some terrain. The screens above does not look that realistic though and to improve the look something called Fractal Brownian Motion can be used. This is a really simple technique and works, like all fractals, by iterating an algorithm over and over. What is iterated is the noise function, starting off with a large distance between the whole pixel inputs (low frequency) and then using smaller and smaller distances (higher frequency) for each iteration. The higher the frequency the smaller the influence, resulting in the low frequency noise creating the large scale features and the high frequency creating the details.

The result of doing so can produce something like this:


Suddenly we get something that looks a lot more like real terrain!

There is lots of stuff that can be done with this and often very simple alteration can lead to interesting results. Here is some iterated fractal noise that as been combined with a sine-function afterwards:


End notes
There is a lot more fun stuff that can be done using noise and I have just scratched the surface with this. It is a really versatile method with tons of usages for graphics. The problem is that that it can be quite slow though and my implementation will not be used for any real-time effects. However, Perlin noise can be simulated on the GPU, allowing it for realtime usage, and this is something I might look into later.

Next up is the hardest part of the terrain rendering - texturing! I am actually still not sure how to do it, but have tons of ideas. Can never get enough of info though, so if anybody know any good papers on terrain texturing, please share!

Banning Happy Meals

I have a post up on HBR Blogs today expressing skepticism that banning toys in fast food meals will actually reduce the quantity of fast food consumed.

Putting yourself in the shoes of the bad: MegaMind

I was reluctant to take the kids to see MegaMind. For one, it was in 3D. For another, it was the second animated movie of the year told from the perspective of the evil mastermind. The other was Despicable Me which was fine but somewhat predictable. Suffice it to say, my expectations were low.

That being said, I am happy to report that MegaMind got itself an "exceeds expectations" evaluation in my book. The story is told from the perspective of the evil mastermind, MegaMind. But the back story was a not too subtle hit on the age-old 'nature versus nurture' debate. MegaMind starts off in exactly the same shoes (albiet with a different skin colour) as his eventual nemesis MetroMan. They escape a planet -- Superman style -- land on Earth with MetroMan landing in a comical life of privilege while MegaMind lands literally in prison where he remains until he is fortunate enough to attend the very same gifted school as MetroMan. MegaMind stuggles socially and with continual bad luck while MetroMan does not. MegaMind, after an heroically long period of misfortune, decides to through in the towel and trying to be good and becomes evil. That, as it turns out, brings him a relatively fulfilled life but as you can imagine with such existential underpinnings, something is amiss and he doesn't work it out until some life changing events occur. 

I won't tell you more of the plot here suffice it to say that (a) it wasn't silly and made sense and (b) you actually wanted to find out what happens. That puts it right up there in the kid-movie stakes. Throughout, without trying too hard, is a ton of 'adults will only get it' referential humour and, indeed, in this theatre, the adults laughed loudest.

One final amusing bit. A commercial came on prior to the movie showing young girls asserting that they "can be whatever they want to be." At the end of it we found out it was a commercial for Barbie eliciting the biggest groans throughout the audience. The good news for Barbie is that people apparently paid attention to this ad. The bad news is that their heroic rebranding strategy doesn't look like it will work.

Tech Feature: Terrain geometry

Introduction
The past two weeks I have been working on terrain, and for two months or so before that I have (at irregular intervals) been researching and planning this work. Now finally the geometry-generation part of the terrain code is as good as completed.

The first thing I had to decide was what kind of technique to use. There are tons of ways to deal with terrain and a lot of papers/literature on it. I have some ideas on what the super secret project will need in terms of terrain, but still wanted to to keep it as open as possible so that the tech I made now would not become unusable later on. Because of this I needed to use something that felt customizable and scalable, and be able to fit the needs that might arise in the future.

Generating vertices
What I decided on was a an updated version of geomipmapping. My main resources was the original paper from 2000 (found here) and the terrain paper for the Frostbite Engine that power Battlefield: Bad Company (see presentation here). Basically, the approach works by having a heightmap of the terrain and then generate all geometry on the GPU. This limits the game to Shader Model 3 cards (for NVIDIA at least, ATI only has it in Shader model 4 cards in OpenGL) as the height map texture needs to be accessed in the vertex shader. This means fewer cards will be able to play the game, but since we will not release until 2 years or so from now that should not be much of a problem. Also, it would be possible to add a version that precomputes the geometry if it was really needed.

The good thing about doing geomipmapping on the GPUis that it is very easy to vary the amount of detail used and it saves a lot of memory (the heightmap takes about about a 1/10 of what the vertex data does). Before I go into the geomipmapping algorithm, I will first discuss how to generate the actual data. Basically, what you do is render one or several vertex grids that read from the heightmap and then offset the y-coordinate for each vertex. The normal is also generated by taking four height samples around current heightmap texel. Here is what it looks in in the G-buffer when normal and depth are generated from a heightmap (which is also included in the image):


Since I spent some time with figuring out normal generation algorithm, here is some explaination on that. The basic algorithm is as follows:

h0 = height(x+1, z);
h1 = height(x-1, z);
h2 = height(x, z+1);
h3 = height(x, z+1);
normal = normalize(h1-h0, 2 * height_texel_ratio, h3-h2);

What happens here is that the slope is calculated along the x-axis and then z-axis. Slope is defined by:
dx= (h1-h0) / (x1-x0)
or put in words, the difference in height divided by the difference in length. But since the distance is always 2 units for both the x and z, slope we can skip this division and simply just go with the difference in height. Now for the y-part, which we wants to be 1 when both slopes are 0 and then gradually lower as the other slopes get higher. For this algorithm we set it to 2 though since we want to get the rid of the division with 2 (which means multiplying all axes by 2). But a problem remains, and that is that actual height value is not always in the same units as the heightmap texels spacing. To fix this, we need to add a multiplier to the y-axis, which is calculated like this:

height_texel_ratio = max_height / unit_size

I save the heightmap in a normalized form, which means all values are between 1-0, and max_height is what each value is multiplied with when calculating the vertex y-value. The unitsize variable is what a texel represent in world space.

This algorithm is not that exact as it does not not take into account the diagonal slopes and such. It works pretty nice though and gives nice results. Here is how it looks when it is shaded:


Note that here are some bumpy surfaces at the base the hills. The is because of precision issues in the heightmap I was using (only used 8bits in the first tests) and is something I will get back to.


Geomipmapping
The basic algorithm is pretty simple and is basically that the longer a part of the terrain is from the camera, the less vertices are used the render it. This works by having a single grid mesh, called patch, that is drawn many times, each time reperesenting a different part of the terrain. When a terrain patch is near the camera, there is a 1:1 vertex-to-texel coverage ratio, meaning that the grid covers a small part of the terrain in the highest possible resolution. Then as patches gets further away, the ratio gets smaller, and and grid covers a greater area but fewer vertices. So for really far away parts of the environment the ratio might be something like 1:128. The idea is that because the part is so far off the details are not visible anyway and each ratio can be a called a LOD-level.

The way this works internally is that a quadtree represent different the different LOD-levels. The engine then traverse this tree and if a node is found beyond a certain distance from the camera then it is picked. The lowest level nodes, with the smallest vertex-to-pixel ratio, are always picked if no other parent node meet the distance requirement. In this fashion the world is built up each frame.

The problem is now to determine what distance that a certain LOD-level is usable from and the original paper has some equations on how to do this. This is based on the change in the height of the details, but I skipped having such calculations and just let it be user set instead. This is how it looks in action:

White (grey) areas represent a 1:1 ratio, red 1:2 and green 1:4. Now a problem emerges when using grids of different levels next to one another: You get t-junctions where the grids meet (because where the 1:1 patch has two grid quads, the 2:1 has only one) , resulting in visible seams. The fix this, there needs to be special grid pieces in the intersections that create a better transition. The pieces look like this (for a 4x4 grid patch):

While there are 16 border permutations in total, only 9 are needed because of how the patches are generated from the quadtree. The same vertex buffer is used for all of these types of patches, and only the index buffer is changed, saving some storage and speeding up rendering a bit (no switch of vertex buffer needed).

The problem is now that there must be a maximum of 1 in level difference between patches. To make sure of this the distance checked, which I talked about earlier, needs to take this into account. This distance is calculated by taking the minimum distance from the previous level (0 for lowest ratio) and add the diagonal of the AABB (where height is max height) from the previous level.


Improving precision
As mentioned before, I used a 8bit texture for height for the early tests. This gives pretty lousy precision so I needed to generate one with higher bit depth. Also, older cards must use a 32bit float shader in the vertex shader, so having this was crucial in several ways. To get hold of this texture I used the demo version of GeoControl and generated a 32bit heightmap in a raw uncompressed format. Loading that into the code I already had gave me this pretty picture:

To test how the algorithm worked with larger draw distances, I scaled up the terrain to cover 1x1 km and added some fog:

The sky texture is not very fitting. But I think this shows that the algorithm worked quite well. Also note that I did no tweaking of the LOD-level distances or patch size, so it just changes LOD level as soon as possible and probably renders more polygons because of the patch size.

Next up I tried to pack the heightmap a bit since I did not want it to take up too much disk space. Instead of writing some kind of custom algorithm, I went the easy route and packed the height data in the same manner as I do with depth in the renderer's G-buffer. The formula for this is:

r = height*256
g = fraction(r)*256
b = fraction(g)*256

This packs the normalized height value into three bit color channels. This 24 bit data gives pretty much all the accuracy needed and for further disk compression I also saved it as png (which has non-lossy compression). It makes the heightmap data 50% smaller on disk and it looks the same in game when unpacked:

I also tried to pack it as 16 bit, only using R and B channel, which also looked fine. However when I tried saving the 24bit packed data as a jpeg (which uses lossy compresion) the result was less than nice:


Final thoughts
There is a few bits left to fix on the geometry. For example, there is some popping when changing LOD levels and this might be lessened by using a gradual change instead. I first want to see how this looks in game though before getting into that. Some pre-processing could also be used to mark patches of terrain that never need the LOD with highest detail and so on. Using hardware tesselation would also be interesting to try out and it should help add surfaces much smoother when close up.

These are things I will try later on though as right now the focus is to get all the basics working. Next up will be some procedural content generation using perlin noise and that kind stuff!

And finally I willl leave you with a screen container terrain, water and ssao:

The circular flow of candy

This weekend was a busy one for the Gans children. On Saturday, I took Child No.1 and Child No.2 to Washington DC for the Rally to Restore Sanity. It was Child No.1's birthday present and you can read my thoughts about the event here. The children absolutely loved the day. The whole event was completely unlike anything they had experienced and I am sure they will remember it for years to come.

But, of course, that wasn't the main event of the weekend. Sunday was, of course, Halloween. You may recall that it was Number One on the list of things they looked forward to being in the US. They had never really experienced it. Indeed, neither had I. I could not believe the sheer volume of activity there was. We had bought huge bags of candy from Costco and it was all gone by 7:30pm. We toured neighbourhoods lit up and decorated. One family had actually built a pirate ship manned by skeletons on a harbour on to the front of their house. It was incredible.

I toured around with Child No.3 on the 5 to 6pm run -- while it was still light out. She was dressed as a black cat. She was a little unsure at first in going up to houses but soon got into the swing of things. Of course, she kept on wanting to eat her goodies as soon as she got them. I was hoping to space it out a little but failed.

Child No.2 toured with a friend for almost three hours and brought home an impressive haul. He built himself a costume as a MacBook Pro -- complete with his own live head on YouTube. It was an impressive engineering feat as he used only materials lying around the house to fashion the device. The costume lasted the evening but has no fallen apart. Nonetheless, it got quite the reaction in our neighbourhood.

No one had been looking forward to Halloween more than Child No.1. I didn't even have the heart to impose a health tax on the night's activities (To be sure, if I had, it would have been based on market value). The problem is that as a 7th grader, she large cohort had been there all before. So out she popped dressed as Indiana Jones only to find that her colleagues wanted to do a little trick or treating before retreating to one of their houses. Apparently, some boys went out and got with the spirit but my daughter didn't realise that was on and so missed out. She came home with a reasonable haul but it wasn't of the scale she had been hoping for. Sadly, she had outgrown Halloween before she had a chance to experience it. She might have been better off putting up with her younger brother.

But I have to say that, as an economist, this entire evening is a curious one. Let us be clear what happened. We all bought bags of candy. We then gave it out while sending our own children to collect more. A simple adding up constraint suggests that the total consequence of the evening was a massive redistribution of individual candy but probably not much change in the aggregate household acquisition. Basically, we just bought our kids a ridiculous amount of special treats and tacked on a hunting task to the endeavour. The candy industry must be thrilled with this turn of events. 

Sadly, there was little innovation to be seen. One house gave out little toys which thrilled everyone. Another gave out fair trade chocolate. But because of the completely irrational fears about poison or something (and let me tell you, from an economic point of view, Halloween is the worst possible time to engage in murder without consequence), no one could make anything and it was difficult to step apart from the crowd. This only occurred to me too late. What remains is a flow of candy in a game of musical chairs where everyone can sit. I can see why 7th graders might get tired of it after a decade or so.

Halloween Tips. Sale and more!

Now that northern hemisphere people move into darker times what can be better than to indulge in some horror! Read along to get some tips on games, books and movies to check out this Halloween!

What to Play?

First of all we have to recommend our own creations that are now available at a very low rate! Amnesia and Penumbra can both be gotten for as low as 50% the price on several online stores. Right now discounts are available at Our Own Store, Steam, GamersGate, ImpulseDriven and the voices tell me Direct2Drive will have discount very soon too.

I would also like to put special attention on our newly launched Mobile Store. It is an ordinary internet store where you can buy the game by simply sending an SMS. It does not get much easier than that and is especially nice for anyone missing a credit card! All our games are on sale there too and if you are lucky they might cost you less than half the normal price! So do not hesitate and check it out now:
http://mobile.frictionalgames.com/

In case you have already played both Amnesia and Penumbra, here are some more more recommendations:

Anchorhead
A lovecraftian Interactive Fiction game with story similar to "Shadow of Innsmouth" and "The Case of Charles Dexter Ward". It is quite long and very well written and implemented. If you can manage playing without graphics this is a great choice.

Call of Cthulhu: Dark Corners of the Earth
Another lovecraft-game, but this time in glorious realtime 3D. Especially the first third of the game is deliciously creepy with a nice foreboding atmosphere. If you can stand a few bugs and cheap deaths, this game is well worth getting.

I have no mouth and I must scream
This is a game that is not that scary, but instead features some extremely disturbing themes. The story takes place in a post apocalyptic future, where the last five people on earth are being tortured by a not-so-friendly AI named AM. It plays like a usual point-and-click but with some fun twists. Unfortunately the game suffers from some annoying puzzle design, but is still worth trying out. And oh, the game works with ScummVM, and should thus run on just about any platform.

What to watch?

At Halloween all kinds of crappy horror movies are released, so to save you from that here are some films that you might have missed:

Fermat's Room
Five people are called to a puzzle evening which takes on a diabolical twist. If you enjoyed limited location based movies like Cube and (first) Saw, this is one is highly recommended!

Eden Lake
A story about a couple taking a trip to a lake is not all that original, but Eden Lake has a nice twist to it. Beware of some disturbing scenes.

Hard Candy
Cranking up the disturb-o-meter, this movie is unsettling to say the least. It starts out with a creepy meeting between a man and a young girl, and then gets progressively worse.

Day of the Beast
To lighten up after Hard candy, you should consider this movie. It is about a priest that in order to stop the anti-christ decides to become evil. He teams up with a mentally unstable death-metal fan to do so. Hilarity ensues.

Lost Highway
This is probably my favorite a Lynch movie, if only for an excellent scene involving a telephone at a party. It is not that scary, but keeps a brooding atmosphere throughout. Beware of weird lynchian plot!

Audition
Since we want to go out with a bang I am rounding up the list with this disturbing masterpiece. The movie is quite slow, but this only helps building to moments of true horror that it has. The end scene is unforgettable.

What to read?

Nothing can tingle the imagination as a good book. So here are some tips on how to invoke those nightmares I bet you long for.

Anything Lovecraft
A novel by the master of horror is a must! For people new to the man, I would recommend "The Whisperer in the Darkness", "The Shadow over Innsmouth" or "The Dunwhich horror", all very typical lovecraftian tales. All of his works is available online, but they are of course best enjoyed in front of the fireplace.

The Terror
A retelling of the doomed Franklin expedition with the addition of a stalking monster. Most of the book is based on true events, and the supernatural spice increase scariness in an already horrific story. This is probably one of the best horror books I have read. It takes a while to get into, but when you do the book will not let you go.

Perdido Street Station
I consider the books author, China Mieville, but be a kind of modern day Lovecraft. He has the same dense, but yet enthralling, prose and an incredible ability of making monsters. The books takes place in a fantasy world, but even though it is very weird, it feels in real in a way. Prepare for some really disturbing imagery.

Stiff: The Curious Lives of Human Cadavers
Ever wondered what happens to human bodies after they die? This book contains all you want to know and then some. It opens up with describing rows of heads lying in bowls (to be used in educational purpose) and then gets worse. For anybody interested for anybody interested in the macabre this is a must.

Your tips?

Please leave any nice Halloween tips you might have in the comments!

What to do about all this hair

Take a look at this picture. This is Child No.1's hair when it has been de-plaited. That hair is apparently what mine would look if (a) it was long and (b) I had more of it. In other words, it is my genetic fault. 

Dealing with this hair is a major cost. To keep it under control it has to be plaited -- more than 10 will last a week but here in the US we have been getting it done outside the house with 64 plaits (lasting a couple of months). The next picture shows the result of that.

So let's add up the costs of all of this. On the plaiting side, there are hairdressing costs. The last time this was done, it took 8 hours. Yes, 8 hours. She sat there for 8 hours. And suffice it to say that involved a considerable monetary cost too. 

But of course every plait eventually has to be de-plaited. Rather than pay for that, yesterday, Child No.1's mother and I undertook that task ourselves. It took both of us working at the same time 5 hours to get rid of 64 plaits. That is 10 'person' hours in total. Suffice it to say, never again, is my new motto.

All this caused me to contemplate the meaning of this endeavour. As with all such things, there is a history. When she was younger, this hair was, in fact, naturally curly. Shirley Temple had nothing on Child No.1. And so that hair became a part of her identity. As I have mentioned before, she has no stereotypical 'girl' like preferences; except for one thing, having long hair. We have saved on dresses, to be sure, but over the years that hair became harder and hard to manage.

For many years, Child No.1's hair was done once a week by her mother. It took about one and a half hours to get 10 plaits. But the problem was not the plaiting but instead just brushing the hair. That was taking all of the time. Something had to be done.

When we came to the US, we worked out that there were other children with similar issues and so opted for braiding, as they call it here. Of course, that has turned out really not to be economical in any sense of the word.

So we are now at a cross-roads. There are two camps. First, there are the cutters; those who believe the hair should be cut to about half of its current length and become within some level of manageability.  I am a loyal and vocal member of this camp. Indeed, at one point yesterday I suggested the merits of cutting the current hair completely off, making a wig, shaving her head and using the wig as a substitute. Despite its compelling rationale, such sensible strategies are not receiving serious air time in our deliberations.

The second camp has no name. It is to do 'something else.' The problem is that the members of the camp do not know what that 'something else' is. So I am putting that question out there to the friendly readership of this blog. What should we do about all this hair?