BroadPhase Dynamic Tree

Topics: Developer Forum
Sep 9, 2009 at 7:05 PM

 

I had a question about the current unreleased Box2d port. I was trying to implement / test out the dynamic tree , but I am running into problems with the tree not providing some pairs on aabb collisions. I'm intrested in the Dynamic tree and  know that the pre release is unstable.  Does anyone know  any good resources/samples to study regarding the Broadphase Dynamic tree.

Coordinator
Sep 9, 2009 at 7:12 PM

I know Christer wrote about incremental build bounding volume trees in his Realtime Collision Detection book. I think that is where the implementation originally came from. Bullet Physics also implement a 3D version of the bounding tree if I remember correctly.

There are a lot of unresolved porting bugs in the latest source code. I had to port over all the new code myself and thus progress is slow. I put in TODOs where I know the code is broken. I will take a look at the dynamic tree implementation in the next weekend. I was not even aware that the broadphase did not report all AABB intersections.

Anyway, bounding volume trees is the subject you should be looking for.

Sep 10, 2009 at 2:48 AM
Edited Sep 10, 2009 at 11:57 AM

I think i solved  the problem I was talking about.  In BroadPhase- UpdatePairs method theres a Pairbuffer that is getting sorted before forwarding the pairs to the fixtures. At first I thought the PairLessThan was the problem because when it adds a pair into the Pairbuffer its adding it to the begining of the array , but whenthe sort is called the zero's  are at the begining of the array and never hits the  new pairs at the end of the list because of the PairCount;I ended up just commenting out the Array.Sort.

I just Relized what its sorting for , skip the duplicates. I might be wrong ,but I think the sort needs to be  sorted within index 0 to paircount.

 

 

Coordinator
Sep 10, 2009 at 12:45 PM

Yeah, I had some trouble with that part of the code. I thought I removed the Array.Sort altogether, but I might not have commited the changes.

Anyway, if you can figure out the sorting mechanism and fix it, I would be more than happy to take a look at your fix. I could not find any good documentation on the return value of std::sort in C++ with the limited time I had. I think the main problem is that the PairsLessThan sort on two variables (First pair, then second) and the current implementation does not take that into account.

Sep 10, 2009 at 5:46 PM
I used this aproach for the sorting and it seams to work well.
Array.Sort(_pairBuffer, 0, _pairCount, _Comparer);

   public class PairComparer : IComparer<Pair>
    {
        public int Compare(Pair pair1, Pair pair2)
        {
            if (pair1.proxyIdA < pair2.proxyIdA)
            {
                return 1;
            }

            if (pair1.proxyIdA > pair2.proxyIdA)
            {
                return -1;
            }

            if (pair1.proxyIdA == pair2.proxyIdA)
            {
                if (pair1.proxyIdB < pair2.proxyIdB)
                {
                    return 1;
                }

                if (pair1.proxyIdB > pair2.proxyIdB)
                {
                    return -1;
                }
            }

            return 0;
            
        }
    }

 

 

 

 

Coordinator
Sep 10, 2009 at 10:25 PM

I will take a look at it this weekend. Thanks a lot for looking into this and helping out.