new BroadPhase (Sweep and Prune)

Topics: Developer Forum
Oct 16, 2007 at 7:12 PM
Edited Oct 16, 2007 at 7:13 PM
I did a quick look through your most recent code and was kind of shocked to find out you still didn’t have a more efficient Broad Phase. So I decided to write one for your engine during my break. I tried to make it simple instead of optimized for ease of understanding.

public class SweepAndPrune
{
    delegate void CollisionCallback(Wrapper w1, Wrapper w2);
 
    class Wrapper
    {
        public Node xBegin;
        public Node xEnd;
        public Node yBegin;
        public Node yEnd;
        public Geometry geometry;
        public List<Geometry> colliders;
        public Wrapper(Geometry geometry)
        {
            this.geometry = geometry;
            this.colliders = new List<Geometry>();
            this.xBegin = new Node(this, true);
            this.xEnd = new Node(this, false);
            this.yBegin = new Node(this, true);
            this.yEnd = new Node(this, false);
        }
        public void Update()
        {
            colliders.Clear();
            xBegin.value = geometry.AABB.Min.X;
            xEnd.value = geometry.AABB.Max.X;
            yBegin.value = geometry.AABB.Min.Y;
            yEnd.value = geometry.AABB.Max.Y;
        }
    }
 
    class Node
    {
        public bool begin;
        public float value;
        public Wrapper wrapper;
        public Node(Wrapper wrapper, bool begin)
        {
            this.wrapper = wrapper;
            this.begin = begin;
        }
    }
 
    List<Wrapper> wrappers = new List<Wrapper>();
    List<Node> xList = new List<Node>();
    List<Node> yList = new List<Node>();
 
    public void AddGeometry(Geometry item)
    {
        Wrapper wrapper = new Wrapper(item);
        wrappers.Add(wrapper);
        xList.Add(wrapper.xBegin);
        xList.Add(wrapper.xEnd);
        yList.Add(wrapper.yBegin);
        yList.Add(wrapper.yEnd);
    }
    public void RemoveDisposed()
    {
        if (wrappers.RemoveAll(delegate(Wrapper w) { return w.geometry.Body.IsDisposed; }) > 0)
        {
            xList.RemoveAll(delegate(Node n) { return n.wrapper.geometry.Body.IsDisposed; });
            yList.RemoveAll(delegate(Node n) { return n.wrapper.geometry.Body.IsDisposed; });
        }
    }
    public void Run()
    {
        Update();
        RunAxis(xList, HandleFirstCollision);
        RunAxis(yList, HandleSecondCollision);
    }
    /// <summary>
    /// Updates the nodes and sorts them.
    /// </summary>
    void Update()
    {
        foreach (Wrapper wrapper in wrappers)
        {
            wrapper.Update();
        }
        xList.Sort(delegate(Node l, Node r) { return l.value.CompareTo(r.value); });
        yList.Sort(delegate(Node l, Node r) { return l.value.CompareTo(r.value); });
    }
    /// <summary>
    /// Runs the collision detection on a axis
    /// </summary>
    void RunAxis(List<Node> list, CollisionCallback callback)
    {
        LinkedList<Wrapper> proximityList = new LinkedList<Wrapper>();
        foreach (Node node in list)
        {
            if (node.begin)
            {
                foreach (Wrapper wrapper in proximityList)
                {
                    callback(node.wrapper, wrapper);
                }
                proximityList.AddLast(node.wrapper);
            }
            else
            {
                proximityList.Remove(node.wrapper);
            }
        }
    }
    /// <summary>
    /// when there is a collsion along the first axis
    /// and if there is no early fail conditions then they are
    /// added to each others colliders list
    /// </summary>
    void HandleFirstCollision(Wrapper w1, Wrapper w2)
    {
        //if(early fail conditions) {return;}
        w1.colliders.Add(w2.geometry);
        w2.colliders.Add(w1.geometry);
    }
    /// <summary>
    /// when there is a collision along the second axis then 
    /// it checks to see if there was a collision along the first. 
    /// if there is then the 2 geometries bounding boxes are colliding.
    /// </summary>
    void HandleSecondCollision(Wrapper w1, Wrapper w2)
    {
        if (w1.colliders.Contains(w2.geometry))
        {
            //this is a confirmed broadphase collision
            //so add a new arbiter or something for 
            //w1.geometry and w2.geometry
        }
    }
}
It was written for your engine so you should be able to integrate this into your engine rather easily.

NOTE: It did compile but I have no guarantee its bug free, but it should work.
Coordinator
Oct 16, 2007 at 7:47 PM
Hey BioSlayer.

Wow, thanks!

Yes, I wanted sweep and prune, but due to my limited time to work on this project, all the other features I wanted to get in, and my lack of experience with sweep and prune, it was left out with intentions of adding it in the future.

I will definetly work on getting this code integerated. It is much appreciated!

So, that's one collision grid class, and one sweep and prune algorithm from you. Much appreciated!

-Jeff
Oct 16, 2007 at 8:25 PM
Beat me to it.

I still might give it a go. I wrote a C++ version a long while ago that was fairly incremental / frame coherent- you only sorted locally when needed (instead of running through list) and most of the time you you did nothing but keep a list of actively colliding boxes to do narrow phase testing. If I remember right, this mean peforming the local sort as the AABB changed position. ... This was about 8 yrs ago, but I was getting about 4000 colliding AABB's as long as there was good frame coherence. At hight speeds, things slowed down because of the insertion sort used in the alogithm. As objects came to a halt, no more work was done because the sweepAndPrune received no updates that AABB's changed position.




Oct 16, 2007 at 9:44 PM
After you get the code working (hopefully it works right away)
You can do a few optimizations.
1. Have the wrapper store the proximityList node for instant removal.
2. Replace the delegates with static methods and a comparer class.
3. Find a faster replacement for the colliders List. I have a special list that stores the Body’s ID and uses a binary search.

Erin Cato’s new Box2D also has a broad phase that I would look into.


Sorting the entire list is not that much of a slow down since .Net implementation of quick sort is insanely fast.
Oct 17, 2007 at 6:29 PM
So looking at my old code, the difference is the the algorithm I used:

1. doesn't require running the x and y axis per frame
2. doesn't require recomputing the proximity lists per frame
3. doesn't require rechecking containment / intersections per frame

All of the above info is cached frame to frame and no work is done unless two extents swap and then you incrementally make adjustments.

Well... I have no idea if the extra bookkeeping pays off in the long run or not...
Coordinator
Oct 17, 2007 at 11:31 PM
Edited Oct 17, 2007 at 11:31 PM
Has anyone done any speed comparisons when the geometry count is low, say under 50? I'm wondering because if brute force is quicker for low geometry counts I will want to keep both broadphase methods (bruteforce and sweep+prune)

Oct 18, 2007 at 1:29 PM
The brute-force way, O(n^2), breaks down rather quickly - without testing, I would argue that even if brute-force won with some number of fewer objects, that victory would be fairly marginal.... and with so few objects, you won't worry about sweep and prune showing any hic-ups in your profiling.

it might be cool, however, to be able to swap in/out different broad-phase collision strategies... maybe via registering a callback or something. Then experiements could be done on different strategies and you could see how much one buys you over the other.

BTW - I noticed that the AABB testing doesn't consider the AABB's previous min/max. Consider one axis for example: if an AABB having an X min/max of (2,4) travels right so that its new min/max is (8,10) - it may miss collisions if that is what is used for broadphase. Shouldn't the broad phase test an AABB (in this case) where its "min" is the previous frames "max" in order to catch collisions with objects that it may have "jumped" over? I'm thinking of objects moving faster than their width. Well anyway, I haven't looked to much into the code, so I'm not really sure how this all works...

Oh, while I'm here posting - great work on the engine. It's been a lot of fun to play with....



Oct 18, 2007 at 2:58 PM
Crashlander:
There was a huge improvement in speed when I implemented this in my engine. I had a simulation that took about 12 seconds to compute each time step with brute force, but with sweep and prune it ran in real time. Trust me it is faster.


Sonofdaedalus:
The current narrow phase has the same problem with tunneling.
Coordinator
Oct 18, 2007 at 4:46 PM
Edited Oct 18, 2007 at 4:48 PM
Ok, when I roll this into the engine I'll probably just make it THE broad phase collider and get rid of brute force.

One of my top design goals is making is simple for the user. One broad phase collider lends itself well to that goal.

I did notice, BioSlayer, that your code doesn't account for geometries that were Removed from the simulation (not Disposed) I assume I just do the same thing as you do when a geometry is disposed?) I admit I haven't had a chance to dig to deeply into your code yet.
Oct 18, 2007 at 6:27 PM
Yea, so just change the conditions for removal to add any flag you have in the geometry for it being removed.



Oct 24, 2007 at 10:41 PM
I think the part that needs to be optimized the most is colliders.Contains.

You may want to try profiling the engine to see where the bottle necks are.

here is a free profiler for .Net
http://www.mertner.com/confluence/display/NProf/Home

I don't know if it works on XNA apps, but i think it should.

if you are interested in the version in my engine here is a link to it in the SVN:
http://physics2d.googlecode.com/svn/trunk/%20physics2d/Physics2DDotNet/Detectors/SweepAndPruneDetector.cs
Nov 5, 2007 at 3:36 AM
Edited Nov 5, 2007 at 4:21 AM
So I spent a few hours and put together a "frame coherent" version of sweep and prune. I used your existing interfaces, so it should be trivial to swap this version in and test. Everything is now being cached including all those "extra" checks for things like collisionGroup compatibility, is static, is enabled, etc. (after all, those things won't change from frame to frame)

Considering I've probably done a lot of bone-headed things and abused C#'s containers, the initial results look promising. I altered two of your demos just to get some tests between NoSAP, the CurrentSAP, and the new FrameCoherent (FCSAP). Here are the details:

Test 1: I altered the pyramid stack demo to have a base of 20. I modified the gravity vector to (0,1) because I wanted to see performance before and after things collided. Here are the results for my machine:


          BlocksFalling         StackAtRest
NoSAP :       2400                      30
CurrSAP:      2500                       5 
FCSAP:        2800                     450

I believe this test really did a number on the current SAP because so many blocks are exactly aligned on an axis... The current version of SAP is actually worse than brute force in this case because of the w1.colliders.Contains(w2.geometry) line... I think what's happening is w1.colliders has a lot of entries for many cases in this scenario...

This isn't really an ideal case for FCSAP as well, but its less affected because of the caching.

As a side note, performance really dropped for all three methods once I rammed the pyramid and there were a lot of complex collisions...

Test2: I took your collision group demo and altered it to have a total of about 320 balls (varying in the 3 sizes). I also removed all the groups so that everything could collide with everything. I recorded the number of updates prior to anything happening and then after ramming the balls with the agent a few times in all directions (I agree, not the best test!) Results on my machine:


            AtRest               BallsColliding
NoSAP :      1015                      825
CurrSAP :    1150                      990
FCSAP:       1475                     1300


If I add just 60 more objects, the app drops to about 2 updates per second with both NoSap and the CurrSAP (after objects come to rest). The FCSap continues with at least 600 update per second.

As you can see, at least initially, the Frame Coherent SAP is fairly promising.

I can send you the code if you like, however, it isn't quite "productized" yet or even tested for more than about 30 minutes yet....
Coordinator
Nov 5, 2007 at 11:33 AM
Wow, very cool.

If you plan to keep tinkering with this I'll wait till your done before I integrate it into Farseer. Otherwise, I'll take it when ever you can send it/post it. :-)

Does it still handle the adding, removing, and disposeing of geometries?

-Jeff Weber
Nov 6, 2007 at 3:44 AM
Ok - let me tinker a little bit - I haven't address the removing / disposing yet. Probably tomorrow I'll post.

-Andy
Nov 6, 2007 at 4:58 AM
Oh well, guess I'll post it now - take it for a spin and let me know if you find any issues. You should be able to use it as is with just a name switch to "SweepAndPruneFC ".

.
.
.

... Doh... the code is too many lines to post to this page...
Coordinator
Nov 6, 2007 at 11:39 AM
You can send it to jeffreyweber AT hotmail.com
Nov 6, 2007 at 2:41 PM
Ok - sent.

Andy.
May 5, 2008 at 5:07 AM

BioSlayer wrote:
I did a quick look through your most recent code and was kind of shocked to find out you still didn’t have a more efficient Broad Phase. So I decided to write one for your engine during my break. I tried to make it simple instead of optimized for ease of understanding.

public class SweepAndPrune
{
    delegate void CollisionCallback(Wrapper w1, Wrapper w2);
 
    class Wrapper
    {
        public Node xBegin;
        public Node xEnd;
        public Node yBegin;
        public Node yEnd;
        public Geometry geometry;
        public List<Geometry> colliders;
        public Wrapper(Geometry geometry)
        {
            this.geometry = geometry;
            this.colliders = new List<Geometry>();
            this.xBegin = new Node(this, true);
            this.xEnd = new Node(this, false);
            this.yBegin = new Node(this, true);
            this.yEnd = new Node(this, false);
        }
        public void Update()
        {
            colliders.Clear();
            xBegin.value = geometry.AABB.Min.X;
            xEnd.value = geometry.AABB.Max.X;
            yBegin.value = geometry.AABB.Min.Y;
            yEnd.value = geometry.AABB.Max.Y;
        }
    }
 
    class Node
    {
        public bool begin;
        public float value;
        public Wrapper wrapper;
        public Node(Wrapper wrapper, bool begin)
        {
            this.wrapper = wrapper;
            this.begin = begin;
        }
    }
 
    List<Wrapper> wrappers = new List<Wrapper>();
    List<Node> xList = new List<Node>();
    List<Node> yList = new List<Node>();
 
    public void AddGeometry(Geometry item)
    {
        Wrapper wrapper = new Wrapper(item);
        wrappers.Add(wrapper);
        xList.Add(wrapper.xBegin);
        xList.Add(wrapper.xEnd);
        yList.Add(wrapper.yBegin);
        yList.Add(wrapper.yEnd);
    }
    public void RemoveDisposed()
    {
        if (wrappers.RemoveAll(delegate(Wrapper w) { return w.geometry.Body.IsDisposed; }) > 0)
        {
            xList.RemoveAll(delegate(Node n) { return n.wrapper.geometry.Body.IsDisposed; });
            yList.RemoveAll(delegate(Node n) { return n.wrapper.geometry.Body.IsDisposed; });
        }
    }
    public void Run()
    {
        Update();
        RunAxis(xList, HandleFirstCollision);
        RunAxis(yList, HandleSecondCollision);
    }
    /// <summary>
    /// Updates the nodes and sorts them.
    /// </summary>
    void Update()
    {
        foreach (Wrapper wrapper in wrappers)
        {
            wrapper.Update();
        }
        xList.Sort(delegate(Node l, Node r) { return l.value.CompareTo(r.value); });
        yList.Sort(delegate(Node l, Node r) { return l.value.CompareTo(r.value); });
    }
    /// <summary>
    /// Runs the collision detection on a axis
    /// </summary>
    void RunAxis(List<Node> list, CollisionCallback callback)
    {
        LinkedList<Wrapper> proximityList = new LinkedList<Wrapper>();
        foreach (Node node in list)
        {
            if (node.begin)
            {
                foreach (Wrapper wrapper in proximityList)
                {
                    callback(node.wrapper, wrapper);
                }
                proximityList.AddLast(node.wrapper);
            }
            else
            {
                proximityList.Remove(node.wrapper);
            }
        }
    }
    /// <summary>
    /// when there is a collsion along the first axis
    /// and if there is no early fail conditions then they are
    /// added to each others colliders list
    /// </summary>
    void HandleFirstCollision(Wrapper w1, Wrapper w2)
    {
        //if(early fail conditions) {return;}
        w1.colliders.Add(w2.geometry);
        w2.colliders.Add(w1.geometry);
    }
    /// <summary>
    /// when there is a collision along the second axis then 
    /// it checks to see if there was a collision along the first. 
    /// if there is then the 2 geometries bounding boxes are colliding.
    /// </summary>
    void HandleSecondCollision(Wrapper w1, Wrapper w2)
    {
        if (w1.colliders.Contains(w2.geometry))
        {
            //this is a confirmed broadphase collision
            //so add a new arbiter or something for 
            //w1.geometry and w2.geometry
        }
    }
}
It was written for your engine so you should be able to integrate this into your engine rather easily.

NOTE: It did compile but I have no guarantee its bug free, but it should work.



Hello,
I'm mansi doing final year engineering in india . As am doing a project on collision detection i have used ray tracing technique to find out collision between diff objects. But i wish to find collision between two 3D objects using "SWEEP AND PRUNE TECHNIQUE" IN 3D.I saw some of ur posts regarding this in codeplex.com.If u can help me in sending the code for this ,I'm very thankful to u.You can post to my id manasa_sn@yahoo.co.in
mansi.

May 5, 2008 at 5:08 AM

crashlander wrote:
Hey BioSlayer.

Wow, thanks!

Yes, I wanted sweep and prune, but due to my limited time to work on this project, all the other features I wanted to get in, and my lack of experience with sweep and prune, it was left out with intentions of adding it in the future.

I will definetly work on getting this code integerated. It is much appreciated!

So, that's one collision grid class, and one sweep and prune algorithm from you. Much appreciated!

-Jeff



Hello,
I'm mansi doing final year engineering in india . As am doing a project on collision detection i have used ray tracing technique to find out collision between diff objects. But i wish to find collision between two 3D objects using "SWEEP AND PRUNE TECHNIQUE" IN 3D.I saw some of ur posts regarding this in codeplex.com.If u can help me in sending the code for this ,I'm very thankful to u.You can send it to my id manasa_sn@yahoo.co.in
mansi.