Sweep and Prune or dBVT for this use case

Please don't post Bullet support questions here, use the above forums instead.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Sweep and Prune or dBVT for this use case

Post by Dirk Gregorius »

I thought about the shape transform and I think it just comes from Maya where shapes nearly always have a parent transform.
sphet
Posts: 38
Joined: Mon May 06, 2013 6:14 pm

Re: Sweep and Prune or dBVT for this use case

Post by sphet »

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
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Sweep and Prune or dBVT for this use case

Post by Dirk Gregorius »

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: Select all

// Bounds are the tight bounds of the parent shape. Displacememnt = LinearVelocity * ElapsedTime
bool rnBroadphase::MoveProxy( int Proxy, const rnBounds3& Bounds, const rnVector3& Displacement )
	{
	if ( mTree.GetBounds( Proxy ).Contains( Bounds ) )
		{
                // No update required
		return false;
		}

	// Update tree with inflated and motion anticipating bounds
	rnVector3 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
sphet
Posts: 38
Joined: Mon May 06, 2013 6:14 pm

Re: Sweep and Prune or dBVT for this use case

Post by sphet »

Dirk Gregorius wrote: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.
sphet
Posts: 38
Joined: Mon May 06, 2013 6:14 pm

Re: Sweep and Prune or dBVT for this use case

Post by sphet »

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
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Sweep and Prune or dBVT for this use case

Post by Dirk Gregorius »

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.
Post Reply