# Heightmap Calculations

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

## Recommended Posts

I created an heightmap in DirectX, now the problem is that when moving a character around in that heightmap, the height of the character should adjust to the height of the heightmap. My heightmap is created by squares made up of two triangles, I already managed to find the three points of the triangle the character is on currently. Also I know what the relative position inside the triangle is. Now how can I calculate the height in that triangle? Since the triangle always is flat it should make things a little bit easier... I hope I made myself clear generally I just want to calculate the Height in a Heigtmap between the points that already where given....

##### Share on other sites
EDIT: Attention please: The formula given here does not consider the triangular conditions
β + γ <= 1 for ACD
β + γ >= 1 for ABD
ABCD needs to be a flat quad if these conditions are not incorporated. See my reply with the code below for a solution that does considering the conditions.

Quote:
 Original post by QuinnieMy heightmap is created by squares made up of two triangles, I already managed to find the three points of the triangle the character is on currently. Also I know what the relative position inside the triangle is.

How have you defined "relative position" w.r.t. 3 reference points?

Assuming the following layout
  vA---B|\* |<| \ ||  \|C---D

and already knowing that the position * is above e.g. {A,B,D}, and you know that * is at a fraction of a between A (where β==1) and B (where β==0), and also at a fraction of γ between B (where γ==0) and D (where γ==1), then I think that the desired height is
z(β,γ) := Az * β * ( 1 - γ ) + Bz * ( 1- β ) * ( 1 - γ ) + Dz * γ
from bi-linear interpolation.

Tests:
z(0,0) = Bz
z(1,0) = Az
z(0,1) = Dz
z(1,1) = Dz

[Edited by - haegarr on March 31, 2006 11:31:30 AM]

##### Share on other sites
Is simply changing the player's height(z position, not how tall he is) as he moves along x and y really the proper approach?
consider the extreme case of a terrain triangle that is almost vertical, as he walks across it he would get a huge change in distance travelled (vertically)
somehow he was magically able to run at superhuman speeds...
my point being that this method actually makes the player faster when moving uphill, wheras in reality he should probably slow down
so perhaps there is a better model/method for doing this kind of terrain walking...

##### Share on other sites
Quote:
 Original post by Anonymous PosterIs simply changing the player's height(z position, not how tall he is) as he moves along x and y really the proper approach?consider the extreme case of a terrain triangle that is almost vertical, as he walks across it he would get a huge change in distance travelled (vertically)somehow he was magically able to run at superhuman speeds...my point being that this method actually makes the player faster when moving uphill, wheras in reality he should probably slow downso perhaps there is a better model/method for doing this kind of terrain walking...

The problem is finding the appropriate z co-ordinate for a given pair of x,y co-ordinates. This has nothing to do w/ the question of how x,y is computed formerly. You could simply add a velocity that is tangential to the ground at the current x,y, and you automagically always walk the same speed (as the quotient of walked distance and elapsed time) everywhere. Even better, scale the velocity vector w.r.t. the tangential vector, and you run down hills while slowly climbing them up. So I agree w/ the AP that the walked distance should depend on the slope, but as soon as a x,y pair is given I think bi-linear interpolation is a way of finding the corresponding z.

##### Share on other sites
Ah
now that does sound like a Better model

how do find the tangential velocity though? assuming that we treat our heightmap cells as bilinear interpolation surfaces, instead of pairs of flat triangle polygons?

##### Share on other sites
Are you (AP) Quinnie or have you hijacked the thread? However, ...

Quote:
 Original post by Anonymous Posterhow do find the tangential velocity though?

Using the principal direction of movement, projecting it onto the face on which * currently resides, normalizing the result, and scaling it with the (scalar) speed value (to yield the "desired" velocity vector). You may need to clip it against the face's border to know when it happens that the velocity is changing due to ground changes.

Quote:
 Original post by Anonymous Posterassuming that we treat our heightmap cells as bilinear interpolation surfaces, instead of pairs of flat triangle polygons?

That doesn't change the principle. Of course, the interpolation to yield in z(β,γ) has now to consider all 4 corners like in
z(β,γ) := Az * β * ( 1 - γ ) + Bz * ( 1 - β ) * ( 1 - γ ) + Cz * β * γ + Dz * ( 1 - β ) * γ

##### Share on other sites
actually, I'm not building a heightmap myself at the moment, I'm mostly just curious. who knows, maybe Quinnie will end up finding the info useful

##### Share on other sites
Quote:
 Original post by Anonymous Posterwho knows, maybe Quinnie will end up finding the info useful

I hope so :)

You want to draw a bi-linear interpolated face w/ 4 corners. AFAIK there is no standard hardware that does the job. Hence I assume you tesselate the face for rendering.

A bi-linear interpolated 4 corner face need not be flat in diagonal directions (say as soon as leaving the interpolation lines). Hence in principle computing the tangential velocity vector has to be done more often on such a face as on tris or quads. However, I assume that approximating the tangential vector is good enough for the given use case of walking on the terrain.

##### Share on other sites
haegarr, thanks a lot for your help and I will definetly study this in the next couple of hours. And yes I already calcualted the relative distances...

##### Share on other sites
EDIT: Attention please: The formulas given here does not consider the triangular conditions
β + γ <= 1 for ACD
β + γ >= 1 for ABD
ABCD needs to be a flat quad if these conditions are not incorporated. See my reply with the code below for a solution that does considering the conditions.

I had to made assumptions of how the tris are organized. I've used the following scheme
  vA---B|\* |<| \ ||  \|C---D

and picked examplarily tri { A,B,C } as the one over which the character is located.

It was stated in the OP that relative co-ordinates inside that tri are already known, and I've assumed a horizontal co-ordinate (denoted by the v in the scheme) I've named β and a vertical one (denoted by the < in the scheme) and named it γ.

Relative co-ordinates range from 0 to 1. It is a convention of how the axes are directed. I've chosen
     β1 <--- 0       | γ       |       v       1

w.r.t. the tris scheme above, so that
Quote:
 * is at a fraction of β between A (where β==1) and B (where β==0), and also at a fraction of γ between B (where γ==0) and D (where γ==1)

From this chosen definition one uses either the coefficient itself or else 1 minus the coefficient to weight the belonging points. Notice that at every valid value for coefficient the condition
coefficient + ( 1 minus the coefficient ) = 1
holds, what is the essence of linear interpolation.

So, linerly interpolating between A and B with the given definitions yield in
AB(β) := A * β + B * ( 1 - β )

This denotes a point on the straight line between A and B with the extremes
AB(β=0) = A * 0 + B * ( 1 - 0 ) = B
AB(β=1) = A * 1 + B * ( 1 - 1 ) = A
what corresponds exactly with the chosen definition above.

(Notice please that here a full point interpolation is shown, not only a z component interpolation, but that makes no difference in the principle.)

Now, since we have a 2D problem, the 1D linear interpolation by itself isn't sufficient. We could do the same with points C and D
CD(β) := C * β + D * ( 1 - β )

and then doing the same once more BUT in the other dimension AND with the results of the interpolations of the first dimension:
ABCD(β,γ) := AB(β) * ( 1 - γ ) + CD(β) * γ

Setting in AB and CD as are given above, we yield
ABCD(β,γ) := A * β * ( 1 - γ ) + B * ( 1 - β ) * ( 1 - γ ) + C * β * γ + D * ( 1- β ) * γ

Voila, that is the formula I gave as the full bi-linear interpolation in the reply to the hijacking AP.

BUT: The OP doesn't deal with a quad { A,B,C,D } but with 2 tris, from what we exemplarily have chosen { A,B,D }. Hence there must be some formula without C.

For this purpose I've chosen the approach
AB(β) := A * β + B * ( 1 - β )
ABD(β,γ) := AB(β) * ( 1 - γ ) + D * γ
= A * β * ( 1 - γ ) + B * ( 1 - β ) * ( 1 - γ ) + D * γ

(EDIT)
Checking the total weight:
β * ( 1 - γ ) + ( 1 - β ) * ( 1 - γ ) + γ = β - β γ + 1 - β - γ + β γ + γ = 1
q.e.d.
(ENDEDIT)

Another approach would be
ABD(β,γ) = AD(γ) * β + BD(γ) * ( 1 - β )
what yields in the same result (as the reader may try herself/himself).

Checking the result by looking at the extreme values is everytime a good idea:
ABD(β=1,γ=0) = A * 1 * ( 1 - 0 ) + B * ( 1 - 1 ) * ( 1 - 0 ) + D * 0 = A
ABD(β=0,γ=0) = A * 0 * ( 1 - 0 ) + B * ( 1 - 0 ) * ( 1 - 0 ) + D * 0 = B
ABD(β=0,γ=1) = A * 0 * ( 1 - 1 ) + B * ( 1 - 0 ) * ( 1 - 1 ) + D * 1 = D
ABD(β=1,γ=1) = A * 1 * ( 1 - 1 ) + B * ( 1 - 1 ) * ( 1 - 1 ) + D * 1 = D
q.e.d.

When the direction of e.g. β should be vice-versa, so that β==0 at A and β==1 at B, simple replace (not recursively ;)
β -> 1 - β
and
1 - β -> β

[Edited by - haegarr on March 31, 2006 11:47:58 AM]

• 18
• 11
• 16
• 9
• 51
• ### Forum Statistics

• Total Topics
631396
• Total Posts
2999789
×