Page 1 of 1

How is the Persistent Manifold Area computed in Bullet ?

Posted: Fri Nov 30, 2012 12:46 pm
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 ?

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

Posted: Fri Nov 30, 2012 4:58 pm
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

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

Posted: Sun Dec 02, 2012 7:11 pm
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 ?

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

Posted: Mon Dec 03, 2012 6:04 pm
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.

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

Posted: Tue Dec 04, 2012 6:52 pm
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