Barycentric coordinates

You have the point P and the triangle points v1, v2, v3. So set up a system of linear equations and solve for the barycentric coordinates. For a small 3x3 system, it seems they like to use cramers method to solve it (that's how real time rendering does it).

Thanks! According to MathWorld the vector analog of Cramer's Rule is:
(A x B) x (C x D) = (A . B x D) * C - (A . B x C) * D

Firstly, forgive me for not seeing the obvious, but how does the line above solve the x, y, and z (the barycentric coords)? If I have got this correctly A, B, C and D are already given, ABC being the points of triangle and D the point P?

(Haven't done Cramer's before, and just briefly read Wiki and MathWorld among others)

Secondly, would it be numerically stable to do a cross product, what if the height of the triangle -> 0, meaning, what if the triangle is almost a line?

For more info on cramers rule, try checking out this place.

You mention collision detection, are you trying to find out the intersection between a ray and a triangle? If so, then I'll try to explain as well as I can. If not, just ignore this.

If the point p is inside the triangle, then:

p(u,v) = (1-u-v)v1 + u*v2 + v*v3

where u and v are the barycentric coordinates which must fulfill the conditions u >=0, v >= 0 and u+v <= 1( the third barycentric coordinate w is w = 1 - u - v ). v1, v2 and v3 are the vertices of the triangle.

When a ray r(t) = o + t*d ( o is the origin of the ray, d is the direction, t >= 0) intersects the triangle, the coordinates of the intersection point are the same in the triangle and the ray:

  r(t) = p(u,v)->  o + t*d = (1 - u - v)v1 + u*v2 + v*v3->  o + t*d = v1 - u*v1 - v*v1 + u*v2 + v*v3->  o - v1 = u(v2 - v1) + v(v3 - v1) - t*dWritten as a matrix equation(excuse the crappy asciis that follow):                    | t |[ -d v2-v1 v3-v1 ]* | u | = o - v1                    | v |You can use Cramers rule to solve for u,v and t. Let     e1 = v2 - v1    e2 = v3 - v1     s = o - v1| t |         1         | det(s,e1,e2) || u | = ------------- * | det(-d,s,e2) || v |   det(-d,e1,e2)   | det(-d,e1,s) |Which can be written as(cross means cross product between the vectors indicated, the . stands for dot product):| t |         1             | cross(s,e1) . e2 |     1      | q . e2 || u | = ---------------- *  | cross(d,e2) . s  | = ------ * | p . s  || v |   cross(d,e2) . e1    | cross(s,e1) . d  |   p . e1   | q . d  |where p = cross(d,e2) and q = cross(s,e1). This speeds up calculations because you can calculate p and q beforehand.

I hope that's helpful and reasonably clear. Especially after I edited the ascii to make it actually readable!

Thank you, that explains a lot. It seems that I have been mistaken, sorry. What I need is to project the point p on the triangle and get the projection's barycentric coordinates.

No, I'm not exactly raytracing, only doing GJK collision - finding the closest point on a simplex (as well as closest feature). Clearly replacing the direction d with the triangle's normal wouldn't be the best way to find the coords?

This is the way bullet is doing this:
http://www.continuousphysics.com/Bullet/BulletFull/btVoronoiSimplexSolver_8cpp-source.html#l00330

Again without cross products, just a bunch of dots. I can follow the line of thought until "float d4" (line 00351), drawing the representations on a piece of paper (triangle and point included).

Sorry for not knowing the name of the method, but thanks for your help and explanations. I do think I understand Cramer's rule now.

I'm glad I could be of help. You say you need to project the point on the triangle? I'll see if I can help, if I understood what you wanted correctly.

We have the point p and the triangle(v1,v2,v3). The distance between these two can be found with the following:

First we need to define a plane. You can do this from the triangle with by first making two vectors:
e1 = v3 - v2
e3 = v2 - v1
The cross product between these will give the perpendicular vector n,which we normalize(cross is cross product between two vectors, || v || would be the length of v):

           cross(e3,e1)     n = ----------------         ||cross(e3,e1)||

A plane is defined as [ x y z d ] and the components of n give the x,y and z. To find out d, we have the equation(where v is one of the points in the triangle, v1 or v2 or v3):
v . n + d = 0
from which we can get:
d = -( v . n)

Now the point p is a point that is not on the plane and the point q can be a point that is on the plane and closest to p. The vector from q to p is perpendicular to the plane and of the form a*n. If n is a unit vector then the distance from p to q is a. The distance will be negative if p is on the back side of the plane.

You can see from this picture(which I made using my incredibly paint skills) that the vector p is the sum of q and a*n:

q + a*n = p

From this we can get:

a = p . q + d

So a is the distance between the point and plane. So to find out the closest point on that plane, lets call it b(p and n are vectors, d is scalar):

b = p + (-a*n)
-> b = p - (p . n +d)*n


So that point b will be the point where your point projects to the triangle. Unless I'm completely wrong, that is. Maybe that can help you more? It's been a while since I did this actively so I hope I remember it right and explained decently.

Thank you again, but I just found what I have been looking for:
http://softsurfer.com/Archive/algorithm_0104/algorithm_0104.htm

Using (a x b) x c = (a . c) b - (b . c) a one can solve p = s * u + t * v with only some dots (and one division) where u and v are the edges from v1 of the triangle.

The whole formula is shown under "Computing Parametric Coordinates".

Perhaps someone could shed some light over the difference between parametric coordinates and barycentric coordinates?

You can actually perform the projection and the barycentric coordinate calculation in one fell swoop. If you form a 2D subspace using the basis vectors v2 - v1 and v3 - v1, then you perform the projection into this subspace using the formula:

(A^TA)^-1A^T(d - v1)

Where A is a 3x2 matrix whose columns are the aforementioned basis vectors, and d is the point you're projecting. This will result in a 2D vector (x,y) where x is the barycentric coordinate of v2, y is the barycentric coordinate of v3, and 1 - x - y is the barycentric coordinate of v1. You then just check to make sure that 0 ≤ x/y ≤ 1. Hopefully I didn't miss anything.

Quote:

Original post by henksgu This is the way bullet is doing this: http://www.continuousphysics.com/Bullet/BulletFull/btVoronoiSimplexSolver_8cpp-source.html#l00330 Again without cross products, just a bunch of dots. I can follow the line of thought until "float d4" (line 00351), drawing the representations on a piece of paper (triangle and point included).

That's basically my code, from pages 141-142 of my book (with changes by Erwin to extract information needed for contact resolution). I cover this code/algorithm in over 6 pages in the book so it's hard to do it justice in a post here.

That particular (optimized) version of the code is the result of starting with an unoptimized code and using Lagrange's identity

Dot(Cross(a, b), Cross(c, d)) = Dot(a, c) * Dot(b, d) - Dot(a, d) * Dot(b, c)

to remove a number of cross products and replace them with dot products. This also means that the resulting code is much less intuitive, as individual dot products (such as "d4") now do not really "mean" anything geometrically.

So, yeah, without the derivation of the preceeding pages in the book, it will be pretty hard to understand the code. That's just the way it is. Sorry. Better understanding can be had by starting with the unoptimized version of the code (given on pages 139-140).