4D perlin noise terrain

Recommended Posts

Hawkblood    1018
I use 3D noise to generate terrain textures for my planets, but I need to generate meshes for the terrain when the ship lands. I’ve been looking at 4D perlin noise as a way to do this, but I can’t seem to find any good articles that cover that….. The goal is to have a series of meshes that “mate up” and they should be able to have cliff overhangs and caves. This might be a tall order, but I would like to try it. I had a previous post asking about perlin noise and someone posted links to articles covering 3D and (I think) 4D, but I can’t seem to find it in the forum.

Share on other sites
RnaodmBiT    1096

Since you are looking at procedural generation of meshes I might point you towards the GPU Gems article on marching cubes and this one also on marching cubes with an actual CPU implementation. Using these two sites I implemented this technique and you really can generate anything you can represent in maths (and noise look-ups). You can using a little geometry math use it to generate spheres and then perturb the surface using any combination of filters to achieve the desired terrain shape. The best part is that due to the way the vector field is converted into a mesh you can even form cave systems and overhangs with a little tweaking of some conditions and so on. Also since each terrain cell will be generated using the same density function you can essentially generate thousands of independent meshes and they will fit together perfectly with no seams (until you try implement some form of LOD that is) so it could be exactly what you are looking for, if maybe a little overly complicated to setup.

Share on other sites
Hawkblood    1018

The generation will need to be FAST. I want to use it for essentially an infinite world. I already read the GPU Gems article. I'm going to read the "this one" now.

EDIT: I looked at the second one. I think I understand the concept when it comes to a volume object. I don't understand how I could create caves. I know it can be done because I have seen videos using that method (don't know if GPU or CPU).

Edited by Hawkblood

Share on other sites
RnaodmBiT    1096

I started with a CPU implementation which generates 32 size cubes in ~60ms which isn't very good but running on a DX11 compute shader it can be done is < 5ms (recycling memory and computation buffers) so you could perhaps generate one of these per frame as you need them, this would drop your frame rate a fair amount but it would still be playable.

As to generating caves and so on, it might pay to understand where the algorithm actually builds a mesh. Using the density function as described in the links, where it is positive is solid and negative is space (or vice versa) so where the function crosses over 0 it will build a triangle, essentially building a wall between the positives and the negatives so that nothing can 'leak' through. What this means is that if you define a flat ground so that if everything below y=4 is solid for example, then you can check is the world space y is less than 4 and then subtract some value from a 3D noise map. What this would do is whenever you are under the defined ground height, it would try to pull the density value back to empty in interesting ways (like caves) as described in the 3D noise. This is just a very basic example but you can generate very extensive and completely random caves that look very interesting. You could allow some of these caves to touch the surface by using two separate height values (perhaps from a 2D noise map) for the ground and cave height (where you apply the cave process if you are below the cave height) so that if the cave height is above the ground height, you can get the entrances on the surface and you could walk right in.

The detail you can create really comes down to your imaginative use of noise maps to generate an interesting density function.

Share on other sites
Hawkblood    1018

I think I need pictures to understand......

The way I understand it (which is probably wrong) is that I would have to use a noise generator that would create values inside an entire XYZ volume. If that's the case, it could be a HUGE amount of data to pour over. I hope I'm wrong.....

Share on other sites
Hawkblood    1018

I think it would be better to start with a simple cliff:

[attachment=17154:Untitled.png]

The top line segments are just an example of "random" noise on the Y axis with a regular distance per segment on the X axis. This shows an opportunity at the right side to have a cliff. Because each value on the X axis is evenly spaced, the Y values can't have any overlap or even have 2 at the same x value.

The bottom shows how a "cliff" could look.......

I am using 3D noise to generate a texture for a planet. The noise is just a height map. The 3D noise I use will only give a 2D representation of the terrain. How do I even generate an actual 3D volume to apply the marching cubes?

Share on other sites
RnaodmBiT    1096

Ok, it sounds like you are really using a 2D noise function (a function that takes x and y and returns a value). A 3D noise function takes x, y, and z and returns a value.

In terms of marching cubes, you don't need to generate a HUGE noise map, you can actually use a 16x16x16 grid of random values in the range of [ -1, 1 ]. I'll explain how this can be useful later. It can be generated by filling a 4096 (16 * 16 * 16) size array with random floats in the above range and then sampled as follows:

float value = noiseMap[x * 256 + y * 16 + z];


When using marching cubes, the terrain is represented by a single 3D function, usually called the density function, one that I have experimented with is:

// Returns a 'density' value for the world space (ws) coord, < 0 means empty, > 0 means solid
float Density(float3 ws)
{
float density = 26 - ws.y + Sample3DOctaves(ws.x, 0, ws.z, 1, 4) * 6;

if (density > 0)
{
// if the current coordinate is 'solid' try lessen the density so a cave might be formed
density -= density * Sample3DOctaves(ws.x, ws.y, ws.z, 2, 4) * 1.8f;
}

return density;
}


This is HLSL code but can be written in normal C++. The Sample3DOctaves(x, y, z, lowest, highest) function uses the 16x16x16 cube of noise and samples it on the defined octaves to get a random noise value. A good site to look at how Perlin noise works (the sampling method I use) is here. What this means is that for any ws coordinate provided we can get a density out, in other words, the function is defined everywhere. Using this as an input to marching cubes we can use it to define the surface of the terrain including caves.

It is very hard to visualize how it works, I will try and make some examples of density functions and the mesh that is generated to help illustrate how it works (unfortunately I have a lecture so you'll have to wait a few hours).

Share on other sites
Hawkblood    1018

Ok, it sounds like you are really using a 2D noise function (a function that takes x and y and returns a value). A 3D noise function takes x, y, and z and returns a value.

No. I'm actually using 3D. I have to use it to make the planet's texture look natural at the poles......

I didn't realize that the 3D noise could be used to do this. After looking again at my planet's height map generation code, I realized the method I was using was only using a single arbitrary value so it would take samples along a sphere instead of a flat surface (or even a volume).

So, if I had my areas to be 100x100, would I need to have 100 as the height? Would it matter? Remember, I am wanting to make this a seamless and endless map of a planet (with caves, overhangs, and cliffs).

Share on other sites
JTippetts    12949
You might take a look at these journal posts I wrote some time ago:

http://www.gamedev.net/blog/33/entry-2227887-more-on-minecraft-type-world-gen/
http://www.gamedev.net/blog/33/entry-2249106-more-procedural-voxel-world-generation/

They discuss building a Minecraft-like world, but the idea can be extended to a spherical planet generator as well. Instead of using a linear gradient function, you would use a spherical gradient function. The rest is pretty much the same. Here's a really quick one-off with features exaggerated to show the effect:

To make that I used a 3D sphere function coupled with 3 fractal functions used to perturb the X, Y and Z components of the sphere's center, then did a quick raymarch through the generated volume to light the "surface". To build geometry from such a beast, you would instead just do a marching cubes on the volume containing the sphere function, to a small enough granularity that detail is captured. Using a noise function like this, you can sample sub-regions of the whole domain in order to just construct chunks of the planet rather than the entire planet all at once. In a real application, you would get more complicated, such as varying the fractals used to displace the sphere to generate different terrain, or using the spherical gradient to attenuate a ridged multi module then multiplying it against the planet, similar to how I did caves in the above journal posts. The trick in doing something like this is to make it fast, however, since elaborate noise functions can get really slow sometimes.

Share on other sites
Hawkblood    1018

I think I understand the method: sample each "element" of an arbitrary volume using 3D noise. Any element value above/below (depending on how I distinguish) 0 is counted as "solid" and all others are "open". Then look at each element and the ones adjacent to it to determine if that element is "crossing" the 0 mark..... How am I doing so far? The ones that cross 0 (border a surface) are then compared using a lookup table to determine which marching cube configuration is needed. Then match up the vertexes with any adjacent ones. Do this for each element that is crossing the surface......

Did I get that right?

Share on other sites
RnaodmBiT    1096

Yep that's about right. It might pay to remember that when you generate the mesh, you define an arbitrary box (say, 32x32x32) and then for each voxel in this box you do the checking and so on to get your triangle out. This is why the method is very good for implementation on the GPU since you can run all of the individual voxels separately and run them all in parallel to lower the run time.

Share on other sites
Hawkblood    1018

and then for each voxel in this box you do the checking and so on

Ok. Does voxel==marching cube?

Do most GPUs have the capability? Which one is easier to implement?

I'm still new to perlin noise. So I mentioned that I am using 3D PN to generate the terrain image for the planets. I am not using PN to create an actual mesh for the planet. The image for each planet is 720x360. As I get closer to the planet, the program will guess where the ship is going to land and start generating the 3D terrain meshes. I need to use the same terrain as the image to do this because I don't want the player to be heading toward a mountain and, when the 3D terrain is generated, now be heading toward an ocean. How far down (zoomed in) can I do the PN calculation? Will it translate or will I need to come up with a method that takes the original terrain into account?

Share on other sites
Hawkblood    1018

Ok. I'm looking at the code I got from "Polygonising a scalar field" article you recommended. I can't figure out how to utilize it. I know I need to generate a random volume with PN, but where would I put that data in the CIsoSurface class? Can you give me a simple example of how to use it?

Share on other sites
RnaodmBiT    1096

From that website, it assumes a GRIDCELL struct is provided defined as:

typedef struct {
XYZ p[8];
double val[8];
} GRIDCELL;


The polygonise function take that as an input. The p array is just an array of vectors defining the corners of the voxel, and the val array is the 'density' and each of those corners. It assumes that these values are already set. So what would be happening in the given example is you would prepare this struct with positions and the output of the density function at that position and then let the polygonise function go on that. Something like the following c++ code:

// You could define this anywhere really, probably better using pre-allocated memory in your case
TRIANGLE *triList = new TRIANGLE[maxTriCount];
int trisMade = 0; // keep track of where we are going to write to in the array

for (int x = 0; x < grid_width; ++x)
for (int y = 0; y < grid_height; ++y)
for (int z = 0; z < grid_height; ++z)
{
GRIDCELL cell;

// setup all the positions for the cell
cell.p[0] = { x, y, z };
cell.p[1] = { x + 1, y, z };
cell.p[2] = { x + 1, y, z + 1 };
cell.p[3] = { x, y, z + 1 };

cell.p[4] = { x, y + 1, z };
cell.p[5] = { x + 1, y + 1, z };
cell.p[6] = { x + 1, y + 1, z + 1 };
cell.p[7] = { x, y + 1, z + 1 };

// fill the density values for each corner
for (int i = 0; i < 8; ++i)
cell.val[i] = DensityFunction(cell.p[i][0] /* x */, cell.p[i][1] /* y */, cell.p[i][2] /* z */);

// the polygonise function adds triangles to the list provided at the trisMade index and returns how many triangles written to the list
// this way we can keep calling this and it will always write to the end of the list.
int count = Polygonise(cell, 0.0 /* isolevel */, &triList[trisMade]);
}


(Note: this code is untested, I just made it up on the spot)

I hope this clears it up a little bit, I suggest trying to look at where the example on the web site gets its inputs and how it uses them to generate each individual triangle.

Share on other sites
Hawkblood    1018

I looked at the code on the website and compared it to the files. GRIDCELL doesn't appear in the code......

Here is what I "think" it should be:

CIsoSurface<float> testTerrain;


defined somewhere.

Then:

testTerrain.GenerateSurface(.....);


to generate the surface.... Don't know where I would grab the vertex buffer to render it though.......

The GenerateSurface is defined as:

void GenerateSurface(const T* ptScalarField, T tIsoLevel, unsigned int nCellsX, unsigned int nCellsY,  unsigned int nCellsZ, float fCellLengthX, float fCellLengthY, float fCellLengthZ);


I assume ptScalarField is a pointer to a linearized version of the random valued volume. tIsoLevel is the "density" value each voxel will be tested against. And the others seem straight forward.

Edited by Hawkblood

Share on other sites
RnaodmBiT    1096

From looking at the code (I previously hadn't looked at it myself) you are right that the ptScalarField is a list of the density values at each corner in the grid to be generated. This array would be generated by you

If you were going to use this as a base implementation to suit to your needs, then you would need to add a method to extract the list of triangles that were generated and stored in the m_trivecTriangles vector of triangles.

Share on other sites
Hawkblood    1018

Yea, that's what I thought..... Well, I can't ask the author to do EVERYTHING for me.

It shouldn't be hard to do that. Looking at the code leads me to believe the author was trying to be as generic as possible. I think I could adapt the classes to use DX vectors. Or would I even need to.....

Share on other sites
RnaodmBiT    1096

I think I could adapt the classes to use DX vectors. Or would I even need to.....

It could potentially save some hassle else where, and I don't imagine it would be terribly difficult, just out of curiosity which math library are you using?

Share on other sites
Hawkblood    1018

What do you mean? I am using the one that is standard with the compiler and all the maths that comes with DX9.

Share on other sites
Facehat    696

You might want to look into Simplex noise (like perlin noise, but N-dimensional and potentially faster).