Sign in to follow this  

Finding terrain height

This topic is 4353 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I made a little terrain demo where the terrain is made up of a bunch of right triangles like this: Terrain in wireframe 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

Share this post


Link to post
Share on other sites
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;

Share this post


Link to post
Share on other sites
Here are a couple of ways to do it:

1. Intersect a vertical ray with the triangle in question. Since you already know the point is in the triangle, this reduces to a ray-plane test. Since the ray is axis-aligned (two of its direction components are zero), the test reduces even further. Finally, you only have to solve for the height component (z or y or whatever). This might be the easiest way to do it.

2. Calculate the 2d barycentric coordinates of the point with respect to the projection of the triangle onto the ground plane (just drop the component corresponding to height). The height is then simply a linear combination of the triangle vertex height components weighted by the BC's.

[Edit: Or just use the code posted above :) ]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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);

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

This topic is 4353 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this