How to interpolate a height-map with normals

I want to interpolate a heightmap by using the normal of each nearby point of the heightmap which is calculated before. When having 4 Points before i gonna have 9 points after it. ( See this question to get a image of it how it's working ).

My Approach

I want to interpolate the height of two points by using the normal of them. To do this i need the tangent of both. When having the tangents i want to interpolate this way:

float resultHeight = Interpolate(TangentVector0, TangentVector1, 0.5f);

public float Interpolate(float p0, float p1, float amount)
{
amount = Math.Sin(x* Math.PI - Math.PI/2) / 2 + 0.5;
// Move vectors along tangents
p0 = p0 * (amount - 1f);
p1 = p1 * amount;
return (p0 + p1) / 2f;
}


Problem ( Question )

I'm a little bit stuck with the math behind. How to i get the tangent of the x or z axis when having a 3D normal.

It sounds like you might want bicubic splines. In particular, since you have two endpoints and a tangent vector at each endpoint, Hermite splines would be appropriate.

To expand, if you have the heights of two adjacent points, h0 and h1, and the normal vectors of the heightfield at those points, n0 and n1, here is how you'd do the interpolation. This assumes that we're interpolating along the X axis and h1 is to the right of (at a greater X value than) h0.

public float InterpolateHeight(float h0, float h1, Vector3 n0, Vector3 n1, float amount)
{
// Calculate slopes along X axis (this incorporates rotating 90 degrees
// to get the tangent and then taking the y/x slope of the tangent vector)
float s0 = -n0.x / n0.y;
float s1 = -n1.x / n1.y;

// Interpolate using cubic Hermite spline
float amountSquared = amount * amount;
float amountCubed = amountSquared * amount;
float a = 2.0 * amountCubed - 3.0 * amountSquared + 1.0;
float b = amountCubed - 2.0 * amountSquared + amount;
float c = -2.0 * amountCubed + 3.0 * amountSquared;
float d = amountCubed - amountSquared;
return a * h0 + b * s0 + c * h1 + d * s1;
}

• Thanks for the suggestion, but my main problem is still how to get the tangent from the 3D-normal. – Felix K. Feb 6 '12 at 22:26
• Oh. You just rotate it 90 degrees. I guess you're using a Y-up coordinate system, so take the normal and rotate by -90 around Z to get the X-tangent, and by 90 around X to get the Z-tangent. – Nathan Reed Feb 6 '12 at 23:02
• But then i still have a 3D coordinate, not a single float. :-/ – Felix K. Feb 6 '12 at 23:40
• Right. You'd do the interpolation in 3D, at least that's what makes sense to me. You could project it down to 2D by throwing out one of the coordinates - for the X-tangent, throw out the Z value, and vice versa. If you need a slope instead of a tangent, divide: Y/X for the X-tangent, Y/Z for the Z-tangent. – Nathan Reed Feb 7 '12 at 0:18
• Hmm but it's a heightmap with fixed points, so 3D interpolation does not makes any sense to me. ;-) Anyway i gonna test it tomorrow, if it's right and you updated your answer the credits belong to you. – Felix K. Feb 7 '12 at 0:23

If you have 3D normal, you can compute tangent in X direction as the cross product of normal and vector heading to Z direction, so tangent_x = cross(normal, VectorToZ), and tangent_z = cross(normal, VectorToX). I'm now not sure about the order of vectors in brakets - it depends on right or left handed system (which one you are using).

If you don't want to use normals, you can calculate slope and then tangent vector. You can use derivation of surface. You can do it for example this way:

slope_in_x = f(x + 1, z) - f(x - 1, z)
slope_in_z = f(x, z + 1) - f(x, z - 1)


where x and z are your x and z coordinates and function f returns height in point (x, z). From this, you can calculate tangent as this:

tangent_x = (1, slope_in_x, 0)
tangent_z = (0, slope_in_z, 1)


And then just normalize these vectors.