Advertisement

AABB collision detection

Started by December 06, 2021 12:05 AM
17 comments, last by JoeJ 2 years, 11 months ago

Well I have stubbed out this code and it works just fine but when I try to integrate it into my breakout game it does not work. I am trying to get the ball to collide with the paddle and output the collision detected text.

float move_paddle = 0.0f;
float ball_x = 0.0f, ball_y = 0.0f;
float xstep = 2.5f, ystep = 2.5f;

class paddle
{
public:
	float p_x = -20.0f + move_paddle;
	float p_y = -100.0f;
	float p_width=40.0f;
	float p_height=15.0f;
}paddle;

class ball
{
public:
	float b_x = -2.5f + ball_x; 
	float b_y = -2.5f + ball_y;
	float b_width=5.0f;
	float b_height=5.0f;
}ball;

void coll()
{
	cout << ball_x << "    " << ball_y << endl;

 	if (paddle.p_x <= ball.b_x + ball.b_width &&
		paddle.p_x + paddle.p_width >= ball.b_x &&
		paddle.p_y <= ball.b_y + ball.b_height &&
		paddle.p_y + paddle.p_height >= ball.b_y)
	{
		cout << "Collision Detected" << endl;
	}
}

Hi PBivens67,

What I did was put a break point on the if statement. I then added each comparison to the watch window (I'm using visual studio).

The first three comparisons evaluated to true, the last one evaluated to false:

paddle.p_y + paddle.p_height >= ball.b_y becomes

-100 + 15 ≥ -2.5 or

-85 ≥ 2.5 = false

The paddle's Y position is -100, the ball's Y position is -2.5. They're far apart in the y-direction!

I would use squared terms (or the pathagorean theorem)

float XDistance(b_x - p_x);

float YDistance(b_y - p_y);

float Width(p_width/2.0 + b_width/2.0);

float Height(p_height/2.0 + b_height/2.0);

if ((XDistance*XDistance <= Width*Width) && (YDistance*YDistance <= Height*Height))

cout << "Collision Detected" << endl;

Advertisement

well I tried the pathagoren theorem but it still does not work

float move_paddle = 0.0f;
float ball_x = 0.0f, ball_y = 0.0f;
float xstep = 2.5f, ystep = 2.5f;

class paddle
{
public:
	float p_x = -20.0f + move_paddle;
	float p_y = -100.0f;
	float p_width=40.0f;
	float p_height=15.0f;
}paddle;

class ball
{
public:
	float b_x = -2.5f + ball_x; 
	float b_y = -2.5f + ball_y;
	float b_width=5.0f;
	float b_height=5.0f;
}ball;

void collision()
{
	float X_dist=(ball.b_x - paddle.p_x);
	float Y_dist=(ball.b_y - paddle.p_y);
	float width=(paddle.p_width / 2.0 + ball.b_width / 2.0);
	float height=(paddle.p_height / 2.0 + ball.b_height / 2.0);
	
	if ((X_dist*X_dist <= width * width) && (Y_dist*Y_dist <= height * height))
	{
		cout << "Collision Detected" << endl;
	}
}

As I originally stated : The paddle's Y position is -100, the ball's Y position is -2.5. They're far apart in the y-direction!

so (Y_dist*Y_dist <= height * height) is false

actually the ball_y position becomes -100.0f

void Timer(int v)
{
	if (ball_x >= 145.0f || ball_x <= -135.0f)
	{
		xstep = -xstep;
	}
	if (ball_y >= 100.0f || ball_y <= -100.0f)
	{
		ystep = -ystep;
	}
	ball_x += xstep;
	ball_y += ystep;
	glutPostRedisplay();
	glutTimerFunc(50, Timer, 0);
}

pbivens67 said:
actually the ball_y position becomes -100.0f

Maybe not.
I'm not sure and wonder this compiles, but you set the members of the class just once:

class ball
{
public:
	float b_x = -2.5f + ball_x; 
	float b_y = -2.5f + ball_y;
...

This is ‘default member initializiation’, and it will be executed once after the object is created, like a constructor. (I wonder why the compiler accepts the global variables ball_x/y here at all.)
But if you change your global variables later during gameplay, the ball object does not update its member variables automatically.
You need to do this manually, or better: Don't use global variables but just the ball class object to avoid such confusions.

Aside of that, both your paddle and ball classes are just AABBs, so you could use a single AABB class instead to avoid code duplication.
If ball and paddle get different member variable as well later, you could either make those classes subclasses of the AABB, or add the AABB as a member variable to both of them. Entity Component Systems would be another option.

Advertisement
			
namespace vml
{
	namespace geo3d
	{
		namespace intersections
		{

			/////////////////////////////////////////////////////////////////////////////
			// intersection between bounding boxes

			static const unsigned int AABBOX_DISJOINT			 = 0;
			static const unsigned int AABBOX_FIRST_INSIDE_SECOND = 1;
			static const unsigned int AABBOX_SECOND_INSIDE_FIRST = 2;
			static const unsigned int AABBOX_INTERSECTED		 = 3;

			/////////////////////////////////////////////////////////////////////////////
			// intersection between bounding boxe - sphere

			static const unsigned int SPHERE_OUTSIDE_AABBOX    = 0;
			static const unsigned int SPHERE_INSIDE_AABBOX     = 1;
			static const unsigned int SPHERE_INTERSECTS_AABBOX = 2;
			static const unsigned int AABBOX_INSIDE_SPHERE     = 3;

			/////////////////////////////////////////////////////////////////////////////
			// checks if ray intersect an axis aligned bounding box

			static const unsigned int AABBOX_RAY_OUTSIDE       = 0;
			static const unsigned int AABBOX_RAY_INTERSECTS    = 1;
			static const unsigned int AABBOX_RAY_INSIDEAABBOX  = 2;

			/////////////////////////////////////////////////////////////////////////////
			// bounding boxe intersection tests 

			static unsigned int AABBoxVsAABBox(const glm::vec3 &bmin1, const glm::vec3 &bmax1, const glm::vec3 &bmin2, const glm::vec3 &bmax2)
			{
				// check if the first bounding box is entirely inside the second bounding box

				if ((bmin1.x >= bmin2.x && bmax1.x <= bmax2.x) &&
					(bmin1.y >= bmin2.y && bmax1.y <= bmax2.y) &&
					(bmin1.z >= bmin2.z && bmax1.z <= bmax2.z))
						return AABBOX_FIRST_INSIDE_SECOND;

				// check if the second bounding box is entirely inside the first bounding box

				if ((bmin2.x >= bmin1.x && bmax2.x <= bmax1.x) &&
					(bmin2.y >= bmin1.y && bmax2.y <= bmax1.y) &&
					(bmin2.z >= bmin1.z && bmax2.z <= bmax1.z))
						return AABBOX_SECOND_INSIDE_FIRST;

				// check if bounding box is out of second bounding box

				if ((bmax2.x < bmin1.x || bmin2.x > bmax1.x) ||
					(bmax2.y < bmin1.y || bmin2.y > bmax1.y) ||
					(bmax2.z < bmin1.z || bmin2.z > bmax1.z))
						return AABBOX_DISJOINT;

				// if we get here bounding boxes are intersecting each ohter

				return AABBOX_INTERSECTED;
			}

			/////////////////////////////////////////////////////////////////////////////
			// intersection between sphere and bounding box

			static int AABBoxVsSphere(const glm::vec3 &bmin, const glm::vec3 &bmax, const glm::vec3 &p0, const float radius)
			{
				// cache values

				float uax = p0.x - bmin.x;
				float uay = p0.y - bmin.y;
				float uaz = p0.z - bmin.z;
				float ubx = p0.x - bmax.x;
				float uby = p0.y - bmax.y;
				float ubz = p0.z - bmax.z;

				// checks if sphere is totally inside the bounding box

				if (uax + radius >= 0 && ubx + radius <= 0)
				if (uax - radius >= 0 && ubx - radius <= 0)
				if (uay + radius >= 0 && uby + radius <= 0)
				if (uay - radius >= 0 && uby - radius <= 0)
				if (uaz + radius >= 0 && ubz + radius <= 0)
				if (uaz + radius >= 0 && ubz - radius <= 0)
						return SPHERE_INSIDE_AABBOX;

				// check if bounding box is totally inside the sphere

				glm::vec3 v0;

				float dax = uax * uax;
				float day = uay * uay;
				float daz = uaz * uaz;
				float dbx = ubx * ubx;
				float dby = uby * uby;
				float dbz = ubz * ubz;

				v0.x = bmin.x;
				v0.y = bmin.y;
				v0.z = bmin.z;

				if (dbx >= dax) { v0.x = bmax.x; dax = dbx; }
				if (dby >= day) { v0.y = bmax.y; day = dby; }
				if (dbz >= daz) { v0.z = bmax.z; daz = dbz; }

				if (dax + day + daz < radius * radius)
					return SPHERE_INTERSECTS_AABBOX;

				// check if sphere and bounding box are intersecting
				// note that uax, uay,uaz,ubx,uby,ubz squared values
				// must be recomputed since we come from the other
				// step and values may get overwritten by the 
				// previous checks

				float dmin = 0.0f;

				if (uax < 0) dmin += uax * uax;
				else if (ubx > 0) dmin += ubx * ubx;

				if (uay < 0) dmin += uay * uay;
				else if (uby > 0) dmin += uby * uby;

				if (uaz < 0) dmin += uaz * uaz;
				else if (ubz > 0) dmin += ubz * ubz;

				if (dmin < radius * radius)
					return AABBOX_INSIDE_SPHERE;

				return SPHERE_OUTSIDE_AABBOX;
			}

			/////////////////////////////////////////////////////////////////////////////
			// intersection between infinit ray and bouding box
			// min is bounding box min
			// max is bounding box max
			// a is firt line point
			// b is sencond line point
			// p and q are intersection points

			static unsigned int AABBoxVsRay(const glm::vec3 &min, const glm::vec3 &max,
											const glm::vec3 &a, const glm::vec3 &b,
											glm::vec3 &p, glm::vec3 &q,
											float &tmin,float &tmax,
											float eps = vml::math::EPSILON)
			{
				glm::vec3 d = b - a;

				if (d.x > -eps && d.x < eps)
					d.x = eps;

				float txmin = (min.x - a.x) / d.x;
				float txmax = (max.x - a.x) / d.x;

				if (txmin > txmax)
				{
					float t = txmin;
					txmin = txmax;
					txmax = t;
				}

				if (d.y > -eps && d.y < eps)
					d.y = eps;

				float tymin = (min.y - a.y) / d.y;
				float tymax = (max.y - a.y) / d.y;

				if (tymin > tymax)
				{
					float t = tymin;
					tymin = tymax;
					tymax = t;
				}

				if ((txmin > tymax) || (tymin > txmax))
					return AABBOX_RAY_OUTSIDE;

				if (tymin > txmin)
					txmin = tymin;

				if (tymax < txmax)
					txmax = tymax;

				if (d.z > -eps && d.z < eps)
					d.z = eps;

				float tzmin = (min.z - a.z) / d.z;
				float tzmax = (max.z - a.z) / d.z;

				if (tzmin > tzmax)
				{
					float t = tzmin;
					tzmin = tzmax;
					tzmax = t;
				}

				if ((txmin > tzmax) || (tzmin > txmax))
					return AABBOX_RAY_OUTSIDE;

				if (tzmin > txmin)
					txmin = tzmin;

				if (tzmax < txmax)
					txmax = tzmax;

				tmin = txmin;
				tmax = txmax;

				p = a + tmin * d;
				q = a + tmax * d;

				return AABBOX_RAY_INTERSECTS;
			}

			/////////////////////////////////////////////////////////////////////////////
			// intersection between infinit ray and bouding box
			// min is bounding box min
			// max is bounding box max
			// a is firt line point
			// b is sencond line point
			// p and q are intersection points

			static unsigned int AABBoxVsLine(const glm::vec3 &min, const glm::vec3 &max,
											 const glm::vec3 &a, const glm::vec3 &b,
											 glm::vec3 &p, glm::vec3 &q,
											 float &txmin, float &txmax,
											 float eps = vml::math::EPSILON)
			{
				// line bounding box
				
				glm::vec3 rmin, rmax;

				if (a.x < b.x) { rmin.x = a.x; rmax.x = b.x; } else { rmin.x = b.x; rmax.x = a.x; }
				if (a.y < b.y) { rmin.y = a.y; rmax.y = b.y; } else { rmin.y = b.y; rmax.y = a.y; }
				if (a.z < b.z) { rmin.z = a.z; rmax.z = b.z; } else { rmin.z = b.z; rmax.z = a.z; }

				// chck if line is contained inside bbounding box
				
				if ((rmin.x >= min.x && rmax.x <= max.x) &&
					(rmin.y >= min.y && rmax.y <= max.y) &&
					(rmin.z >= min.z && rmax.z <= max.z))
				{
					p = a;
					q = b;
					return AABBOX_RAY_INSIDEAABBOX;
				}
				
				// check if bounding box is out of second bounding box

				if ((max.x < rmin.x || min.x > rmax.x) ||
					(max.y < rmin.y || min.y > rmax.y) ||
					(max.z < rmin.z || min.z > rmax.z))
						return AABBOX_RAY_OUTSIDE;
					
				// check for intersection

				glm::vec3 d = b - a;

				if (d.x > -eps && d.x < eps)
					d.x = eps;

				txmin = (min.x - a.x) / d.x;
				txmax = (max.x - a.x) / d.x;

				if (txmin > txmax)
				{
					float t = txmin;
					txmin = txmax;
					txmax = t;
				}

				if (d.y > -eps && d.y < eps)
					d.y = eps;

				float tymin = (min.y - a.y) / d.y;
				float tymax = (max.y - a.y) / d.y;

				if (tymin > tymax)
				{
					float t = tymin;
					tymin = tymax;
					tymax = t;
				}

				if ((txmin > tymax) || (tymin > txmax))
					return AABBOX_RAY_OUTSIDE;

				if (tymin > txmin)
					txmin = tymin;

				if (tymax < txmax)
					txmax = tymax;

				if (d.z > -eps && d.z < eps)
					d.z = eps;

				float tzmin = (min.z - a.z) / d.z;
				float tzmax = (max.z - a.z) / d.z;

				if (tzmin > tzmax)
				{
					float t = tzmin;
					tzmin = tzmax;
					tzmax = t;
				}

				if ((txmin > tzmax) || (tzmin > txmax))
					return AABBOX_RAY_OUTSIDE;

				if (tzmin > txmin)
					txmin = tzmin;

				if (tzmax < txmax)
					txmax = tzmax;
				
				if (txmin > txmax) 
				{
					float t = txmin;
					txmin = txmax;
					txmax = t;
				}
				
				if (txmin < -eps)     txmin = 0.0f;
				if (txmax > 1.0f+eps) txmax = 1.0f;
				
				p = a + txmin * d;
				q = a + txmax * d;
				
				return AABBOX_RAY_INTERSECTS;
			}

			static int AABoxVsSphereSAT(const glm::vec3 &s, float radius,
										const glm::vec3 &c, const glm::vec3 &halfextents,
										vml::geo3d::collisions::MTV &mtv)
			{
				// clean mtv data struct

				mtv.Distance = 0.0f;
				mtv.Normal = glm::vec3(0, 0, 0);
				mtv.ContactPoint = glm::vec3(0, 0, 0);
				mtv.SurfaceNormal = glm::vec3(0, 0, 0);
				mtv.HasContactPoints = false;

				// Find point p on OBB closest to sphere center

				glm::vec3 p;

				float dist;

				glm::vec3 d = s - c;

				// Start result at center of box; make steps from there

				p = c;

				// For each OBB axis...
				// ...project d onto that axis to get the distance
				// along the axis of d from the box center

				// x axis

				dist = d.x;

				// If distance farther than the box extents, clamp to the box

				if (dist > halfextents.x) dist = halfextents.x;
				if (dist < -halfextents.x) dist = -halfextents.x;

				// Step that distance along the axis to get world coordinate

				p.x += dist;

				// y axis

				dist = d.y;

				// If distance farther than the box extents, clamp to the box

				if (dist > halfextents.y) dist = halfextents.y;
				if (dist < -halfextents.y) dist = -halfextents.y;

				// Step that distance along the axis to get world coordinate

				p.y += dist;

				// z axis

				dist = d.z;

				// If distance farther than the box extents, clamp to the box

				if (dist > halfextents.z) dist = halfextents.z;
				if (dist < -halfextents.z) dist = -halfextents.z;

				// Step that distance along the axis to get world coordinate

				p.z += dist;

				// Sphere and OBB intersect if the (squared) distance from sphere
				// center to point p is less than the (squared) sphere radius

				glm::vec3 v = p - s;

				float l0 = v.x*v.x + v.y*v.y + v.z*v.z;
				
				// halfradius

				float l = l0 - radius * radius * 0.25f;

				if (l < 0)
				{

					mtv.Distance         = (sqrtf(l0) - radius*0.5f) * 1.01f;
					mtv.Normal           = glm::normalize(v);
					mtv.SurfaceNormal    = mtv.Normal;
					mtv.ContactPoint     = p;
					mtv.HasContactPoints = true;
					return 1;
				}

				return 0;
			}

		} // end of intersections namespace

	}	// end of geo3d namespace

}	// end of vml namespace


wow that is a lot of code

This is only a fraction of my vml libs, maybe one day will public everything as open source code , but for the moment enjoy this code.

But looks indeed more code than needed. A ray - aabb intersection can be as simple as this, for example:

		void DistanceRayFrontAndBackface (float &ffd, float& bfd, const vec& boxMin, const vec& boxMax, const vec& rayOrigin, const vec& rayInvDirection)
		{
			vec t0 = vec(boxMin - rayOrigin).MulPerElem (rayInvDirection);
			vec t1 = vec(boxMax - rayOrigin).MulPerElem (rayInvDirection);
			vec tMin = t0.MinPerElem (t1);
			vec tMax = t0.MaxPerElem (t1);
			ffd = tMin.MaxElem(); // front face distance (behind origin if inside box) 
			bfd = tMax.MinElem(); // back face distance	
		}

Should be much faster. Given Vector member functions boil down to a single SIMD instruction, and no branches.

My favorite resource to look up for more difficult intersection tests is this: https://github.com/davideberly/GeometricTools

This topic is closed to new replies.

Advertisement