🔒 Locked

Bounding Box Intersections?

Started by pcmattman Jan 17, 2008 at 3:13 AM 2 replies 800+ views

Original Post

Jan 17, 2008 at 3:13 AM

Hi everyone, I recently implemented bounding box collision between any object with a bounding box and a loaded map (Quake 3 BSP format). However, I'm now stuck trying to implement collisions between two entities (ie, the player and an elevator). I'm not 100% sure how I'm meant to tell when one bounding box is inside another one (ie, a collision is occuring), especially when only a small part of one entity's bounding box may be colliding at once. Any pointers as to a method of implementing this (psuedo-code, tutorials, etc...) would be greatly appreciated. At the moment all I have is an idea that I may need to use the normal vector of each face of the bounding boxes. Thanks in advance!

Gage64

135

Gage64

Jan 17, 2008 at 3:27 AM

The following code checks if two static (i.e., not moving) AABBs intersect. It is taken from here and is fairly self explanatory:

bool	intersectAABBs(	const AABB3 &box1,	const AABB3 &box2,	AABB3 *boxIntersect) {	// Check for no overlap	if (box1.min.x > box2.max.x) return false;	if (box1.max.x < box2.min.x) return false;	if (box1.min.y > box2.max.y) return false;	if (box1.max.y < box2.min.y) return false;	if (box1.min.z > box2.max.z) return false;	if (box1.max.z < box2.min.z) return false;	// We have overlap.  Compute AABB of intersection, if they want it	if (boxIntersect != NULL) {		boxIntersect->min.x = max(box1.min.x, box2.min.x);		boxIntersect->max.x = min(box1.max.x, box2.max.x);		boxIntersect->min.y = max(box1.min.y, box2.min.y);		boxIntersect->max.y = min(box1.max.y, box2.max.y);		boxIntersect->min.z = max(box1.min.z, box2.min.z);		boxIntersect->max.z = min(box1.max.z, box2.max.z);	}	// They intersected	return true;}

That site also contains the code for a dynamic intersection test (which takes the AABB's velocities into account) but it is much longer so I won't post it here. It's also heavily commented.

You might also want to look here.

pcmattman

Author

pcmattman

Jan 17, 2008 at 3:38 AM

Hi,

Thanks for that code. When you posted I was in the middle of converting one of the algorithms on the Wikipedia page on "Bounding volume" into relevant code, so it saved me some time. However, I still need to know on what axis the collision occurred (for instance, are you on top of the elevator entity or underneath it) - how would I go about finding that out?

d00fus

Jan 17, 2008 at 3:52 AM

If you understand how the code is derived you'll be better off when it comes to classifying what sort of intersection has occurred. Generally for bounding boxes, intersection tests are based on the Separating Axis Theorem (SAT). If you google this you should find more info, but briefly it states that (in the context of 3D) two convex shapes do not intersect if and only if you can place a plane that separates them. If you think about it, this is quite intuitive.

When implemented, the equivalent specification is often used: that two convex shapes do not intersect if and only if there exists an axis that the projected extents of each convex polyhedron onto that axis do not overlap. Think of this like looking "side-on" at the separating plane. If it separates the objects, if you project the objects onto the plane normal (the axis) their projections won't overlap.

The real strength of the theorem however is that for convex polyhedra, it specifies that the separating axis can only be parallel to either a face normal from one of the objects, or the cross product of each pair of edges of the objects. This gives you a limited set of axes to check - if any one of them separates the objects, then they do not intersect, and you can then do something based on which axis this is.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.