The ObjReaderConfig::triangulation_method field was declared but never used. This PR makes it functional, adds a preserve_quads option for quad+triangle decomposition, implements the MWT (Minimum Weight Triangulation) greedy algorithm, and adds standalone sweep-line and earcut Z-curve triangulation algorithms with a benchmark program.

API changes

• triangulation_method now dispatches at runtime between:
  • "fan" / "simple" — triangle fan from vertex 0 (fastest, naive)
  • "earclip" — built-in ear clipping (default, robust)
  • "earcut" / "mapbox" — mapbox earcut (requires TINYOBJLOADER_USE_MAPBOX_EARCUT)
  • "mwt" / "greedy" — Minimum Weight Triangulation greedy algorithm with directional optimization (near-optimal triangulation minimizing total diagonal length, based on drmasifhabib/MWT_Greedy_Algorithm)
• preserve_quads (bool, default false) — keep quad faces as-is, only triangulate 5+ ngons
• Default changed from "simple" (unused) to "earclip" (matches actual default behavior)
• v1 LoadObj(..., bool triangulate) API is unchanged; true maps to earclip

MWT Greedy Algorithm

The MWT greedy algorithm implements the directional greedy approach described in "A Linear-Time Greedy Algorithm with Directional Optimization for Near-Optimal Minimum Weight Triangulation of Convex Polygons":

1. Finds the shortest external edge and rotates the polygon to start there
2. For each window of 4 consecutive vertices, compares two possible diagonals and picks the shorter one to split off a triangle
3. Tries both clockwise and counter-clockwise winding directions and picks the result with lower total diagonal weight

Standalone triangulation sandbox

Five triangulation algorithms are extracted into standalone files under sandbox/triangulation/ for independent testing and evaluation without any tinyobjloader dependency:

• sandbox/triangulation/triangulation.h — self-contained header-only library with five algorithms:
  • Fan — simple triangle fan from vertex 0
  • Earclip — built-in ear clipping (handles concave polygons)
  • MWT — Minimum Weight Triangulation greedy with directional optimization
  • Sweep-Line — monotone polygon decomposition via sweep-line event processing (vertex classification into start/end/split/merge/regular, edge status structure with helpers, diagonal insertion), recursive polygon splitting at diagonals, and stack-based O(n) monotone polygon triangulation
  • Earcut Z-Curve — enhanced ear clipping using Z-order curve (Morton code) spatial indexing with doubly-linked circular list and Z-sorted auxiliary list for fast point-in-triangle rejection, with fallback to full scan
• sandbox/triangulation/main.cc — 38 standalone test cases covering all five algorithms across triangles through octagons, concave polygons, 3D vertices, edge cases, and MWT weight optimization verification
• sandbox/triangulation/benchmark.cc — benchmark program measuring all 5 algorithms across regular n-gons, random convex, and star-shaped concave polygons of 4 to 1024 vertices (make bench)
• sandbox/triangulation/Makefile — build with make test (tests) or make bench (benchmark)

Internals

• exportGroupsToShape and LoadObjInternal take unsigned int tri_method, bool preserve_quads instead of bool triangulate
• LoadObjEx static helpers thread extended params from v2 ObjReader API without changing v1 signatures
• parseTriangulationMethod() converts config string to TINYOBJLOADER_TRIANGULATE_* constant once per load
• Added TINYOBJLOADER_TRIANGULATE_MWT constant (value 4)

Usage

tinyobj::ObjReaderConfig config;
config.triangulate = true;
config.triangulation_method = "mwt";   // or "fan", "earclip", "earcut"
config.preserve_quads = true;          // quads kept, 5+ ngons triangulated

tinyobj::ObjReader reader;
reader.ParseFromFile("model.obj", config);

Tests

15 new tinyobjloader test cases: fan/earclip/mwt on quads and pentagons, mwt on hexagons, preserve_quads with multiple methods, no-triangulation passthrough, default config values, string aliases, v1 API backward compat, and mwt file-based loading. Plus 38 standalone tests in sandbox/triangulation/ covering all five algorithms.

🔒 GitHub Advanced Security automatically protects Copilot coding agent pull requests. You can protect all pull requests by enabling Advanced Security for your repositories. Learn more about Advanced Security.