FAILURE MAP
← Case archive

FA-88501 / Mesh topology invariants / Open access

Edge collapse reports the boundary rule before the link rule · case 01

A collapse that violates both conditions is reported as "boundary" rather than "link".

Verified by executionVariant 1 · 7 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The boundary check runs before the link check.

THE FAILURE

The boundary check runs before the link check.

Unsuccessful approach: Moving the link check after the minimal check misreports small closed meshes.

Case contract

Input [faces, a, b] for a triangle mesh. Collapsing edge (a,b) is checked in order: missing edge -> [false,"no-edge"]; common neighbours of a and b must equal the opposite vertices of the triangles on the edge -> else [false,"link"]; if a and b are both boundary vertices the edge itself must be a boundary edge -> else [false,"boundary"]; a closed mesh with 4 or fewer vertices -> [false,"minimal"]; otherwise [true,"ok"].

Why this case matters

Mesh processing pipelines (remeshing, export, simulation, printing) trust these topological counts and adjacency answers; a wrong invariant silently accepts broken meshes or rejects valid ones.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces,a,b=x
    adj={}
    opp=[]
    ecount={}
    for f in faces:
        for i in range(3):
            u,v=f[i],f[(i+1)%3]
            adj.setdefault(u,set()).add(v)
            adj.setdefault(v,set()).add(u)
            k=(min(u,v),max(u,v))
            ecount[k]=ecount.get(k,0)+1
        if a in f and b in f:
            opp.append([w for w in f if w!=a and w!=b][0])
    k=(min(a,b),max(a,b))
    if k not in ecount: return [False,'no-edge']
    bnd=set()
    for (u,v),c in ecount.items():
        if c==1: bnd.update((u,v))
    if a in bnd and b in bnd and ecount[k]!=1: return [False,'boundary']
    if (adj[a]&adj[b])!=set(opp): return [False,'link']
    if not bnd and len(adj)<=4: return [False,'minimal']
    return [True,'ok']
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['disk spoke', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 0, 1]], [True, 'ok']], ['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['fan missing edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 1, 3]], [False, 'no-edge']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']]], [['fan missing edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 1, 3]], [False, 'no-edge']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['octahedron reversed', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 5, 2]], [True, 'ok']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['two triangles shared edge', [[[[0, 1, 2], [2, 1, 3]], 1, 2]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']]], [['octahedron reversed', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 5, 2]], [True, 'ok']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['two triangles shared edge', [[[[0, 1, 2], [2, 1, 3]], 1, 2]], [False, 'boundary']], ['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']]], [['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']], ['grid interior spoke', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 4, 5]], [True, 'ok']], ['rotated face order', [[[[2, 0, 1], [3, 0, 2]], 0, 2]], [False, 'boundary']]], [['disk spoke', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 0, 1]], [True, 'ok']], ['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']], ['grid interior spoke', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 4, 5]], [True, 'ok']], ['rotated face order', [[[[2, 0, 1], [3, 0, 2]], 0, 2]], [False, 'boundary']]]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
disk spoke[True, 'ok'][True, 'ok']Passed
disk rim[True, 'ok'][True, 'ok']Passed
fan interior edge[False, 'boundary'][False, 'boundary']Passed
fan missing edge[False, 'no-edge'][False, 'no-edge']Passed
tetrahedron edge[False, 'minimal'][False, 'minimal']Passed
octahedron edge[True, 'ok'][True, 'ok']Passed
strip over-constrained[False, 'boundary'][False, 'link']Failed

SHA-256 / a0b162798e93f5ee68f8714e5c38917e40fd769673b8aa4f460efa85331bc82a

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces,a,b=x
    adj={}
    opp=[]
    ecount={}
    for f in faces:
        for i in range(3):
            u,v=f[i],f[(i+1)%3]
            adj.setdefault(u,set()).add(v)
            adj.setdefault(v,set()).add(u)
            k=(min(u,v),max(u,v))
            ecount[k]=ecount.get(k,0)+1
        if a in f and b in f:
            opp.append([w for w in f if w!=a and w!=b][0])
    k=(min(a,b),max(a,b))
    if k not in ecount: return [False,'no-edge']
    bnd=set()
    for (u,v),c in ecount.items():
        if c==1: bnd.update((u,v))
    if a in bnd and b in bnd and ecount[k]!=1: return [False,'boundary']
    if not bnd and len(adj)<=4: return [False,'minimal']
    if (adj[a]&adj[b])!=set(opp): return [False,'link']
    return [True,'ok']
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['disk spoke', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 0, 1]], [True, 'ok']], ['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['fan missing edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 1, 3]], [False, 'no-edge']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']]], [['fan missing edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 1, 3]], [False, 'no-edge']], ['tetrahedron edge', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], 0, 1]], [False, 'minimal']], ['octahedron edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 0, 1]], [True, 'ok']], ['octahedron reversed', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 5, 2]], [True, 'ok']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['two triangles shared edge', [[[[0, 1, 2], [2, 1, 3]], 1, 2]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']]], [['octahedron reversed', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1], [5, 2, 1], [5, 3, 2], [5, 4, 3], [5, 1, 4]], 5, 2]], [True, 'ok']], ['open tetra cap', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1]], 1, 2]], [False, 'link']], ['two triangles shared edge', [[[[0, 1, 2], [2, 1, 3]], 1, 2]], [False, 'boundary']], ['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']]], [['two triangles rim edge', [[[[0, 1, 2], [2, 1, 3]], 0, 1]], [True, 'ok']], ['torus edge', [[[[0, 3, 4], [0, 4, 1], [1, 4, 5], [1, 5, 2], [2, 5, 3], [2, 3, 0], [3, 6, 7], [3, 7, 4], [4, 7, 8], [4, 8, 5], [5, 8, 6], [5, 6, 3], [6, 0, 1], [6, 1, 7], [7, 1, 2], [7, 2, 8], [8, 2, 0], [8, 0, 6]], 0, 1]], [False, 'link']], ['cylinder rung', [[[[0, 1, 5], [0, 5, 4], [1, 2, 6], [1, 6, 5], [2, 3, 7], [2, 7, 6], [3, 0, 4], [3, 4, 7]], 0, 5]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']], ['grid interior spoke', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 4, 5]], [True, 'ok']], ['rotated face order', [[[[2, 0, 1], [3, 0, 2]], 0, 2]], [False, 'boundary']]], [['disk spoke', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 0, 1]], [True, 'ok']], ['disk rim', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1]], 1, 2]], [True, 'ok']], ['fan interior edge', [[[[0, 1, 2], [0, 2, 3], [0, 3, 4]], 0, 2]], [False, 'boundary']], ['strip over-constrained', [[[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 4]], 1, 3]], [False, 'link']], ['grid diagonal', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 0, 4]], [True, 'ok']], ['grid interior spoke', [[[[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [3, 4, 7], [3, 7, 6], [4, 5, 8], [4, 8, 7]], 4, 5]], [True, 'ok']], ['rotated face order', [[[[2, 0, 1], [3, 0, 2]], 0, 2]], [False, 'boundary']]]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
disk spoke[True, 'ok'][True, 'ok']Passed
disk rim[True, 'ok'][True, 'ok']Passed
fan interior edge[False, 'boundary'][False, 'boundary']Passed
fan missing edge[False, 'no-edge'][False, 'no-edge']Passed
tetrahedron edge[False, 'minimal'][False, 'minimal']Passed
octahedron edge[True, 'ok'][True, 'ok']Passed
strip over-constrained[False, 'boundary'][False, 'link']Failed

SHA-256 / 020d53f878286879891ca099088fd0edfedda35c95635d99a2a8c69f6307beef

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 7 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

Sign in to the archive ↗

Verification & scope

Pure combinatorial teaching model over integer face lists with a stipulated contract; no geometry kernel or file format is implied. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:51:08.783994+00:00.

Case digest / 46af56d7b6626cf7eff7af0145b9562a3b82631eed2411c74763172d6eecf419