Jump to content
  • Advertisement
Sign in to follow this  
robustpotato

Getting the height of a point on a triangle

This topic is 2660 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

Heres the problem




Heres what we know:
The 3 vertices of the triangle
the x and z coordinates of a point P, which definatly lies within the bounds of the triangle.


I need this method for several different things, for my terrain generator.




any help appreciated. cheers

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites

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

Share this post


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




Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!