This project has moved. For the latest updates, please go here.

SAT Update

May 29, 2009 at 8:34 PM

Hi everyone,

SAT is basically complete for the moment. Please test it. Download the latest source code to test.

Please compare with the DistanceGrid Collider the update times, quality of the collisions, jittery, number of arbiters, penetration, bodies collapsing into each other, and anything else you can think of.

Some things to note are -

  • SAT doesn't like subdivided edges. So rectangles should only have 4 edges. Comment out all the lines in Vertices.CreateRectangle that don't multiply by .5 on both width and height. (should be that way in the latest source already, but be sure to change it back to use the DistanceGrid)
  • Concave polygons are not supported by SAT. I am working on an automatic polygon decomposition algorithm.
  • SAT likes a slightly lower BiasFactor (try 0.3f or 0.25f if it seems jittery)

Please share your detailed findings on this discussion. The more detail the better able I am able to find and fix problems.

May 29, 2009 at 10:10 PM

Does the subdivide problems with polygon verts as well?

I wuld assume it did, I just wish it didnt

And what would be a good way of getting around it for subdividing polygons, or it unneccesary?

May 29, 2009 at 11:13 PM

@tlegion: It basically just doesn't like edges that share the same normal. It acutally makes Farseer much more memory effeicent, in usage and in bandwidth. I still have to do some Xbox360 testing and tuning but both those features only should help the 360's performance. Can I ask why subdivision is important for you?

May 29, 2009 at 11:51 PM

Little update on the results I'm getting on my own tests. I focused on the pyramid sample in both the simple and advanced (multithreaded) samples.

With IsFixedTimeStep and SynchronizeWithVerticalRetrace false I tried to acheive the maximum number of bodies/geoms while maintaining a stable simulation.

Here are my numbers with the AdvancedSamples implementation.

Geoms      Aribters       FPS        Narrow         Total

 467           900+         75-100      5ms          14-16ms

 539          1000+         55-65       5.8ms       17-18ms

May 30, 2009 at 12:02 AM

Looks nice.

I also tried it out and just by looking at the performance panel I could see that there were only a small difference between distance grid and SAT. Basically same performance, but with SAT, we have the posibility of on-the-fly geom creation.

Just a quick note: could you revert the changed you made to the samples? :) I see some of your test code inside of it (and the change in screen resolution). Need to keep it clean for the upcoming release.

May 30, 2009 at 12:11 AM

My bad, I think I checked it in twice, once after I start trying to stress it out!

May 30, 2009 at 12:28 AM

Well efficiency is most important,

But for me its important because the way i edit and save polygon geometrys is I supply a list of vertices

trhough point and click stuff

then i give them to a new MapPiece which saves that list THEN it subdivides the edges and creates the geomtry and body etc.

This makes it so i can save a few points then when i want to load em in they just have to subdivide the points.

Its much easier to click the points that are iportant and not have to worry about clicking every single point in between and having inconsisten spacing

It also saves space for serialization, were talking serious kb's here

I can adapt easily but I will wait to see the documentation to see the limitations are and what not.

May 30, 2009 at 2:25 AM

@tlegion: Well currently the only benefit from using SAT is the ability to do real time geometry and possibly a slightly more stable simulation. So feel free to continue to use the DistanceGrid.

May 30, 2009 at 4:47 AM

I'm kinda busy this weekend but ill see if i can test it. Since i am expecting a large (probably 100-300 at times) number of geoms it is paramount that i have the fastest running simulation.Thanks!

May 30, 2009 at 6:50 PM

Hi Matt, subdivision is also important for me, otherwise, to integrate 2.1 into my main project I will have to get my artists to manually divide their polygons or write the algorithm myself  ;)

By the way, congratulations on adding a very nice SAT algorithm to Farseer. On the fly geoms is a massive step forwards.

May 30, 2009 at 7:11 PM

@roonda - I have made a similar algorithm to subdivide but i think its the fact that they are the same that SAT doesnt like, so i think any form of subdivision is gone which is kindof upsetting to me, hopefuly I am terribly incorrect

May 30, 2009 at 7:57 PM

Subdivision is still included in the engine, and will continue to be so. SAT is just another narrow phase algorithm that we decided to include in FP - You still have the distance grid as the default narrow phase collider.

SAT could come in handy for those who wants to create geometries on the fly, but without the posibility of preloading them. Take a game like worms - You can destroy the terrain in the game, but currently this would be hard to do in FP because it takes some time to precompute the distance grid. With SAT (when using SAT), this delay is completely gone.

Of course you could still make a worm game with the distance grid. Just split up the terrain into smaller chunks so that the distance grid only covers a small geometry. - Doing this automatic can prove difficult, and because we want our users to be able to create great game with least amount of effort, SAT was simple the naturel way to go. If you’re in the progress of developing a game there is no need to change anything, you still have the same features as you have in 2.0.1, but we hopefully made it easier for those who are creating a game that is not possible with the current version of our physics engine.

Jun 1, 2009 at 7:38 AM
Edited Jun 1, 2009 at 1:34 PM

Apologies for any confusion.  When I said "subdivision is important to me", I actually meant "Auto Divide is important, because I want to use SAT but I already have lots of concave polygons :)".

@tlegion: As I understand it, subdivision is particularly unhelpful for SAT because it just means more edges which more more axis tests.

Jun 1, 2009 at 8:39 AM

o, well i guess i could use auto-divide on rough polygons instead of subdivide, if it divides it up into managable triangle geoms then i dont see the need for more vertices as it wont even be one geometry, atleast thats how i percieve auto-divide at this point