How is a 3d perlin noise function used to generate terrain?

Question

I can wrap my head around using a 2d perlin noise function to generate the height value but I don't understand why a 3d perlin noise function would be used. In Notch's blog, http://notch.tumblr.com/post/3746989361/terrain-generation-part-1, he mentioned using a 3d perlin noise function for the terrain generation on Minecraft. Does anyone know how that would be done and why it would be useful? If you are passing x,y, and z values doesn't that imply you already have the height?

Answer 1

2D perlin noise is good for height maps, but in this case it seems that he is not using a height map. Instead he has a 3D grid, where any cell can be empty. This allows caves and such formations, where the ground height is not a single value for given 2D location.

Answer 2

Instead of sampling the “ground height”, I treated the noise value as the “density”, where anything lower than 0 would be air, and anything higher than or equal to 0 would be ground.

Simply put, for every place where a block can be, a noise function is evaluated, and if it is >0, a block is placed. Notch's noise function is skewed by adding height from water level to its value, that's why lower areas are mostly solid (height is large negative, so height+noise is negative too) and higher areas are mostly empty (height is large positive, so height+noise is positive too).

There's probably some additional alchemy to decide what kind of block gets generated, and to carve caves. But I guess it's not directly related to this noise function.

Also note that this method works for Notch because Minecraft has a voxel-based terrain. If you tried to pull that off in a polygon-based world, simply sampling noise function would not be enough. You' have to use some algorithm to turn samples into a surface, and create polygons that approximate this surface. One such algorithm is marching cubes.

Answer 3

3D noise becomes mandatory if the terrain needs cave networks and overhangs.

To extract an isosurface from density information, the 2 most popular techniques are Marching Cubes (MC), and the newer Dual Contouring (DC). The data structure needed is quite different depending on the chosen method.

As previously mentioned, Geiss's GPU Gems 3 article is a very instructive starting point for understanding and implementing MC terrains on the GPU (Note that his MC approach run entirely on the GPU and requires at least SM4 - GS- capable one).

Because density data on MC voxels can only stay on voxel's edges, classic MC may contour the volume without preserving sharp edges features. DC does not suffers this drawback since the density info is expressed as a 3D point (QEF minimizer) laying anywhere inside the voxel plus the sign at each corner.

On the other hand, MC does not suffer from self-intersecting faces because all generated triangles are enclosed in their corresponding voxels, whereas DC needs additional computations to prevent intersections between generated faces. DC authors addressed this issue in an improved version of their algorithm.

http://www.cs.wustl.edu/~taoju/research/interfree_paper_final.pdf

http://www.cs.berkeley.edu/~jrs/meshpapers/SchaeferWarren2.pdf

This fellow also propose a likely cleaner approach based on convex / concave analysis for avoiding self-intersections. He uses as well better quad splitting rules to help preserve edge's orientation:

http://www2.mae.cuhk.edu.hk/~cwang/pubs/TRIntersectionFreeDC.pdf

Classic MC is also not out-of-box "crack-free" and may require crack patching if ran on unrestricted octrees. DC does not suffer from this last issue.

Here is a pretty nice and complete survey of most mesh extraction techniques : http://www.cs.berkeley.edu/~jrs/mesh/

An octree / voxel approach is intrinsically "CSG-friendly", which make it easier to plan a neat fully "destructible" game level strategy, but if one needs to implement all this in a game, the octree depth will also need to be frustum-dependent.

If the whole stuff fits in memory or is correctly streamed, the data can also be used for rendering AO and computing physics / collisions.

Answer 4

My guess, in that particular example, is that he used the z value to determine what type of material: bedrock, stone, dirt, or air.

Answer 5

Minecraft uses the marching cubes algorithm to generate 3D terrain. I don't have a refernce for this, I'm sorry. I'm not sure exactly what Notch was talking about when he mentioned the Perlin Noise function - perhaps a seed for the marching cubes algorithm. More info here:

• http://en.wikipedia.org/wiki/Marching_cubes

And a great GPU Gems article if you're interested in marching cubes:

• https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch01.html

Answer 6

for (int x = 0; x < Width) 
{
  for (int y = 0; y < Depth) 
  {
    for (int z = 0; z < Height) 
    {
      if(z < Noise2D(x, y) * Height) 
      {
        Array[x][y][z] = Noise3D(x, y, z)
      } else {
        Array[x][y][z] = 0
      }
    } 
  } 
}