🔒 Locked

Slowest AABB overlap test ever?

Started by Finalspace Jul 3, 2017 at 8:37 AM 8 replies 7k views

Original Post

Jul 3, 2017 at 8:37 AM

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);
}

ApochPiQ

Jul 3, 2017 at 4:56 PM

Take input AABB, call it Fred.
Turn Fred into a convex hull data structure.
Take input AABB, call it George.
For each vertex in George, do a point-in-convex-hull test against Fred.
Do not early out at any time.

ferrous

Jul 3, 2017 at 5:06 PM

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.

ongamex92

Jul 3, 2017 at 6:30 PM

Compute it on the Cloud on multiple machines!

fastcall22

Jul 3, 2017 at 6:48 PM


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.

ferrous

Jul 3, 2017 at 9:19 PM

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.

OandO

Oct 21, 2017 at 1:35 AM

On 03/07/2017 at 5:56 PM, ApochPiQ said:

Take input AABB, call it Fred.

Turn Fred into a convex hull data structure.

Take input AABB, call it George.

For each vertex in George, do a point-in-convex-hull test against Fred.

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.

lawnjelly

Oct 21, 2017 at 9:50 AM

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.

SolDirix

Aug 5, 2018 at 5:48 AM

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.

Topic Locked

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