SAT collision detection with concave polygons

Topics: User Forum
Feb 27, 2010 at 9:23 PM
Edited Feb 27, 2010 at 9:38 PM

First off, I have just recently started messing around with Farseer in XNA; with the eventual intention of building a game around it. So far I have been very impressed with how easily Farseer can be integrated into a project, and how well it seems to work in general; keep up the good work. :)

I have, however, run into a few different issues; the most recent being collision detection between between circles and concave polygons. In particular I have a static polygon which is in the shape of an 'L'; also in the scene are various circles bouncing around, all of which is contained in a larger box made from 4 rectangles. For the most part, everything works fine, the problem comes if a ball is headed towards the inner corner of my 'L' shaped polygon. When that happens a collision is reported long before the circle makes contact with the polygon. On top of that, the collision response is abnormal; instead of bouncing away, the circle seems to slow down, and then suddenly jump through the polygon over to the far side.

This only happens when I am using SAT collision (with the default collision everything acts as I would expect). I am using SAT collision because my polygons are destined to have their vertices manipulated to allow for objects that change shape dynamically. It is my understanding that SAT is the only collision method that allows the vertices of a geometry to be altered without having to reconstruct the geom (possibly every frame).

I have read in some old posts that SAT does not support concave collisions, but the current documentation states that if you supply it with a concave polygon, it will jsut divide it into convex polygons for the colision detection. If this is not goign to work, is there a better way to achieve what I want to do?

Thanks for any help or advice. :)

Mar 6, 2010 at 7:17 PM

So... that's a "no" then?

Apr 9, 2010 at 9:58 PM

I'd like to know the answer to this one as well.

Apr 10, 2010 at 2:46 PM

I don't think we ever implemented automatic decomposition for SAT. In the new 3.0 source there are 2 polygon decomposition algorithms included and both should work with 2.x. One thing to keep in mind is if your changing the vertices a lot then you will need to do a complete decomposition every frame. That can start giving you performance problems if your using a really complex concave polygon. Let me know if this helps you.

Jul 11, 2010 at 3:34 PM
Edited Jul 11, 2010 at 3:38 PM

Just wanted to say I ran into this problem as well. Took your advice and tried moving the decomposers over to 2.1.3.


The Earclip decomposer seems to work well, but the Bayazit decomposer seems to have some flaws in it. I noticed the Bayazit decomposer usage is actually commented out in the 3.0 source, so I'm wondering if that's a known issue.


Anyway, porting it over was pretty simple; just had to move over Earclipdecomposer.cs, LineTools.cs, Math.cs, Settings.cs, and SimplifyTools.cs and it worked.


Here's the code I ended up writing to create a group of geoms from one, using the decomposer:


// points are assumed to already be moved relative to centroid
Vertices vertices = new Vertices(_points.Select(x => x.ToVector()).ToList());
//vertices.SubDivideEdges(10);  // no need to do this with SAT now.

var subdivisions = EarclipDecomposer.ConvexPartition(vertices);
foreach (var subdivision in subdivisions)
    // need to offset all points by their new centroid or the geom factory 
    // will just re-centre them all at 0,0 and make a jumbled mess
    Vector2 centroid = subdivision.GetCentroid(); 
    var g = GeomFactory.Instance.CreatePolygonGeom(Level.Simulator, body, subdivision, centroid, 0, 0);
    g.Tag = this;