Sign in to follow this  

getHeight() for TIN terrains

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

Hi, I have added TIN terrains to my engine. The terrain is subdivided with a quad tree, and culling, rendering works great. I'm now trying to put together a fast getHeight() function. I got to the point where I loop through the node triangles and perform a 2d point test, to see if the point (x,z) actually lies within the triangle. Now I need to calculate the height/penetration at that location, and that's where I, again, get stuck. Supplied are the three triangle vertices (x,y,z), and the point (x,y,z) that may lie above or below the triangle surface. I don't really have a clue what to do next... I know this is very much like a ray-tri test, but can't it be simplified/optimized since it works vertical only? Any hints, links etc.?

Share this post


Link to post
Share on other sites
Quote:
Original post by remdul
I know this is very much like a ray-tri test, but can't it be simplified/optimized since it works vertical only?
Sure. This has been covered recently, but in short, just plug the x and y values into the plane equation for the triangle and solve for z. (Or solve for y using x and z if y is up...)

Share this post


Link to post
Share on other sites
I still don't understand what I'm supposed to do. I read a few recent topics about similar problems here, but I'm not sure I'm doing the same.

I'm doing something similar to this:

http://www.merl.com/papers/docs/TR96-17.pdf#search=%22MERL-TR-96-17%22

Except that that paper doesn't go into retrieving the height value I think, and if it does, I don't understand.

Hmm, not even sure what I'm looking for...

Share this post


Link to post
Share on other sites
If you have the triangle to test against, this is really quite easy.

Calculate the plane equation of the triangle from the three points, r.n = d, where n=(v1-v0)×(v2-v0) and d=v0.n.

Then find the z value for which the line is on the plane. This is a line-plane collision, but since the line is axis aligned you can calculate h directly as:
h=d-(xnx+yny).

Share this post


Link to post
Share on other sites

// Returns the height above a triangle. z axis is up.
float HeightAtXY(float x, float y, t_Vec3 *v1, t_Vec3 *v2, t_Vec3 *v3) {
float q, u, v, w;

// Calculate the barycentric weights and use them to find the height at the x,y location
q = (v2->x - v1->x) * (v3->y - v1->y) -
(v3->x - v1->x) * (v2->y - v1->y);

if (q == 0)
return v1->z; // Bad triangle, but at least return something...

q = 1.0 / q;
u = q * ((v2->x - x) * (v3->y - y) - (v3->x - x) * (v2->y - y));
v = q * ((v3->x - x) * (v1->y - y) - (v1->x - x) * (v3->y - y));
w = q * ((v1->x - x) * (v2->y - y) - (v2->x - x) * (v1->y - y));

return u * v1->z + v * v2->z + w * v3->z;
}


Share this post


Link to post
Share on other sites
Ah yes that's it. I realize I've actually done this before (calculating world position of texture coordinates), and it needed only minor modifications.

Thanks PlayerX for the slightly faster code, and Bob Janova for the explaination (I actually understand it now!). :)

Share this post


Link to post
Share on other sites

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