Barycentric coordiantes and voronoi solver

[John McCutchan]

Q1) I've been studying up on barycentric coordinates of a triangle, and from what I've read it's only defined if the point P lies in the plane of the triangle. I can't seem to find where in the code you project the origin onto the plane of the triangle.

Q2) When you have a full simplex, and you can't reduce it down to a smaller one, you just give up. Don't some uses of the gjk algorithm require you to calculate the lambda values even if you end up with a full simplex? An example that comes to mind is closest points on objects.

[Erwin Coumans]

Q1) I've been studying up on barycentric coordinates of a triangle, and from what I've read it's only defined if the point P lies in the plane of the triangle. I can't seem to find where in the code you project the origin onto the plane of the triangle.

The projection of the origin into the triangle plane happens here:
http://www.continuousphysics.com/Bullet ... ource.html

Code: Select all

00405     // P inside face region. Compute Q through its barycentric coordinates (u,v,w)
00406     float denom = 1.0f / (va + vb + vc);
00407     float v = vb * denom;
00408     float w = vc * denom;
00410         result.m_closestPointOnSimplex = a + ab * v + ac * w;
00414         result.SetBarycentricCoordinates(1-v-w,v,w);

Q2) When you have a full simplex, and you can't reduce it down to a smaller one, you just give up. Don't some uses of the gjk algorithm require you to calculate the lambda values even if you end up with a full simplex? An example that comes to mind is closest points on objects.

There are two cases in which the simplex solver will terminate the Bullet GJK implementation:

1) No reduction is done, because the origin is inside the tetrahedron. This means means the two convex objects are penetrating. The GJK outerloop will break.

2) Degenerate simplex, 3 or more points that are co-linear. This will also terminate the GJK loop. Degeneracy can also be caused by cancellation, as Gino stated before, this can be a problem in cases with large difference in feature sizes. If this is really a problem, some improvements can be made by re-ordering calculations to remove this cancellation effect.

In both cases either the current seperating distance is within the chosen collision-margins there will be a closest point result (penetration) reported, or a seperate user-provided penetration depth algorithm will be used.

Erwin

[John McCutchan]

The projection of the origin into the triangle plane happens here:
http://www.continuousphysics.com/Bullet ... ource.html

Code: Select all

00405     // P inside face region. Compute Q through its barycentric coordinates (u,v,w)
00406     float denom = 1.0f / (va + vb + vc);
00407     float v = vb * denom;
00408     float w = vc * denom;
00410         result.m_closestPointOnSimplex = a + ab * v + ac * w;
00414         result.SetBarycentricCoordinates(1-v-w,v,w);

Sorry, I didn't phrase my question properl. I'd like to understand the geometry behind your calculations. I understand the geometry behind d1 & d2 but what is the geometry behind d3,d4,d5,d6, vc, vb, and va. A reference to where you developed this formula would be appreciated.

Q2) When you have a full simplex, and you can't reduce it down to a smaller one, you just give up. Don't some uses of the gjk algorithm require you to calculate the lambda values even if you end up with a full simplex? An example that comes to mind is closest points on objects.

There are two cases in which the simplex solver will terminate the Bullet GJK implementation:

1) No reduction is done, because the origin is inside the tetrahedron. This means means the two convex objects are penetrating. The GJK outerloop will break.

This is the case I was asking about, some of the gjk algorithms still attempt to compute some values even when the simplex couldn't be reduced. Examples from solid, DT_Convex.cpp::common_point, DT_Convex.cpp::closest points. I don't how accurate these values will be even if the system of equations was solved, because like you say, the origin is inside the tetrahedron, and the objects are in penetration.

[Christer Ericson]

Sorry, I didn't phrase my question properl. I'd like to understand the geometry behind your calculations. I understand the geometry behind d1 & d2 but what is the geometry behind d3,d4,d5,d6, vc, vb, and va. A reference to where you developed this formula would be appreciated.

These calculations are from my book, where I describe in detail where the terms come from (in several steps, one more optimized than another).

[John McCutchan]

These calculations are from my book, where I describe in detail where the terms come from (in several steps, one more optimized than another).

I currently can't afford your book, but I do plan on picking it up in the near future. Could you tell me, do you provide an explanation on how to project the origin onto a tetrahedron? Some of the gjk algorithms still require it, even in the case where the origin is inside the tetrahedron. Currently bullet's implementation doesn't handle that case.

[Christer Ericson]

Could you tell me, do you provide an explanation on how to project the origin onto a tetrahedron? Some of the gjk algorithms still require it, even in the case where the origin is inside the tetrahedron. Currently bullet's implementation doesn't handle that case.

What you're asking for is a special case of finding the point Q of a tetrahedron ABCD closest to a given query point P (where, in your question, P is the origin). Yes, I cover the general problem in Section 5.1.6 (and again in Section 9.5.2). When P lies inside ABCD, P itself is the closest point Q; this case falls out directly based on how the testing is performed so I'm a bit surprised to hear you say the Bullet implementation does not handle it. If you can provide a test case of a query point and four tetrahedron vertices for which you consider the code broken, I'm sure Erwin can verify if the code has a problem, and if so, fix it.

[Erwin Coumans]

When P lies inside ABCD, P itself is the closest point Q; this case falls out directly based on how the testing is performed so I'm a bit surprised to hear you say the Bullet implementation does not handle it.

Bullet detects the case where the origin lies within the tetrahedron in VoronoiSimplexSolver.cpp here:

Code: Select all

00468    if (!pointOutsideABC  && !pointOutsideACD && !pointOutsideADB && !pointOutsideBDC)
00469          {
00470                  return false;
00471          }

So this case is handled by Bullet by detecting it, and based on this result the GJK loop terminates. Then penetration depth calculation is performed and a penetration information is reported. So in this case, the barycentric coordinates of the origin/P are not calculated, because GJK will terminate anyway.

Which GJK implementation requires more information from the simplex solver, and how does it use this exactly, JMC ?

Erwin

[John McCutchan]

Which GJK implementation requires more information from the simplex solver, and how does it use this exactly, JMC ?
Erwin

The whole reason I brought this up was because SOLID uses the values even in the case that the simplex is full. Look at SOLIDs common_point and closest_points in DT_Convex.cpp.

Clarification: Both of those functions bail out of the gjk loop when there is a full simplex, but then they call gjk.compute_points which use the barycentric coordinates.

[gino]

Which GJK implementation requires more information from the simplex solver, and how does it use this exactly, JMC ?
Erwin

The whole reason I brought this up was because SOLID uses the values even in the case that the simplex is full. Look at SOLIDs common_point and closest_points in DT_Convex.cpp.

Clarification: Both of those functions bail out of the gjk loop when there is a full simplex, but then they call gjk.compute_points which use the barycentric coordinates.

In case of a full simplex the Johnson routine returns the barycentric coordinates of the origin (four parameters corresponding to the four vertices of a tetrahedron). You need these to compute a common point (In case of an intersection the closest points coinicde.) How to compute a common point or a pair of closest points from the barycentric coordinates is explained on page 141 of my book. In case you want to return a boolean only or want to compute the penetration depth, you do not need the barycentric coordinates of the origin for a full simplex. Hope this helps.

Cheers,