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.
Barycentric coordiantes and voronoi solver
-
- Posts: 133
- Joined: Wed Jul 27, 2005 1:05 pm
- Location: Berkeley, CA
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
Re: Barycentric coordiantes and voronoi solver
The projection of the origin into the triangle plane happens here:jmc wrote: 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.
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);
There are two cases in which the simplex solver will terminate the Bullet GJK implementation:jmc wrote: 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.
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
-
- Posts: 133
- Joined: Wed Jul 27, 2005 1:05 pm
- Location: Berkeley, CA
Re: Barycentric coordiantes and voronoi solver
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.Erwin Coumans wrote: The projection of the origin into the triangle plane happens here:
http://www.continuousphysics.com/Bullet ... ource.htmlCode: 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);
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.Erwin Coumans wrote:There are two cases in which the simplex solver will terminate the Bullet GJK implementation:jmc wrote: 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.
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.
-
- Posts: 23
- Joined: Mon Jun 27, 2005 4:30 pm
- Location: Los Angeles
Re: Barycentric coordiantes and voronoi solver
These calculations are from my book, where I describe in detail where the terms come from (in several steps, one more optimized than another).jmc wrote: 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.
-
- Posts: 133
- Joined: Wed Jul 27, 2005 1:05 pm
- Location: Berkeley, CA
Re: Barycentric coordiantes and voronoi solver
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 wrote: These calculations are from my book, where I describe in detail where the terms come from (in several steps, one more optimized than another).
-
- Posts: 23
- Joined: Mon Jun 27, 2005 4:30 pm
- Location: Los Angeles
Re: Barycentric coordiantes and voronoi solver
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.jmc wrote: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.
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
Re: Barycentric coordiantes and voronoi solver
Bullet detects the case where the origin lies within the tetrahedron in VoronoiSimplexSolver.cpp here:Christer Ericson wrote: 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.
Code: Select all
00468 if (!pointOutsideABC && !pointOutsideACD && !pointOutsideADB && !pointOutsideBDC)
00469 {
00470 return false;
00471 }
Which GJK implementation requires more information from the simplex solver, and how does it use this exactly, JMC ?
Erwin
-
- Posts: 133
- Joined: Wed Jul 27, 2005 1:05 pm
- Location: Berkeley, CA
Re: Barycentric coordiantes and voronoi solver
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.Erwin Coumans wrote: Which GJK implementation requires more information from the simplex solver, and how does it use this exactly, JMC ?
Erwin
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.
-
- Physics Researcher
- Posts: 22
- Joined: Mon Jun 27, 2005 9:28 am
- Location: Helmond, Netherlands
Re: Barycentric coordiantes and voronoi solver
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.jmc wrote: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.Erwin Coumans wrote: Which GJK implementation requires more information from the simplex solver, and how does it use this exactly, JMC ?
Erwin
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.
Cheers,