Barycentric Coordinates and Point in Triangle Tests

 

I know it’s been a little while since my last post, and I apologize. I’ll try and keep the posts a little more frequent moving forward.

In the last post, we briefly encountered barycentric coordinates and loosely defined them as the coefficients of an affine combination. While that’s true, we can do better. We can define a more precise definition, and we can take a closer look at what they really mean, both numerically and geometrically. That’s the topic of this post, as well as taking a brief look at how we could use them in a real world game programming context.

First, let’s take a look at the formal definition of the coordinates, then we’ll consider a slightly refactored version that works better for our situations. Consider a triangle ABC (see Figure 1), and then imagine a little weight at each vertex. We can assign each weight as having 100% weight contribution from that vertex, and 0 contribution from the other vertices. So, for point A that’s (1, 0, 0), for point B it’s (0, 1, 0), and for point C it’s (0, 0, 1). This means that if you’re at the vertex, you only get the weight from that 1 vertex. Anywhere else within the triangle would be a combination of these weights. The barycenter of the triangle is the point inside the triangle where you could balance the weights. In other words, the weights would be contributing evenly to that point. Assuming that the weights at each vertex are equal (1), this would be the mean of the weights (or vertices):

The barycentric coordinates for the barycenter then become (1/3, 1/3, 1/3) given our equation above. Notice that this is exactly the equation of an affine combination, which is why we stated that the coefficients of an affine combination are also the barycentric coordinates. The dashed lines in the image represent the barycentric axes. A barycentric axis starts on a triangle edge, where the weight for the opposite vertex is 0. They then extend through the barycenter of the triangle to the opposite vertex, where the weight for that vertex is 1. Notice that the other coordinates in the base of each axis are 1/2. This is just a coincidence since we happen to be looking at an equilateral triangle. This won’t hold true for other kinds of triangles.

Now, what else can we observe? Well, for each axis, our values only extend from 0 to 1, since they are weights of that vertex. In other words, a value less than 0 or greater than 1 would be outside of our simplex (triangle in this case). Furthermore, the sum of the coordinates is necessarily equal to 1. Since these coordinates represent the amounts of each weight that you observe at that point, they are percentages, and therefore must sum up to the total. Otherwise, you’d be missing some of the weight from the system. These two observations will be extremely helpful as we examine uses in game code. The other thing I wanted to mention here is that if the restriction that coefficients of an affine combination must sum up to 1 didn’t make sense after my explanation before, I hope that looking at it from the perspective of barycentric coordinates helps to justify the restriction.

 

Now that we’ve examined the formal definition and use of barycentric coordinates, let’s take a slightly modified look at them, and see how we can make them more useful to us as game developers. We saw in the last post that any affine combination could be refactored and expressed as a single point, or origin, added to a linear combination. Let’s take our barycentric equation (which is an affine combination) and refactor it in this way now, using s, r, and t as our barycentric coordinates (coefficients):

 

 

 

 

 

 

 

We’ve substituted u and v as (B-A) and (C-A), respectively. Relating our result to the figure above, we see that we’ve picked A as our local origin, and two of the triangle’s edges as u and v. Our barycentric coordinates have been reduced to just r and t, and are now expressed relative to the local origin A. It’s important to note that mathematically, this ‘reduced’ form of the barycentric coordinates is equivalent to the formal version, but this format is much more usable to us. Because r and t are still barycentric coordinates, they must still fall between 0 and 1, and their sum still cannot exceed 1. Notice that we said exceed this time, and not sum up to 1. This is a subtle difference than before, and it can be explained like this: previously, we had the sum of s, r, and t = 1. This still must hold true. However, we’ve made s implicit in our new reduced form, and therefore it is not directly included in our sum. If r and t sum up to 1, then s is 0. However, r and t can sum to less than 1, and s will be equal to the remainder (see the second and third steps of how we arrived to our reduced form). In summary:

Now let’s see how we can use this. Imagine we’re trying to write a function in our game that determines whether or not a point is contained within a triangle. This is actually quite the common problem to solve in collision detection. In two dimensions, it might be a direct collision detection query. In three dimensions, we normally will first determine if a point is in the plane of a triangle, and if so, then reduce it to a two dimensional problem exactly like the normal 2D case. In either situation, we need a robust way to determine if a point is contained within a triangle. We can use barycentric coordinates in the reduced form to solve this, by taking the following steps:

1. Pick a vertex of the triangle to be our local origin, which we’ll refer to as A

2. Compute u and v using the differences of the other two vertices and our origin as we did above (ex: u = B-A, v = C-A)

3. Compute the r and t barycentric values for our point P with respect to A

4. Check that r and t are both within 0 and 1, and that their sum is less than or equal to 1. If so, return true. Otherwise, the point is outside, return false.

It’s actually quite straightforward, with the exception that we haven’t yet discussed how you’d complete step 3, computing the barycentric coordinates. Let’s take a look at that now, and then with r and t computed, we’ll be able to complete the function. There are several approaches to finding the barycentric coordinates in this step. The simpler of the two uses some identities and properties of vectors we’ve covered up to this point, which is why I’ll choose to show that one now. However, after we take a good look at matrices and solving systems of linear equations with them, we’ll see that there’s a more efficient way to compute them. See Figure 2 to see the problem we’re trying to solve.

Let’s start by refactoring our equation slightly, and move the A over to the other side:

We’ve replaced P-A with the vector w. We need to now solve for r and t. If we look at some of the vector rules that we covered earlier, we’ll remember that any vector crossed with itself (or any collinear vector) will result in the 0 vector. So, to eliminate t, let’s take the cross product of both sides with v:

 

 

 

 

We can see that by having the cross product of v with itself go to the 0 vector, we were able to eliminate t from the equation and solve for r. We can repeat this same process for t to obtain:

At this point, we can determine whether or not r and t are going to be greater than 0 or not. This is the first requirement of our test. The equations for r and t above represent ratios between two cross products. The two cross products each represent a vector, so in other words we’re taking the ratio of two vectors. The only way r or t can be negative is if these vectors point in opposite directions. So, let’s use the dot product to determine if the numerator and denominator in each case point in the same direction:

The sign() of each side will be > 0 if the vectors are pointing the same direction, or < 0 if the vectors are pointing away from each other. At this point, if either is < 0, we can exit the function with a false result.

The next requirement we need to meet is that r and t must each be smaller than 1, and that their sum must also be less than 1. To do this, let’s take the norm of each of the equations above. Since we already know that r and t are positive, we know that the norm of r and t is just r and t.

 

Again, we can repeat this same process to solve for t, and we’ll get:

Also, since swapping the order of a cross product doesn’t change the magnitude of the resulting vector, only it’s direction, then we can also say that

Which gives us a common denominator in our r and t formulas, so we only have to compute the value once. And there we have it, we now have r and t computed, which means we can complete our function. A sample implementation, written in C# and using XNA might look like this:

///<summary>

/// Determine whether a point P is inside the triangle ABC. Note, this function

/// assumes that P is coplanar with the triangle.

///</summary>

///<returns>True if the point is inside, false if it is not.</returns>

public static bool PointInTriangle(ref Vector3 A, ref Vector3 B, ref Vector3 C, ref Vector3 P)

{

    // Prepare our barycentric variables

    Vector3 u = B - A;

    Vector3 v = C - A;

    Vector3 w = P - A;

 

    Vector3 vCrossW = Vector3.Cross(v, w);

    Vector3 vCrossU = Vector3.Cross(v, u);

 

    // Test sign of r

    if (Vector3.Dot(vCrossW, vCrossU) < 0)

        return false;

 

    Vector3 uCrossW = Vector3.Cross(u, w);

    Vector3 uCrossV = Vector3.Cross(u, v);

 

    // Test sign of t

    if (Vector3.Dot(uCrossW, uCrossV) < 0)

        return false;

 

    // At this point, we know that r and t and both > 0.

    // Therefore, as long as their sum is <= 1, each must be less <= 1

    float denom = uCrossV.Length();

    float r = vCrossW.Length() / denom;

    float t = uCrossW.Length() / denom;

 

 

    return (r + t <= 1);

}

 

 

 

 

And that concludes this post on barycentric coordinates, and one of their uses in game code. I hope that this post also served to solidify some of the previous information about affine combinations. Finally, it gave us a chance to use what we’ve covered so far to so something useful. I hope you enjoyed it, and I’ll be moving on to matrices next.

Comments

• Anonymous
  August 12, 2011
  Thanks a lot your blog is very helpful to me please keep it up I am looking forward to the physics stuff. Thanks again BakerCo

• Anonymous
  September 04, 2011
  Hi, Nice post. But I have a question. According to your post, it appears that r and t never go below 0 because you are only working with vector lengths. Ideally, when we test a point outside the triangle, either or both the values of r and t must be < 0.

• Anonymous
  September 05, 2011
  Hi Vektor, I think my last reply got lost so I'll reply again. You're absolutely right. You pointed out a pretty big oversight on my part and I've corrected the blog to reflect the right solution. Since we are taking the norm of the equation, the signs of r and t got lost, so checking for > 0 at the end was meaningless. I've corrected it to determine the signs earlier before taking the norm, with an explanation of how we do that. Thanks for catching that!

• Anonymous
  September 16, 2013
  Great post. Finally I understood some math I was missing. So would this code be working in 3D, without projecting triangles to 2D plane, or should I use something different. For example: use Crammer rule to solve for 3D space?

• Anonymous
  September 16, 2013
  Thanks Michael, glad that it helped. If your goal is to test that the projection of a point onto a 3D triangle is inside that triangle, then you can make it work for 3D with very little modification. The points A, B, and C are all going to be coplanar since they are on a triangle. The values s and t are ratios, which hold up just fine in 3D as well. The only interesting part is the point P that you're testing. You'll want to find the projection of P onto the plane of ABC, say we call that Q, and then you can test that Q is inside of ABC using this method. While I haven't tried it, it seems reasonable that you might be able to extend this further into 3D by considering a 3D point and a tetrahedron instead of a triangle. You could just pick a vertex A, and then take the 3 edge vectors that extend from that vertex, call then u, v, and w. Then you'd find the ratios a, b, and c along each edge vector (instead of s and t) using similar derivation to the above.

• Anonymous
  January 04, 2014
  return (r <= 1 && t <= 1 && r + t <= 1); can be replaced by return (r + t <= 1); because r and t are both >=0. Nice post!

• Anonymous
  January 04, 2014
  And correct "piont" to "point" and "> 0" to ">= 0" in comment :)

• Anonymous
  January 05, 2014
  Thanks for catching the spelling error :) Yes, you're right. Since each are positive and we show their sum <= 1, we don't need to verify that r & t are individually <= 1. I've updated the post to reflect that. Thanks!

• Anonymous
  January 25, 2014
  I wrote a complete article about point in triangle test. It shows the barycentric, parametric and dot product based methods. Then it deals with the accuracy problem occuring when a point lies exactly on one edge (with examples). Finally it exposes a complete new method based on point to edge distance. totologic.blogspot.fr/.../accurate-point-in-triangle-test.html Enjoy !

• Anonymous
  February 01, 2014
  Nice article! I like the real world examples of accuracy problems.

• Anonymous
  September 28, 2014
  Great article, thanks for writing this.

• Anonymous
  November 05, 2016
  In C programming problem. if you have a triangle ABC where A(1,3), B(5,2), C(4,4), and if you have a point D(2,3). Write a program that will tell if the point D is inside, outside, or edge of a triangle.could you help me this?

• Anonymous
  November 05, 2016
  In C programming problem. if you have a triangle ABC where A(1,3), B(5,2), C(4,4), and if you have a point D(2,3). Write a program that will tell if the point D is inside, outside, or edge of a triangle.