Box2D contact caching question

[oztune]

Hey,

I've been playing around with the Box2D source code and reading the slides.

One (of the few) things that kind of confuses me is the contact caching method. Could someone please explain in more detail how it works?

More specifically I was wondering:
- When should contacts be stored? when should they be removed?
- How many contacts does the cd system find every timestep?
- What is the underlying reason for this whole mechanism?

Thanks!
- Oz

[Erwin Coumans]

Hey,
I've been playing around with the Box2D source code and reading the slides.
One (of the few) things that kind of confuses me is the contact caching method. Could someone please explain in more detail how it works?

I don't know about Box2D, but the work is likely derived from the older Bullet's btPersistentManifold implementation.

More specifically I was wondering:
- When should contacts be stored? when should they be removed?

Each new contact gets added in local space (just like ordinary constraints get stored in local space, for example point to point constraint). The constraint gets removed when it is invalid: each frame, the points get transformed into worldspace, and if the distance exceeds a threshold it can be removed. Also, a reduction/removal can happen when too many contacts are cached. In practice in 3D, only 4 points get good quality.

- How many contacts does the cd system find every timestep?

This approach only needs to add a single contact point each timestep. It can be extended to add multiple contact points, by pertubing/rotating the object around the separating normal. This give a single shot solution at the cost of lost performance.

- What is the underlying reason for this whole mechanism?

Performance and quality. It allows to calculate multiple contact points almost at the cost of a single closest point calculation.
Unlike a clipping method for polyhedra, this contact caching method works for general convex objects (implicit cylinders and so on). And by caching the contacts, you can also cache additional information, for example friction information and previous frames solver solution. This allows 'warm starting': starting the iterative impulse based solution with previous frames solution, instead of with a zero impulse.

Hope this helps,
Erwin

[Erin Catto]

Erwin has given a good description of how Bullet works, however Box2D works differently.

The primary reason for contact caching in Box2D is to improve the performance of the iterative impulse solver by using the solution of the previous time step. This is called warm starting. It allows the solution to be improved over several time steps, decreasing CPU cost and improving stability.

Box2D uses the separting axis test (SAT) for collision detection. It performs clipping to give up to 2 contact points in one shot (in 3D you could get many more). Based on this clipping, I generate contact point ids, similar to an article in Game Programming Gems 4. I match these ids against old contact points. If a match is found, I recover the stored impulses from the previous step.

- Contact point ids and impulses should be stored in the arbiters at the end of each time step. Arbiters exist as long as the objects touch.
- In Box2D, each box-box contact has 0, 1, or 2 points
- The underlying reason is to improve the solution generated by iterative solver.

[oztune]

@erwin:

Thanks for the reply. Btw, cool new theme. The header picture kinda hurts my eyes, and the sidebar overlaps the site's body here on my 1024x786 firefox workspace, but nice overall.

@erin
That def clears it up. The next thing I was meaning to ask is about clipping those points. I tinkered a bit with Box2D to show me the contact points in different penetration positions (that sounds kinda wrong ). The power point covers it very vaguely and it's a little confusing to me:

a) how you get the other contact point
b) how you decide which object's edge to use as the contacts' positions

Thanks,
Oz

[Dirk Gregorius]

Look at Erin's presentation and the code. The algorithm works like this:

1) Find the axis of minimum penetration. The associated edge (face) with this axis becomes your reference edge. In order to find the minimum axis you run a SAT test for all possible separating axis. In 2D these possible axis are the "edge" (face) normals of the boxes. Totally four face normals, and two from each box.

2) After you identified the reference edge you need to identify the incident edge (face). There is a function called ComputeIncidentEdge() which does this for you. I hope you already looked at the code.

3) Now you clip the incident edge against the side edges (planes) of the reference edge. There is a function called ClipSegmentToLine() in the code. The result are your contact points. Keep points on the negative side of the reference face...


The best way to understand the clipping process is to draw two or three different case and perform the algorithm by hand...



HTH,
-Dirk

[oztune]

The best way to understand the clipping process is to draw two or three different case and perform the algorithm by hand...

Sounds like a good idea. Thanks for the explanation, I will give all this a try.

- Oz

[oztune]

This is getting a lot clearer now, after toying with it for a bit.
I was wondering, is this a standard method for finding collision points given the collision normal?

What I was doing until now (in 2d) is finding the closest vertex/vertices in the direction of the normal on bodyA and the closest on bodyB in the opposite direction....

How does this method compare to the one used in box2d? Is there a standard method?

Also, can this be extended for other convex shapes?