How does Java triangulate a Path2D?

Question

I'm developing an application that parses glyph data from a TrueType Font and converts it into polygons for rendering using OpenGL ES 2.0.

I've managed to convert the glyph data into discrete instructions such as MOVE_TO, LINE_TO, QUAD_TO and CLOSE, similar to Java's Path2D class. I then triangulate these paths for rendering.

The problem I am having is that I seem to be handling these instructions in a non-standard way, since I can effectively render some fonts but fail to render others, as shown below. After some testing it seems to be the decision making logic I'm using when moving between LINE_TO and BEZIER_TO instructions, but I cannot find a sequence that is compatible with both fonts.

Is there any online documentation available on how Java's Path2D data is triangulated?

1. A correctly rendered glyph ('c').

2. An incorrectly rendered glyph, from a different font ('c').

In the snippet below, I am choosing the points to plot for triangulation. Whether we're on the inside or outside of the curve, we plot the ends of the Bezier curve or the Bezier control point. The Bezier curves are correctly rendered separately to this code.

switch(lVectorPathComponent) {
        case MOVE_TO   :
            /* Append the current vertex to PolygonPoints. */
            if((lLastPathComponent == EVectorPathComponent.BEZIER_TO || lLastPathComponent == EVectorPathComponent.MOVE_TO)) {
                lPolygonPoints.add(new PolygonPoint(pVectorPath.getPathData()[i + 1], pVectorPath.getPathData()[i + 2]));
            }
            /* Initialize the start location of the path. */
            lStartX = pVectorPath.getPathData()[i + 1];
            lStartY = pVectorPath.getPathData()[i + 2];
        break;
        case LINE_TO   : 
            if(lLastPathComponent != EVectorPathComponent.MOVE_TO) {
                lPolygonPoints.add(new PolygonPoint(pVectorPath.getPathData()[i + 1], pVectorPath.getPathData()[i + 2]));
            }
            else {
                if((lNextPathComponent == EVectorPathComponent.LINE_TO || lNextPathComponent == EVectorPathComponent.BEZIER_TO)) {
                    lPolygonPoints.add(new PolygonPoint(pVectorPath.getPathData()[i + 1], pVectorPath.getPathData()[i + 2]));
                }
            }
        break;
        case BEZIER_TO : 
            if(VectorPathGlobal.onCalculateBezierDirection(pVectorPath, i) == pVectorPath.getWindingOrder()) {
                if(!(lLastPathComponent == EVectorPathComponent.LINE_TO && lNextPathComponent == EVectorPathComponent.BEZIER_TO)) {
                    lPolygonPoints.add(new PolygonPoint(pVectorPath.getPathData()[i - 2], pVectorPath.getPathData()[i - 1])); /* Last X, Y */
                    lPolygonPoints.add(new PolygonPoint(pVectorPath.getPathData()[i + 1], pVectorPath.getPathData()[i + 2])); /* Control Point */
                    lPolygonPoints.add(new PolygonPoint(pVectorPath.getPathData()[i + 3], pVectorPath.getPathData()[i + 4])); /* Bezier end X, Y */
                }
            }
            else {
                lPolygonPoints.add(new PolygonPoint(pVectorPath.getPathData()[i + 3], pVectorPath.getPathData()[i + 4]));
            }
        break;
        case CLOSE     : 
            lPolygonPoints.add(new PolygonPoint(lStartX, lStartY));
        break;
    }
}

The correctly rendered curve consists of these commands:

MOVE_TO x:121.0 y:682.0
BEZIER_TO cx:121.0 cy:840.0 x:164.0 y:969.0
BEZIER_TO cx:208.0 cy:1098.0 x:289.0 y:1189.0
BEZIER_TO cx:370.0 cy:1281.0 x:485.0 y:1330.0
BEZIER_TO cx:601.0 cy:1380.0 x:746.0 y:1380.0
BEZIER_TO cx:797.0 cy:1380.0 x:838.0 y:1374.0
BEZIER_TO cx:880.0 cy:1369.0 x:914.0 y:1360.0
BEZIER_TO cx:949.0 cy:1351.0 x:978.0 y:1339.0
BEZIER_TO cx:1007.0 cy:1327.0 x:1033.0 y:1314.0
LINE_TO x:978.0 y:1184.0
BEZIER_TO cx:929.0 cy:1207.0 x:872.0 y:1220.0
BEZIER_TO cx:816.0 cy:1234.0 x:746.0 y:1234.0
BEZIER_TO cx:650.0 cy:1234.0 x:571.0 y:1202.0
BEZIER_TO cx:492.0 cy:1170.0 x:435.0 y:1102.0
BEZIER_TO cx:379.0 cy:1035.0 x:348.0 y:931.0
BEZIER_TO cx:317.0 cy:827.0 x:317.0 y:682.0
BEZIER_TO cx:317.0 cy:537.0 x:349.0 y:432.0
BEZIER_TO cx:382.0 cy:327.0 x:441.0 y:259.0
BEZIER_TO cx:500.0 cy:191.0 x:583.0 y:158.0
BEZIER_TO cx:666.0 cy:126.0 x:768.0 y:126.0
BEZIER_TO cx:811.0 cy:126.0 x:847.0 y:131.0
BEZIER_TO cx:884.0 cy:137.0 x:915.0 y:146.0
BEZIER_TO cx:946.0 cy:155.0 x:972.0 y:165.0
BEZIER_TO cx:998.0 cy:176.0 x:1020.0 y:186.0
LINE_TO x:1062.0 y:58.0
BEZIER_TO cx:1009.0 cy:25.0 x:933.0 y:2.0
BEZIER_TO cx:858.0 cy:-20.0 x:746.0 y:-20.0
BEZIER_TO cx:601.0 cy:-20.0 x:485.0 y:30.0
BEZIER_TO cx:370.0 cy:81.0 x:289.0 y:173.0
BEZIER_TO cx:208.0 cy:265.0 x:164.0 y:394.0
BEZIER_TO cx:121.0 cy:524.0 x:121.0 y:682.0

The incorrectly rendered curve uses these:

MOVE_TO x:831.0 y:1391.0
BEZIER_TO cx:556.0 cy:1391.0 x:398.0 y:1215.0
BEZIER_TO cx:240.0 cy:1039.0 x:240.0 y:733.0
BEZIER_TO cx:240.0 cy:420.0 x:389.0 y:247.0
BEZIER_TO cx:538.0 cy:74.0 x:815.0 y:74.0
BEZIER_TO cx:999.0 cy:74.0 x:1153.0 y:121.0
LINE_TO x:1153.0 y:31.0
BEZIER_TO cx:1008.0 cy:-20.0 x:791.0 y:-20.0
BEZIER_TO cx:483.0 cy:-20.0 x:306.0 y:179.0
BEZIER_TO cx:129.0 cy:378.0 x:129.0 y:735.0
BEZIER_TO cx:129.0 cy:958.0 x:213.0 y:1128.0
BEZIER_TO cx:298.0 cy:1298.0 x:456.0 y:1390.0
BEZIER_TO cx:615.0 cy:1483.0 x:825.0 y:1483.0
BEZIER_TO cx:1039.0 cy:1483.0 x:1208.0 y:1403.0
LINE_TO x:1167.0 y:1311.0
BEZIER_TO cx:1007.0 cy:1391.0 x:831.0 y:1391.0

Answer 1

I've found that the tessellation methods used in LibTess2 were compatible with Java's Path2D triangulation.

In my original question, the issue I was having was that for triangulation of my vertices I was using Poly2Tri, which doesn't support vertices that lie on the edge of the polygon; because of this issue, a few strange triangles were being generated that seemed to ramp down to the origin. LibTess2 also struggles to triangulate non-simple polygons, however upon detection of conflicting vertices, it allows the user to provide a method for resolving the conflict via it's combine() method callback. By making an equality between conflicting vertices, erroneous tessellation could be resolved, which results in a correctly triangulated glyph. earcut-j is also robust enough to handle these vertices.