PDA

View Full Version : Terrain triangle question



03-30-2003, 07:13 PM
This is an easy one, I'm sure...maybe you guys can help me.

I've got my terrain represented as a linked list of triangles. I want to find out, using the coordinates of my moving object(car), which triangle it is inside of. So I want to traverse my list until I find the triangle that the car is in.

Do any of you guys know an equation or expression to represent this relationship? How can I tell if the car's (x,z) coordinates ly in the polygons area (triangle)?

This way, I can figure out what the Y coordinate of my car should be, which I don't have a problem doing. It's just figuring out which polygon (triangle) is in the region of the car.

oliii
03-31-2003, 06:15 PM
for each of the three edges of the triangle, calculate the edge plane, that is going along an edge and along the triangle normal. If the point lies on the positive side of the plane, then it's not in the triangle. If the point lies inside the negative side of all the three planes, the point is inside the triangle.





bool PointInTriangle(float P[2], float V[3][2])
{
for(int i = 0; i < 3; i ++)
{
// edge direction
float E[2] = { V[(i+1)%3][0] - V[i][0], V[(i+1)%3][1] - V[i][1] };


// relative position of point to edge start
float D[2] = { P[0] - V[i][0], P[1] - V[i][1] };


//edge normal, pointing to the outside of the triangle
float En[2] = { -E.y, E.x };


// distance of point from edge plane
float dp = En[0] * D[0] + En[1] * D[1];


// point on the positive side of plane (with a threhold)
if (dp > 0.0001f) return false;
}

return true;
}


if your triangles are on a terrain and therefore roughly pointing up, as you said, use the (x, z) coords of the car and the (x, z) coords of the triangles, that's why the algorithm is in 2D.

If it is in 3D, you need to find which of the x, y, z axis the normal roughly points towards to.

example Normal of tri is (0.1, -0.1, -0.81), use (x, y) coordinates of the vertices to avoid having your triangle fold into a line in the intersection test, and give erroneous results (due to the theshold value, which you need to use to avoid gaps between triangles).

[This message has been edited by oliii (edited 03-31-2003).]