Function Triangulate

Source/Engine/Tools/ModelTool/ModelTool.OpenFBX.cpp:542–704

}

int Triangulate(OpenFbxImporterData& data, const ofbx::GeometryData& geom, const ofbx::GeometryPartition::Polygon& polygon, int* triangulatedIndices)
{
    if (polygon.vertex_count < 3)
        return 0;
    else if (polygon.vertex_count == 3)
    {
        triangulatedIndices[0] = polygon.from_vertex;
        triangulatedIndices[1] = polygon.from_vertex + 1;
        triangulatedIndices[2] = polygon.from_vertex + 2;
        return 3;
    }
    else if (polygon.vertex_count == 4)
    {
        triangulatedIndices[0] = polygon.from_vertex + 0;
        triangulatedIndices[1] = polygon.from_vertex + 1;
        triangulatedIndices[2] = polygon.from_vertex + 2;
        triangulatedIndices[3] = polygon.from_vertex + 0;
        triangulatedIndices[4] = polygon.from_vertex + 2;
        triangulatedIndices[5] = polygon.from_vertex + 3;
        return 6;
    }

    const ofbx::Vec3Attributes& positions = geom.getPositions();
    Float3 normal = ToFloat3(geom.getNormals().get(polygon.from_vertex));

    // Check if the polygon is convex
    int lastSign = 0;
    bool isConvex = true;
    for (int i = 0; i < polygon.vertex_count; i++)
    {
        Float3 v1 = ToFloat3(positions.get(polygon.from_vertex + i));
        Float3 v2 = ToFloat3(positions.get(polygon.from_vertex + (i + 1) % polygon.vertex_count));
        Float3 v3 = ToFloat3(positions.get(polygon.from_vertex + (i + 2) % polygon.vertex_count));

        // The winding order of all triangles must be same for polygon to be considered convex
        int sign;
        Float3 c = Float3::Cross(v1 - v2, v3 - v2);
        if (c.LengthSquared() == 0.0f)
            continue;
        else if (Math::NotSameSign(c.X, normal.X) || Math::NotSameSign(c.Y, normal.Y) || Math::NotSameSign(c.Z, normal.Z))
            sign = 1;
        else
            sign = -1;
        if ((sign < 0 && lastSign > 0) || (sign > 0 && lastSign < 0))
        {
            isConvex = false;
            break;
        }
        lastSign += sign;
    }

    // Fast-path for convex case
    if (isConvex)
    {
        for (int i = 0; i < polygon.vertex_count - 2; i++)
        {
            triangulatedIndices[i * 3 + 0] = polygon.from_vertex;
            triangulatedIndices[i * 3 + 1] = polygon.from_vertex + (i + 1) % polygon.vertex_count;