Finding where ground is in procedurally generated terrain

Question

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.

Answer 1

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.