Getting the height of a point on a triangle

If you just want a formula, try barycentric coordinates. If you scroll down a bit there are formulas for lambda 1 through 3.

Since you have 3 vertices p1=(x1,y1,z1), p2, p3, and want to find y at x,z, in your case it becomes (untested):

float calcY(vec3 p1, vec3 p2, vec3 p3, float x, float z) {
float det = (p2.z - p3.z) * (p1.x - p3.x) + (p3.x - p2.x) * (p1.z - p3.z);

float l1 = ((p2.z - p3.z) * (x - p3.x) + (p3.x - p2.x) * (z - p3.z)) / det;
float l2 = ((p3.z - p1.z) * (x - p3.x) + (p1.x - p3.x) * (z - p3.z)) / det;
float l3 = 1.0f - l1 - l2;

return l1 * y1 + l2 * y2 + l3 * y3;
}


An alternative that might be easier in your case is to just calculate the Y of the triangles plane at a specific X,Z.
If you already have the plane as ax + by + cz + d = 0 you get, y = -(ax + cz + d) / b, so that's a lot shorter.

thanks for the reply, just tried to put it in. bt came across a problem

Where you have the line:


return l1 * y1 + l2 * y2 + l3 * y3;




they seem undeclared.

what is y1,y2,y3.


did you mean p1.y, p2.y and p3.y?




cheers

Yes i meant p1.y p2.y and p3.y. =)

I thought so. cheers

You'll have to forgive me because I don't really understand the maths that well.

I plugged it in and I'm getting weird outputs. Ill give you a real case.

I picked a point i know is in the triangle. (these values are taken from the terrain in my program)

X = 42.779999
Z = 28.450001

These are the vertices of the triangle


p1 = {x=42.000000 y=3.2046642 z=29.000000 }
p2 = {x=43.000000 y=3.9619608 z=28.000000 }
p3 = {x=43.000000 y=3.5283644 z=29.000000 }


the height being return is = 4.1337585,

clearly higher than the 3 y values of the vertices's.




Ive run it several times (each time it generates different height values, but the X and Z grid will be the same) picked the same X/Z points. Obviously the vertex heights are different but the answer still is incorrect.

I get 3.695628 from those values.. perhaps you accidentally use a point outside the triangle.


#include <cstdio>

struct vec3 {
vec3(float x, float y, float z) : x(x), y(y), z(z) {}

float x, y, z;
};

float calcY(vec3 p1, vec3 p2, vec3 p3, float x, float z) {
float det = (p2.z - p3.z) * (p1.x - p3.x) + (p3.x - p2.x) * (p1.z - p3.z);

float l1 = ((p2.z - p3.z) * (x - p3.x) + (p3.x - p2.x) * (z - p3.z)) / det;
float l2 = ((p3.z - p1.z) * (x - p3.x) + (p1.x - p3.x) * (z - p3.z)) / det;
float l3 = 1.0f - l1 - l2;

return l1 * p1.y + l2 * p2.y + l3 * p3.y;
}

int main() {
float x = 42.779999f;
float z = 28.450001f;

vec3 p1(42.0f, 3.2046642f, 29.0f);
vec3 p2(43.0f, 3.9619608f, 28.0f);
vec3 p3(43.0f, 3.5283644f, 29.0f);

float y = calcY(p1, p2, p3, x, z);

printf("y = %f\n", y);
}


Check your code very carefully, making sure you have the right subscripts, signs and parentheses correct. Your routine should also check for the point being on or inside the triangle.

Check that L1, L2 and L3 are all in the range 0 <= L <= 1. A value of 0 or 1 for any lambda means the point is on the edge of the triangle.

Thanks. I re copied the method and it seems to work. i need to test it more.

what would i do if the point is on the edge of a triangle?

Thanks. I re copied the method and it seems to work. i need to test it more.

what would i do if the point is on the edge of a triangle?

If you're just looking for height interpolation, it'll still be valid. Just wanted to let you know how to interpret the lambdas.

EDIT: So, if you use that routine to test points being on/in a triangle, you can return as soon as you find an unacceptable lambda.
I.e.,

L1 = //....
if( L1 < 0 || L1 > 1.0f ) return some indication of that point not on/in triangle;
L2 = //...
if( L2 < 0 || L2 > 1.0f) // etc.
// no need to test L3 if L1 and L2 both 0 <= L <= 1


hmmm. well i took the X/Z of my camera and got the way using my method, and it kinda works, but not that accurately, it seems to jump when changing triangles. The hills on the terrain are pretty high and varied. it never goes too far, its roughly right but its very jerky, cant think of any reason it would be doing that.




Erik Rufelt mentioned rearranging: Ax + By + Cz + D = 0 to get the height.
I wouldn't mind giving that a try. how can i make my triangle into a plane in that form. (ive never used it before).





cheers

hmmm. well i took the X/Z of my camera and got the way using my method, and it kinda works, but not that accurately, it seems to jump when changing triangles. The hills on the terrain are pretty high and varied. it never goes too far, its roughly right but its very jerky, cant think of any reason it would be doing that.

Erik Rufelt mentioned rearranging: Ax + By + Cz + D = 0 to get the height.
I wouldn't mind giving that a try. how can i make my triangle into a plane in that form. (ive never used it before).

cheers

Off the top of my head:

A, B and C are the coefficients of the unit normal to the triangle. Do a cross-product of 2 of the edges to get the normal vector. Normalize it and nx, ny, nz == A, B, C.

Then, pick one of the vertices (x,y,z) and solve for D.

EDIT: Using the plane equation form, be sure to check for B==0, else you'll divide by zero. Also, if B != 0, you'll always get a return value. That doesn't mean the point is on/in the triangle! It just gives you the elevation at ( x,z ) for the infinite plane containing the triangle. If I understand how you're using this, you'll still need to check for point-on/in-triangle.

Ok so I tried that out also this is the code.



// p1 p2 and p3 are all known

D3DXVECTOR3 e1 = p3-p1;
D3DXVECTOR3 e2 = p2-p1;

//cross product
D3DXVECTOR3 normal;
normal.x = e1.y*e2.z - e1.z*e2.y;
normal.y = e1.z*e2.x - e1.x*e2.z;
normal.z = e1.x*e2.y - e1.y*e2.x;

//NORMALIZE THE VECTOR
float magnitude = sqrt((normal.x * normal.x) +(normal.y * normal.y) + (normal.z * normal.z));
normal.x /= magnitude;
normal.z /= magnitude;
normal.y /= magnitude;

//ax + by + cz + d = 0

//rearange
// d = - (ax + by + cz )
float D = -((normal.x * p1.x) + (normal.y * p1.y) + (normal.z * p1.z));

// y = - (ax + cz + d ) / b
float y = - ((normal.x * p1.x) + (normal.z * p1.z) + D ) / (normal.y * p1.y);




it always outputs the same results.

For smooth movement over the terrain using the triangle height is hard to get right (ie you need physics etc, and can't just put the camera at a constant height over the terrain). Try using bilinear interpolation of height values.

Something like this:

float heightmap[width][height];

float getHeight(float x, float z) {
int ix1 = (int)x;
int ix2 = ix1 + 1;

int iz1 = (int)z;
int iz2 = iz1 + 1;

..clamp indices to [0,width-1] and [0,height-1] to avoid crash if you move outside the map


float y1 = heightmap[ix1][iz1];
float y2 = heightmap[ix1][iz2];
float y3 = heightmap[ix2][iz1];
float y4 = heightmap[ix2][iz2];


float xfrac = x - floor(x);
float zfrac = z - floor(z);

float yleft = y1 + (y2 - y1) * xfrac;
float yright = y3 + (y4 - y3) * xfrac;

float y = yleft + (yright - yleft) * zfrac;

return y;
}

I realised my mistake



// y = - (ax + cz + d ) / b


float y = - ((normal.x * p1.x) + (normal.z * p1.z) + D ) / (normal.y * p1.y);





(normal.y * p1.y); is actually (by) and not b as i wrote in the comments.

also After solving D. i reused the point p1 in the next line, where as i should have plugged in my x/z coordinates of the point i want to find the height.




anyway it works fantastically. smooth terrain following. thanks guys, i actually understand it too so ive learned something.