Daniel's Musings

After trying a few approaches, I came up with a method for rendering infinite terrain which I’m pretty satisfied with.

In a nutshell,

• I use the floating point variation of Perlin noise for the heightmap. Originally I had tried using a variation on the diamond-square algorithm which mapped any pair of integers to a height by viewing the bits of each integer as branches in a quadtree. The terrain looked great, but the speed just wasn’t there, unless I used a lot of smoothing to mask low underlying resolution.
• I precompute a large binary triangle tree at the start. All of the triangle coordinates are relative to the camera position, so I have enough information to do my LOD tests and remove triangles which lie beyond the far clipping plane upon initialization. Not having to deal with LOD at runtime is very helpful.
• I ended up using no caching at all. There are several reasons for this –
  • I wanted to be able to move the camera very rapidly, or teleport to a completely new location, with no performance degradation. If the heightmap only performed well after warming the cache, I would lose that flexibility.
  • A nice feature of floating point Perlin noise is that its precision is infinite (well, bounded only by the numerical precision of the floats). If you bring the camera very close to a feature of the terrain, you can see very precise curves. This is difficult
  • Besides, the noise function is fast enough that caching is not that  helpful. I tried adding a quick LRU cache implementation and was not that pleased by the speedup.

The major drawbacks are

• With no caching, it is difficult to apply even crude erosion algorithms without slowing down the program considerably.
• There is no opportunity to precompute the normals of the heightmap. They could be cached, but not with the infinite precision that runtime computation offers. Finding the normals at runtime can take a fair bit of CPU time, depending on the desired accuracy. I should probably use GLSL for this (but I want to rely on GPU performance as little as possible).

In summary, this approach is quite a bit slower than traditional texture-based heightmap rendering, but it is extremely flexible, and the performance is acceptable for most purposes.

I wrote a terrain generator in Java the other day, inspired by several discussions. Here are some screenshots:

The algorithm is roughly as follows:

• We start with a map comprised of large blocks. The default block size is 64 by 64. The state of each block (land or water) is entirely pseudorandom.
• Repeat until all blocks are 1 by 1 in size:
  • Divide each block into four smaller blocks.
  • For each derived block, decide on a probability for that block becoming a land block. This probability is based on the state of the block it was derived from, and the land mass of surrounding blocks. The probability computation can be configured in different ways with different weights.
  • If a pseudorandom number between 0 and 1 is less than that probability, the derived block becomes a land block. Otherwise, it becomes a water block.
• Darken land blocks which are contiguous with water blocks.

Here is a runnable JAR to play around with. You can also view the source code, although it may be difficult to understand the algorithm from the code alone.