Extending Box2D Concepts to Polygon2D

[crashlander]

In Erin Catto's paper: 'Fast and Simple Physics using Sequential Impulses', he uses boxes.
I am interested in extending this to 2d convex polygons with more than 4 sides for a simple 2d physics engine I'm developing.

I've read through the code and understand it all for the most part. However, I'm looking for ideas on how to extend the clipping and coherence concepts to non-box bodies.

clipping: Is there anything that needs to be done differently when using non-boxes? Or is the clipping algo the same regardless of the number of sides?

coherence: Any suggestions on how to implement the "ContactID's" for many sided polygons? I'm thinking of just using some simple arrays.

Any other tips you can give for moving the concepts in this paper to many-sided convex polygons would be appreciated.

Thanks.

[Erin Catto]

It ought to be straightforward. You should store the verts in local space in CCW order. The edge number is implicit: 1, 2, 3, ..., n, where n is the number of verts. Contact IDS are just the two edge numbers that produce the verts. The two edges could come from either polygon (1,1), (1,2), (2,1), or (2,2).

The clipping algorithm is the same: incident edge versus reference edge side edges. For the side edges, just imagine the reference edge belongs to a box and do the same clipping.

Before all that you need to use the SAT for convex polygons. To start with, you can just use the edge normal for each edge of both polygons. Later you my try to optimize this by storing hints in the Arbiters.

I think it would be very cool if you achieve this. Let us know about your progress.

[crashlander]

Hi Erin, thanks for the response.

I've started digging into this and still have some small questions.

For box/box I can see how the contactId can be made up of the two edge numbers that produce the verts, but with poly-poly, the clipping will most likely not be done by an edge of the poly but rather by "artificial" side vectors perpendicular to the reference edge. So, the question is what do I use for the contactId in this situation. The only thing I could think of was to create some additional indexes for these clipping edges and use those.

Also, in your gdc presentation(slide 15 or so) you breifly talk about applying weightings to prefer one axis over another. How exactly are you "weighting" your objects. Could you expand a little on this topic?

Thanks again for your help.

[Erin Catto]

I see two choices for contact ids:

- use the adjoining edge ids.
- give each vertex an edge id corresponding to an edge that is perpendicular to the xy-plane.

There is no one right way of defining contact ids. They just have to be unique and consistent.

Now consider the weighting technique used in Box2D. Look at this section of Collide.cpp:

Code: Select all

	axis = FACE_A_X;
	separation = faceA.x;
	normal = dA.x > 0.0f ? RotA.col1 : -RotA.col1;

	if (faceA.y > 1.05f * separation + 0.01f * hA.y)
	{
		axis = FACE_A_Y;
		separation = faceA.y;
		normal = dA.y > 0.0f ? RotA.col2 : -RotA.col2;
	}

The code first chooses FACE_A_X as the separating axis. If FACE_A_Y provides a significant increase in separation, then it is chosen as the best separating axis so far. The factor 1.05 requires a 5% increase and 0.01 * hA.y guards against very small separation magnitudes.

[crashlander]

Ok, that's kinda the idea i had for contactID's Seems pretty straight forward.

Thanks for the info on the weighting. I saw that code but didn't realize that was what you meant by weighting. Makes sense now.