Computing Barycentric Coordinates

Quote:

Original post by Chad Seibert I'm trying to compute barycentric coordinates using V1 + F(V2 - V1) + G(V3 - V1), where F and G are weighting factors and V1V2V3 are the coordinates of the simplex(triangle). Are these vector subtractions or a simple subtractions? Any optimization tips would also be welcome.

As V1, V2, and V3, are points (the vertices of the triangle), the subtractions would have to be vector subtractions, wouldn't they?

Also, you don't compute barycentric coordinates with the expression you gave. It's the other way around: given barycentric coordinates F and G (and, implicitly, E = 1 - F - G) you compute a point P on the triangle (or on the plane of the triangle) defined by V1, V2, and V3, using that expression.

To obtain the scalars F and G in the first place, you can e.g. compute them as the ratios:

F = SignedAreaOfTriangle(P, V3, V1) / SignedAreaOfTriangle(V1, V2, V3)
G = SignedAreaOfTriangle(P, V1, V2) / SignedAreaOfTriangle(V1, V2, V3)

These expressions are equivalent to solving for F and G by Cramer's rule.

Scroll to the bottom of this page and you'll see a lengthy answer that I posted to another website a few years ago, which gives more detail:

http://www.experts-exchange.com/Programming/Game/3D_Prog./Q_20174959.html

Quote:

Original post by Christer Ericson Scroll to the bottom of this page and you'll see a lengthy answer that I posted to another website a few years ago, which gives more detail

Actually, I'll just cut and paste the article here...


Barycentric coordinates will indeed let you map points from one triangle to another.

The barycentric coordinate of a point P with respect to the vertices A, B and C of a triangle ABC is a triplet of values, (a, b, c), such that P = a*A+b*B+c*C, with a+b+c=1. With appropriate values for a, b and c, P can assume the position of any point in the plane of ABC.

Given a different triangle DEF with vertices D, E and F, you can now map P into the plane of DEF to some point Q by computing Q=a*D+b*E+c*F. For instance, the barycentric coordinates (1,0,0), (0,1,0) and (0,0,1) would map A into D, B into E and C into F, respectively.

There are many ways of actually computing the barycentric coordinates (a, b, c) for P with respect to the triangle ABC. The perhaps simplest method uses the fact that a, b and c are proportional to ratios of specific (signed) triangle areas. If |ABC| denotes the area of the triangle with vertices A, B and C (given counter-clockwise in that specific order) then specifically you have that:

a = |PBC| / |ABC|,b = |PCA| / |ABC|,c = |PAB| / |ABC| = 1 - a - b

It's important that these areas are "signed", which simply means that when looking at the triangles from a fixed position, if their vertices are arranged counter-clockwise, the area is positive, and if clockwise, it's negative.

What remains is to actually compute |ABC| for some given points. This too can be done in many ways. A conceptually straightforward way (but somewhat expensive computation-wise) is to use the fact that a cross product of two vectors gives you a vector whose magnitude is twice the area of the triangle with those two vectors as its sides.

So, to compute (a, b, c) you would do something like this (assuming a reasonable C++ vector class):


This computation can be made less computationally expensive by projecting the triangle and the point into one of the XY, XZ or YZ planes and performing the calculations there (which automatically reduces the computation by 1/3 as there is one less coordinate to perform calculations on).

You can test your code, making sure it's working, by computing:


and making sure that the components of Zero are indeed (near) zero.

Relative areas are one way of computing barycentric coordinates. However there's another way that could be simpler for simplexes. What you do is treat one of the vertices as a local origin (such as V1), and generate the vectors X = (V2-V1) and Y = (V3-V1). You also generate a new test point from the old test point using the same method, P' = (P - V1). Let the columns of matrix A be the vectors X and Y. The equation A^-1P' will give you the barycentric coordinates for V2 and V3 with respect to P/P'. You can then calculate the coordinate for V1 directly from those.

When dealing with triangles or other objects that don't have enough points to be a simplex (i.e. a triangle in 3D space), the above equation generalize to (A^TA)^-1A^TP'. However at that point you'd probably be better off using relative areas, even in light of the fact that a ton of the matrix math can be simplified greater for lower dimensions.

Thank you very much! This was exactly what I was looking for.