Sign in to follow this  
r_bewick

How to get height of a point inside a triangle

Recommended Posts

Hi I have a triangle ABC and a point P. This point is somewhere inside the triangle and I know its X and Z position but not Y (it's height). I also know the coordinates of the points A, B and C. How can I find the height of point P if it is anywhere in the triangle? thanks, r_bewick

Share this post


Link to post
Share on other sites
Find the barycentric coordinates of the point within the triangle in XZ space, then use those coordinates to interpolate Y.

Share this post


Link to post
Share on other sites
One method would be plug the x and z values into the plane equation for the triangle and solve for y, i.e. (off the top of my head, so no guarantee of correctness):
ax + by + cz + d = 0
ax + cz + d = -by
y = -(ax + cz + d) / b
You can easily compute the plane equation for the triangle from its vertices (A, B, and C).

Share this post


Link to post
Share on other sites
Quote:

Find the barycentric coordinates of the point within the triangle in XZ space, then use those coordinates to interpolate Y.


I have looked at barycentric coordinates on wikipedia etc but it is really confusing to me. Could you point me out to a tutorial that shows me how to do this?

Quote:

ax + by + cz + d = 0

ax + cz + d = -by

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

This looks simple enough. But can you please explain which each letter means? eg which letter is what vertice of the triangle and which is point P?

thankyou very much for the quick replies :)

Share this post


Link to post
Share on other sites
Quote:
This looks simple enough. But can you please explain which each letter means? eg which letter is what vertice of the triangle and which is point P?

thankyou very much for the quick replies :)
x and z in the equation are the x and z components of the point P.

ax + by + cz + d = 0 is the general equation of a plane (see equation 2, here). Geometrically, a, b, and c correspond to the x, y, and z components of a vector normal to the plane, and d is proportional to the orthogonal distance from the plane to the origin.

Given a triangle with vertices A, B, and C, you can find the equation of the plane as follows:
vector3 normal = cross(B - A, C - A);

// The coefficients of the plane equation are then:
a = normal.x;
b = normal.y;
c = normal.z;
d = -dot(A, normal);
Note that it's fairly common to normalize the plane normal (which should be done before computing the distance), but it's not strictly necessary in this case.

The plane equation can also be expressed in a couple of other forms - see the article linked above for details.

Share this post


Link to post
Share on other sites
thanks for replying again. I put all the values in but it didnt work for me :(
I'm not sure why.

I'm using this for making units walk the right height on terrain smoothly but now the units jump up and down really high when they go over slopes. Are you sure that everything you gave me is correct? also Im not sure if some of my code is correct but I don't know if you want me to post it (C++ & directX)




Share this post


Link to post
Share on other sites
Quote:
also Im not sure if some of my code is correct but I don't know if you want me to post it (C++ & directX)
Yes, post the relevant code (be sure to use [ source ] tags).

Share this post


Link to post
Share on other sites

//_fPosX & _fPosY = position of point in triangle
int iTileX = static_cast<int>((_fPosX - m_vec3Position.x) / m_fTileSizeX);
int iTileZ = static_cast<int>((_fPosZ - m_vec3Position.z) / m_fTileSizeZ);
unsigned int iCurrentVertice = iTileX + (iTileZ * (m_iNumTilesX));

if ((iCurrentVertice + m_iNumTilesX + 1 >= m_vecVertices.size()) || (iTileX > m_iNumTilesX) || (iTileX < 0) || (iTileZ > m_iNumTilesZ) || (iTileZ < 0))
{
return 0;
}

float fHeight; //height of point (unknown)

D3DXVECTOR3 N; //normal
D3DXVECTOR3 A; //triangle v1
D3DXVECTOR3 B; //triangle v2
D3DXVECTOR3 C;// triangle v3

//distance from position to top vertice
float dx = _fPosX-m_vecVertices[iCurrentVertice+m_iNumTilesX].vec3Position.x;
float dz = _fPosZ-m_vecVertices[iCurrentVertice+m_iNumTilesX].vec3Position.z;
//If dz > dx then the point would be in the first triangle (v0,v1,v2).

if (dz > dx) //1st triangle.
{
//vector of terrain vertices
A = m_vecVertices[iCurrentVertice].vec3Position;
}
else //2nd triangle
{
A = m_vecVertices[iCurrentVertice+1].vec3Position;
}

B = m_vecVertices[iCurrentVertice+m_iNumTilesX].vec3Position;
C = m_vecVertices[iCurrentVertice+m_iNumTilesX+1].vec3Position;


D3DXVec3Cross(&N,&(B - A),&(C - A));
D3DXVec3Normalize(&N, &N);

float a,b,c,d;
a = N.x;
b = N.y;
c = N.z;
float x,z;
x = _fPosX-m_vecVertices[iCurrentVertice].vec3Position.x;
z = _fPosZ-m_vecVertices[iCurrentVertice].vec3Position.z;
d = -D3DXVec3Dot(&A,&N);
fHeight = -(a*x + c*z + d) / b;

return fHeight;

Share this post


Link to post
Share on other sites
I didn't proof all of the code, but it looks to me like you might be using the wrong vertices for one of the two triangles that make up the quad. (You might try sketching out each case on paper to make sure that you're grabbing the right vertices.)

Share this post


Link to post
Share on other sites
I checked again and am quite sure they are right.

Instead of trying to find the height of a point in the triangle I also Set the units height to the average height of the 3 vertices of the triangle it is closest to and it does follow the terrain height properly it was just very jumpy as it moved from one triangle to the next.

any other ideas? I have absolutely no idea about whats wrong.

by the way thanks so much for all your help jyk. I really appreciate it

Share this post


Link to post
Share on other sites
Quote:
I checked again and am quite sure they are right.
Maybe I'm missing something, but looking at this code:

	if (dz > dx) //1st triangle.
{
//vector of terrain vertices
A = m_vecVertices[iCurrentVertice].vec3Position;
}
else //2nd triangle
{
A = m_vecVertices[iCurrentVertice+1].vec3Position;
}

B = m_vecVertices[iCurrentVertice+m_iNumTilesX].vec3Position;
C = m_vecVertices[iCurrentVertice+m_iNumTilesX+1].vec3Position;

It appears to me that in the first case you get:
B--C
| /
|/
A
And in the second case you get:
B--C
\ |
\|
A
Is that correct? If so, that won't work - you have two overlapping triangles there, when what you want is two 'complimentary' triangles that together form a (not necessarily planar) quad.
Quote:
by the way thanks so much for all your help jyk.
No problem :)

Share this post


Link to post
Share on other sites
oh you are right! sorry! I didn't know about that I'm still quite new to terrain programming stuff. Thanks!
Does this look better?

1st:

B--C

| /

|/

A

A = m_vecVertices[iCurrentVertice].vec3Position;
B = m_vecVertices[iCurrentVertice+iNumTilesX].vec3Position;
C = m_vecVertices[iCurrentVertice+m_iNumTilesX+1].vec3Position;

2nd: ?

C

/ |

/ |

A--B

A = m_vecVertices[iCurrentVertice].vec3Position;
B = m_vecVertices[iCurrentVertice+1].vec3Position;
C = m_vecVertices[iCurrentVertice+m_iNumTilesX+1].vec3Position;

Edit : argh i cant get the triangle right. C is above B

[Edited by - r_bewick on March 9, 2010 2:08:19 AM]

Share this post


Link to post
Share on other sites
You probably don't need this, but let me suggest another way of doing the Math. If the vertices of your triangle are (x1,y1,z1), (x2,y2,z2) and (x3,y3,z3), any other point (x,y,z) on the triangle will satisfy

|x1 y1 z1 1|
|x2 y2 z2 1| = 0
|x3 y3 z3 1|
| x y z 1|


You can expand the determinant and solve the first-degree equation in y.

Share this post


Link to post
Share on other sites

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