Tuesday, December 7, 2010

Terrain generation and lighting

The terrain generator is quite simple at the moment. It starts with 2-D Perlin noise to generate a height map. In some places, it adds 3-D noise around the surface, up to a certain vertical distance above and below (right now set to 30 meters).  The amount of extra noise that gets mixed in tapers off at the edges. The result is a world with bits of rolling hills, and bits with weird rock formations. And the occasional floating boulder.

Now something didn't go quite right, the transition between the two terrain types isn't as smooth as I had hoped.  It's easy to fix, but on the other hand, now you get all these cool faults and fissures. Hmm, I think I'll keep this glitch, but make it rare.  Keeps the game world fun to explore.

The lighting is calculated per block. From the center of each block, a bunch of rays are shot out, to see if the sky is visible in that direction.  The total number of rays that don't intersect with another block determine how much light reaches that particular block.

For the ambient occlusion, the rays are distributed in a hemisphere, to model an overcast sky that evenly lights everything. But if you add a couple of extra rays, very close together like a narrow beam, one part of the sky starts acting like a very bright disc.  So in the same algorithm, we can get ambient light, sunlight, and soft shadows. Here's the Stanford dragon again, but this time you can see how his head casts a shadow on the neck:

Ergh, that would have looked much better without the distance fog...

The first results looked promising, but had a lot of artifacts in it. A block on a hillside that has three blocks around it (say, north, east, and down) would already be almost halfway occluded. This leads to a lot of dark spots in an otherwise sunny hillside. To prevent this, there's a blur filter applied to the light map as a second step.  (It doesn't yet work perfectly at the edges of a chunk, so you will still see some dark specks:)

You might be wondering if it doesn't take ages to calculate the lighting. The first version was indeed incredibly slow. But there are some ways to speed this up tremendously. For example, you only need to calculate the light voxels that are close to the surface of the terrain. Right now, with 56 sampling rays, it runs at about 300 chunks (=16x16x16) per second on my 3 Ghz AMD64, but there's still some really dumb code in there that should be optimized. Using the other 3 cores would be an easy speed boost, too.

The speed isn't much of an issue though. It has to be done only once. And the client also generates a preliminary light map using a much faster method. Only when the server is done number-crunching it replaces it with the awesomer version. Remember that new terrain is only generated as the player explores new areas. The new chunks are far away, so the switch is not very noticeable.

Next time, water and trees. Now that the world isn't 64 blocks high anymore, we can skip the little 6-block fruit trees and plant mighty oaks and sequoias, and more importantly, build a proper tree house. There's still a limit in the current code that prevents me from generating a Na'vi home tree, but I hope to have that part redesigned next week.

No comments:

Post a Comment