Is there any good algorithm for detection between concave polygons? I'd appreciate any help as so far I've only found algorithms for detection between convex polygons.
-
3Did you even look at title of that question? It is about CONVEX polygons, my question is about concave ones.– Dariusz G. JagielskiDec 11, 2013 at 21:17
-
I too came to find out the answer but my solution is to break a concave polygon into convex polygons. we can do that with the pac man but what about a crescent moon? so I am heading to the below answer.– NecktwiFeb 12, 2017 at 21:34
3 Answers
This paper from 2004 explores an efficient collision detection algorithm for 2D polygons, regardless of concave- or convex-ness.
In case the link ever goes dead, here's some authorship/citation information:
Juan José Jiménez, Rafael J. Segura, Francisco R. Feito
Departamento de Informática. E.P.S.J. Universidad de Jaén
Journal of WSCG, Vol.12, No.1-3, ISSN 1213-6972
This is old, but still relevant and there doesn't seem to be alot of answers for this question, so here goes:
For polygons whose overall shape does not change (may rotate and scale, but relationships between vertices may not change), there are ways to pre-process the vertex data to achieve an and/or series of tests for the lines in the polygon to test if the other polygon collides with it.
I'm in the process of writing this algorithm, so I will provide you with the theory behind it instead of a ready-made one:
Legend: && means AND, || means OR.
Step 1a:
Going through the lines of the polygon and testing each line against all other points of it, we separate the lines where all other points are on the line or on the 'inside' side of the line.
These collected lines form a new node in the collision checking formula and they are considered to be logical AND checks in relation to one another.
Step 1b:
Separate each islanded vertexgroup into their own collections and feed them to the next steps separately: These islands are considered logical AND in relation to one another.
Step 1c:
If any lines were collected during step 1a and we are collecting more than one line at a time due to getting to step 3a/3b, reset any variables set in steps 3a/3b and step right back into 1a.
Step 2a:
Going through the lines of the polygon and testing each line against all other points of it, we separate the lines where all other points are on the 'outside' side of the polygon (or to put it more specifically, all on the non-colliding side of the line).
These collected lines form a new node in the collision checking formula and they are considered to be logical OR checks in relation to one another.
Step 2b:
Separate each islanded vertexgroup into their own collections and feed them to the next steps separately. These islands are considered logical OR in relation to one another.
Step 2c:
If any lines were collected during step 2a, reset any variables set in steps 3a / 3b and step right back into 1a.
Step 3a:
Getting to this stage means there are no lines left for which all vertices fall on one side of, which means we need to collect the lines more aggressively:
Raise the number of consecutive lines to be collected in steps 1a and 2a. This means instead of all vertices falling one a side of one line, they must fall on one side of at least one of the collected lines (inside in 1a and outside in 2a). This gets reset back to 1 once any lines are collected.
Step 3b:
If number of consecutive lines to be collected exceeds the number of lines in the shape, reset the number to 2 and allow collection of non-consecutive lines (arriving here is also a good indication that your mesh is a bit complicated and you may want to think about cutting it down a bit, getting to 3a is no big deal though, as a simple star shape requires entering it to solve).
When using the resulting nodes for collision testing, simply feed the shapes (point / line / circle) of the object to test against the processed mesh into the nodes one by one.
For two polygons to be collision tested, only one of them must be processed like this.
Creating the formula for an example polygon:
1) Feed the example polygon to step 1a:
The red lines in the picture are all lines of which all other vertices fall inside of, so a shape must be inside of all of them for the shape to be able to collide with the polygon.
The polygon will be islanded into two (A and B) after 1b.
2) Feed A and B to Step 2a:
The green lines in the picture are all lines of which all other vertices fall outside of, so a collision will occur if the shape is inside one of them.
Both islanded polygons A and B will be further islanded into C, D, E and F after 2b.
3) Feed C, D, E and F to step 1a:
The polygon C will lose one line (lets call the new shape G), D will be islanded into two (H and I) after step 1b and polygons E and F have no lines left to collect.
4) Feed G, H and I to step 2a:
The polygon G will be islanded into two (J and K) after step 2c, H will lose 2 lines (call the new shape L) and I will have no lines left to collect.
5) Feed J, K and L to Step 1a:
After this, all lines have been collected in just 3 repetitions of the steps.
The final formula for the original polygon then becomes: Final formula on one line and with phases marked down A bit more visual representation: Final formula with visual representation
Here's the original polygon with the lines marked: Polygon with lines marked
Using this method, concave polygons are the same speed or even faster to test collision against than if they were broken down into convex polygons (worst case scenario is the same time if both have same amount of vertices, best case scenario can cut tests down to all lines from step 1 and one line from step 2, cutting out testing for any of the more complex squiggles of the shape if collision happens elsewhere).
The limitations of this algorithm are at least the following:
1) If vertices of polygon are being animated, the above formula no longer applies and it has to be re-made. This is not a problem for a small amount of not-too-complicated polygons though, as the above steps are not very complicated (requires (n - 2)^2 of "which side of the line this point resides" -tests whose results can be cached and re-used throughout the steps).
2) Does not automatically handle holes in the polygon. Holes can be processed as above too though and just apply the following rule to it: a shape that collides with the original polygon must also either a) intersect with the lines of the hole or b) not collide with hole polygon for the collision to occurr.
3) The rules I presented for how to break the polygon down are not tested for arbitarily complex polygons and further rules may be needed to handle them.
4) You have to write the code for the algorithm yourself, as I have no intention of making a release until I have a working universal version, which may take a while.
Since I've done this recently, I thought I'd document the approach I used here as there don't seem to many clear answers.
This answer will avoid describing the underlying algorithm that's generally used for collision detection which is SAT (Separating Axis Theorem) as there is good information about that readily available. The information provided below provides instructions on how to add concave polygon support to an existing convex collision detection scheme.
Triangulation
The simplest form of convex decomposition is triangulation.
Simplest Approach
The easiest method for performing triangulation is ear-clipping which I found was most clearly described in this article.
Why Triangulate
While triangulation is a valid convex decomposition; it will lead to more SAT checks than a polygon decomposition so it's not optimal, however polygon decomposition often uses triangulation as the first step.
It's also worth noting that a triangle decomposition is good for calculating centroids, moment of inertia and other physical properties as well as being a nice option for rendering.
Improvements
Basic ear-clipping will produce very thin strips during triangulation which may not be ideal for collision checks and rendering, and can lead to less than optimal polygon decomposition.
Modified Ear-Clipping
Ear-clipping may be improved by selecting the ears with the best aspect ratio, as described in this article.
Delauney Triangulation
The delauney sweepline triangulation algorithm provides a triangulation with the maximum minimum internal angle. Put more simply it produces a triangulation with fewer thin strips, while the technique is readily searchable here is an article which describes the approach well.
Polygon Decomposition
Polygon decomposition is important as it reduces the number SAT axis checks which are required, which improves runtime performance.
Simplest Approach
The simplest approach to this is the Hertel-Mehlhorn algorithm which promises to produce no more than 4 times the number of polygons of the optimal solution. In practice for simple concave polygons this algorithm often produces the optimal solution.
The algorithm is very simple; iterate over the internal edges "diagonals" created by triangulation and remove non-essential diagonals. A non-essential diagonal is found when at either end of the diagonal the points linked would be convex. This is determined by testing the orientation of the points.
The best description of the algorithm I could find was this article.
Improvements
There are a large number of polygon decomposition algorithms with differing time-complexities, some can produce more optimal results for complex concave polygons, however in most real-time usage, the polygon complexity is likely low.
Implementation Details
Use Vertex Indexing
For both triangulation and polygon decomposition, it's best to perform the decompositions using indexing. This saves memory and provides an easy method to determine which edges are internal since external edges will always have adjacent indices.
SAT and Collision Normals
Since polygon decomposition creates internal edges, it can lead to an SAT collision returning a collision normal based on an internal edge. To work around this it's should be possible to differentiate between internal and external edges/normals, and discard any collision normals provided by internal edges.
Intersection & Constraints
A constraint based physics engine (e.g. box2d, chipmunk, bullet) can't provide concave primitives since this would allow for multiple points of collision which can't be resolved in a single tick. This means that for constraint based physics engines a joint must be used and since constraints can't always be met; there will be cases where the polygons are not strictly rigidly attached.
In a physics engine which supports CCD (Continuous Collision Detection) and does not allow for polygon intersections, it's possible to support convex collisions in the solver itself since there will by definition always be a first collision point. This obviously comes at the cost of performance.