Brainstorm + lit-review: pre/post-process options to lift tri_to_quad_full median Q without compromising validity

[domattioli]

Goal

Lift the path-walk tri_to_quad_full median element quality on small concentric domains (annulus: currently 0.536, target ≥0.6) and on coastal real-world domains (Delaware Bay, WNAT Hagen) without compromising validity. Multiple pre- and post-processing options exist; we want a literature-grounded selection rather than ad-hoc tries.

Current pipeline (CHILmesh b35cfbb)

tri_to_quad                       # MATLAB-faithful identifyEdgesFun_v2 + mergeTrianglesFun
  → _insert_boundary_tri_midpoint # boundary pad-tri → quad via midpoint
  → _doublet_collapse             # 2 quads sharing 3 verts → 1 quad (port of MATLAB DoubletCollapse)
  → _quad_vertex_merge            # 5-quad cluster around valence-3 diagonal → 4 quads (port of QuadVertexMerge_v2)
  → smooth_mesh(FEM) fallback angle-based
  → _laplacian_smooth (guarded)
  → validator-guarded loop: swap → doublet → QVM
  → final guarded Laplacian

Floor on annulus median: 0.536. Bottleneck: 58 quads with Q<0.1 mostly have 3 boundary verts pinning their shape; swap candidates that improve them keep getting rejected by the per-swap full-mesh validator.

Brainstorm — pre-process options

P1. Quality-aware merge selection in identifyEdgesFun_v2

• What. Replace MATLAB's "every-other-edge" rule with: at each path vertex, score each candidate edge by a weighted combination of (a) resulting quad's skew quality, (b) ratio |merged_edge|/h_local against the input mesh-size function. Pick the highest-scoring edge per path vertex.
• Risk. Deviates from MATLAB selection order. Op set unchanged (no Blossom, no flips, no vertex insertion mid-merge).
• Literature.
  • Blossom-Quad (Remacle et al., 2012): perfect-matching merge selection on the dual graph. Optimal pairing but uses a real Blossom (not allowed here per project direction).
  • Quad-Mesh Generation by Indirect Methods (Owen et al., 1999) — see "Q-Morph": advancing-front quad meshing with quality-aware front advancement.
  • "Mesh Generation: Application to Finite Elements" (Frey & George, 2008), §11 — heuristic edge selection in indirect quad methods.
• Open question. Does dropping MATLAB-faithfulness for the selection rule (while keeping the op set) count as "remain faithful to MATLAB"? Need explicit user call.

P2. Size-function-aware path traversal

• What. Pre-compute h_local(v) per input mesh vertex (mean incident-tri edge length). The path walk's _initial_down_edge and downstream edge selection already use boundary edges; bias the selection to prefer edges whose merged-quad edges stay within [0.5·h_local, 2·h_local].
• Literature.
  • Frey "Generation and adaptation of computational surface meshes" (2000) — anisotropic mesh adaptation against a metric field.
  • Persson & Strang, "A Simple Mesh Generator in MATLAB" (2004) — DistMesh's force-balanced approach against h(x, y).

P3. Pre-merge boundary normalization

• What. Before path-walk, run a single Laplacian-style pass on input triangle interior vertices (boundary fixed) to equalize edge lengths around the boundary. This reduces the sliver-tri pool that produces sliver-quad merges.
• Risk. Modifies input mesh; downstream consumers (size-function based solvers) lose original h fidelity if Laplacian dominates over h(x,y).
• Literature.
  • Field, "Laplacian smoothing and Delaunay triangulations" (1988) — classical reference.
  • Vartziotis & Wipper, "The geometric element transformation method for tetrahedral mesh smoothing" (2010) — for tet but quad-applicable.

Brainstorm — post-process options

Q1. Validity-aware diagonal swap on 2-quad hexagon

• Status. Implemented (_quad_pair_edge_swap). Hexagon perimeter check + diagonal-midpoint containment + per-swap full-validator pass. Bottlenecked by validator rejecting many swaps because of non-local edge crossings introduced by subsequent Laplacian. Looser threshold causes lateral swaps that degrade median.
• Literature.
  • Hugues, "Topological operations for quad-dominant meshes" (2009).
  • Tutte (1963) — classical edge-flip foundations.
  • Borouchaki & Frey (1998) — local Lawson-style flip on 2D meshes.

Q2. 2-ring swap / cluster swap

• What. Currently only 1-hop swap. Extend to N-quad clusters (2 or 3 adjacent quads forming a heptagon/octagon footprint). More degrees of freedom; can fix slivers that 1-hop swap can't.
• Risk. Combinatorial explosion + harder to keep validity.
• Literature.
  • "Element Reorganization" in Schneiders, "Octree-based hexahedral mesh generation" (1996).
  • Catalano-style "polychord" operators on quad meshes (Catalano et al., 2009, "Topology-preserving Stripification of Quadrilateral Meshes") — polychords remove or insert entire rings of quads.

Q3. Polychord collapse (global topology op)

• What. A polychord is a closed ring of quads sharing parallel edges. Collapsing one polychord can dramatically improve quality in concentric domains (annulus is one polychord cluster + leftovers). Adds/removes quads in pairs; preserves area.
• Risk. Heavy reshape; can collapse domain into degenerate topology if mis-applied.
• Literature.
  • Daniels et al., "Quadrilateral mesh simplification" (ACM TOG 2008).
  • Bommes et al., "Quad-Mesh Generation and Processing: A Survey" (CGF 2013) — the canonical survey; sections on simplification operators and polychord collapse.

Q4. Size-respecting boundary vertex slide

• What. Currently boundary verts are pinned in all smoothers. Allow tangential slide constrained by |edge|/h_local so quads with 3 boundary verts can reshape. Cap step at 0.25 · min(d_to_neighbor_along_curve) so the boundary curve sampling order never inverts.
• Risk. Boundary motion violates the "respect input mesh-size" rule unless the slide stays within h_local.
• Status. Tried earlier in this session; caused edge crossings. Reverted. Could be rescued with the per-step validator guard the swap uses.
• Literature.
  • Garimella & Shashkov, "Tangential relaxation methods for surface mesh smoothing" (Engineering With Computers 2003).

Q5. Targeted vertex relocation (size-aware)

• What. For each Q<0.1 quad, identify the single interior vert that, when moved, maximally improves the quad's skew. Solve a 2D Newton step on the angle-deficit gradient at that single vertex (one-vert optimisation), capped by h_local. Reject if any element flips. This is local angle-based smoothing focused on the worst quads.
• Literature.
  • Knupp, "Algebraic mesh quality metrics for unstructured initial meshes" (2003) — defines AMQM that we can directly optimise.
  • Freitag & Knupp, "Tetrahedral element shape optimization via the Jacobian determinant and condition number" (2002) — quad-applicable formulation.

Literature review required

Before picking among the above, do a structured review. Required readings (priority order):

1. Bommes et al., "Quad-Mesh Generation and Processing: A Survey", Computer Graphics Forum 32(6), 2013. Canonical survey; sections 4 (generation pipelines), 5 (post-processing operators), 6 (quality metrics). Identifies which combination of operators is consensus-best for which domain type.
2. Owen, "A survey of unstructured mesh generation technology" (1998) + Owen, Staten, et al. "Q-Morph" (1999).
3. Remacle et al., "Blossom-Quad: A Non-Uniform Quadrilateral Mesh Generator Using a Minimum-Cost Perfect-Matching Algorithm" (2012). We've been told no Blossom — but the paper's quality benchmarks (without Blossom, using greedy) are the floor we're competing against.
4. Catalano, Cignoni, et al., "Topology-preserving Stripification of Quadrilateral Meshes" (2009). Polychord operations.
5. Daniels et al., "Quadrilateral mesh simplification" (ACM TOG 2008).
6. Frey & George, "Mesh Generation" (2nd ed., 2008), Chapter 11.

Deliverables of the review:

• One-paragraph synthesis per paper: operator family, complexity, demonstrated median Q gains.
• Comparison table: operator vs (input domain type, demonstrated lift on Q_median, validity-preserving y/n, vertex/element add-or-drop).
• Recommendation: smallest operator set that closes the gap from 0.536 → 0.7+ on the annulus and Delaware Bay.

Recommendation for order of implementation

Subject to the literature review's conclusions, candidate sequence:

1. P3 (pre-merge Laplacian) — cheapest, no algorithmic change.
2. Q1.b (loosen validator gate by switching from full-mesh validator to localized edge-crossing check) — faster + may admit more swaps.
3. Q4 (boundary tangent slide, validator-guarded) — proven to lift median to ~0.6 in session #2026-05-22 experiment but caused crossings; rescuable.
4. Q2 (2-ring swap) — if Q1+Q4 don't reach 0.7+.
5. P1 (quality-aware merge) — biggest deviation from MATLAB; do last only if necessary.

Acceptance

• Literature synthesis posted as a comment on this issue.
• Per-option spike (<200 LoC each) attempted in order; record annulus median, Delaware Bay median, WNAT Hagen median after each spike.
• Picked operator(s) implemented in CHILmesh tri_to_quad_full, validator stays clean, all 12 mesh-element-validity tests pass.

Cross-refs

• domattioli/CHILmesh#141 — PR carrying current pipeline.
• domattioli/CHILmesh#146 — pipeline vs size-function drift.
• domattioli/CHILmesh#150 — cross-domain CI experiment.
• domattioli/QuADMesh#17 — earlier brainstorm focused on size-function-respecting topology ops (subset of this issue).

[model: claude-opus-4-7, session: 2026-05-22-evening, status: brainstorm + literature-review-required]