# Finding where ground is in procedurally generated terrain

Terrain in my voxel game is generated by combining 2d and 3d perlin noise.

if (y < (noise2d(x, z) + noise3d(x, y, z)) * amplitude)
{
// place block
}


To generate structures like trees, I need to find where the ground is. The simplest way is to just go through every block from min height to max height and check if there is a block with no block above it. This works, but it is slow. Is there a faster way to do this?

I tried using bisection, but it sometimes returns positions one block below the ground.
Simplified code for bisection:

float min = minHeight;
float max = maxHeight;
float mid = (min + max) / 2.0f;
while (abs(mid - combinedNoise(mid)) > 0.5f)
{
if (sign(mid - combinedNoise(min)) == sign(mid - combinedNoise(mid)))
{
min = mid;
}
else
{
max = mid;
}

mid = (min + max) / 2.0f;
}


I think removing the absolute value might fix the blocks below the ground, but I don't think I can remove it because it can create an infinite loop because of how bisection works.

• Note that if you include 3D Perlin noise, you may have multiple "grounds" per (x,z) position, since you may have overhangs. Otherwise I would suggest that you used the bisection method, which finds the transition between negative and positive function values, i.e., where the ground is, in logarithmic time (it does this even if you have overhangs; you're just not sure which of the multiple grounds you will find). Jan 21, 2022 at 13:35
• Comments are not for extended discussion; this conversation has been moved to chat. Jan 21, 2022 at 13:58

Let's define your block placement rule as a function of position:

bool IsSolid(x, y, z) {
return y < (noise2d(x, z) + noise3d(x, y, z)) * amplitude;
}


Looking at this, we can make our initial search bounds tighter.

Let baseHeight = noise2d(x, y) then expand that based on your range of values from your noise3d function. (Typically 0-1 or -1 to 1, but you may have a custom noise here with other behaviour)

int minHeight = floorToInt((baseHeight + minNoise3dValue) * amplitude);
int maxHeight = ceilToInt((baseHeight + maxNoise3DValue) * amplitude);


(If you have constraints on the maximum slope of the noise3d function, you might be able to make this even tighter)

By construction, we know IsSolid(x, minHeight, z) == true and IsSolid(x, maxHeight, z) == false, and we'll maintain this as an invariant as we go.

while (maxHeight > minHeight + 1) {
int midHeight = (maxHeight + minHeight)/2; // Compiler will make this >> 1

if (IsSolid(x, midHeight, z)) {
minHeight = midHeight;
} else {
maxHeight = midHeight;
}
}


At the end of this process, minHeight points to a solid block and maxHeight points to an empty block directly above it, so this is a point on the surface of your terrain. Note that because you're using 3D noise, you can get overhangs or voids, so this procedure does not guarantee that this is the top-most surface in this column, only that it is some place where there is a transition from solid immediately below to empty immediately above.