Why should i use AABB for Circle-Circle collision

1
votes

In my wip game i have to implement Circle-Circle collisions. To implement this i simply calculate the square distance between their Centers (x1-x2)² + (y1-y2)². If this is smaller then their sqared radiuses (r1+r2)² a collision happened. But today i saw this link: Circle-Circle collision

Here they first use AABB collision to notice if the circles are near. But why should i do this? The circle-circle collision is a simple and not realy expensive calculation. When i use the AABB first i do at least the same number of calculations and if circles are near even more.

Let me explain:

I do an AABB collision detection for every circle with every other. So i have to do n! / (n-2)! calculations. n = number of circles to test. For every AABB colliding circle-pair i then have to do another calculation if they realy collide.

Without the AABB collision detection i only do n! / (n-2)! calculations and i don't think this calculations are so costly. What do you think?

2
algorithmcollision-detectiongeometryaabb
Typically, only few circles are really close together. So yes, you would need n(n-1) AABB checks (see that n!/(n-2)! = n(n-1)?), but typically only few collision checks. Say the AABB is only a factor 2 cheaper (it's probably more), then this is a speedup for small n already. – Vincent van der Weele
In hindsight, looking at the link you provided, I think you are indeed correct that comparing the squares is not more expensive than comparing the AABB. You will only have a speedup if you check the AABBs instead of computing the square roots, because those are time consuming. I think your method is fine without AABB check (might be even faster: 6 add/subtract + 3 multiply + 1 compare vs 8 add + 4 compare; depends on your compiler + hardware what will be better, I'd call it a tie ;-) ). – Vincent van der Weele
So the AABB is useful if your hardawr and/or Compiler is faster with additions then with multiplications? And if you are using square roots which you don't Need for circle-circle collision (but many People use them :P). Thanks for that fast answer. Can you post it as an answer so i can mark it as solved and vote you up? Thanks – Springrbua

2 Answers

1
votes

I think here is way you can do this in O(NlogN) in average case but O(N^2) in worst : -

  1. Consider each circle as rectangle of 2R*2R with center at center of circle.

  2. Use sweep line algorithm for rectangles which is O(NlogN + R) where is number of intersections.

  3. The intersecting pairs of rectangles can be checked as circles for intersection using your algorithm in O(R^2).

Note: If R is small then it is O(NlogN) but else if R = O(N) then it is O(N^2)

0
votes

This comment is the right answer. It depends on your Hardware and compiler. If you are using AABB detection first you have 8 add + 4 compare operations. If you compare the square distance and the square radiuses you do 6 add/subtract + 3 multiply + 1 compare. Maybe your hardware and compiler is faster with compares then with multiplications. But it shouldn't be a big difference in performance. If you instead of comparing the squares use the square roots (for whatever reason) you should do the AABB compare first cause square root calculations take some time. There are ofc also better Solutions like in this answer. If you have to do many detections between many objects you can think about one of this solutions.