Box2D Feature Points - Need clarification

[cycloverid]

I've been looking at the Box2D code and slides, and I'm confused about how features are created for contact points. This probably requires a simple explanation, but this is my current understanding:

So there are 4 feature points allocated for each contact point, right? In the code I identified 4 per contact. In the slides it only shows two per contact point. Or is it 4 per contact set and somehow and I don't have a good grasp of what the code is doing? Also, the slides show the contact points before they are projected, is this intentional? In the code they are projected, which makes sense because you also store the separation.

Here is the picture I'm referring to. I added the projected points in red.

boxes.JPG

Would these be correct? Does the left contact point belong on the reference face, or am I wrong? For c1, Box 1's feature is edge 2. This however is not the reference face. I'm totally confused. In the descriptions in the slides it seemed clear that we were generating contact points via projections onto the reference face. ( Intuitively I would think feature points would follow suit ).

[Dirk Gregorius]

1) In 2D there are at maximum two points. In 3D there can be more (e.g. up to eight points for two boxes). Since it is usually sufficient to have only four points you reduce the set of contact points. An article about this can be found in GPG IV

2) What you refer to as projection is that Erin pulls the contact points onto the surface of the reference face. This is good in 3D in order to cull points as mentioned above, but in 2D in has no effect. So if you only deal with 2D you can ignore this, but keep it mind when you want to extend to 3D...

I think you are mixing features and contact points. In Erin terminology each contact point is created as the intersection of two features (here edges). In your picture c1 is the intersection of e2 from box1 and e3 from box2. This is used to create contact IDs which are later used to match new contacts with older ones in order to warmstart the solver. Also note the the intersecting edges don't need to come necessarily from both boxes. Contact c2 is the intersection of e3 and e4 exclusively from box2.

HTH,
-Dirk

[Erin Catto]

There are 4 edge ids per contact id. Only two of them are used, while the other two are invalid. The reason there are 4 edge ids instead of 2 is so that I can distinguish these two cases:
1) One edge from each box.
2) Two edges from the same box.

[cycloverid]

Thanks very much for your responses. If I could have a quick moment to review

Firstly, by edge ids, you mean feature points, correct?

That makes perfect sense that you would need to use 4 feature points per contact, since with the current system you wouldn't be able to tell which id went on which box. Since you use a char (not unsigned ), one suggestion I have is perhaps using negative numbers to indicate A, and positive to indicate B, and 0 could indicate none.

I am also to understand that projections are not needed for the contact points in 2D (which is what I'm using). I can see how this works now. My code used projections so I was kinda locked into that line of thinking.

If I could entertain the idea of extending this system to arbitrary convex polygons:

So I compute the minimum axis using SAT just like Box2D. This yields separation and my first contact point. Now I test the other vertex on the incident edge to see if it is also penetrating the reference object / reference edge. Now, referring to the picture above once again, how would you be able to tell which edge to clip the second incident vertex to? Since we're not dealing with boxes anymore this seems more complicated to me.

I have drawn a picture to illustrate the ideas I'm presenting. The dark black dots indicate contact points ( and whose connected edges represent feature edges - two per ).

features.JPG

The circled picture is my main area of question. I have drawn the potential contact points in red green and blue. Red would indicate that we bound the second incident vertex to the reference edge ( as discussed in the slides - or was that because we were limited to boxes? ). The green one indicates that we actually clip the whole incident edge against the adjacent edge of the reference edge. The blue one is not valid, but I drew it anyway

If indeed we chose the green point, how would you tell whether or not to clip against the adjacent edge? ( since scenarios occur as depicted in the other 3 drawings where clipping is not necessary ).

If red, what are the two feature points since it lies along only one edge?

[Erin Catto]

No they are edge ids. Every contact point is formed from the intersection of two edges. You are right, I could use a sign bit. It seemed simpler at the time to code it using 4 bytes.

In your drawing I would use the red and black points. If the overlap was very small, then the red point would be a good approximation. The large overlap case doesn't matter much because it is transitional (short lived). So to get the red point, just clip the incident edge against the side planes of the reference edge. You can get the normal for the side plane using direction of the reference edge.

I'm now favoring a different contact id that seems to be doing well in my tests. The problem with the 2-edge id is that you get some flip-flop if two vertices are close. This comes up when stacking identical boxes in perfect alignment.

The new contact id uses:
byte 1: the reference edge id
byte 2: the incident edge id
byte 3: the vertex number on the incident edge (0 or 1)
byte 4: flip (sign bit)

I think this is easier to understand and it seems to be more robust. I suppose I could use a bit array and easily squash this down into a byte or two.