Sign in to follow this  
Chad Seibert

Computing Barycentric Coordinates

Recommended Posts

Hello, Community 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. Thanks for any assistance, Chad Seibert

Share this post


Link to post
Share on other sites
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


Share this post


Link to post
Share on other sites
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):

// Compute the normal of the triangle
Vector N = Normalize(Cross(B-A,C-A));

// Compute twice area of triangle ABC
float AreaABC = Dot(N,Cross(B-A,C-A));

// Compute a
float AreaPBC = Dot(N,Cross(B-P,C-P));
float a = AreaPBC / AreaABC;

// Compute b
float AreaPCA = Dot(N,Cross(C-P,A-P));
float b = AreaPCA / AreaABC;

// Compute c
float c = 1.0f - a - b;

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:

Point PP = a*A + b*B + c*C;
Point Zero = PP - P;

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

Share this post


Link to post
Share on other sites
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 (ATA)-1ATP'. 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.

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