Barycentric Coordinates

Barycentric Coordinates, or 'Area Coordinates' (or uv's) provide a linear interpolation of coordinates in terms of the space of a triangle (or polytope), and have applications from collision detection to texture mapping.

In essence any point P on a triangle with vertices A,B,C can be described as:
P = A + u * (C - A) + v * (B - A)
this is the parametric form of describing a triangle. (ie: Make A the origin, and describe the coordinates in terms of a linear combination of C and B)

The barycentric coordinates are illustrated in blackpawn's barycentric flash application


We can rearrange this parameterized equation by subtracting A from both sides:
(P - A) = u * (C - A) + v * (B - A)
And substitute v0,v1,v2 for our vectors v2=(P-A),v0= (C-A), v1= (B-A):
v2 = u * v0 + v * v1

Now we can convert this single equation into two equations with two unknowns by performing the dot product on both sides. This is different from the scalar case, as we are performing a dot product with 2D vectors, ie:
a + b = k
Multiply both sides by two vectors:
(a + b).v0 = k.v0
(a + b).v1 = k.v1
Expanding:
(a.x + b.x)*v0.x+(a.y + b.y)*v0.y = k.x * v0.x + k.y*v0.y
(a.x + b.x)*v1.x+(a.y + b.y)*v1.y = k.x * v1.x + k.y*v1.y
Giving us two equations with two unknowns.

Applying this to our paramaterized triangle equations above we now have:
(v2) . v0 = (u * v0 + v * v1) . v0
(v2) . v1 = (u * v0 + v * v1) . v1
and can re-arrange to:
v2 . v0 = u * (v0 . v0) + v * (v1 . v0)
v2 . v1 = u * (v0 . v1) + v * (v1 . v1)
Which we can re-write in matrix form as:

Finally, we can perform a matrix inversion and get the final result:
u = ((v1.v1)(v2.v0)-(v1.v0)(v2.v1)) / ((v0.v0)(v1.v1) - (v0.v1)(v1.v0))
v = ((v0.v0)(v2.v1)-(v0.v1)(v2.v0)) / ((v0.v0)(v1.v1) - (v0.v1)(v1.v0))

This gives us the complete routine:

// Compute vectors        
v0 = C - A
v1 = B - A
v2 = P - A

// Compute dot products
dot00 = dot(v0, v0)
dot01 = dot(v0, v1)
dot02 = dot(v0, v2)
dot11 = dot(v1, v1)
dot12 = dot(v1, v2)

// Compute barycentric coordinates
invDenom = 1 / (dot00 * dot11 - dot01 * dot01)
u = (dot11 * dot02 - dot01 * dot12) * invDenom
v = (dot00 * dot12 - dot01 * dot02) * invDenom

// Check if point is in triangle
return (u >= 0) && (v >= 0) && (u + v <= 1)