Collision polygons - how the number of points affects performance?

Post reply
0 favourites
From the Asset Store
Point to Point - Happy Animals Educational Kids Game
$8 USD
Connect the dots in the correct order and draw happy animals!
01smile's avatar
01smile

  • We've all seen this warning message displayed when you are trying to add more than 8 points to a collision polygon.

    I decided to test if complex collision polygons are really that bad for performance. Here is the test project.

    Note, that this test is quite extreme - there are 210 rotating objects, each object is tested for overlapping with all other objects on every tick. That's about 2.5 million collision checks per second!

    And yet on my mid-level laptop the difference between 4 points and 20 points in the collision polygon is really not that big!

    I'm also working on another project, where people can load a custom image and its collision polygon is detected automatically. As a result, some images might have 200-300 points in their collision polygon. And this still doesn't cause any noticeable performance issues.

    Conclusion:

    First of all - kudos to Scirra for optimizing collision checks!

    Second - don't be afraid to add a few extra points when needed. But of course, try to keep the number of collision checks low.

    And finally - I think the threshold for that warning needs to be increased. Maybe show it after adding 15 or 20 points. And I would really like to be able to click "never show this message again" and hide if forever.

  • Interesting, and good points overall!

  • interesting... although honestly I don't see the need to have more than 8. Most of the time a simple box will do, you just make sure its within the sprite...

    showing a little overlap between sprites when they collide works well.

    I guess it depends on your art style but I've never needed to be so precise with the polygon that I needed more points...

  • We've all seen this warning message displayed when you are trying to add more than 8 points to a collision polygon.

    I decided to test if complex collision polygons are really that bad for performance. Here is the test project.

    Note, that this test is quite extreme - there are 210 rotating objects, each object is tested for overlapping with all other objects on every tick. That's about 2.5 million collision checks per second!

    And yet on my mid-level laptop the difference between 4 points and 20 points in the collision polygon is really not that big!

    I'm also working on another project, where people can load a custom image and its collision polygon is detected automatically. As a result, some images might have 200-300 points in their collision polygon. And this still doesn't cause any noticeable performance issues.

    Conclusion:

    First of all - kudos to Scirra for optimizing collision checks!

    Second - don't be afraid to add a few extra points when needed. But of course, try to keep the number of collision checks low.

    And finally - I think the threshold for that warning needs to be increased. Maybe show it after adding 15 or 20 points. And I would really like to be able to click "never show this message again" and hide if forever.

    Did you tested for mobile? Every platform must need to be taken together

  • jobel I sometimes need more than 10 points, when the shape is very complex, or when I need a perfect curve/circle, or like in this example when I needed to make a hole in the sprite:

    Cascade Games I did test on mobile with a smaller number of objects, and the difference in performance is still around 30%. Like I mentioned, it's an extreme case - 20 points per polygon is a lot! And 2.5M collision checks per second is something that should never happen in a real game.

  • jobel I sometimes need more than 10 points, when the shape is very complex, or when I need a perfect curve/circle, or like in this example when I needed to make a hole in the sprite:

    Cascade Games I did test on mobile with a smaller number of objects, and the difference in performance is still around 30%. Like I mentioned, it's an extreme case, 2.5M collision checks per second is something that should never happen in a real game.

    Cool

  • what if each orange/white part was it's own object, then put into a family? would their be a difference in performance since you could probably get away with a bounding box polygon for each...

  • Try Construct 3

    Develop games in your browser. Powerful, performant & highly capable.

    Try Now Construct 3 users don't see these ads

  • jobel Splitting the image into multiple parts, and pinning them to some base object (with drag&drop behavior) will require a lot more effort. And I imagine performance wise it will be much worse than one object with a complex collision polygon.

  • I wish we had more methods beside polygons. Objects in other objects are particularly hard to deal with, although tilemaps work in some situations.

  • Just an educated guess, but the engine probably does a bounding box collision test first, basically a rectangle that contains the entire object, and checks that against the bounding boxes of other objects. This is very fast to compute. If the bounding boxes don't collide, then there is no way the polygons collide, so no more computation needed. If the bounding boxes do collide, then then engine will then check to see if the more complex polygons collide.

  • simstratic Yeah, there's probably a lot of optimization going on.. Looks like the polygon shape matters more than the number of points. The polygon on the right has fewer points, but it's slower than the left one!

    Anyway, I'm still testing with an extreme number of collision checks. If there is one ball in the game, adding 5-10 extra points to its polygon for a more rounded shape will not cause any problems.

  • EDIT_2: THIS IS NOT CORRECT FOR CONSTRUCT - PLEASE SEE POST BELOW MINE. (2) is probably still applicable.

    dop2000 that is all a good sign that it is heavily optimized. There are two factors at play in your last example.

    (1) Polygon collisions are done by triangulating the polygon into a series of triangles (this may already be done when the project is exported). During a collision, each triangle is checked to see if it colliding with the triangles in the other object. As soon as a triangle collision is detected it can stop, i.e. it doesn't need to check all the triangles unless there is bounding box collision but NOT a polygon collision. There are different triangulation algorithms, some of which can favor large triangles which will be more likely to collide early. Spiky and concave objects will generally require smaller triangles.

    (2) The pink background almost shows what the bounding box would be (the one on the right would be a little smaller). The one on the left, the collision polygon occupies a much larger percentage of the bounding box, if the bounding boxes collide it is far more likely the polygons will be colliding, and an early collision will be probably detected and less triangles will be tested. Inversely, the one on the right occupies a smaller percentage of the bounding box, so you will get more cases where the bounding boxes collide, but the polygons do NOT collide, so it will have to check every triangle like I said in (1).

    The extreme case would be something like a very thin '+ or 'L' or '/' shape collision polygon that extends the entire height and width of the sprite. Because you would get many bounding box collisions, but less polygon collisions, so more triangles (points) would be checked.

    EDIT: One thing I forgot to mention, is long skinny objects (like a stick), when they are rotated in the game, will have larger bounding boxes, and hence more 'false positive' collisions where every triangle needs to be checked. So for these type of objects you want to minimize your points. All the above assumes a axis aligned bounding box collision optimization is being used in the engine.

  • I had to have a look at the collision code since i didn't think the collision polygon was triangulated, and it's not.

    the polygon collision code is made up of two parts: a check to see if a point is inside of a polygon and if two line segments overlap. Algo is basically this:

    O(1) if A and B in same spacial hash then continue

    O(1) if A and B bounding box overlap then continue

    O(n) loop over points in A, if any are inside poly B then stop, objects are overlapping

    O(m) loop over points in B, if any are inside poly A then stop, objects overlapping

    O(n*m) loop over edges in A and edges of B, if any two edges intersect then stop, objects overlap

    In general it tries to figure out as soon as possible if the objects overlap or not so it doesn't have to check everything. In front of each line I put the big O notion showing the complexity of each step. It starts with stuff that can be done with one check, then it's proportionate to the number of points, and finally it's proportionate to the number of points multiplied together.

    The main complexity that was probably the reasoning of the warning is the edge overlapping check. The max number of checks it can do is the A.pointCount*B.pointCount. So with the standard 8 point polys it's doing a maximum of 64 checks. Two 20 point ones could do a max of 400 checks.

    Edit:

    More points would make calculating an object's bounding box take a longer for objects with more points, but it's a linear increase.

    And what it's worth the physics object does triangulate the collision poly for it's uses. Actually with box2d it merely converts it into concave polygons.

  • Thanks for the correction and the information R0J0hound. I jumped in too early with some bad assumptions :) Didn't know we could look at the engine code in that much detail...

  • You're welcome. I was able to kind of browse it with the browser debugger when previewing a game. You can browse all the js files used, although the whitespace was stripped so i had to use a js beautifier to be able to better see what it did. I had poked around c2's collision detection before and it's largely the same, so I kind of knew what I was looking for.

Post reply
Return to board index
Jump to:
Active Users
There are 1 visitors browsing this topic (0 users and 1 guests)