MathGem:Height of a Point in a Triangle

From GPWiki
Jump to: navigation, search

Height of a Point in a Triangle

This shows how to find the value of one component of a point in a triangle given the other two components. In this article, we find Z given X and Y, but this method could apply to any component simply by swapping axis names.

Procedure

Given three vertices of a triangle, P, Q, and R, and x and y of the point,

  1. Find a vector that is perpendicular to the plane of the triangle. If you already have the normal, use that. Otherwise, this will do:
    N = (R - P) \times (Q - P)
  2. Find the value of z using this formula:
    z = \frac{N_X(x-P_X) + N_Y(y-P_Y)}{-N_Z} + P_Z

Note: If N_z is 0, then the triangle is parallel to the Z axis and there is no unique z.

Applications

The Height of the Terrain

One instance where this is used is to find the height of the terrain at a particular location. Once the particular triangle at the location is found, the height of the object can be determined from the equation above. It should be noted that if the vertices of the terrain are on an axis-aligned regular grid (such as a heightmap), the calculation of N\,\! is simplified. Assuming that \overrightarrow{P Q} is parallel to the X axis, \overrightarrow{P R} is parallel to the Y axis, and the distance between points in the grid is h, N\,\! is computed as follows:

   \begin{matrix}N_X & = & Q_X - P_X \\ N_Y & = & R_Y - P_Y \\ N_Z & = & h \end{matrix}

Color Interpolation

Another common application is interpolating the color of a point in a triangle in 2D given the colors at the vertices. In this case, the Z component is a color instead of a location.

Derivation

If the point X:[x,y,z] is in the plane of the triangle, then the dot product of a vector, N perpendicular to the plane, and the vector (X-P) is 0.

   0 = N \bullet (X-P)
0 = N_X(x-P_X) + N_Y(y-P_Y) + N_Z(z-P_Z)\,\!
(z-P_Z) =  \frac{N_X(x-P_X) + N_Y(y-P_Y)}{-N_Z}
z =  \frac{N_X(x-P_X) + N_Y(y-P_Y)}{-N_Z} + Pz

Other Method

if P,R,Q is a triangle vertices, and X,Y - is a coordinates of point, then:

a:=-(R[1]*Q[2]-P[1]*Q[2]-R[1]*P[2]+P[2]*Q[1]+R[2]*P[1]-Q[1]*R[2]);
b:= (P[1]*R[0]+Q[1]*P[0]+R[1]*Q[0]-Q[1]*R[0]-P[1]*Q[0]-R[1]*P[0]);
c:= (Q[2]*R[0]+P[2]*Q[0]+R[2]*P[0]-P[2]*R[0]-Q[2]*P[0]-Q[0]*R[2]);
d:=-a*P[0]-b*P[2]-c*P[1];
result:= -(a*X+c*Y+d)/b; //z of point