• Advertisement

AABB Broadphase non overlapping case

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!
	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
						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;
						HashTableEntry<Arbiter *> *oldArbiterEntry = physics->arbiterHashMap.GetEntryWithCompare(tmpArbiter.hash, &tmpArbiter, CompareArbiters);
						// 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);



Edited by Finalspace

Share this post

Link to post
Share on other sites

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.




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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement