Remember my last post on how to turn concave polygons into convex ones so that you can actually use them in Box2D? Well, turns out my solution didn't quite work out that well. The thing is, if you mess up the order of vertices in the polygon (Box2D requires them to be in counter-clockwise order), the results are really weird and the collision starts bugging out. So I looked around for some better solution that would work more reliably.
On the blog of Emanuele Feronato I found a great algorithm which is a lot more mathematical and less "lets try until it (maybe) works". It uses ray-casting to split up the polygons and I just had to port it to Java and clean it up a bit. So first of all the polygon needs to be simplified (meaning removing unnecessary vertices) and the order of the vertices must be counter clockwise (if you want to know how to do that, have a look at the source code here and some explanation here). First of all here is some source code (which might not actually work since I pasted it together for this blog post, for a definitely working version see the repository):
So let me try and explain how this algorithm works. First of all it uses a queue to recursively process all polygons - so if we cut one polygon in half we get two new ones that need checking. The algorithm runs through all corners of the polygon checking if they are all convex (in the picture to the right all but #4 are convex). If they are all convex, that's great and the polygon can just be kept as is. Otherwise we have to split it up at the given corner (from line 41).
That is where the ray-casting comes in as we basically follow the last segment's direction until we hit another segment of the polygon. This ray (red in the picture) is the line we will use to cut the polygon in half. This is done by checking each segment individually and using the one with the shortest distance (line 81). The new found hit point is then inserted into both new polygons. Now the most interesting part is the actual ray and seeing if it hits anything. The math for that comes from Graphics Algorithms FAQ (Subject 1.03):
private static Vec2 hitRay(Segment ray, Segment segment)
{
// See http://www.faqs.org/faqs/graphics/algorithms-faq/
float ray_numerator = Vec2.cross(segment.delta, ray.start.sub(segment.start));
float segement_numerator = Vec2.cross(ray.delta, ray.start.sub(segment.start));
float denominator = Vec2.cross(ray.delta, segment.delta);
// Segment and ray are parallel
if (denominator == 0)
{
return null;
}
float ray_pos = ray_numerator / denominator;
float segement_pos = segement_numerator / denominator;
// The potential hit point is not actually on the segment
if (segement_pos 1)
{
return null;
}
// The hit point would be in opposite direction of the ray
if (ray_pos 
Here if segoff is inbetween 0 and 1 the hit point is on the segment and if rayoff is positive then the ray hits it from the right direction as well so we have found ourselves a hit. All that is left to do here is calculating the actual hit point which is simple:
All that is left to do then is splitting the polygons up by adding the new diagonal. That is done in to first code from line 94 by splitting the list of vertices up using the two indices (the one of the ray segment and the one of the hit segment). Noteworthy is that the initial corner (the one that was concave) is left out in one polygon as it lies on the ray and is therefor redundant. So in the above example part A would contain the points #2 and #3 as well as the hit point and part B would have #4, #5, #1 and the hit point. In the next steps both parts would be checked for convexity as well - which they are, so that's the final result.
I hope I could help you guys if you're wondering how to make those stupid polygons convex... Feel free to leave some comments, suggestions or whatever. And you can use the code for pretty much anything you want. Grab it from the repository as that probably is the cleaner and ready-to-use version. Cheers :)