Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
add comment

5 Answers

up vote 10 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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:

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

share|improve this answer
1  
Marching cubes is an algorithm for generating a mesh from a scalar field. That means it needs to have data first, then it generates a mesh to fit the data. It's not for generating data or terrain. –  Byte56 Mar 30 '12 at 23:35
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.