# Physics Simulation Forum

 Page 1 of 1 [ 9 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Barycentric coordiantes and voronoi solverPosted: Thu Sep 22, 2005 3:29 am

Joined: Wed Jul 27, 2005 1:05 pm
Posts: 133
Location: Berkeley, CA
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.

Top

 Post subject: Re: Barycentric coordiantes and voronoi solverPosted: Sun Sep 25, 2005 2:43 pm

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3825
Location: California, USA
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.

The projection of the origin into the triangle plane happens here:
http://www.continuousphysics.com/Bullet ... ource.html
Code:
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);

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.

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

Top

 Post subject: Re: Barycentric coordiantes and voronoi solverPosted: Mon Sep 26, 2005 3:45 am

Joined: Wed Jul 27, 2005 1:05 pm
Posts: 133
Location: Berkeley, CA
Erwin Coumans wrote:
The projection of the origin into the triangle plane happens here:
http://www.continuousphysics.com/Bullet ... ource.html
Code:
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.

Erwin Coumans wrote:
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.

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.

Top

 Post subject: Re: Barycentric coordiantes and voronoi solverPosted: Sat Oct 01, 2005 6:15 am

Joined: Mon Jun 27, 2005 4:30 pm
Posts: 25
Location: Los Angeles
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.

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

Top

 Post subject: Re: Barycentric coordiantes and voronoi solverPosted: Tue Oct 04, 2005 3:23 am

Joined: Wed Jul 27, 2005 1:05 pm
Posts: 133
Location: Berkeley, CA
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).

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.

Top

 Post subject: Re: Barycentric coordiantes and voronoi solverPosted: Sat Oct 08, 2005 8:58 pm

Joined: Mon Jun 27, 2005 4:30 pm
Posts: 25
Location: Los Angeles
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.
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.

Top

 Post subject: Re: Barycentric coordiantes and voronoi solverPosted: Sun Oct 09, 2005 2:00 am

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3825
Location: California, USA
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.

Bullet detects the case where the origin lies within the tetrahedron in VoronoiSimplexSolver.cpp here:
Code:
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

Top

 Post subject: Re: Barycentric coordiantes and voronoi solverPosted: Tue Oct 11, 2005 12:21 am

Joined: Wed Jul 27, 2005 1:05 pm
Posts: 133
Location: Berkeley, CA
Erwin Coumans wrote:
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.

Top

 Post subject: Re: Barycentric coordiantes and voronoi solverPosted: Tue Oct 11, 2005 9:17 am
 Physics Researcher

Joined: Mon Jun 27, 2005 9:28 am
Posts: 20
Location: Helmond, Netherlands
jmc wrote:
Erwin Coumans wrote:
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,

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 9 posts ]

#### Who is online

Users browsing this forum: No registered users and 1 guest

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ BULLET PHYSICS LIBRARY USERS    General Bullet Physics Support and Feedback    Release Announcements    Applications, Games, Demos or Movies using Bullet PHYSICS AUTHORING TOOLS, SERIALIZATION AND STANDARDS    Physics authoring tools, serialization, standards and related topics RESEARCH AND DEVELOPMENT IN COLLISION DETECTION & PHYSICS. Don't post Bullet support questions here!    Research and development discussion about Collision Detection and Physics Simulation    Links, Papers, Libraries, Demos, Movies, Comparisons       Non-technical forum and license/patent discussion    Career Opportunities