Another Broad Phase (Selective Sweep)

Topics: Developer Forum
Nov 14, 2007 at 6:52 AM

I have created a new broad phase algorithm that steals a lot of its design from sweep and prune. It gives a massive speed improvement. For more information here is my post on it:
http://groups.google.com/group/physics2ddotnet/browse_thread/thread/b4857badbdd6e7a2
I was running the system with over 30,000 objects in the demo and it was still updating at a slow but respectable speed.

I tried to adapt my code to farseer here it is:
 
    public sealed class SelectiveSweep 
    {
        sealed class StubComparer : IComparer<Stub>
        {
            public int Compare(Stub left, Stub right)
            {
                if (left.value < right.value) { return -1; }
                if (left.value > right.value) { return 1; }
                return ((left == right) ? (0) : ((left.begin) ? (-1) : (1)));
            }
        }
        sealed class Wrapper
        {
            public LinkedListNode<Wrapper> node;
            public Geom geom;
            public bool shouldAddNode;
            public float min;
            public float max;
            Stub xBegin;
            Stub xEnd;
            Stub yBegin;
            Stub yEnd;
            public Wrapper(Geom body)
            {
                this.geom = body;
                this.node = new LinkedListNode<Wrapper>(this);
                xBegin = new Stub(this, true);
                xEnd = new Stub(this, false);
                yBegin = new Stub(this, true);
                yEnd = new Stub(this, false);
            }
            public void AddStubs(List<Stub> xStubs, List<Stub> yStubs)
            {
                xStubs.Add(xBegin);
                xStubs.Add(xEnd);
 
                yStubs.Add(yBegin);
                yStubs.Add(yEnd);
            }
            public void Update()
            {
                AABB rect = geom.AABB;
                //if it is a single point in space
                //then dont even add it to the link list.
                shouldAddNode = rect.Min.X != rect.Max.X || rect.Min.Y != rect.Max.Y;
 
                xBegin.value = rect.Min.X;
                xEnd.value = rect.Max.X;
 
                yBegin.value = rect.Min.Y;
                yEnd.value = rect.Max.Y;
            }
 
            public void SetX()
            {
                this.min = this.xBegin.value;
                this.max = this.xEnd.value;
            }
            public void SetY()
            {
                this.min = this.yBegin.value;
                this.max = this.yEnd.value;
            }
        }
        sealed class Stub
        {
            public Wrapper wrapper;
            public bool begin;
            public Scalar value;
            public Stub(Wrapper wrapper, bool begin)
            {
                this.wrapper = wrapper;
                this.begin = begin;
            }
        }
 
        static StubComparer comparer = new StubComparer();
 
        static bool WrapperIsRemoved(Wrapper wrapper)
        {
            return !wrapper.geom.IsDisposed;
        }
        static bool StubIsRemoved(Stub stub)
        {
            return !stub.wrapper.geom.IsDisposed;
        }
 
        PhysicsSimulator physicsSimulator;
        List<Wrapper> wrappers;
        List<Stub> xStubs;
        List<Stub> yStubs;
 
        public SelectiveSweep(PhysicsSimulator physicsSimulator)
        {
            this.physicsSimulator = physicsSimulator;
            this.wrappers = new List<Wrapper>();
            this.xStubs = new List<Stub>();
            this.yStubs = new List<Stub>();
        }
        public void AddGeom(Geom item)
        {
            Wrapper wrapper = new Wrapper(item);
            wrappers.Add(wrapper);
            wrapper.AddStubs(xStubs, yStubs);
        }
        public void Clear()
        {
            wrappers.Clear();
            xStubs.Clear();
            yStubs.Clear();
        }
        public void RemoveExpiredBodies()
        {
            wrappers.RemoveAll(WrapperIsRemoved);
            xStubs.RemoveAll(StubIsRemoved);
            yStubs.RemoveAll(StubIsRemoved);
        }
 
        /// <summary>
        /// updates all the nodes to their new values and sorts the lists
        /// </summary>
        private void Update()
        {
            for (int index = 0; index < wrappers.Count; ++index)
            {
                wrappers[index].Update();
            }
            xStubs.Sort(comparer);
            yStubs.Sort(comparer);
        }
 
        /// <summary>
        /// Finds how many collisions there are on the x and y and returns if
        /// the x axis has the least
        /// </summary>
        private bool ShouldDoX()
        {
            int xCount = 0;
            int xdepth = 0;
            int yCount = 0;
            int ydepth = 0;
            for (int index = 0; index < xStubs.Count; index++)
            {
                if (xStubs[index].begin) { xCount += xdepth++; }
                else { xdepth--; }
 
                if (yStubs[index].begin) { yCount += ydepth++; }
                else { ydepth--; }
            }
            return xCount < yCount;
        }
 
        public void Detect()
        {
            Update();
            DetectInternal(ShouldDoX());
        }
        private void DetectInternal(bool doX)
        {
            List<Stub> stubs = (doX) ? (xStubs) : (yStubs);
            LinkedList<Wrapper> currentBodies = new LinkedList<Wrapper>();
            for (int index = 0; index < stubs.Count; index++)
            {
                Stub stub = stubs[index];
                Wrapper wrapper1 = stub.wrapper;
                if (stub.begin)
                {
                    //set the min and max values
                    if (doX) { wrapper1.SetY(); }
                    else { wrapper1.SetX(); }
 
                    Geom geom1 = wrapper1.geom;
                    for (LinkedListNode<Wrapper> node = currentBodies.First;
                        node != null;
                        node = node.Next)
                    {
                        Wrapper wrapper2 = node.Value;
                        Geom geom2 = wrapper2.geom;
                        if (wrapper1.min <= wrapper2.max && //tests the other axis
                            wrapper2.min <= wrapper1.max)
                        {
                            OnCollision( geom1, geom2);
                        }
                    }
                    if (wrapper1.shouldAddNode)
                    {
                        currentBodies.AddLast(wrapper1.node);
                    }
                }
                else
                {
                    if (wrapper1.shouldAddNode)
                    {
                        currentBodies.Remove(wrapper1.node);
                    }
                }
            }
        }
        private void OnCollision(Geom geom1, Geom geom2)
        {
            if (!geom1.body.enabled || !geom2.body.enabled)
            {
                return;
            }
 
            if ((geom1.collisionGroup == geom2.collisionGroup) &&
                geom1.collisionGroup != 0 &&
                geom2.collisionGroup != 0)
            {
                return;
            }
 
            if (!geom1.collisionEnabled || !geom2.collisionEnabled)
            {
                return;
            }
 
            if (geom1.body.isStatic && geom2.body.isStatic)
            { //don't collide two static bodies
                return;
            }
 
            if (((geom1.collisionCategories & geom2.collidesWith) == Enums.CollisionCategories.None) & ((geom2.collisionCategories & geom1.collidesWith) == Enums.CollisionCategories.None))
            {
                return;
            }
 
            Arbiter arbiter = physicsSimulator.arbiterPool.Fetch();
            arbiter.ConstructArbiter(geom1, geom2, physicsSimulator.allowedPenetration, physicsSimulator.biasFactor, physicsSimulator.maxContactsToDetect, physicsSimulator.maxContactsToResolve);
 
            if (!physicsSimulator.arbiterList.Contains(arbiter))
            {
                physicsSimulator.arbiterList.Add(arbiter);
            }
            else
            {
                physicsSimulator.arbiterPool.Release(arbiter);
            }
        }
    }

Coordinator
Nov 14, 2007 at 4:40 PM
Cool, BioSlayer.

I haven't read your post yet or dug into the code but I'm really looking forward to it.

Are there any gotchas to look out for.


Thanks again for the code!
Nov 15, 2007 at 3:53 AM
Um it may not compile since it was just an eyeball port.

The only thing that got me was all my stress tests were no longer stressing.

I made a new one just to watch it in action:
http://www.youtube.com/watch?v=LMegkL1RD5s
Nov 15, 2007 at 11:23 AM
If I understood the algorithm, the big improvement here is that you no longer perform the List<>".Contains" which could really slow down the previous algorithm. Do you know how much of a win you received by selecting an axis? It seems that this might not be worth it in the general case. I suppose it could be a win for some applications where there are lots of overlaps in one extent but not the other... and moreover, that the extents which has more overlaps fluxuates from time to time.

But looking at your youtube demo, I might guess the majority of your extent overlaps occur on the x-axis (since you have falling bodies in the y)... if that is true, you might as well just assume that is the case for your application...

Just arm-chair thinking.

The more I think about it - it seems that broadphase collision detection is really application specific. I wonder if a physics engine shouldn't just allow the user to supply his/her own broadphase solution (as well as provide a few typical options like s&p).


Coordinator
Nov 15, 2007 at 11:42 AM
Very impressive video BioSlayer. Wow.

I'm not sure my engine could do that even with the quick broad phase. I think something else might become a bottleneck. Never know unless I try I guess. Hopefully next week I can get this rolled into the enigne and do some testing.

-Jeff
Nov 15, 2007 at 5:19 PM
The win with the selection is that the axis with the least number of collisions is always ran. Without the selection of the axis the algorithm ran just as well as SAP. With the selection of the axis it really kicks butt.

The selection code is linear so it scales to O(n) its not a bottle neck and the profiler confirms this. It’s only about 1% while the rest of the detection takes about 25%. Basically I’m saying the overhead to do automatic selection of the best case is not worth worrying about. But don't take my word for it, try it out yourself.

I do agree that some kind system should be incorporated to allow people to select the broad phase they want. This option has been in my code since the beginning of Physics2D.Net.

Sonofdaedalus: would you be interested in making a frame coherent version of this algorithm?


Nov 15, 2007 at 6:25 PM
That's cool. I'll give it a try. I think its good to have a handfull of options for the broadphase. A guy here in the office swears by spatial hashing which is what I think is used in the Chipmunk physics engine...

I'll also pop by your website (later tonight) and see if I can find your email address and send you the code for the frame-coherent version. You've already got some stress tests and profiling going on, so I would be curious to see how well it performs.

-Andy
Coordinator
Nov 15, 2007 at 7:38 PM
Edited Nov 15, 2007 at 7:38 PM
BioSlayer when is the next release of your engine and what features, besides the new broadphase collider, will it have. Just curious.

With Farseer, one of my primary goals is simplicity both in code and usablity. While I agree, pluggable broadphase colliders would be nice I will probably opt for 1 good broadphase collider. Sometimes less is more when it comes to keeping it simple.

It looks like your SelectiveSweep collider might be the one I go with. Still need to test it out and make sure it works ok with my code,
Nov 16, 2007 at 5:35 AM
The next release won’t be containing much and I would like to release it soon.
For my next release I already have a newer and improved bitmap to polygon algorithm that allow multiple polygons in an image to be extracted. The immobile objects in the ball machine video were extracted from an image file. I have already updated the engine to be able to run on XNA and the 360 (someone else tested this for me). Someone has brought up collision ignoring and collision event ignoring, so I’m working on some code for that. After I get everything tested I’ll do the release.

The release after that I’m thinking I may incorporate object freezing (once I can make heads or tails of box2D) I plan to add all the joints stuff he has added and update the math for the solver. OR make a new solver for the newest box2D algorithm if it proves too different then what my current solver is.
Nov 16, 2007 at 6:29 PM
BioSlayer - I went to Physics2D.Net and found what I think is your address - you should have the code.

Andy.
Nov 17, 2007 at 6:13 PM
First off I would like to point out an error with the FCSAP.

There is a line that is
while (iCurr != iMax)
This fails and causes an index out of range exception to be thrown when indexing with iCurr.
I changed it to this to stop the exceptions:
while (iCurr < iMax)

I’m getting worse performance with FCSAP then with brute force, mainly because it’s giving me a lot of false positives. It’s even giving me some false negatives so something is obviously not working right.
Nov 17, 2007 at 10:54 PM
Thats not good.

I'm assuming you are seeing these issues after porting FCSAP to your physics2d? Could it be something in the translation?

I'm surprised that the "while (iCurr != iMax) " is producing an error for you since the line above it initializes iCurr to be "iMin + 1" and since iMin should always be guaranteed to be less than iMax going into the loop, it should be fine as originally coded. My guess is that your application is feeding FCSAP AABB's having "min==max" which is admittedly unexpected... I don't think tested that.

I'm also surprised you are seeing worst performance. I've modified every farseer demo to stress test and my own results show FCSAP to be the best by at least 7-15%. Basically, I just keep bumping up the number of objects up in the demos until the other methods can't handle it any more, and I watch FCSAP still go at interactive framerates (the stacked pyramid is a special case as its performace ultimately depends on the narrow-phase once the objects all stack).

I also have not seen any false positives or "any" false negatives. For example, in the collision groups demo, I have bumped up the number of objects such that it's quite crowded and all the objects are hitting and colliding and responding fine....

Given my experience and yours - I can only guess that it is either the translation to your engine or a specific use case that is the issue. Maybe if you really are passing in AABB's with "min==max" cases, that might be causing some issues. I'm not sure.

The only other thing I can think of is, if you have modified FCSAP to add a small "delta" to help the caching for stacked objects - if you did this wrong, you might see what you are describing (I know, because I added it and did it wrong the first time).

In any case, if you want any help, let me know.

Andy.

Nov 18, 2007 at 11:36 PM
The problem with the while statement is caused by particles which is the (min == max) case. In your algorithm when an objects min is equal to its max then the min is inserted after the max.

I have yet to dig deep into the code to find out why I’m getting false negatives and positives. I didn’t have to change much to get it to run, just the add, remove, and collision handling code. As well as the Geom to Body search and replace and the names for the bounding box. So I may just try to port it again to see if it resolves the issues.
Nov 18, 2007 at 11:44 PM
To show what I'm seeing, I've posted a stress test on youtube.

I entered BruteForce, SAP, SAPFC, and SelectiveSAP into the test.

The Test:
The test consisted of a modification to Farseer's collision-groups demo (demo5). I expanded the resolution and added 1,250 geometries. I also added some logic to apply a random force to every object. To ensure that we were really looking at broadphase stress, I made all the circle geometries belong to a group that did not collide with each other. Since the collision group check is currently performed by all broadphase candidates, it effectively shows broadphase performance without convoluting narrow-phase performance in with the test.

The results:
- BruteForce and SAP were non-starters. They never got above 0 frames per-second with this many objects.
- Both SAPFC and SelectiveSAP had a good starting frame-rate. SAPFC typically was about 100-200 frames higher than SelectiveSAP. When all spheres get their initial random force impules, both algorithms take a hit in framerate, however...
- SAPFC usually shows the quickest recovery and the highest frame rates (Often in the 200-350 range upon recovery). Let it run such that objects gradually come to a halt, and the more that do, the frame-rate goes up to approach starting conditions. Overall, it appeared to me that SAPFC performs the best.
- SelectiveSAP appeared a pretty close contender, however, it doesn't seem to recover as well as SAPFC and can lag about 100 or so frames in best conditions. Also, it appears that it can get into states where it never recovers. I've seen it hit sub-0 frame-rates and never come back.

I've posted a result of a run for each here on youtube:
SelectiveSAP: http://www.youtube.com/watch?v=OZXqTYhYAM0
SAPFC: http://www.youtube.com/watch?v=zRYoSICmak0

I also went ahead and turned on collisions for everything and ran the tests again. It looks like SAPFC still continues to perform better, but the framerates seem to be effected more heavily by the narrowphase and the results are move convoluted:
SelectiveSAP: http://www.youtube.com/watch?v=tSy0yuFynnA
SAPFC: http://www.youtube.com/watch?v=uaeEltdJnNY

All of this said, this is just one test application - and how often do you have random spheres flying in all directions? Also, I think since the results were actually somewhat close, SelectiveSAP has the very nice feature of not coming into the game with all the maintenance/cacheing required - I think that is a real plus. I would probably consider adding the ability to "pre-set an axis without performing a best axis detection" as an additional option.












Coordinator
Nov 19, 2007 at 2:03 AM
I'm finally getting a chance to look into this more.

First, a note: I discovered the diagnostics that get displayed in the demos when you hit F1 were very incorrect. They were suppose to show the time in ms of each of the primary simulator functions: broadphase, narrowphase, .. etc. I was doing some arithemetic wrong so the numbers were wrong. They should be correct now so they should be a pretty good for comparison between collision techniques.

I've integrated the SAPFC version and found it performs really well with a bunch of objects floating around the environment. I had close to 2000 spheres floating around with pretty good framereates.

However, if you turn gravity on and let the spheres fall to the ground things fall apart very fast.

With just 200 spheres setup so that narrow phase collisions would not occur between them, if I turn on gravity and let all the spheres fall to the ground SAPFC comes to a crawl. In this particular case, brute force performed quite a bit better.

sonofdaedalus, do you get similar results when you turn gravity on?

My next step is to test SelectiveSAP under similar scenarios.

sonofdaedalus, did the verison of SelectiveSAP require any modifications from what BioSlayer posted to get it to run in Farseer? If so would you mind posting the code you are using? It would save me some time.

-Jeff


Nov 19, 2007 at 5:04 AM
The SelectiveSAP was fairly easy to get running. I just grabbed it as is and changed the "Detect" method to "Run" as the previous SAP (though, I suggest "Update" as a better public method name). Also, SelectiveSAP didn't have the RemoveDispose and RemoveRemove calls which I added but did not bother to implement them (sorry). So really, other than maybe a syntax issue, I believe that is all I ended up doing.

Regarding SAPFC and objects hitting the ground with gravity... I did not test this too much. When I did, I had a good number of objects and a good frame-rate until the objects came into contact with the floor (or stacked objects). I passed this off as a side-effect of the ping-pong effect and then, upon fixing that, I attributed the slowness to the cost of narrow phase for so many objects. Since I couldn't run brute-force with the number of objects I was testing, I couldn't make the analysis that brute-force was performing better. So I guess I really haven't done due diligence here..

That said, I can only think of one reason why this situation is pathological for SAPFC (assuming the ping-pong effect is handled by adjusting the AABB) - that is, I might be sorting the axis incorrectly - ie, given the extent values of { 10,12,12,12, 12, 12, 15}, I hope I'm not sorting each "12" with its neighboring "12"... its possible that I'm doing that and if that is the case, SAPFC would being doing that every frame and performance would come to a crawl... I'll have to take a look.

-Andy








Nov 19, 2007 at 5:51 AM
I ported it again and I have managed to get the SAPFC to perform as promised. I removed the test of the 2 AABB in the TestForCollisions thinking it was an unnecessary extra test. This time I did not and now the false positives are gone. I also made sure the isMin extent always comes in front of the max one with the following code in the InsertIntoSortedList method.

                while (insertAt < this.Count &&
                    (this[insertAt].value < newExtent.value ||
                    (this[insertAt].value == newExtent.value &&
                    this[insertAt].isMin && !newExtent.isMin)))
                {
                    insertAt++;
                }

But I’m still getting weird false negatives. I use a body in the engine as a way to do clipping for drawing objects, with no narrow phase. So any object that collides with the screen’s clip rectangle is drawn. So I know it’s the broad phase when something is not drawn and that is what’s happening. Other objects collide with those objects but they are not drawn unless the demo is restarted.

Here is an example:
http://img135.imageshack.us/img135/2470/fcerrorwd2.png
Notice how 2 of the rag dolls do not have their legs drawn?
It does not happen very often and it only happens on the start of a demo. And I’m not able to reproduce this error with the other broad phases (I tried for quite a while).

Nov 19, 2007 at 6:12 AM
Somewhat promising news.

I changed the 2 occurences of the line "while (currExtent.value >= evalExtent.value)" in SAPFC to be ">" instead of ">=". I also added a delta of .01 to my AABB's.

I then retested the pyramid demo. I made a base of 20. I also removed the agent. I let the blocks fall and watched as long as it took for the pyramid to collapse (usually within a minute, I think) and hit the floor. I also initialize the gravity vector to be (0, 50). Here are the results on my machine:

BruteForce: Starts off at 125 fps... then when the pryamid starts to collapse, it drops down to less than 0 fps for me.

SelectiveFC: Starts off at a solid 560 fps... then when the pyramid collapse, it does ok for several seconds, but finally hits about 2 fps... and never seems to recover.

SAPFC: Starts off at a solid 585 fps.... then when the pyramid collapse, it dipped down into the 100 range once. But stayed around 200-400 fps. It was actually quite impressive and interactive the entire time. (After this, I also went back and tested the collision-groups stress test and saw big improvements there too!)

Now for the mixed-news.
After trying that pryamid test several times and being satisfied with the consistency of the results... I bumped up the gravity vector to be (0,100), and suddenly, in this situation - SAPFC seems to be on par with SelectiveFC.... both hit the 2 fps count once the pryamid starts to collapse... and neither seem to recover.... I can't real explain that.

Andy.










Nov 19, 2007 at 6:47 AM
Edited Nov 19, 2007 at 6:51 AM
I made the changes you listed and now SAPFC runs a lot better. (there were some tests where it just froze for a while now it does not.)
I’m thinking of one way you or I could optimize the insertion in SAPFC. (Right now inserting any number of objects at regular intervals brings it to its knees.) In my engine bodies get added to a pending list before they are fully added to the engine. (I think farseer does something similar) This makes it so I’m always adding a list of objects to the broad phase. So insertion can be done at a list level. My idea is that the bodies/geoms could be sorted before adding and then do a merge sort type insertion. This would make insertion only have the cost of sorting the input O(nlogn) then the cost insertion using the merge sort algorithm O(n+m), and only have to resize the array holding it once. This would be done for both the axis would have the total cost of insertion at O(2*(m+n+nlogn)) instead of O(2*m*n)

Another rout would be to use a binary search to find the points of insertion.
Nov 19, 2007 at 6:48 AM
Edited Nov 19, 2007 at 7:08 AM
When I pushed the demos to make it really stressing I had it add 11k bodies. It ran at around 4-8 FPS. I made one similar to the videos above.
Here is a image of the stress:
http://img235.imageshack.us/img235/9963/11kbodiestestum5.png
Coordinator
Nov 19, 2007 at 11:45 AM
Wow, great news.

I can't keep up with the improvements. :-)

sonofdaedalus, would mind sending me your latest version? I'd appreciate it.


As for the issue with gravity. Did you try different values for the delta on the AABB's? It could be that the bodies are "compacting" together more at hight gravity levels.

-Jeff
Nov 19, 2007 at 1:06 PM

BioSlayer - those methods to improve the adding of bodies/geoms would definitely be a big improvement. In an earlier post, you mentioned getting weird false negatives. Is that still occurring? One thing I can think of is - I haven't tested adding bodies/geoms such that their AABBs are overlapping right from the start. Since there is separate code that ensures the AABB's are inserted in order, it might be that there is a bug in that code. If there is, its possible that the overlap list isn't initially created correctly and then, never really gets repaired. One thing that you could do is call the "ForceNonIncrementalUpdate" after all geometries have been added or after each geometry has been added. This will make the code much slower, but it might determine if that was the issue.... BTW, 11k bodies is awesome - you must have a much faster machine than I do! How many bodies can you get in and still maintain a decent frame-rate?

CrashLander - I did change the delta's on the AABBs, but I still saw the issues when I cranked up the gravity.... so still confused (its possible I didn't play around with it enough). I'll send what I currently have. One other thing I change was to change the underConsiderations-list from a LinkedList<> to a List<>. I don't know if that had much effect on performance one way or the other.

Oh - here is a useful metric that I temporary hacked into the physicsSimulatorView debug window:

spriteBatch.DrawString(spriteFont, String.Format("Broadphase Pairs: {0}",
this.physicsSimulator.sweepAndPrune.collisionPairs.Keys.Count), new Vector2(120, 215), Color.White);

That line will show you exactly how many broad-pair collisions there are at each frame. The more widely this number is fluxuating, the worst the algorithm is probably doing...

-Andy.










Coordinator
Nov 19, 2007 at 4:41 PM
Sounds great, Andy.

I'll add that metric to the debug view.
Coordinator
Nov 20, 2007 at 10:25 AM
Edited Nov 20, 2007 at 10:27 AM
Broadphase Collison Update:
I've implemented the latest code: SweepAndPruneFC2 with modifications suggested by BioSlayer. I get really good results in all my tests. (I did rename it to just SweepAndPrune in the engine.)

Andy, I don't see the issue with gravity you are seeing, at least I can't tie the slow down to the sweep and prune collider. In my tinkering, though, I did notice the value of physicsSimulator.AllowedPenetration does have some affect. This is a "slop" factor designed to help stabalize resting collisions. I bumped up the default from .01 to .05 and I see slightly better framerates in the pyramid demo.

I also bit the bullet and went ahead and created an interface for broad phase. The interface looks like this:

namespace FarseerGames.FarseerPhysics.Collisions {
public interface IBroadPhaseCollider {
void ProcessRemovedGeoms();
void ProcessDisposedGeoms();
void Add(Geom geom);
void Update();
}
}

This should make it easier to test new broad phase colliders in the future. I defaulted the simulator to the new SweepAndPrune.

You can get a preliminary build with these changes here: here.



Nov 21, 2007 at 1:30 AM
Edited Nov 21, 2007 at 3:40 PM
I’ve finally done some benchmarks. And one result was really surprising.

The numbers are updates per second. In my engine’s demo the drawing and physics update happen in separate threads. So FPS is not used as a metric, UPS is.
11k Contained Bodies:
   Selective Sweep: 
	Starts: 12 
	Stabilizes: 8
   SAPFC: 
	Starts: 0 
	Stabilizes: 4
 
Ball Machine:
   Selective Sweep: 
	Starts: 230 
	Stabilizes: 130-140
   SAPFC: 
	Starts: 200
	Stabilizes: 90-100
 
Pyramid: (it stabilized very fast)
   Selective Sweep: 160
   SAPFC: 175
 
Insertion test: (20 particles added per update, they are removed after .9 seconds)
   Selective Sweep: 
	Before: 200
	During: 230
   SAPFC: 
	Before: 200
	During: 8
Key: 
   Starts: peek value at the start of a demo
   Stabilizes: after running a while this is the UPS that is displayed most often with the least fluctuations. 
   Before: before the test is started.
   During: during the test when it stabilizes.
Notice that in the insertion test, the updates per seconds actually increased for Selective Sweep! Which makes sense since Selective Sweep uses quick sort every turn which is faster with unsorted lists.

So my conclusion (based on these limited tests) is that Selective sweep is better for changing situations and SAPFC is better for more static scenarios, at least in my engine.

Now the only real way to know what system is better is to have a actual game using it and have them decide.

Also I’m still getting false negatives with SAPFC.
Coordinator
Nov 21, 2007 at 10:51 AM
Very cool metrics, BioSlayer.

I guess it would be good to include both.

Now I need to decide which would work best for MOST cases. I'll need to run some more tests.
Nov 21, 2007 at 1:12 PM
I definitly agree that SAPFC in its current form isn't good at add and deletions. One improvement to SAPFC would be to allow adding objects without the incremental-insertion / maintenance. Basically, if you have a bunch of objects that need to be added (or removed) all at once, it would be most efficient to make a special call that did all that adding/removing without any maintenance overhead. Then, after you were finished adding/removing objects without the normal overlap maintenance, you could call the ForceNonIncrementalSort to rebuild everything using quick-sort. What would be annoying about that, however, is that you would have to go around the cool new interface Jeff added since its fairly specific to this algorithm.

I agree - cool metrics BioSlayer. Also, I wish I could help you with the false-negatives... let me know if I can help in some way. If you want me to run some code, let me know.


Happy Thanksgiving guys!


Andy
Nov 21, 2007 at 9:10 PM
Edited Nov 22, 2007 at 9:41 PM
I have committed to the SVN the most recent code for Physics2D.Net. Here is the info for accessing the SVN:
http://code.google.com/p/physics2d/source

The problem with the false negatives is reproducible with the 0 (zero) demo. The ball that falls and nocks over the dominoes should not be falling.

Line 480 in Demo.cs is where you select the broad phase. Right now it’s set to yours which is named FrameCoherentSAPDetector.

EDIT: the version of the SVN I am talking about is 123
Coordinator
Nov 22, 2007 at 9:37 AM
Edited Nov 22, 2007 at 9:38 AM
BioSlayer, has your SelectiveSweep code changed since you posted your code above? I currently have what you posted running in Farseer and I'm going to use it as the default broadphase collider.

SAPFC, is also included in Farseer but I chose SelectiveSweep because it seemed a little more resiliant(I need spell check, codeplex) for general use.

-Jeff
Nov 22, 2007 at 5:54 PM
Nope, it hasn't changed.
The SVN is there for sonofdaedalus (or anyone interested in the code) so he can see the false negatives.

Nov 24, 2007 at 12:43 AM
I've fixed the false negatives by getting rid of the incremental adding of new geometries and instead, after the desired geometries have been added, just recalculating the cache.

The SAPFC has a degree of productization that is needed and enough caveats... seems like a good choice to go with SelectiveSweep.

Andy.
Coordinator
Nov 25, 2007 at 9:55 AM
What code changes do I need to make for this? I'm going to include both colliders but I'll default to SelectiveSweep.
Nov 27, 2007 at 3:59 PM
Looks like I'm late - Actually, I didn't "really" fix the issue as much as avoided it. I'll have to dig a little deeper when I get a chance. BioSlayer had a nice method to add a collection of geometries which I would like to propose for the farseer broadphase interface. In any case, since he was adding all his geometries at once, I avoided incrementally inserting each geometry's extents, but instead, just performed a full forced update (much faster for this case). The bug apparently is some edge case that occurs while inserting geometry.

I'll down load the latest release later and see if I can isolate that bug... and send you the changes...

Andy.
Coordinator
Nov 27, 2007 at 4:35 PM
Sounds good. If you send a snippet of the change you would like to the broad phase interface I can see about updating that as well.