browser icon
You are using an insecure version of your web browser. Please update your browser!
Using an outdated browser makes your computer unsafe. For a safer, faster, more enjoyable user experience, please update your browser today or try a newer browser.

Cutting Concave Polygons

Geschrieben von am 11. March 2012

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):

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
// Use this list for finished convex polygon results
ArrayList<Polygon> result = new ArrayList<Polygon>();

// Queue used for recursively handling polygons
ArrayDeque<Vector<Vec2>> queue = new ArrayDeque<Vector<Vec2>>();

queue.clear();

// Make sure there are no uncessecary vertices as the algorithm might
// not work otherwise
poly = simplify(poly);

// Make sure the vertices are in counter-clockwise order
if (!isCCW(poly))
{
    poly = flip(poly);
}

// Start off with the given polygon
queue.add(makeVectors(poly));

while (queue.size() > 0)
{
    // See if the polygon needs splitting and do it
    poly = handlePolygon(queue.remove());

    int last_vertex = vectors.size() - 1;
    boolean is_convex = true;

    // Walk through all vertices until we find a concave one
    for (int current_idx = 0; current_idx < vectors.size(); current_idx++)
    {
        // Grab a triplet of vertices
        int last_idx = current_idx == 0 ? last_vertex : current_idx - 1;
        int next_idx = current_idx == last_vertex ? 0 : current_idx + 1;

        Vec2 last = vectors.get(last_idx);
        Vec2 current = vectors.get(current_idx);
        Vec2 next = vectors.get(next_idx);

        // Use the cross product to determine if the current vertex is at a
        // concave position. If cross product is negative, the vertex is not
        // convex, so we need to split here
        if (Vec2.cross(current.sub(last), next.sub(current)) < 0)
        {
            is_convex = false;
            Segment ray = new Segment(last, current);

            int split_idx = current_idx;

            // To use the closest segment for ray intersection order them by
            // distance. Using the closest prevents the cut to go through any
            // unwanted segments.
            float min_distance = Float.MAX_VALUE;

            int hit_start = -1;
            int hit_end = -1;
            Vec2 hit_point = null;

            // For each segment in the polygon
            for (int start_idx = 0; start_idx < vectors.size(); start_idx++)
            {
                // Calculate the index of the end vertex
                int end_idx = start_idx == last_vertex ? 0 : start_idx + 1;

                // Ignore the ray segment and the one after it
                if (start_idx == split_idx || start_idx == last_idx)
                {
                    continue;
                }

                Segment segment = new Segment(vectors.get(start_idx), vectors.get(end_idx));

                // Try casting a ray along the problematic segment which if
                // successful can be used to split up the polygon along it
                Vec2 res = hitRay(ray, segment);

                if (res != null)
                {
                    // Hit another segment, so check if it's the closest one
                    float distance = res.sub(ray.end).lengthSquared();

                    // This one is closer to the original
                    if (distance < min_distance)
                    {
                        hit_point = res;
                        min_distance = distance;
                        hit_start = start_idx;
                        hit_end = end_idx;
                    }
                }
            }

            // Yay! Lets cut it up!
            if (hit_start != -1)
            {
                // Prepare the parts
                Vector<Vec2> part_a = new Vector<Vec2>();
                Vector<Vec2> part_b = new Vector<Vec2>();

                // Only add the new points if they are to far from the end/start of
                // the associated segment
                if (!deltaEquals(vectors.get(hit_end), hit_point))
                {
                    part_a.add(hit_point);
                }
                if (!deltaEquals(vectors.get(hit_start), hit_point))
                {
                    part_b.add(hit_point);
                }

                // Build the parts which both contain the new found cut as an edge
                for (int j = hit_end; j != split_idx; j = (j == last_vertex) ? 0 : j + 1)
                {
                    part_a.add(vectors.get(j));
                }
                for (int j = split_idx; j != hit_end; j = (j == last_vertex) ? 0 : j + 1)
                {
                    part_b.add(vectors.get(j));
                }

                // And check those new parts for convexity
                queue.add(part_a);
                queue.add(part_b);

                break;
            }
            else
            {
                throw new Error("Invalid polygon - polygons must not overlap!");
            }
        }
    }

    // The polygon was convex so we simply add it
    if (is_convex)
    {
        result.add(makePolygon(poly));
    }
}

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):

1

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 < 0 || segement_pos > 1)
{
return null;
}

// The hit point would be in opposite direction of the ray
if (ray_pos <= 0) { return null; } // Calculate the hit point return ray.start.add(ray.delta.mul(ray_pos)); }[/pygmentize] You can determin the offset ob both the ray and the segment using the formula: \text{rayoff} = \frac{(\mathbf{segend} - \mathbf{segstart}) \times (\mathbf{raystart} - \mathbf{segstart})}{(\mathbf{rayend} - \mathbf{raystart}) \times (\mathbf{segend} - \mathbf{segstart})} \\
\text{segoff} = \frac{(\mathbf{rayend}  - \mathbf{raystart}) \times (\mathbf{raystart} - \mathbf{segstart})}{(\mathbf{rayend}  - \mathbf{raystart}) \times (\mathbf{segend} - \mathbf{segstart})} 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: \mathbf{hitpoint} = \mathbf{raystart} + \text{rayoff} \cdot (\mathbf{rayend} - \mathbf{raystart}) 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 :)

Find ich gut!
0
  • Twitter
  • Facebook
  • email
  • RSS

Leave a Reply

Your email address will not be published. Required fields are marked *