Polygon triangulaton

I’m loving using jme for a cartography project - rendering building floor-plans and similar. One thing has been bugging me about polygons:

I have a concave polygon defined by a set of corner points - what is the simplest way to render it? My problem is that I don’t have a triangulation - some polygons have holes, and might be a little non-planar.

The opensource java tesselators I’ve found haven’t been of great robustness (I run a lot of data through this). gluTess used to be super-robust, but I can’t find a way to use it in the jme3?

Thanks!

One way is to write an algorithm to make triangles out of your polygon.

Another simpler approach: you can load your model in blender, triangulate it there and export it to jme.

Where do your polygons come from? Your description makes it sound very difficult… and a collection of possibly-non-planar points cannot be consistently turned into triangles, anyway.

Thanks for the suggestions!

@The_Leo, I’ve learnt never to try and avoid writing geometry algorithms wherever possible. It’s easy to spend weeks fixing all the edge cases.

@pspeed The source is a mapping data. Systems such as GML define polygons and holes using lists of corners.

I can work in 2D if required, but I seem to recall the GLU tesselator gave solid results with moderately non-planar/3D faces as inputs?

If you can make it a 2D problem then you might be able to use Swing/AWT’s Polygon class. It only works with integer vertexes but you can always scale it up.

Else there is no way around either writing something or finding a working library.

@pseed thanks for confirming that there’s nothing in jme. I’ll go hunting for a 3rd party library - AWT seems like a strong contender.

I’m using an open source constrained delaunay triangulation library called jmescher for my true type font library. It can be found at Google Code Archive - Long-term storage for Google Code Project Hosting.

It is dependent upon two GPL libraries that can easily be removed. @louhy created https://github.com/hamersly/jDelaunay that can replace the javax.vecmath dependency.

The APFloat library doesn’t need to be replaced, there are, if memory serves, two methods in the Mesh class that need to be commented out and two that need a slight adjustment to account for the now missing methods. The two methods are only used when advanced precision is required which is only really necessary if you’re doing something like facial recognition.

This library only takes in a series of points and edges then triangulates them. It doesn’t account for holes or the fact that your desired result is concave. Holes will be filled in with triangles so you need a method to determine whether a particular triangle is inside or outside of your desired shape.

For me it wasn’t too hard, glyph contours in a true type font are read so that the ‘inside’ of the shape is to the right of the direction of travel. What I did was modify the addConstraint method in the Mesh class of jmescher so that it would return the HalfEdge created by adding the constraint and then maintained a list of the HalfEdge constraints that I added. When triangulation was finished I determined what triangles were in the shape by looking at each constraint in the list and determining if the off-edge point in the associated triangle was to the right of the edge or not, if it was I added the HalfEdge's triangle to the list of triangles to draw, if it wasn’t I added the HalfEdge's ‘sibling’ traingle instead.

In jmescher you can get the three points of a triangle by looking at a HalfEdge. Each HalfEdge is defined by an origin point the the origin point of the next HalfEdge. So a full triangle is defined as HalfEdge.origin, HalfEdge.next.origin and HalfEdge.next.next.origin. For each HalfEdge in my constraints the off-edge point is HalfEdge.next.next.origin.

So what I did was create a class that defines a constraint edge:

private class Seg {
    public final Point p1;
    public final Point p2;
    public HalfEdge he;
    
    private Seg(Point p1, Point p2) {
        this.p1 = p1;
        this.p2 = p2;
    }
    
    /**
        * Determines if the supplied point is on the right side of
        * the line segment.
        * 
        * @param p The point to check against.
        * @return True if the point is on the right side otherwise false.
        */
    public final boolean onRight(Point p) {
        return (p2.x - p1.x) * (p.y - p1.y) - (p2.y - p1.y) * (p.x - p1.x) < 0;
    }
    
    /**
        * Determines if the supplied point is on the segment.
        * 
        * @param p The point to check against.
        * @return True if the point is on the line segment otherwise false.
        */
    public final boolean onLine(Point p) {
        float ab = FastMath.sqrt(FastMath.sqr(p2.x - p1.x) + FastMath.sqr(p2.y - p1.y));
        float ap = FastMath.sqrt(FastMath.sqr(p.x - p1.x) + FastMath.sqr(p.y - p1.y));
        float pb = FastMath.sqrt(FastMath.sqr(p2.x - p.x) + FastMath.sqr(p2.y - p.y));
        float result = ab - (ap + pb);
        
        return (result >= 0) ? result < EPSILON : result > -EPSILON;
    }
}

Whenever I created an edge while reading the contour I used this class with p1 as the starting point of the edge and p2 as the ending point, he was set later when I added the constraint to the triangulation. Then I iterated over the list of segs using the onRight method to determine if the off-edge point of the triangle was on the right or left. In jmescher each HalfEdge has a ‘sibling’ which is the opposite triangle, if the off-edge point was on the right, great, if not the ‘sibling’ triangle’s off-edge point was on the right.

I don’t know the format you’re using to get the points that define your shape, but I must assume there’s some method for determining where the ‘inside’ of the shape is in relation to the points you’re reading.

P.S. In regards to creating glyphs there’s quite a few more steps than just the above, such as looking for triangles inside the shape that don’t share an edge with the contour, looking for overlapping quadratic curve triangles and splitting them in two etc…

Thanks @Tryder! This looks like a more dependable (and faster) library than the alternatives.

I’ve gotten good results with J3D’s old ear clipping implementation - it was only necessary to import 4 classes (EarCutTriangulator, HashSet, ObjectArray, and PolyVertex). But I haven’t run any stress tests yet…

1 Like