some questions on the collision detection method of box2d

[chensb]

Hi. I'm very interesting in Box2D's underline mechanism. now I've looked through the two slides(GDC 2007) and have some questions:
As I know, the engine doesn't create any contact points until the two objects have collided, rather than test the distance of the two to prevent colliding. Is my comprehension correct?
At the stage of Box-Box Clipping Setup, is it all right to select any of the two as the reference/incident face?
How does it find the right contact point? i guess it ascertain a point from the incident face to approximate the real one, but i don't know it clearly.
Any suggestion will be appreciated. thanks!

[Dirk Gregorius]

Is my comprehension correct?

Yes. Please note that Erin added CCD lately which does take the distance into account.

At the stage of Box-Box Clipping Setup, is it all right to select any of the two as the reference/incident face?

Yes, but for the warmstarting it is better if the incident face and reference don't flip between two frames. This will give different contact IDs and you will loose the accumulated impulse. This issue is addressed through the some weighting. Look for relative_error and global_error when the axis of minimum penetration is searched

How does it find the right contact point?

Once you have identified the incident and reference face you create a polygon from the incident face (for a box simply create a polygon from the four corner vertices) and clip it against the *side* faces (planes) of the reference face. The vertices of this *clipped* polygon are then tested against the reference face. You just keep points below it. Don't clip against the reference face as well. So your contact points are the vertices of the *clipped* polygon below the reference face (plane). For the box-box example this can create up to eight contact points which need to be reduced to usually four points (this is an empirical number known to work well with iterative solvers). There is some code in the ODE which does this reduction or look at the article of A. Moravansky in GPG 4 which describes another method. Of course you can use all eight points which is even better. The reduction to four points is only because of performance considerations.


HTH,
-Dirk

[chensb]

Thank you, dirk. Let me draw a picture to follow you(I don't know how to draw a rectangle in gimps so it looks somehow ugly...).

First question, is CCD stand for the depth of penetration?

Second. We start from figure 1. The box parallel to the ground is marked as reference. Next frame, if we come to the stage of figure 2, it is properly detected and the reacting force(or impulse) is rightly computed. however, if
we come to the stage of figure 3 computation might be wrong since the incident box nearly flips over the reference one. then we need some method to correct it( warm starting or weighting?).

Third. Two box are overlapping. we clip edges of the incident box by AABB of the reference one(Figure 4), resulting a polygon(Figure 5). because only points below the reference box survive, the two red points are selected. Right? So we can get up to 8 contact points one box in 3D world( or 4 in 2D).
I also wonder what's article A.

Thanks again.

[Dirk Gregorius]

CCD stands for Continuous Collision Detection.

Did you look at the slides of Erin? Please look at his presentation from 2006 - 2008 and study them thoroughly! There are sketches similar to yours which should answer your questions. Also for learning purposes look at Box2D_Lite which is much easier to understand. It can be found at the same address or comes with the slides! I try to look later at your sketch, but from a first view it doesn't look correct.

http://www.gphysics.com/downloads

[chensb]

CCD stands for Continuous Collision Detection.

Did you look at the slides of Erin? Please look at his presentation from 2006 - 2008 and study them thoroughly! There are sketches similar to yours which should answer your questions. Also for learning purposes look at Box2D_Lite which is much easier to understand. It can be found at the same address or comes with the slides! I try to look later at your sketch, but from a first view it doesn't look correct.

http://www.gphysics.com/downloads

Thank you for your help! I've figured it out. here comes another question: we can apply bias impulse to prevent from penetration, however this method would also introduce extra momentum. How can we correct it? It seems "split impulse" could solve it, but what on earth is it? thanks.

[Dirk Gregorius]

Right, the bias (aka Baumgarte stabilization) adds energy. The split impulse basically solves for the velocity and position error separately sharing the same Jacobians and effective mass, so the position error is not added to the momentum. I think Erwin added the split impulse lately to Bullet. There also exist versions of Box2D using the split impulse (you might ask on the Box2D forum where to look for it).