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.