How is the Persistent Manifold Area computed in Bullet ?

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
Dani3L
Posts: 28
Joined: Tue Jun 30, 2009 6:56 am
Location: Switzerland
Contact:

How is the Persistent Manifold Area computed in Bullet ?

Post by Dani3L »

Hello,

I am studying the implementation of the persistent contact manifold in Bullet in the file btPersistentManifold.cpp.

At some point, if the contact cache is full, we want to keep the new contact point, the contact point with the deepest penetration depth and then, we choose the points that maximize the area of the manifold. As we can see in the btPersistentManifold::sortCachedPoints() method, the magnitude of the cross product is used to compute an area. For instance, we have the following code :

Code: Select all

 if (maxPenetrationIndex != 0)
 {
      btVector3 a0 = pt.m_localPointA-m_pointCache[1].m_localPointA;
      btVector3 b0 = m_pointCache[3].m_localPointA-m_pointCache[2].m_localPointA;
      btVector3 cross = a0.cross(b0);
      res0 = cross.length2();
}
According to me, we can use the cross product magnitude to compute the area of a triangle ABC using the cross product AB^AC. However, in the above code, we have four different points ABCD and we compute the cross product AB^CD. What kind of area this gives us ?
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: How is the Persistent Manifold Area computed in Bullet ?

Post by Dirk Gregorius »

I would guess this is the area of a convex quadrilateral. See here under "vector formulas":
http://en.wikipedia.org/wiki/Quadrilateral
Dani3L
Posts: 28
Joined: Tue Jun 30, 2009 6:56 am
Location: Switzerland
Contact:

Re: How is the Persistent Manifold Area computed in Bullet ?

Post by Dani3L »

Thanks a lot for your answer, I didn't know this formula.

According to the Wikipedia page, this formula is used to compute the area of a convex quadrilateral ABCD using the cross product AC^BD where AC and BD are the two diagonals of the quadrilateral. However, I am not sure I understand why we are allowed to use this formula in the case of the contact manifold because we don't know if the quadrilateral is convex and we don't know which points to use for the diagonals. Am I missing something here ?
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: How is the Persistent Manifold Area computed in Bullet ?

Post by Dirk Gregorius »

I totally agree. This is exactly the same conclusion I made when I looked into this code. My guess was that the construction adds the points in such a way that the formula will work, but I never verified this. You can simply add an assert there. Build the cross product between the main diagonal and the manifold normal and check if the two two other points are on different sides. If this triggers there might be a potential bug.
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: How is the Persistent Manifold Area computed in Bullet ?

Post by Erwin Coumans »

Indeed, it is only a heuristic to maximize the area under the convex hull of the points,
it is not the actual area under the quadrilateral so it might not always be the optimal solution.

There is a better way to compute the maximal area of the convex hull, see gContactCalcArea3Points and calcArea4Points,
but it is slower and I didn't notice improvement so I left it disabled.
https://code.google.com/p/bullet/source ... nifold.cpp

If you have improvements, please let me know (in the Bullet forum, not general discussion)
Erwin
Post Reply