1
\$\begingroup\$

This question already has an answer here:

I have a number of quads (suppose like 20-40) and i want to quickly check the collisions between any of them. I would like to know if there's a quick algorithm to do that 60 times per second without performance decrease

\$\endgroup\$

marked as duplicate by Seth Battin, Kromster, Anko, Josh Jul 23 '15 at 16:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • \$\begingroup\$ Regarding my close vote: your answer lays firmly within the "collision detection" section of the accepted answer to that question. Spoiler: the answer is space partitioning. \$\endgroup\$ – Seth Battin Jul 15 '15 at 13:59
  • \$\begingroup\$ Oh i didn't see the duplicate, thanks for that by the way. \$\endgroup\$ – user51054 Jul 15 '15 at 14:04
3
\$\begingroup\$

You may want to consider looking to spacial partitioning, such as a Quadtree.

In a nutshell, you would be dividing your world into sub-sections, and only check collisions between objects that are inside of the same sub-sections, greatly improving the complexity.

\$\endgroup\$
0
\$\begingroup\$

In the worst case (for 40 AABBs) you'll need to do 780 tests. There's not going to be any problems with a simple 4 comparison test:

a_min.x <= b_max.x
b_min.x <= a_max.x
a_min.y <= b_max.y
b_min.y <= a_max.y

If all of these are true, you have an intersection.

At this point partition structures (like AABB trees) are not necessary at all. You might only want to start thinking about them when test count goes over 10 000, which is when you need to test about >140 AABBs.

Best to avoid using the broadphase for as long as you can because it will introduce a lot of complexity and hard choices and measurements. Not one of them is going to give a good speed improvement without serious workload and staying within special constraints with your AABBs.

\$\endgroup\$
  • \$\begingroup\$ So you're claiming that a simple collision test between two bodies will overwhelm having an O(n^2) algorithm for the number of tests? I disagree. \$\endgroup\$ – Seth Battin Jul 15 '15 at 14:09
  • \$\begingroup\$ @SethBattin I'm not sure what you think I'm saying. And what "bodies"? To my understanding, we're talking about AABBs here. \$\endgroup\$ – snake5 Jul 15 '15 at 14:14
  • \$\begingroup\$ I'm saying that recommending against a broadphase because each individual test is simple is bad advice. Your performance threshold numbers are going to be completely technology- and system- dependent; they aren't good rules of thumb. And you're conflating bounding boxes of bodies with the structure that holds them (a tree), which doesn't make sense either. \$\endgroup\$ – Seth Battin Jul 15 '15 at 17:53
  • \$\begingroup\$ @SethBattin A low-end 1 GHz CPU on Android can easily crunch at least 100k hash table reads per second, you think 3200 two-instruction cache-efficient comparisons can slow anything down? No need to assume ridiculous things. Any tech this wouldn't work on was discontinued at least 10 years ago. As for "conflating" - you seem to be imagining things now. a) Nobody except you is talking about "bodies". b) OP wants to compare AABBs. c) At no point did I say that AABBs have to be integrated in AABB trees. P.S. BVHs have overhead, you know. It's not like they magically speed things up for free. \$\endgroup\$ – snake5 Jul 15 '15 at 19:03
0
\$\begingroup\$

A nice but lesser well known algorithm for this situation is called dimensional reduction.

If you keep your list of rectangles sorted on one axis (say, x axis by sorting on the minimum x value of the rectangles), then collision detection just becomes a 1 dimensional overlap test on the y axis, for whatever overlaps there were on the x axis.

Works better when most objects are stationary, but the same is true of all spatial subdivision algorithms (;

\$\endgroup\$