0
\$\begingroup\$

I recently discovered a paper on Dual Marching Cubes which produces a much reduced poly count to other methods like Dual Contouring and Marching Cubes, however a recurring theme when reading these papers is that they make reference to implicit functions.

I've been wanting to implement a form of this for procedural terrain created using a noise function (like Simplex Noise) but I don't understand how if I were to use a data structure like an Octree, or even a uniform grid, I could then use the algorithm since it wants an Implicit Function.

I think I'm going about this all wrong and not understanding something correctly, can anyone explain how it would be possible, or even if it is at all, to represent procedural terrain with an implicit function?

\$\endgroup\$
1
\$\begingroup\$

Implicit Functions and Surfaces

An implicit function is simply a function that, from any point in N-dimensional space gives you a real number:

forall x in R^N, f(x) -> R

In your case, what you want is a 3D function that returns some real (i.e floating point) number:

f(x, y, z) -> [-infinity, +infinity]

The implicit part comes in when we reinterpret this function as a series of isosurfaces generated by fixing the output of the function to some constant c.

surface_c = all x, y, z such that f(x, y, z) = c

The Signed Distance Function

A common implicit function used to represent real surfaces is the Signed Distance Function (SDF). The SDF represents the scene such that at every point in space, it stores the distance to the nearest surface. For points in the scene that lie outside of the surface, the SDF is positive. For points inside of the surface, the SDF is negative. Exactly on the surface, the SDF is zero. Therefore, the SDF is an implicit function that represents the surface whenever it equals zero.

As an illustrative example, consider the SDF of a sphere with radius r and center c_x, c_y, c_z. At all points in space, the distance to the center of the sphere is given by:

f_center(x, y, z) = sqrt((x - c_x)^2 + (y - c_y)^2 + (z - c_z)^2);

The signed distance to the surface of the sphere is therefore:

f_sphere(x, y, z) = f_center(x, y, z) - r;

We can easily find the isosurface describing the sphere by simply finding all points in 3D space which are equal to zero:

sphere_surface = all x, y, z such that f_sphere(x, y, z) = 0

This surface can be extracted using marching cubes.

Perlin Noise as a Signed Distance Function

Perlin/Simplex noise is a function that has the same signature as the signed distance function. At every point in space, it returns a real number. The number is technically random, but the Perlin/Simplex noise function is also locally smooth. These are very nice properties for an implicit surface function!

So all we have to do is reinterpret the Perlin noise as a signed distance function! Then, the surfaces of the scene will be:

surface_perlin = all x, y, z such that Perlin(x, y, z) = 0

Of course, you will want to adjust the parameters of the perlin noise to give you realistic terrains. For one thing, you can ignore the z value, and instead create a height map from the perlin noise. In that case, the SDF isosurface can still be formed as:

surface_heightmap = all x, y, z such that (z - Perlin(x, y, 0) = 0)

You can read about more of this at GPU gems, where an implementation is shown.

What Data Structure to Use?

I strongly recommend you avoid octrees for representing implicit surfaces. They're great for memory usage, but abysmal at iterating and querying. Since you're using Marching Cubes to extract an isosurface, your time usage will be dominated by iteration. For that reason, I would recommend a fixed 3D array. If you want something that can extend over very large distances without running out of memory, I would recommend using spatially hashed 3D chunks of volumetric data like Minecraft.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer, I had almost forgotten I'd posted this. I do feel that I was jumping the gun a bit by posting it. Question: Does ignoring the z-value to create the height map eliminate the possibility of the highly sought after caves and overhangs? \$\endgroup\$ – Mark A. Ropper Dec 26 '14 at 17:42
  • \$\begingroup\$ @MarkA.Ropper, yes, since essentially you are creating a terrain that will only have one vertical value per 2D coordinate. To add overhangs or caves you must implement 3D noise functions with all values. Subtract from the surface for caves or add to empty space for terrain with overhangs. It is more expensive to iterate over all 3 dimensions, so you need to add some fall-off values to reduce the area to compute. See here for an example. \$\endgroup\$ – ChrisC Dec 26 '14 at 18:16
0
\$\begingroup\$

You are able to use the dual marching cubes algorithm because it just operates on an array you provided.

So your code generates an area in the form of an array and the marching cubes algorithm then scans over the scene starting at some origin point you assign and finds where all the edges of your volumetric data array would be located and places bits of edging/skin.

You could use the Octree algorithm to break down the volumetric objects your putting into your world space into mini spaces and run the marching cubes algorithm only over the small space that actually contain parts of the volumetric objects to attempt to save on power.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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