Libgdx polygon triangulation

Question

Ok, so I have a polygon (simple but concave) that I'm trying to cut into triangles to make it collide with an other polygon.

I knew my polygone was concave, so i decided to use LibGDX EarClippingTriangulator to manage to cut it into triangles.

So, with this code, I get my triangles vertices :

public void triangulate()
    {
        Vector<float[]> trianglesVertices = new Vector<float[]>();
        ShortArray pointsCoords = new ShortArray();
        EarClippingTriangulator triangulator = new EarClippingTriangulator();

        // Cut in triangles
        pointsCoords = triangulator.computeTriangles(this.getTransformedVertices());

        // Make triangles
        for (int i = 0; i < pointsCoords.size / 6; i++)
        {
            trianglesVertices.add(new float[] {
                    pointsCoords.get(i), pointsCoords.get(i+1),
                    pointsCoords.get(i+2), pointsCoords.get(i+3),
                    pointsCoords.get(i+4), pointsCoords.get(i+5),
            });
            Polygon triangle = new Polygon(trianglesVertices.get(i));
            triangles.add(triangle);
        }

        System.out.printf("Triangulation made %d triangles.\n", pointsCoords.size / 6);
    }

But when i try to draw thoses triangles I just made, they just stack in the 0,0 coord.. And, is it normal that all triangles seems almost the sames, I mean they all got the same orientation ?

I didn't found so much info about this trangulation use for libgdx Can you help ?

(Sorry for my english i'm french, and sorry for no pictures, i'm too young here)

EDIT: This is my polygon (in CCW)

hitbox.setVertices(new float[]{  
                this.getX() + 13, this.getY() - 60,
                this.getX() + 16, this.getY() - 74,
                this.getX() + 39, this.getY() - 74,
                this.getX() + 45, this.getY() - 105,
                this.getX() + 81, this.getY() - 105,
                this.getX() + 88, this.getY() - 74,
                this.getX() + 108, this.getY() - 74,
                this.getX() + 114, this.getY() - 61,
                this.getX() + 106, this.getY() - 30, // Top right
                this.getX() + 101, this.getY() - 29,
                this.getX() + 101, this.getY() - 57,
                this.getX() + 83, this.getY() - 62,
                this.getX() + 75, this.getY() - 50,
                this.getX() + 65, this.getY() - 4, // Top mid
                this.getX() + 62, this.getY() - 4, // Top mid
                this.getX() + 52, this.getY() - 50,
                this.getX() + 44, this.getY() - 62,
                this.getX() + 25, this.getY() - 56, 
                this.getX() + 25, this.getY() - 30,
                this.getX() + 19, this.getY() - 30,  // Top left
                });

EDIT2: Now i got enough point to show you the polygon here it is

Arc

Can you bring the polygon you have trouble with? – Nonsuch

I just add it, in fact it's a ship – Arc

Answer 1

The problem is with your loop:

        // Make triangles
        for (int i = 0; i < pointsCoords.size / 6; i++)
        {
            trianglesVertices.add(new float[] {
                    pointsCoords.get(i), pointsCoords.get(i+1),
                    pointsCoords.get(i+2), pointsCoords.get(i+3),
                    pointsCoords.get(i+4), pointsCoords.get(i+5),
            });
            Polygon triangle = new Polygon(trianglesVertices.get(i));
            triangles.add(triangle);
        }

First triangle will have correct coordinates, but second one will will use 1, 2, 3, 4, 5, 6 elements of pointsCoords that doesn't make any sence. You should multiply i by 6 inside loop to take offset into account:

                    pointsCoords.get(i*6), pointsCoords.get(i*6 + 1),
                    pointsCoords.get(i*6 + 2), pointsCoords.get(i*6 + 3),
                    pointsCoords.get(i*6 + 4), pointsCoords.get(i*6 + 5),

Nonsuch

Well you're right, the triangulation works well now. The only one problem left is their position, i make the triangulation from the transformed vertices of my polygon, but the triangles still at coords 0,0 even after translation – Arc

Yep, i finally didn't use EarClipping Triangulator. I cut by myself the Ship into convex polygons, then check for each one if it collide. For exemple my ship took nine polygons. But it works very well :) – Arc

Answer 2

The issue here is that EarClippingTriangulator.computeTriangles is returning different output than you're expecting. It returns an array of indices, where each index represents a vertex in the array you passed in originally. So if you passed in an array of size 8, that would represent 4 vertices; the array returned would be size 6 (3 vertices for triangle 1, 3 vertices for triangle 2).

Let's say you have a 2 x 3 rectangle with the bottom left at (5, 5). Your vertices would be:

• Vertex 0: (5, 5)
• Vertex 1: (7, 5)
• Vertex 2: (7, 10)
• Vertex 3: (5, 10)

You would flatten those down to an array and pass them into computeTriangles as:

[5, 5, 7, 5, 7, 10, 5, 10]

The returned array would look something like this:

[0, 3, 2, 2, 1, 0]

Each set of three indices in the returned array forms a triangle. Each of those values represents the index of a vertex in the data you passed in. In this example, the output would be telling you to use these vertices:

• Triangle 1: Vertex 0, Vertex 3, Vertex 2
• Triangle 2: Vertex 2, Vertex 1, Vertex 0

So you would need to draw these triangles:

• Triangle 1: (5, 5) -> (5, 10) -> (7, 10)
• Triangle 2: (7, 10) -> (7, 5) -> (5, 5)

Note that this is not necessarily the actual output you would get with the inputs I provided, it's just a sample designed to illustrate how you're supposed to use the data returned.

Here's the code I ended up with, which will correctly draw Polygon instances, although you can do the same thing with any properly formulated vertex array:

private void drawFilledPolygon(Polygon polygon, Color color) {
    shapeRenderer.begin(ShapeRenderer.ShapeType.Filled);
    shapeRenderer.setColor(color);

    float[] vertices = polygon.getTransformedVertices();

    // NOTE: you probably don't want to create a new EarClippingTriangulator each frame
    ShortArray triangleIndices = new EarClippingTriangulator().computeTriangles(vertices);
    for (int i = 0; i < triangleIndices.size; i += 3) {
        shapeRenderer.triangle(
            vertices[triangleIndices.get(i) * 2], vertices[triangleIndices.get(i) * 2 + 1],
            vertices[triangleIndices.get(i + 1) * 2], vertices[triangleIndices.get(i + 1) * 2 + 1],
            vertices[triangleIndices.get(i + 2) * 2], vertices[triangleIndices.get(i + 2) * 2 + 1]
        );
    }

    shapeRenderer.end();
}

Overarm