A few things I found while integrating the engine

[snake5]

First of all, I'd like to say that after having tried Chipmunk Physics engine, I think it works nicely and can be considered as serious competition to Box2D. I tried using this engine because I didn't really like the direction Box2D was taking with fixtures and somewhat complex C++'ish constructs and automatic joint destruction.

Since I've made lots of small modifications to it, I cannot easily submit a patch. So I thought I'd just let you know about a few things I found out.

1. I could not find a way to override the memory handling functions. This is something I really wanted to have myself (for memory debugging and statistics, mainly) so I implemented it myself but there's one unclear thing about it - whether something in the code relies on the calloc's ability to fill memory with 0's.

2. There were some places where infinity floating point values were generated through calculations (division by 0). This throws FP exceptions (which I wouldn't like to have during normal operation) so I had to patch them up.
- cpPolyShapeSegmentQuery, cpPolyShape.c, line 126
- cpBBSegmentQuery, cpBB.h, lines 97 and 103

3. There's some things I found highly useful in Box2D that I didn't find here and implemented them myself: category/mask filtering (this would save the need to convert categories/masks to ANDed combo enumeration flags, which is what essentially layers appear to be) and different angular/linear damping settings for each body (for fine-tuning ragdoll dynamics).

4. I was used to Box2D's clockwise polygons so I changed the vertex order around everywhere. This calls for some #define setting that would make the code accept reversed vertex order.

5. There's a bug in cpvslerp. When "omega" is a tiny value (v1 and v2 are almost the same, but not exactly the same), it makes "denom" too big and sometimes generates a wrong result. I changed "if(omega){" to "if(omega>0.001f){" and "return v1;" to "return cpvlerp( v1, v2, t );", it appears that the bug has been fixed (at least just enough to avoid generating completely wrong values).

P.S. The game that I was testing Chipmunk with: http://www.youtube.com/watch?v=iNT75-2HrCA

[slembcke]

Hey! Good list. It's always good to get some feedback.

1) While you can't change the memory handling functions at runtime, you can configure it to use something different at compile time. That is where the defines for cpcalloc(), cprealloc(), and cpfree() are located. It makes it pretty trivial to make Chipmunk work with the Boehm GC or work with memory allocated by language bindings for instance. I've tried to make sure that I don't rely on cpcalloc() to zero the memory anymore, but it's not well tested. Most Chipmunk memory can be allocated and freed externally too. Instead of using new/free (or the rare alloc), you use init/destroy instead on externally managed memory. Only internal structs like arbiters, arrays and buffers would me managed by Chipmunk then. Does that make more sense? It's not really documented. I assumed the few people that wanted to know would just end up finding it. (great documentation strategy huh?)

2) So this is perhaps misunderstanding on my part, but what is the problem with this? Divide by zero to get infinity is in the spec and pretty handy. With most ABIs, it's even invalid to turn FP exceptions on (unless you turn them back off before making system calls). This came up too. Near as I can tell, all modern CPUs with an FPU (ARM, x86 with SSE, PPC, etc) seem to handle "exceptional" math with infinities and subnormals without a performance hit.

3) Actually, this came up recently (can't find the thread...). I have it on my TODO list to allow for compile time re-definition of the fast collision filtering. Basically you'd just need to give it a struct and a short inline function. In the past, I didn't really get why it was useful to have separate mask/category bits. They encode more or less the same information except redundantly, and let you set up contradictory rules. A could say that it collides with B, and B could say that it doesn't, so what would happen? Anyway, ODE uses the same rules and I looked up the explanation in their docs a couple months ago. Basically it said just that, you could encode the same information into a single bitmask, but it's not as easy or clear. It also lets you say objects of the same type don't collide, one thing you can't do with a single bitmask. ODE let you handle the contradiction yourself which makes sense, Box2D did not which always confused me. Anyway... long explanation.

Per-body properties: I've thought about adding a number of per-body attributes like that. Just haven't gotten around to it mostly. You can do it yourself by defining custom integration functions, but the documentation for those currently just says to look at the Planet demo. <_< Doing so isn't always convenient either.

4) This actually drives me nuts... It was a mistake I made very early on with Chipmunk because I started with a bunch of the polygon collision code I had before Chipmunk. It didn't really occur to me that it was "backwards" from the way that regular math-ish stuff works until other people had already been using the code for a while. I'm getting a little tired of adding negatives into just about every piece of code I write that deals with polygons. Now that you bring it up, it makes me think I should make a compile time define to pick the winding direction and deprecate the current direction. Will put it on the TODO list to think more about.

5) I recently fixed a really boneheaded bug in cpvslerp() too. -_- Basically I had never tested it with non-normalized vectors, and had only used it once or twice anyway. Oops. The regular trick for handling very small angular differences is to lerp them yeah (the curve is so small it's pretty much linear anyway). I'll put that on the TODO list too.

Awesome looking game so far. Reminds me of a 2D version of Max Payne (except without the ).

[snake5]

Thanks for the detailed answers!

1) The main point of changing the allocator was statistics/debugging (hence the need for a complete solution) but it's nice to know that it's possible to manually allocate memory for most external things too. This might come in handy if I decide to implement separate pools for bodies, shapes, constraints to improve memory access.

2) Ah, it's just my way of developing things - I like to reserve FP exceptions for the cases when I've done something bad unintentionally to know about it as quickly and precisely as it's possible.

3) Nice to hear it's in the TODO list. As for the "A collides with B, B doesn't collide with A", I'd say the boolean AND approach makes sense to me - both bodies should approve the collision for it to happen. As for my specific use case, . With layers, I figured I'd have to assign layer to each intersecting category combo. I probably wouldn't hit any limits anyway but if we consider queries too, things don't quite come together intuitively in my mind. But perhaps it's just me. As for per-body properties, I considered the approach you suggested but I had my user data pointer already occupied by a contact listener. Modifying the engine seemed to be and actually was much easier.

4) Ah, well, I fixed the last bug I had with the changed polygon order just now (circle2poly) so I could give a list of places to visit and what I changed there to make things work. Cannot guarantee if it's all perfect though, it's largely a "works for me" kind of a fix, some features might stay unpatched too.

5) Heh, looks like all bugs will be found here now.

By the way, after doing more testing, I found a few more things I wanted to ask about so here goes:

6) Raycasts (segment queries) don't detect if starting point is inside the shape. Didn't consider the feature really useful until I lost it in the transition, found out some core features depend on it. Since I'm at crossroads here, I could assume that using a second query for the point is an option to consider. So the question is, is it faster than the combined method Box2D has? I have lots of raycasts so revisiting options might prove useful...

7) Segment shape appears to be the 2D equivalent of a capsule, which is why it might prove useful in simulating characters like the ones I have in the game. I used to have 2 spheres and a box in Box2D for that. Apart from the issue with segment-segment intersections, everything appears to behave just as I expected and I'd really like to stick to this configuration. So I'm interested if there's any chance in getting segment-segment intersection tests implemented anytime soon or at least some pointers on how to do that with what I have; I'm not that good with collision math above basic separating axis tests myself.

[slembcke]

6) I guess the issue is that Chipmunk calculates the collision normal of the ray, which isn't well defined if the ray start is inside of a shape. IIRC starting a segment query inside of a segment shape can cause weird results, colliding with the inner parts of the end caps. PhysX works this way too (or at least it used to, dunno about now), which consoled me a little.

You can get a decent approximation of the normal using a nearest point query and using that to get the minimum separating distance. That at least tells you the shortest path to the surface anyway. Probably what people would want in most cases. I have no idea what the difference in performance would be though if I did both at once. Nearest point queries are relatively cheap by themselves.

I used to have a note in documentation about how the result of starting inside a shape was undefined... Now it's just undocumented. Whoops. :p

7) Loooooong story. Basically generating good collision points for colliding segments is hard. I've tried and failed many times now. Recently I've been working on getting GJK based collisions working in Chipmunk. It has a few nice benefits (like polygons with a radius too, makes swept collisions a step closer, will allow for smoothed terrain collisions), and in order to use the GJK output I need to solve the same colliding line segment problem. I feel like I'm very close, but it's like leveling a table by sawing the legs. Fix one weird special case and it creates another. The table still wobbles and it gets shorter until I give up for a while. :-\ Not really the answer you were looking for though.

[snake5]

6) The collision normal could be 0;0 - that feels kind of appropriate for normalized vectors as an invalid value since that value silently disables most kinds of subsequent calculations. Though the normal isn't really important for me since I use those raycasts mostly to get the intersection position or just to see if there's some free space in a path.

7) Seems like it's hard, yes. But what if it's assumed that only segments with a positive radius value could be capable of colliding with each other? In practice radius should be properly sized too (between 0.1 and 10 m). I've got some ideas myself which I'll try to implement anytime soon but I'd like to find out about many different possibilities, in case any of them doesn't work good enough or at all.

[slembcke]

6) So I've considered returning (0, 0) before actually. That's sounding like more of a better idea hearing it again from somebody else. Is that what Box2D does? If you check for (0, 0) and want to use the nearest point trick to estimate a normal, you can still always do that. Honestly any change is fair game as the behavior is currently undefined anyway. I'll have to think about this a little more...

7) You would not be able to have a negative radius no. Supporting "negative" shapes is rather tricky in general, though occasionally useful. Maybe I'm making it to hard for myself, but I'm trying to reuse the same calculation for *all* colliding manifolds. You can check out the GJK branch if you want to fiddle around with it. It's completely undocumented and not quite done though... That might be a really bad place to plunge in.

[snake5]

6) Not sure if it's what Box2D does but I've had no problems with using a 0;0 vector as the value for an "invalid normalized vector" - normalized vectors are most often used in dot product/multiplication operations, both of which are properly handled this way (returning 0). Not expecting reciprocals of the dot product because they would equal the inverse length of the other vector in case the data is valid.

7) Thanks for the tip, I'll have a look at it.

[slembcke]

6) Yeah, I've done that in my own code a few times and it's been handy. I guess it would *probably* be fine in general too. It shouldn't be too hard to extend the segment query functions to do a parallel point query check. I'll look into it.

[LegoCylon]

I needed segment-to-segment collision support, too and ended up just writing it myself. I sent my changes into Scott but never heard back so I don't know if he had a problem with them or not. They've been working well for me so far.

Here's my patch to cpCollision.cpp:

Index: cpCollision.cpp
===================================================================
--- cpCollision.cpp (revision 198)
+++ cpCollision.cpp (working copy)
@@ -126,6 +126,64 @@
}
}

+static int
+seg2seg(const cpShape* shape1, const cpShape* shape2, cpContact* con)
+{
+ cpSegmentShape* seg1 = (cpSegmentShape *)shape1;
+ cpSegmentShape* seg2 = (cpSegmentShape *)shape2;
+
+ cpVect v1 = cpvsub(seg1->tb, seg1->ta);
+ cpVect v2 = cpvsub(seg2->tb, seg2->ta);
+ cpFloat v1lsq = cpvlengthsq(v1);
+ cpFloat v2lsq = cpvlengthsq(v2);
+ // project seg2 onto seg1
+ cpVect p1a = cpvproject(cpvsub(seg2->ta, seg1->ta), v1);
+ cpVect p1b = cpvproject(cpvsub(seg2->tb, seg1->ta), v1);
+ // project seg1 onto seg2
+ cpVect p2a = cpvproject(cpvsub(seg1->ta, seg2->ta), v2);
+ cpVect p2b = cpvproject(cpvsub(seg1->tb, seg2->ta), v2);
+
+ // clamp projections to segment endcaps
+ if (cpvdot(p1a, v1) < 0.0f)
+ p1a = cpvzero;
+ else if (cpvdot(p1a, v1) > 0.0f && cpvlengthsq(p1a) > v1lsq)
+ p1a = v1;
+ if (cpvdot(p1b, v1) < 0.0f)
+ p1b = cpvzero;
+ else if (cpvdot(p1b, v1) > 0.0f && cpvlengthsq(p1b) > v1lsq)
+ p1b = v1;
+ if (cpvdot(p2a, v2) < 0.0f)
+ p2a = cpvzero;
+ else if (cpvdot(p2a, v2) > 0.0f && cpvlengthsq(p2a) > v2lsq)
+ p2a = v2;
+ if (cpvdot(p2b, v2) < 0.0f)
+ p2b = cpvzero;
+ else if (cpvdot(p2b, v2) > 0.0f && cpvlengthsq(p2b) > v2lsq)
+ p2b = v2;
+
+ p1a = cpvadd(p1a, seg1->ta);
+ p1b = cpvadd(p1b, seg1->ta);
+ p2a = cpvadd(p2a, seg2->ta);
+ p2b = cpvadd(p2b, seg2->ta);
+
+ int num = 0;
+
+ if (!circle2circleQuery(p1a, p2a, seg1->r, seg2->r, nextContactPoint(con, &num)))
+ --num;
+
+ if (!circle2circleQuery(p1b, p2b, seg1->r, seg2->r, nextContactPoint(con, &num)))
+ --num;
+
+ if (!circle2circleQuery(p1a, p2b, seg1->r, seg2->r, nextContactPoint(con, &num)))
+ --num;
+
+ if (!circle2circleQuery(p1b, p2a, seg1->r, seg2->r, nextContactPoint(con, &num)))
+ --num;
+
+ return num;
+}
+
// Find the minimum separating axis for the give poly and axis list.
static inline int
findMSA(const cpPolyShape *poly, const cpPolyShapeAxis *axes, const int num, cpFloat *min_out)
@@ -362,8 +420,8 @@
NULL,
NULL,
circle2segment,
+ seg2seg,
NULL,
- NULL,
circle2poly,
seg2poly,
poly2poly,

[snake5]

I did a quick test on it and for my needs, it currently appears to be good enough. Would it be OK if I used it in my game?