Back to Coding Horrors

Slowest AABB overlap test ever?

Coding Horrors Community

Started by Finalspace July 03, 2017 08:37 AM

8 comments, last by SolDirix 5 years, 8 months ago

Finalspace

1,222

Author

July 03, 2017 08: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);
}

My youtube channel: https://www.youtube.com/user/F1nalspace

ApochPiQ

23,138

July 03, 2017 04: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.

Wielder of the Sacred Wands
[Work - ArenaNet] [Epoch Language] [Scribblings]

ferrous

6,164

July 03, 2017 05: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

3,287

July 03, 2017 06:30 PM

Compute it on the Cloud on multiple machines!

fastcall22

10,918

July 03, 2017 06: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

6,164

July 03, 2017 09: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

1,576

October 21, 2017 01: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

2,021

October 21, 2017 09: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.