meshquadmatch.h File Reference

#include "mesh/meshquadquality.h"
#include "mesh/meshresult.h"
#include <QPair>
#include <QSet>
#include <QVector>

Include dependency graph for meshquadmatch.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	mesh::QuadTemplate
	Four vertex ids in cyclic (CCW) order. Before the PSLG is built these are meshquadpoints' combined indices; MeshGenerator maps them to Triangle output vertex ids before pairing. More...
struct	mesh::QuadPairingOptions
struct	mesh::QuadPairingStats

Namespaces
namespace	mesh

Functions
QuadPairingStats	mesh::pairTrianglesIntoQuads (MeshResult &mesh, const QVector< int > &cellIds, const QVector< QuadTemplate > &templates, const QSet< QPair< int, int > > &lockedEdges, const QuadPairingOptions &opts, QVector< int > *oldToNew)
	Pair the triangles cellIds (indices into mesh.triangles; every one must be a triangle) into quads. templates carry OUTPUT vertex ids. lockedEdges (mesh::edgeKey pairs) are never straddled. On return oldToNew (optional) maps every old cell index to its new index (a paired triangle maps to its quad). Region triangles that were not paired keep their tag/mannings/initDepth; a quad inherits them from its first triangle (tags of the two triangles are equal inside a region).
QVector< int >	mesh::maximumMatching (int n, const QVector< QPair< int, int > > &edges)
	Maximum-cardinality matching on a general graph — Edmonds' blossom algorithm (O(V·E)). edges are unordered pairs in [0, n). Returns mate[i] (-1 = unmatched). Exposed for the brute-force cross-check test.
bool	mesh::unionQuad (const QVector< MeshVertex > &vertices, const MeshTriangle &t1, const MeshTriangle &t2, MeshTriangle &quad)
	The CCW quad formed by two triangles sharing edge (p,q): returns false when they do not share exactly two vertices or the union is not a simple quad. quad receives v0..v3 (tag etc. copied from t1).

Detailed Description

Author

Caleb Buahin caleb.nosp@m..bua.nosp@m.hin@g.nosp@m.mail.nosp@m..com

Date

2026

License\n GPL-3.0-or-later

Pairing triangles into quads inside a quad region (workplans/QUAD_MESHING_REDESIGN_PLAN_2026-09-06.md §4.4f) — no external library:

1. TEMPLATE PAIRING. meshquadpoints recorded, for every lattice square it placed, the four vertex ids (a QuadTemplate). After Triangle runs, the two triangles whose vertex sets lie inside a template's four vertices (either diagonal) are looked up by sorted vertex triple and merged. Templates are visited best-score first; one whose triangles are already used, split (a vertex was inserted on its edge) or whose quad fails the bounds is skipped.
2. GAP PAIRING. The residual region triangles form a dual graph (vertices = triangles, edges = shared unlocked edges whose union is an acceptable quad). Edmonds' blossom algorithm (maximum-cardinality matching) pairs as many as possible; an alternating-4-cycle polish then swaps pairs when Σ score increases. Unmatched triangles stay triangles.

Output honours the engine cell order (triangles first, then quads; existing quads keep their relative order after the new ones are appended behind them — see meshquadmerge.cpp for the same rebuild) and emits every quad CCW. Callers pass all cells of the mesh; only cellIds are touched.