constrained delaunayRefine inserts two circumcenters at the same point → zero-area triangle

[designbynumbers]

Runnable reproducer (gist): https://gist.github.com/designbynumbers/8347ae053074a4c1387350977483d3c9
(refine_degeneracy.cpp, the minimized gc-refine-repro.txt, and suggested-fix-proximity-guard.patch.)

Version: master @ 1e8e43d2d50b18c98ea0b4a53ffaf5848dbaaa26 (2026-05-04).

Summary

On a freshly built IntegerCoordinatesIntrinsicTriangulation (all edges
shared) whose metric is valid (every triangle satisfies the triangle
inequality; pre-mollified; min interior angle 1.69°), calling
delaunayRefine(25°) traces a Steiner circumcenter onto an existing vertex
— the new point lands on a triangle corner, coincident with a previously-inserted
Steiner vertex (the two occupy the bit-identical location on the input surface),
immediately creating a ~zero-length edge → a degenerate needle triangle. This
happens iff a subset of interior edges is fixed via setMarkedEdges
(constrained / Chew's-2nd-with-segments).

Controlled A/B on the exact same mesh + metric (attached gc-refine-repro.txt,
419 V / 547 F), delaunayRefine(25°):

interior marked edges	result
41 (+417 boundary, auto-fixed)	degenerate: V 419→1182, F→2013, min angle 0°, worst triangle edge lengths 0.249122, 1.51626e-09, 0.249122
0 (417 boundary only)	clean: V 419→693, F→1019, min angle 25.1244°

Both arms run the identical mesh + metric; they differ only in the 41
interior marked edges, which isolates them as the trigger. The unconstrained
refiner reaches the angle bound cleanly; only the marked-edge (segment-
constrained) path manufactures the needle.

The failure is fully deterministic and environment-independent — the
output above (down to the 1.51626e-09 edge length and V=1182 F=2013
counts) is bit-identical across:

• stock gc, -O3 -DNDEBUG, no local patches;
• a Debug -O0 -fsanitize=address build (gc assertions enabled).

The ASan/Debug build reports no memory error and trips no
GC_SAFETY_ASSERT — refinement completes "successfully" and simply returns a
triangulation containing a zero-area triangle (so a downstream cotan-Laplacian
/ BFF solve then blows up). This is an algorithmic correctness bug in the
constrained refinement, not memory unsafety.

Root cause (confirmed by instrumenting IntrinsicTriangulation::insertCircumcenter + delaunayRefine)

delaunayRefine inserts circumcenters via the base
IntrinsicTriangulation::insertCircumcenter (src/surface/intrinsic_triangulation.cpp:248).
Instrumenting just after its insertVertex call shows the degenerate edge is
created immediately at insertion (not by a later flip):

insert produced tiny incident edge IMMEDIATELY: minInc=2.82087e-15 maxInc=4.45961 endType=Face

i.e. the traced circumcenter ends as a Face-type point sitting on a corner
of the intrinsic triangle it landed in — coincident with an existing vertex. In
the final mesh the resulting needle's short edge connects two distinct inserted
Steiner vertices at the bit-identical input-surface location:

worst edge (len 1.51626e-09) endpoints:
  tail: deg 5, input face f_114, bary (0.593902, 0.166484, 0.239615)
  tip : deg 7, input face f_114, bary (0.593902, 0.166484, 0.239615)   <- identical
  both Face-type circumcenters

There is no proximity/coincidence guard before/after insertVertex (the
only guards are: trace blocked by a marked edge → split that edge's midpoint;
trace failed → bail). Why the constrained path hits this and the unconstrained
path doesn't: the input has a 1.69° angle at a constrained corner; marked
edges can't be flipped or refined away, so Chew's-with-segments repeatedly
targets the skinny faces around that corner and their circumcenters cluster
onto essentially one point. (Relatedly, delaunayRefine's deleteNearbyVertices
cleanup, which removes previously-inserted vertices near a new one, is registered
as an edge-split callback only — it never fires on face-interior circumcenter
insertions, so clustered coincident circumcenters are never cleaned up either.)

A standard fix is the usual Delaunay-refinement proximity guard: if the traced
circumcenter falls within ε of an existing vertex, reject the insertion (accept
the triangle) rather than inserting a coincident point — see Suggested fix.

Reproducer

Self-contained, gc-only (no other deps). Files:

• refine_degeneracy.cpp (~140 lines). Args: <state.txt> [mollifyEPS=1e-5] [markEdges=1].
• gc-refine-repro.txt — the input state: nV nF nE, then nF triangles
  (vertex-index triples), then nE edges (a b length marked). A compressed
  manifold triangle mesh with boundary; lengths/marks keyed by vertex-pair so
  they're independent of gc's edge indexing. Marked edges are reconstructed on
  the IT's intrinsicMesh before setMarkedEdges (mirroring correct gc usage).
  (It is an automatically delta-debug-minimized reduction of a larger real
  pipeline state — the many small holes / large boundary are a reduction
  artifact, not essential to the bug.)

Build (against a stock gc build tree):

c++ -std=c++17 -O3 -DNDEBUG \
  -I<gc>/include -I<gc>/deps/happly -I<gc>/deps/nanoflann/include \
  -isystem <eigen> \
  refine_degeneracy.cpp <gc-build>/lib/libgeometry-central.a \
  -o refine_degeneracy

Run (constrained = degenerate; unconstrained = clean control):

./refine_degeneracy gc-refine-repro.txt 1e-5 1   # marked:   min angle 0°  (REPRODUCED)
./refine_degeneracy gc-refine-repro.txt 1e-5 0   # unmarked: min angle 25.1244°

Expected

delaunayRefine on a valid constrained triangulation should terminate with
all non-constrained angles ≥ the bound (or at worst leave bounded-but-small
angles only where two constraint edges meet at a genuinely small input
angle) — never insert a zero-area / coincident-vertex triangle.

Notes

• The attached input is an automatically minimized (delta-debugged) reduction
  of a real pipeline state; happy to share the larger original or minimize
  further if useful.
• The bug is independent of intrinsic mollification: the input metric is
  already mollified and the IT ctor's mollifyEPS (1e-5 here) does not change
  the outcome.
• Our day-to-day build carries an unrelated 2-line local patch to
  SurfacePoint::inEdge; the bug reproduces identically on stock gc with
  no patches (shown above), so the patch is not involved.

Suggested fix (tested)

A minimal proximity guard in IntrinsicTriangulation::insertCircumcenter
(src/surface/intrinsic_triangulation.cpp): after insertVertex, if the new
vertex has a near-zero incident edge (it landed on an existing vertex), undo the
insertion and return Vertex(). delaunayRefine already treats Vertex() as
"insertion failed" and continues, leaving the unrefinable constrained corner as
a healthy (non-degenerate) triangle.

  // === Phase 3: Add the new vertex
  Vertex newV = insertVertex(newPositionOnIntrinsic);

  // Proximity guard: a traced circumcenter can land coincident with an existing
  // vertex (ends as a Face/Edge point on a triangle corner), creating a
  // zero-area needle. Undo such an insertion rather than poisoning the mesh.
  if (newV != Vertex()) {
    double minInc = std::numeric_limits<double>::infinity(), maxInc = 0.;
    for (Edge e : newV.adjacentEdges()) {
      minInc = std::min(minInc, edgeLengths[e]);
      maxInc = std::max(maxInc, edgeLengths[e]);
    }
    if (minInc <= 1e-9 * maxInc) {
      removeInsertedVertex(newV);
      return Vertex();
    }
  }
  return newV;

Results on the attached repro (stock gc, otherwise unchanged):

case	before	after patch
41 interior marked (constrained)	min angle 0°, edge 1.5e-9	min angle 4.21°, minEdge 0.446, no degeneracy (deterministic)
0 interior marked (control)	min angle 25.1244°	min angle 25.1244° (unchanged)

Full diff: suggested-fix-proximity-guard.patch. Notes: (a) the same guard
likely belongs in IntegerCoordinatesIntrinsicTriangulation::insertCircumcenterOrSplitSegment
for its callers (delaunayRefine itself uses the base insertCircumcenter).
(b) A heavier alternative — extending delaunayRefine's deleteNearbyVertices
cleanup (currently an edge-split callback only) to fire on face insertions via
faceInsertionCallbackList — would also remove the coincidence, but runs a
Dijkstra ball-search + vertex deletions on every circumcenter and risks
insert/delete oscillation; the local guard is cheaper and side-effect-free.