Jump to content
  • Advertisement
Finalspace

AABB Broadphase non overlapping case

This topic is 381 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I added a simple AABB broadphase to my physics system so i create/update arbiters / contacts only for body/shape pairs when there AABBs overlap.

How do i deal with arbiters which was not overlapping in that simulation step? Remember and remove after the broadphase - or is there a smarter way to do it?

Right now i am doing the simplest possible thing, which are very slow (One hashtable lookup for each body/shape pair + check shapes even when there was no overlap):

	//
	// Broad and narrow phase
	//
	// @SPEED: Real broadphase!
	BEGIN_BLOCK("Broadphase");
	for (u32 bodyIndexA = 0; bodyIndexA < physics->bodies.count; bodyIndexA++) {
		Body *bodyA = physics->bodies.used[bodyIndexA];
		for (u32 bodyIndexB = bodyIndexA + 1; bodyIndexB < physics->bodies.count; bodyIndexB++) {
			Body *bodyB = physics->bodies.used[bodyIndexB];
			if ((bodyA->type == BodyType::Dynamic) ||
				(bodyB->type == BodyType::Dynamic)) {
				b32 isOverlap = IsAABBOverlap(bodyA->aabb, bodyB->aabb);
				for (u32 shapeIndexA = 0; shapeIndexA < bodyA->shapeCount; ++shapeIndexA) {
					Shape *shapeA = bodyA->shapes + shapeIndexA;
					for (u32 shapeIndexB = 0; shapeIndexB < bodyB->shapeCount; ++shapeIndexB) {
						Shape *shapeB = bodyB->shapes + shapeIndexB;

						Arbiter tmpArbiter = {};
						InitArbiter(&tmpArbiter, bodyA, bodyB, shapeA, shapeB);

						// Initialize new arbiter on the stack
						if (isOverlap) {
							// Calculate transforms
							Transform worldTransformA = TransformMake(tmpArbiter.bodyA->position, tmpArbiter.bodyA->rotation);
							Transform worldTransformB = TransformMake(tmpArbiter.bodyB->position, tmpArbiter.bodyB->rotation);
							Transform transformA = TransformMult(tmpArbiter.shapeA->localTransform, worldTransformA);
							Transform transformB = TransformMult(tmpArbiter.shapeB->localTransform, worldTransformB);

							// Generate contacts for new arbiter
							tmpArbiter.contactCount = PhysicsContactsGenerate(physics, transformA, transformB, tmpArbiter.shapeA, tmpArbiter.shapeB, tmpArbiter.contacts);
						}

						// Get existing arbiter hash entry
#if PHYSICS_USE_STD_MAP
						HashTableEntry<Arbiter *> *oldArbiterEntry = nullptr;
						ArbiterKey arbiterKey = ArbiterKey(tmpArbiter.bodyA, tmpArbiter.bodyB, tmpArbiter.shapeA, tmpArbiter.shapeB);
						std::map<ArbiterKey, HashTableEntry<Arbiter *>>::iterator arbiterHashIterator = physics->arbiterHashMap.find(arbiterKey);
						if (arbiterHashIterator != physics->arbiterHashMap.end()) {
							oldArbiterEntry = &arbiterHashIterator->second;
						}
#else
						HashTableEntry<Arbiter *> *oldArbiterEntry = physics->arbiterHashMap.GetEntryWithCompare(tmpArbiter.hash, &tmpArbiter, CompareArbiters);
#endif
						// Update or remove arbiter and call enter / leave collision callbacks
						if (oldArbiterEntry != nullptr) {
							Arbiter *prevArbiter = oldArbiterEntry->value;
							if (tmpArbiter.contactCount > 0) {
								UpdateArbiter(physics, prevArbiter, &tmpArbiter);
							} else {
								if (physics->collisionLeave != nullptr) {
									physics->collisionLeave(oldArbiterEntry->value, physics->userData);
								}
								RemoveArbiter(physics, oldArbiterEntry);
							}
						} else if (tmpArbiter.contactCount > 0) {
							Arbiter *newArbiter = AddArbiter(physics, &tmpArbiter);
							if (physics->collisionEnter != nullptr) {
								physics->collisionEnter(newArbiter, physics->userData);
							}
						}
					}
				}
			}
		}
	}
	END_BLOCK();

 

 

Edited by Finalspace

Share this post


Link to post
Share on other sites
Advertisement

When you do the overlap tests you need to check if you already created a contact for that pair. A hashtable is a good choice for this. Usually the arbiters also store a list of contacts (contact graph) so you can also search that list. You can search either arbiter since the contact would be referenced on both arbiters. Make sure to search the shorter list since e.g. the world arbiter can have potentially a large number of contacts.

The other issue is how to detect when a pair is *not* overlapping anymore. The solution to this problem depends quite a bit on your acceleration structure in your broadphase. E.g. SAP has a natural begin and end overlap event where you can handle the pair management. A dynamic tree doesn't have these events and things become a bit more tricky. So my broadphase only *adds* pairs. Then when I iterate the current contacts to send them to the solver a contact needs to be confirmed (a quick AABB overlap test for the involved shapes). If a contact is not confirmed it is skipped and removed from the list.

 

HTH,

-Dirk 

Edited by DonDickieD

Share this post


Link to post
Share on other sites

Pretty sure Box2D just looks through a list to see if the contact is already existing. If not then it goes ahead and makes arbiters, but only if they don't already exist for a given pair. Then each arbiter is tracking it's own state, and destroys itself when the inner proxies separate enough.

New pairs: https://github.com/erincatto/Box2D/blob/master/Box2D/Box2D/Collision/b2BroadPhase.h#L184-L238

Contact removal: https://github.com/erincatto/Box2D/blob/848b8fddf348ae0090f0046c845e1170c1331a1b/Box2D/Box2D/Dynamics/b2ContactManager.cpp#L37-L100

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!