I made a little terrain demo where the terrain is made up of a bunch of right triangles like this: My question is how to find the height of any given point on the terrain. I already know how to find which triangle the point of contact is touching, I just need to know how to find the actual height. I know there is a way to start at the corner of the triangle and interpolate between that and the other two points and somehow find the height from that, I am just not clear as to exactly how to do it. An example of a triangle would be at points (0,0,0), (0,4,2), and (2,6,0). From there it's just a matter of linear interpolation between the point at (0,0,0) and the other two, then do something with those two values to find the height. Does anyone know how to properly do this? Thanks, -Chris

This function assumes your terrain top left corner is 0,0
and the terrain space is in the positive x and y.

Replace Y with Z depending on your coordinate system.

X needs to be world position divided by cell width
Y needs to be world position divided by cell height

function GetInterpolatedHeight(X, Y: Single): Single;
var
ix, iy, ixn, iyn : Integer;
h1, h2, h3 : Single;
begin
ix := Trunc(x); x := Frac(x);
iy := Trunc(y); y := Frac(y);
ixn :=ix + 1;
if ixn >= STEP_SIZE then ixn := ix;
iyn := iy + 1;
if iyn >= STEP_SIZE then iyn := iy;
if x > y then begin
// top-right triangle
h1 := GetHeight(ixn, iy);
h2 := GetHeight(ix, iy);
h3 := GetHeight(ixn, iyn);
Result := h1 + (h2 - h1) * (1 - x) + (h3 - h1) * y;
end else begin
// bottom-left triangle
h1 := GetHeight(ix, iyn);
h2 := GetHeight(ixn, iyn);
h3 := GetHeight(ix, iy);
Result := h1 + (h2 - h1) * (x) + (h3 - h1) * (1 - y);
end;
end;

I'm not exactly sure how that function works. I realize I should probably be able to figure out how to convert that for C++, but I guess I do not quite understand what is happening there. Would there be any way to just give the functions the three heights of the points and the X,Z of the point in question and return the Y?

-Chris

For example...

if you have x, y, z and y is your up axis...


Object.Y := GetInterpolatedHeight(Object.X/CELL_SIZE, Object.Z/CELL_SIZE);

or if Z is your up axis...

Object.Z := GetInterpolatedHeight(Object.X/CELL_SIZE, Object.Y/CELL_SIZE);

The problem I am having is actually with the function itself, it relies on other variables and functions that I do not have. I guess what I am asking is if there would be a way to alter it so that you just give it the height of the three points, and have it return the height of the point in question. Something like this:

float GetHeight( float Point1.Height, float Point2.Height, float Point3.Height, D3DXVECTOR2 PointPosition );

Where Point1 would be the corner point at (0,0,0), Point2 is at (0,0,2), and Point3 is at (2,0,0). The cell size and the X,Z of all the points except the one in question shouldn't even be a factor (assuming the PointPosition is a number between 0 - 1 for the X and for the Z).

-Chris

I *believe*, though I'm not certain, that (given coordinates a, b, c, with b at corner, checking for height of coordinate d) the height will just be

(d.x / (a.x - b.x)) * (a.y - b.y) + (d.z / (c.z - b.z)) * (c.y - b.y) + b.y

But test that out. It works for a trivial case - if a's height is 10, b's height is 8, and c's height is 10, for example. I think it'll work for less stupid examples, but I haven't actually done the paperwork. You'll need to do some sign fixing; (d.x / (a.x - b.x)) is intended to represent the distance of d from b along the x axis in terms of the magnitude of the a-b line, and should always be positive.

Within the fuction... GetHeight() returns the height of the actual heightmap at that point.

function GetHeight(X, Y: Integer): Single;
begin
if X > MAP_SIZE-1 then X := MAP_SIZE-1;
if X < 0 then X := 0;
if Y > MAP_SIZE-1 then Y := MAP_SIZE-1;
if Y < 0 then Y := 0;

Result := HeightMap[x + (y * MAP_SIZE)];
end;

X/CELL_SIZE converts world coordinates to heightmap coordinates.

The GetHeight() function gets the height from the heightmap not the mesh itself.
This is because if you are using a CLOD or ROAM algorithm instead of brute-force
the mesh won't match up to the heightmap because the CELL_SIZE will vary and lose
accuracy.

This function is compatible with both types of terrain...
brute-force or CLOD/ROAM.

This is much faster than first figuring out which triangle you're touching,
then getting the point values as you seem to be doing.