Runtime-switchable triangulation methods, MWT greedy algorithm, sweep-line, earcut Z-curve, and quad preservation option#423

Copilot

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":

Finds the shortest external edge and rotates the polygon to start there
For each window of 4 consecutive vertices, compares two possible diagonals and picks the shorter one to split off a triangle
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.

syoyo

@copilot Implement MWT_Greedy_Algorithm https://github.com/drmasifhabib/MWT_Greedy_Algorithm

Copilot

@copilot Implement MWT_Greedy_Algorithm https://github.com/drmasifhabib/MWT_Greedy_Algorithm

Implemented the MWT Greedy Algorithm from drmasifhabib/MWT_Greedy_Algorithm in commit d174bce. The algorithm is available as a new triangulation method via config.triangulation_method = "mwt" (or "greedy").

It implements the directional greedy approach:

Finds the shortest external edge and starts from there
For each window of 4 consecutive vertices, compares the two possible diagonals and picks the shorter one
Tries both winding directions and picks the result with lower total diagonal weight

Added TINYOBJLOADER_TRIANGULATE_MWT constant and 5 test cases (quad, pentagon, hexagon, preserve_quads, file load). All 55+ tests pass.

syoyo

@copilot make triangulation implementation separate file so that we can test the algorithm standalone manner before integrating to tinyobjloader. put files to sandbox/triangulation/

Copilot

@copilot make triangulation implementation separate file so that we can test the algorithm standalone manner before integrating to tinyobjloader. put files to sandbox/triangulation/

Created sandbox/triangulation/ with standalone files in commit 4c91a3c:

triangulation.h — self-contained header with fan, earclip, and MWT greedy algorithms. No tinyobjloader dependency; operates on flat std::vector<double> vertex arrays and outputs triangle index triples.
main.cc — 24 standalone test cases covering all three algorithms (triangles through octagons), concave polygons, 3D vertices, edge cases, and MWT weight optimization verification.
Makefile — make test builds and runs everything.

The algorithms match the implementations in tiny_obj_loader.h but are fully independent and testable standalone.

syoyo

@copilot Implement our own Sweep-Line and Earcut(with zcurve) algorithm and also make benchmark program to test each triangulation algorithm.

Copilot

@copilot Implement our own Sweep-Line and Earcut(with zcurve) algorithm and also make benchmark program to test each triangulation algorithm.

Implemented in commits 2cd27a7 and 57156fa. Added to sandbox/triangulation/:

Sweep-Line (TriangulateSweepLine):

Classifies vertices (start/end/split/merge/regular)
Sweep-line with edge status structure adds diagonals at split/merge vertices for monotone decomposition
Recursive polygon splitting at diagonals
Stack-based O(n) monotone polygon triangulation

Earcut Z-Curve (TriangulateEarcutZCurve):

Doubly-linked circular list of polygon vertices
Z-order curve (Morton code) spatial hashing for fast point-in-triangle rejection
Searches outward from candidate ear in Z-sorted list within triangle's Z-range
Falls back to full scan when Z-filtered pass gets stuck

Benchmark (benchmark.cc, run with make bench):

Tests all 5 algorithms across regular n-gons, random convex, and star-shaped concave polygons (4–1024 vertices)
Fan is fastest (trivial), MWT and SweepLine are competitive on convex polygons, EarcutZ scales well on concave polygons

14 new test cases (38 total standalone tests), all passing. 0 CodeQL alerts.

Initial plan

666a2b0

Copilot AI assigned Copilot and syoyo Mar 6, 2026

Copilot started work on behalf of syoyo March 6, 2026 18:05 View session

Copilot AI and others added 3 commits March 6, 2026 18:15

Add tests for triangulation methods and preserve_quads option …

0099a2d

Co-authored-by: syoyo <18676+syoyo@users.noreply.github.com>

Fix code formatting in mapbox earcut quad path per review feedback …

df885e7

Co-authored-by: syoyo <18676+syoyo@users.noreply.github.com>

Copilot AI changed the title [WIP] Add efficient triangulation algorithm for wavefront .obj format Runtime-switchable triangulation methods and quad preservation option Mar 6, 2026

Copilot finished work on behalf of syoyo March 6, 2026 18:21

Copilot started work on behalf of syoyo March 7, 2026 00:28 View session

Copilot AI and others added 2 commits March 7, 2026 00:32

Fix loop condition in MWT emit per review feedback …

c772dca

Co-authored-by: syoyo <18676+syoyo@users.noreply.github.com>

Copilot AI changed the title Runtime-switchable triangulation methods and quad preservation option Runtime-switchable triangulation methods, MWT greedy algorithm, and quad preservation option Mar 7, 2026

Copilot finished work on behalf of syoyo March 7, 2026 00:36

Copilot started work on behalf of syoyo March 7, 2026 02:43 View session

Copilot finished work on behalf of syoyo March 7, 2026 02:51

Copilot started work on behalf of syoyo March 7, 2026 20:44 View session

Copilot AI and others added 2 commits March 7, 2026 21:02

Address code review: use named constant for tolerance, fix comment style …

57156fa

Co-authored-by: syoyo <18676+syoyo@users.noreply.github.com>

Copilot AI changed the title Runtime-switchable triangulation methods, MWT greedy algorithm, and quad preservation option Runtime-switchable triangulation methods, MWT greedy algorithm, sweep-line, earcut Z-curve, and quad preservation option Mar 7, 2026

Copilot finished work on behalf of syoyo March 7, 2026 21:05

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

Runtime-switchable triangulation methods, MWT greedy algorithm, sweep-line, earcut Z-curve, and quad preservation option#423