Jump to content
  • Advertisement
Finalspace

Slowest AABB overlap test ever?

Recommended Posts

Well found a very old aabb overlap test of mine, still works but well... it may be slow, maybe its slowest ever - or it is not that bad?

Try to beat it ;)

union Vec2f {
	struct {
		float x, y;
	};
	float m[2];
};

union AABB {
	struct {
		Vec2f min, max;
	};
	Vec2f m[2];
};

bool IsAABBOverlap(const AABB &a, const AABB &b) {
	// @SPEED: This is the slowest aabb overlap test ever exists!
	float distanceX = a.max.x - a.min.x;
	float distanceY = a.max.y - a.min.y;
	float otherDistanceX = b.max.x - b.min.x;
	float otherDistanceY = b.max.y - b.min.y;
	float bothRadiusX = (Abs(distanceX) + Abs(otherDistanceX)) * 0.5f;
	float bothRadiusY = (Abs(distanceY) + Abs(otherDistanceY)) * 0.5f;
	float otherCenterX = b.min.x + otherDistanceX * 0.5f;
	float otherCenterY = b.min.y + otherDistanceY * 0.5f;
	float centerX = a.min.x + distanceX * 0.5f;
	float centerY = a.min.y + distanceY * 0.5f;
	float diffX = Abs(centerX - otherCenterX);
	float diffY = Abs(centerY - otherCenterY);
	float overlapX = diffX - bothRadiusX;
	float overlapY = diffY - bothRadiusY;
	float result = !(overlapX > 0 || overlapY > 0);
	return(result);
}

 

Share this post


Link to post
Share on other sites
Advertisement
  1. Take input AABB, call it Fred.
  2. Turn Fred into a convex hull data structure.
  3. Take input AABB, call it George.
  4. For each vertex in George, do a point-in-convex-hull test against Fred.
  5. Do not early out at any time.

 

Share this post


Link to post
Share on other sites

Make it multithreaded!  Spawn a thread to check if a.max.X < b.min.X, then spawn another thread to check the Y, etc.  then wait for all the threads to return to compute the result.  Should be blazingly fast.

Share this post


Link to post
Share on other sites
bool intersects(const AABB& a, const AABB& b) {
	AABB test = {
		min(max(a.min, b.min), b.max),
		min(max(a.max, b.min), b.max),
	};

	return (test.max - test.min).sq_len() > FLOAT_EPSILON;
}

Erm, I mean…  Post each query to a math forum, using a rendering of the two AABBs on a 3D graph.  If the account gets banned for spamming, just keep making new ones.

Share this post


Link to post
Share on other sites

Render the results to an offscreen render target, with each being a different color and opacity, then check the contents of the texture for a pixel that is overlapped.  For an optimization you can return early on the first pixel you find that is overlapped.

Share this post


Link to post
Share on other sites
On 03/07/2017 at 5:56 PM, ApochPiQ said:
  1. Take input AABB, call it Fred.
  2. Turn Fred into a convex hull data structure.
  3. Take input AABB, call it George.
  4. For each vertex in George, do a point-in-convex-hull test against Fred.
  5. Do not early out at any time.

 

Fails to detect intersections where no vertex of Fred is inside the convex area of George or vice versa.
Addendum:
6. Create edge line segments between every pair of vertices in Fred.
7. Create edge line segments between every pair of vertices in George.
8. Perform line segment intersection test for every edge in Fred against every edge in George.

Share this post


Link to post
Share on other sites
8 hours ago, OandO said:

Fails to detect intersections where no vertex of Fred is inside the convex area of George or vice versa.

No no no. Instead of all that complex error-prone maths, use brute force:
 
6. Choose random point within George, check whether it is within Fred.
7. If within Fred, terminate, they overlap.
8. If not within Fred, repeat from 6.
 
While this will terminate earlier in many cases of overlap, in the case of no-overlap, the routine will NEVER terminate, because it can't be sure. Bonus points if the random points are floating point, and you keep a history to prevent checking the same point twice as an optimization.

Share this post


Link to post
Share on other sites

Or you could just use a physics/collision engine. That can sidestep the issue.

I remember the olden days when I used to try to build my own collision engine, only to have the whole dang thing replaced by Bullet Physics later on.

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
×

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!