Real-Time Physics Simulation Forum

Re: Sweep and Prune or dBVT for this use case

2014-03-07T04:48:24+00:00

Good question! Currently I create a contact when the fat AABBs begin to overlap. I never have compared this, though I definitely should. I have other caching schemes (as described earlier) in place which kind of do this though.

Statistics: Posted by Dirk Gregorius — Fri Mar 07, 2014 4:48 am

Re: Sweep and Prune or dBVT for this use case

2014-03-07T03:25:17+00:00

Dirk,

Do you save the pre-inflated bounds for each object and perform an overlap test with that prior to narrow phase? Obviously the inflated bounds are used to manage the overlapping pairs, but I wonder if smaller objects would benefit from performing a tight-fighting bounds overlap test prior to entering narrow phase.

S

Statistics: Posted by sphet — Fri Mar 07, 2014 3:25 am

Re: Sweep and Prune or dBVT for this use case

2014-03-06T18:17:31+00:00

Are you inflating in the direction of the linear movement of the body or do you use a fixed amount of to inflate? I use a combination of both.

Here is my code for reference. I moved the inflation part into the broadphase and the dynamic tree doesn't know about this. What kind of inflation strategy (if any) you use depends on the use-case so I decoupled it.

Dirk,

I did exactly the same thing - I plan on using the dynamic tree for a number of subsystems so I simply made it ignorant of the inflation and did the work in the broadphase.

For bodies with dynamics I inflate in the direction of linear velocity and I inflate it by some amount. For animation-driven bodies (bones) I currently inflate it by a consistent amount around the entire body as I don't currently infer linear velocity from the bone positions - it isn't required in my use case and I can't afford any extra maths.

I may actually put an additional fudge factor into the bodies themselves so that the client code has control over this for certain cases such as rotation-only animated objects (powerups) and fast moving narrow animated objects (projectiles).

Seems we are on the same page here - thanks.

Statistics: Posted by sphet — Thu Mar 06, 2014 6:17 pm

Re: Sweep and Prune or dBVT for this use case

2014-03-06T17:43:14+00:00

Are you inflating in the direction of the linear movement of the body or do you use a fixed amount of to inflate? I use a combination of both.

Here is my code for reference. I moved the inflation part into the broadphase and the dynamic tree doesn't know about this. What kind of inflation strategy (if any) you use depends on the use-case so I decoupled it.

Code:

// Bounds are the tight bounds of the parent shape. Displacememnt = LinearVelocity * ElapsedTimebool rnBroadphase::MoveProxy( int Proxy, const rnBounds3& Bounds, const rnVector3& Displacement ){if ( mTree.GetBounds( Proxy ).Contains( Bounds ) ){                // No update requiredreturn false;}// Update tree with inflated and motion anticipating boundsrnVector3 Extension = rnVector3( RN_BOUNDS_EXTENSION, RN_BOUNDS_EXTENSION, RN_BOUNDS_EXTENSION );rnBounds3 ExtendedBounds;ExtendedBounds.Min = Bounds.Min - Extension;ExtendedBounds.Max = Bounds.Max + Extension;if ( Displacement.X < 0.0f ){ExtendedBounds.Min.X += RN_BOUNDS_MULTIPLIER * Displacement.X;}else{ExtendedBounds.Max.X += RN_BOUNDS_MULTIPLIER * Displacement.X;}if ( Displacement.Y < 0.0f ){ExtendedBounds.Min.Y += RN_BOUNDS_MULTIPLIER * Displacement.Y;}else{ExtendedBounds.Max.Y += RN_BOUNDS_MULTIPLIER * Displacement.Y;}if ( Displacement.Z < 0.0f ){ExtendedBounds.Min.Z += RN_BOUNDS_MULTIPLIER * Displacement.Z;}else{ExtendedBounds.Max.Z += RN_BOUNDS_MULTIPLIER * Displacement.Z;}mTree.MoveProxy( Proxy, ExtendedBounds );BufferMove( Proxy );        // Update required        return true;}

HTH,
-Dirk

Statistics: Posted by Dirk Gregorius — Thu Mar 06, 2014 5:43 pm

Re: Sweep and Prune or dBVT for this use case

2014-03-05T23:26:57+00:00

So I took another look at my implementation and discovered that I was incorrectly inflating the AABBs for the bone objects. Once I took that into account, things got a lot better. I had to use quite a large inflation value (2 meters) but it does effectively remove all but the first broadphase overlap tests when the characters are pushing up against one another.

In my test case it is 1/10th the cost of SAP in a similar situation with the added bonus of ray queries being faster.

Thanks for your feedback and help Dirk - looks like a win here.

S

Statistics: Posted by sphet — Wed Mar 05, 2014 11:26 pm

Re: Sweep and Prune or dBVT for this use case

2014-03-04T17:48:02+00:00

I thought about the shape transform and I think it just comes from Maya where shapes nearly always have a parent transform.

Statistics: Posted by Dirk Gregorius — Tue Mar 04, 2014 5:48 pm

Re: Sweep and Prune or dBVT for this use case

2014-03-04T00:12:51+00:00

So after implementing a dynamic AABB tree following the example by Erin, and hooking it up to the broadphase, I did a comparison between the Sweep and Prune and the Dynamic Tree specifically looking at character bones and their costs in the broadphase. I can't really print any numbers out because they don't have any significance to anyone but me, but the results were interesting.

My setup involves many characters with 12 bone rigs running against each other. The bones in one system cannot collide with themselves, only with bones of opposing players.

Having all bones in the world is much slower in SAP than Dynamic Tree (although I needed a large AABB expansion buffer on the tree nodes of approximately 1 meter to make this worthwhile).

Having all the bones in the world in the Dynamic Tree is still slower than having all the bones in a List Shape ( List shape takes 12 bones out of broadphase and replaces with 1 object). Additional cost is incurred because of some bounding box combining, and no mid-phase detection in the list shape versus list shape collider.

Having all the bones in a List Shape in Sweep and Prune is comparable to the Dynamic Tree. I think this is now due to the low number of entities in the broadphase.

I don't think my Dynamic Tree broadphase wrapper is nearly as efficient as the SAP was, given that my class hierarchy (overlapping pair management, dispatcher, etc) is based on SAP's explicit Add/Remove callback. Dynamic Tree leaves it up to the client broadphase to perform AABB test on the existing overlapped pairs to check for removal every frame, which can cause the AABB overlap test to be duplicated in some cases. Plus the plumbing for some of that logic just isn't there right now.

When bones move enough to trigger a leaf re-insert, the cost of combining AABBs to get the SAH costs show up in the profiler on my device, so I need to minimize this happening.

I believe that the Dynamic Tree would be faster than the SAP in all cases (and is easier to debug) plus the benefits of Ray Casting against it are well documented. I am sad that the BVT was not enough to allow me to keep the bones in the broadphase directly, without the list shape collider.

Thanks for your help.

Statistics: Posted by sphet — Tue Mar 04, 2014 12:12 am

Re: Sweep and Prune or dBVT for this use case

2014-03-03T17:36:01+00:00

For hulls I use SAT. You can find my GDC presentation and some implementation here:
https://box2d.googlecode.com/files/DGre ... DC2013.zip

It is pretty much what I use these days though there is some room for SIMD optimizations to get rid of some branches. The major idea to make the narrow phase (and also the broadphase) fast is to use temporal coherence. So once you have a separating axis you test it in the next frame first. Once you have two touching features you try to rebuild the contact manifold from the last two touching features based on some heuristic (e.g. whether the relative orientation has changed). The SAT is still O(n^2) as I presented it. You should see the pattern here for both broadphase and narrow phase. As long as you hit your caches you do nothing and you should only update a small part of your proxies and manifolds each frame. If everything is settled (before going to sleep) nothing should be updated at all!

Statistics: Posted by Dirk Gregorius — Mon Mar 03, 2014 5:36 pm

Re: Sweep and Prune or dBVT for this use case

2014-03-03T06:34:49+00:00

I don't use any shape transforms. The shapes are defined as:

1) Sphere: Center and Radius
3) Capsule: 2 Centers and Radius (This is nice since you don't need to deal with any up-directions)
3) Hulls: Vertices, Faces and Edge
4) Meshes: Vertices and Triangles

Interesting - I pass down the transform in all cases as well - shapes are always defined in the local space of the parent - but sphere's are simply a radius, and capsules oriented along z(up). Perhaps the need for listshapes also comes from this kind of implementation because there is no way to offset a sphere in the local space of a rigid body without another shape in the hierarchy. So essentially you can create many spheres shapes with local space offsets and radii and then attach them all to the body - there is a lot of potential savings here compare to listshapes with a child-offset matrix which requires full concatenation.

Regarding sharing, the size of a sphere or capsule shape will be very small so duplicating that isn't the end of the world. This is the same as my system.

I will have to look over my implementations as I suspect that all of the collision agents easily handle non-centered points.

For hulls are you still using SAT or GJK? You've written a lot about SAT. I need to tackle that soon as of right now I only support sphere, capsule, finite/infinite plane and mesh. I need to add box soon.

Sorry for dragging this topic so way off course but it's good to talk out these issues and ideas.

S

Statistics: Posted by sphet — Mon Mar 03, 2014 6:34 am

Re: Sweep and Prune or dBVT for this use case

2014-03-03T00:12:00+00:00

I don't use any shape transforms. The shapes are defined as:

1) Sphere: Center and Radius
3) Capsule: 2 Centers and Radius (This is nice since you don't need to deal with any up-directions)
3) Hulls: Vertices, Faces and Edge
4) Meshes: Vertices and Triangles

Is is basically all vertices defined under some parent transform. You could cache a world transform, I guess. Erin uses a fixture to attach a shape to a body which does the caching iirc, but I don't even do this. In all function calls I usually pass down the a parent transform and the associated shape. So far this really works out pretty clean and concise.

You usually want to keep tree updates low anyway. That is why the dynamic tree works with inflated (fat) AABBs. So far the tree updates haven't been any issue. Even in pathological test scenes where each shape is spawned at the same time and invalidate their fat broadphase AABB all in the same frame. I think your point is valid, but before it is not a practical problem I would not address it. It is probably as you said and it goes back to the inefficiencies of SAP handling insertions and removals.

Good luck! Let me know how it works out

Edit:
I can share hulls and meshes. rnHullShape and rnMeshShape reference rnHull and rnMesh which is owned by the user. For meshes this might make sense, but for hulls I don't even bother. They are so memory efficient the way I store them they never showed up. Surprisingly hulls are very expensive in PhysX though. Havok usually cares for memory more. My shapes are really cheap and have hardly any overhead since they don't cache any transforms.

Statistics: Posted by Dirk Gregorius — Mon Mar 03, 2014 12:12 am