Advertisement Jump to content

AABB Broadphase non overlapping case

This topic is 560 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!
	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:

Contact removal:

Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!