Performance of SAT algorithm

Topics: Developer Forum, User Forum
Aug 10, 2009 at 6:48 PM

I'm very new to Farseer but so far I am in awe of how easy it is to use and how powerful it is.  Great job!

I have a question, really just to check my understanding of the SAT narrow phase collision algorithm.  I was playing with the advanced samples number 7, wind and explosions, with a base pyramid size of 14.  Using distance grid I noticed that over time the pyramid collapses itself.  I am interested in making a stacking game so clearly this isnt ideal.

I read that using SAT fixes this, so I switched to SAT in this sample and then I get around 2 fps performance.  Performance is ok with a base of 6 or so, deteriorates gradually until at a base size of 14 I can see the demo takes 16+ ms in the narrow phase collision.

I also read that SAT doesnt like vertices and DG does, and the manual says if I use SAT I need to use Vertices.CreateSimpleRectangle, although I dont see that anywhere in the demo.  Is it normal for SAT to struggle with this pattern of 100+ stacked objects?  Are there any optimisations that I could make if I make the assumption that all my game objects will be convex?





Aug 11, 2009 at 1:48 AM
Edited Aug 11, 2009 at 1:50 AM

The pyramid should stand perfectly fine when you don't touch it too much. The collapsing happens because the size of the grid cell size in the distance grid is too high. Creating the geometries with a lower grid cell size should solve that problem.

In the case of SAT; yes, it does indeed require less polygons. It only needs the real outline of the polygon, so for a rectangle you need 4 points. Distance grid adds more points that needed to get a more accurate grid.
SAT grows linearly in time consumed with the number of points, so a small amount of points is way better and probably the cause of your performance issues.

Instead of:

_rectangleBody = BodyFactory.Instance.CreateRectangleBody(32, 32, 1f);
_rectangleGeom = GeomFactory.Instance.CreateRectangleGeom(_rectangleBody, 32, 32);

You will have to do it like this:

_rectangleBody = BodyFactory.Instance.CreateRectangleBody(32, 32, 1f);
_rectangleGeom = GeomFactory.Instance.CreatePolygonGeom(PhysicsSimulator, _rectangleBody,Vertices.CreateSimpleRectangle(32, 32), 0);

Update: A new SAT implementation that is more efficient than the current one should be out soon. I've not been able to get a hold of Matthew for the past weeks, so he must be quite busy. Keep an eye out for the release.

Aug 11, 2009 at 6:50 AM

For using the SAT, I added a quick peice of code to Vertices.cs. As opposed the Subdivide, which is helpful for the distance grid, I made a Simplify for the SAT, which looks for extrantanious linear vertices within a bias and eliminates them. This seems to help the performance of the SAT as well as the accuracy (especially if you use the Texture->Verticies like I am).

Aug 11, 2009 at 5:49 PM

There should be a Simplify in the Vertices class. It was implemented together with the subtraction/addition of vertices. I've not used it myself (user contribution), but it should be there.

Aug 11, 2009 at 11:58 PM
Edited Aug 12, 2009 at 12:21 AM

Wow, that there is... I feel rather silly. It's very similar to what I wrote, except I didn't find it because it was a static, and I was just looking through the intellisense for the instance.

Edit: Actually, looking at that one, it works either by distance with a bias or complete linear vertices. It doesn't have support for any variance in linearity which is what I wanted, because the Texture->Vertices can't always get a rectangle even perfectly rectangular. It ussually leaves at least one vertice in the middle of a side or something that is one pixel out and so not exactly linear with the rest.