# 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 on other sites
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 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 on other sites

Compute it on the Cloud on multiple machines!

##### 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 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 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.
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 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 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.

## Create an account

Register a new account

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 14
• 14
• 45
• 22
• 27
• ### Forum Statistics

• Total Topics
634044
• Total Posts
3015212
×