I'm working on a 2D game engine and I'm trying to get collision detection as efficient as possible. One thing I've noted is that I have a Rectangle Collision collider, a Shape (polygon) collider and a circle collider. Would it be more efficient (either dev-time wise or runtime wise) to have just one shape collider, rather than have that and everything else? I feel it would optimize my code in the back end, but how much would it affect my game at runtime? Should I be concerned with this at all, as 3D games generally have tens of thousands of polygons?
\$\begingroup\$
\$\endgroup\$
6
-
1\$\begingroup\$ If you complete polygon to polygon there's little reason to hand-roll OBB related routines, unless you have a lot of spare time on your hands. Speed benefits will be negligible. Box2D does not even have specific OBB routines (anymore). Adding circle to polygon isn't too hard and can be done pretty quickly. \$\endgroup\$– RandyGaulCommented Oct 21, 2013 at 9:41
-
1\$\begingroup\$ Most physics engines use a broadphase pass to filter out the majority of the noncollisions. Most of those tens of thousands of polygons aren't colliding with a large number of other polygons \$\endgroup\$– ThorinIICommented Oct 21, 2013 at 9:43
-
\$\begingroup\$ A square is a polygon? \$\endgroup\$– TheNickmaster21Commented Oct 21, 2013 at 11:14
-
\$\begingroup\$ @TheNickmaster, that is irrelevant. It isn't the fact that a square is a polygon. It's the fact that only an axis-aligned, rectilinear structure (which includes axis-aligned squares) enables very rapid conditional/arithmetic prechecks / elimination. \$\endgroup\$– EngineerCommented Oct 21, 2013 at 19:14
-
1\$\begingroup\$ @ThorinII is correct. In fact ALL such engines, including Box2D, use broadphase filters. It is the only logical approach. Just because Box2D no longer exposes that through it's public API (if that is true), does not mean it is not being used internally. \$\endgroup\$– EngineerCommented Oct 21, 2013 at 19:15
|
Show 1 more comment
2 Answers
\$\begingroup\$
\$\endgroup\$
Why do we use axis-aligned bounding boxes (AABBs) in collision detection? This question has been asked and answered more than once on this site, but I will answer it here again, briefly.
AABB checks are an optimisation. And the optimisation works as follows: You do the very cheap check before you even approach doing the order-of-magnitude more expensive check. The latter, more expensive check still has a good chance of failing. Because the disparity between execution times for these two types of checks is so large, it is statistically worthwhile to always do AABB pre-checks. This would still be the case even if 50% of all bodies in the world were colliding on every single frame.
Why are AABB checks so very cheap, by comparison? Because they are nothing more than a greater-than or less-than check, limited to one each per individual axis (2 in 2D, 3 in 3D). There is no trig, there are no divisions, there are no square roots, and there is no iteration (which introduces excess conditionals).
So provided that you've already precalculated what your maximum extents are in each axis, this is a very rapid pre-check that can be used to eliminate far more expensive checks which utilise one or more of the aforementioned operations -- any of which polygonal checks will require (and this worsens as per the Curse of Dimensionality). This is further compounded by the number of discrete elements per polygon (2D) / polyhedron (3D), i.e. points, edges and (3D) faces. O(n) in the number of pertinent elements, vs. O(d) where d is the dimensionality.
\$\begingroup\$
\$\endgroup\$
It's simple, the more vertices you have, the higher the performance cost. But, keep in mind you are doing 2D collisions so it's not as intensive as 3D. Doesn't mean things can't get complicated, but for the most part there won't be a huge difference between a square and say, an octagon or some custom polygon. Take a look at Box2D and how they handle more complicated collisions and notice how little performance is required.
Now, if this is for mobile then every vert counts so keep that in mind. There will be a much larger difference from a square and an 100 vert pixel perfect collider on mobile. But not so much on PC's because of things like dedicated vRAM that phones don't have (most).
