FA-88446 / Mesh topology invariants / Open access

Half-edge twin lookup finds the half-edge itself · case 01

Boundary half-edges report a twin.

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

ROOT CAUSE

The twin test checks (a,b) instead of the reversed pair.

VERIFIED REPAIR

Look up (b,a).

Unsuccessful approach: Testing whether another face merely contains both vertices treats a quad diagonal as a shared edge.

Case contract

Input [faces, queries]. Build half-edges (f[i], f[i+1 mod n]) with face index, next and prev half-edges. A repeated directed half-edge returns ["duplicate-halfedge", [a,b]]. For each query (a,b) return null if it is not a half-edge, else [face, next, prev, twin] with twin [b,a] when that directed half-edge exists, else null.

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,queries=x
    H={}
    for fi,f in enumerate(faces):
        n=len(f)
        for i in range(n):
            h=(f[i],f[(i+1)%n])
            if h in H: return ['duplicate-halfedge',list(h)]
            H[h]=(fi,(f[(i+1)%n],f[(i+2)%n]),(f[(i-1)%n],f[i]))
    out=[]
    for a,b in queries:
        h=(a,b)
        if h not in H:
            out.append(None)
            continue
        fi,nx,pv=H[h]
        tw=[b,a] if (a,b) in H else None
        out.append([fi,list(nx),list(pv),tw])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['quad pair', [[[[0, 1, 2, 3], [3, 2, 4, 5]], [[0, 1], [2, 3], [3, 2], [4, 5], [1, 0]]]], [[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]], ['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['triangle then quad', [[[[0, 1, 2], [2, 1, 3, 4]], [[1, 3], [3, 4], [2, 1], [4, 2]]]], [[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]], ['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]]], [['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]], ['cube', [[[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]], [[0, 3], [3, 0], [4, 5], [7, 6]]]], [[0, [3, 2], [1, 0], [3, 0]], [5, [0, 4], [7, 3], [0, 3]], [1, [5, 6], [7, 4], [5, 4]], [4, [6, 2], [3, 7], [6, 7]]]], ['missing queries', [[[[0, 1, 2], [2, 1, 3]], [[0, 3], [3, 0], [2, 0]]]], [None, None, [0, [0, 1], [1, 2], None]]]], [['quad pair', [[[[0, 1, 2, 3], [3, 2, 4, 5]], [[0, 1], [2, 3], [3, 2], [4, 5], [1, 0]]]], [[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]], ['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['triangle then quad', [[[[0, 1, 2], [2, 1, 3, 4]], [[1, 3], [3, 4], [2, 1], [4, 2]]]], [[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]], ['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['cube', [[[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]], [[0, 3], [3, 0], [4, 5], [7, 6]]]], [[0, [3, 2], [1, 0], [3, 0]], [5, [0, 4], [7, 3], [0, 3]], [1, [5, 6], [7, 4], [5, 4]], [4, [6, 2], [3, 7], [6, 7]]]], ['missing queries', [[[[0, 1, 2], [2, 1, 3]], [[0, 3], [3, 0], [2, 0]]]], [None, None, [0, [0, 1], [1, 2], None]]]], [['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['triangle then quad', [[[[0, 1, 2], [2, 1, 3, 4]], [[1, 3], [3, 4], [2, 1], [4, 2]]]], [[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]], ['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]]], [['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]], ['cube', [[[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]], [[0, 3], [3, 0], [4, 5], [7, 6]]]], [[0, [3, 2], [1, 0], [3, 0]], [5, [0, 4], [7, 3], [0, 3]], [1, [5, 6], [7, 4], [5, 4]], [4, [6, 2], [3, 7], [6, 7]]]], ['missing queries', [[[[0, 1, 2], [2, 1, 3]], [[0, 3], [3, 0], [2, 0]]]], [None, None, [0, [0, 1], [1, 2], None]]]]]
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 fixture	Actual	Expected	Outcome
quad pair	`[[0, [1, 2], [3, 0], [1, 0]], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], [5, 4]], None]`	`[[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]`	Failed
triangle pair	`[[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], [2, 3]], [0, [1, 2], [2, 0], [1, 0]]]`	`[[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]`	Failed
triangle then quad	`[[1, [3, 4], [2, 1], [3, 1]], [1, [4, 2], [1, 3], [4, 3]], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], [2, 4]]]`	`[[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]`	Failed
quad then triangle	`[[0, [1, 2], [3, 0], [1, 0]], [1, [4, 3], [3, 2], [4, 2]], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]`	`[[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]`	Failed
tetrahedron	`[[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]`	`[[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]`	Passed
flipped duplicate	`['duplicate-halfedge', [0, 1]]`	`['duplicate-halfedge', [0, 1]]`	Passed
quad diagonal not twin	`[[1, [2, 4], [4, 0], [2, 0]], [1, [4, 0], [0, 2], [4, 2]], [0, [2, 3], [0, 1], [2, 1]]]`	`[[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]`	Failed

SHA-256 / 244ede80c76800d41e36103e0943711ded3382eec060d8e74d6c7590d548317c

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,queries=x
    H={}
    for fi,f in enumerate(faces):
        n=len(f)
        for i in range(n):
            h=(f[i],f[(i+1)%n])
            if h in H: return ['duplicate-halfedge',list(h)]
            H[h]=(fi,(f[(i+1)%n],f[(i+2)%n]),(f[(i-1)%n],f[i]))
    out=[]
    for a,b in queries:
        h=(a,b)
        if h not in H:
            out.append(None)
            continue
        fi,nx,pv=H[h]
        tw=[b,a] if any(a in g and b in g for g in faces if g is not faces[fi]) else None
        out.append([fi,list(nx),list(pv),tw])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['quad pair', [[[[0, 1, 2, 3], [3, 2, 4, 5]], [[0, 1], [2, 3], [3, 2], [4, 5], [1, 0]]]], [[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]], ['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['triangle then quad', [[[[0, 1, 2], [2, 1, 3, 4]], [[1, 3], [3, 4], [2, 1], [4, 2]]]], [[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]], ['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]]], [['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]], ['cube', [[[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]], [[0, 3], [3, 0], [4, 5], [7, 6]]]], [[0, [3, 2], [1, 0], [3, 0]], [5, [0, 4], [7, 3], [0, 3]], [1, [5, 6], [7, 4], [5, 4]], [4, [6, 2], [3, 7], [6, 7]]]], ['missing queries', [[[[0, 1, 2], [2, 1, 3]], [[0, 3], [3, 0], [2, 0]]]], [None, None, [0, [0, 1], [1, 2], None]]]], [['quad pair', [[[[0, 1, 2, 3], [3, 2, 4, 5]], [[0, 1], [2, 3], [3, 2], [4, 5], [1, 0]]]], [[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]], ['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['triangle then quad', [[[[0, 1, 2], [2, 1, 3, 4]], [[1, 3], [3, 4], [2, 1], [4, 2]]]], [[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]], ['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['cube', [[[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]], [[0, 3], [3, 0], [4, 5], [7, 6]]]], [[0, [3, 2], [1, 0], [3, 0]], [5, [0, 4], [7, 3], [0, 3]], [1, [5, 6], [7, 4], [5, 4]], [4, [6, 2], [3, 7], [6, 7]]]], ['missing queries', [[[[0, 1, 2], [2, 1, 3]], [[0, 3], [3, 0], [2, 0]]]], [None, None, [0, [0, 1], [1, 2], None]]]], [['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['triangle then quad', [[[[0, 1, 2], [2, 1, 3, 4]], [[1, 3], [3, 4], [2, 1], [4, 2]]]], [[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]], ['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]]], [['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]], ['cube', [[[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]], [[0, 3], [3, 0], [4, 5], [7, 6]]]], [[0, [3, 2], [1, 0], [3, 0]], [5, [0, 4], [7, 3], [0, 3]], [1, [5, 6], [7, 4], [5, 4]], [4, [6, 2], [3, 7], [6, 7]]]], ['missing queries', [[[[0, 1, 2], [2, 1, 3]], [[0, 3], [3, 0], [2, 0]]]], [None, None, [0, [0, 1], [1, 2], None]]]]]
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 fixture	Actual	Expected	Outcome
quad pair	`[[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]`	`[[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]`	Passed
triangle pair	`[[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]`	`[[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]`	Passed
triangle then quad	`[[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]`	`[[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]`	Passed
quad then triangle	`[[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]`	`[[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]`	Passed
tetrahedron	`[[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]`	`[[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]`	Passed
flipped duplicate	`['duplicate-halfedge', [0, 1]]`	`['duplicate-halfedge', [0, 1]]`	Passed
quad diagonal not twin	`[[1, [2, 4], [4, 0], [2, 0]], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]`	`[[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]`	Failed

SHA-256 / f12538d79ee772c167740de258868f5fe3d09123eda86ec97fd86147c75774f5

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    faces,queries=x
    H={}
    for fi,f in enumerate(faces):
        n=len(f)
        for i in range(n):
            h=(f[i],f[(i+1)%n])
            if h in H: return ['duplicate-halfedge',list(h)]
            H[h]=(fi,(f[(i+1)%n],f[(i+2)%n]),(f[(i-1)%n],f[i]))
    out=[]
    for a,b in queries:
        h=(a,b)
        if h not in H:
            out.append(None)
            continue
        fi,nx,pv=H[h]
        tw=[b,a] if (b,a) in H else None
        out.append([fi,list(nx),list(pv),tw])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['quad pair', [[[[0, 1, 2, 3], [3, 2, 4, 5]], [[0, 1], [2, 3], [3, 2], [4, 5], [1, 0]]]], [[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]], ['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['triangle then quad', [[[[0, 1, 2], [2, 1, 3, 4]], [[1, 3], [3, 4], [2, 1], [4, 2]]]], [[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]], ['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]]], [['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]], ['cube', [[[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]], [[0, 3], [3, 0], [4, 5], [7, 6]]]], [[0, [3, 2], [1, 0], [3, 0]], [5, [0, 4], [7, 3], [0, 3]], [1, [5, 6], [7, 4], [5, 4]], [4, [6, 2], [3, 7], [6, 7]]]], ['missing queries', [[[[0, 1, 2], [2, 1, 3]], [[0, 3], [3, 0], [2, 0]]]], [None, None, [0, [0, 1], [1, 2], None]]]], [['quad pair', [[[[0, 1, 2, 3], [3, 2, 4, 5]], [[0, 1], [2, 3], [3, 2], [4, 5], [1, 0]]]], [[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]], ['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['triangle then quad', [[[[0, 1, 2], [2, 1, 3, 4]], [[1, 3], [3, 4], [2, 1], [4, 2]]]], [[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]], ['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['cube', [[[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]], [[0, 3], [3, 0], [4, 5], [7, 6]]]], [[0, [3, 2], [1, 0], [3, 0]], [5, [0, 4], [7, 3], [0, 3]], [1, [5, 6], [7, 4], [5, 4]], [4, [6, 2], [3, 7], [6, 7]]]], ['missing queries', [[[[0, 1, 2], [2, 1, 3]], [[0, 3], [3, 0], [2, 0]]]], [None, None, [0, [0, 1], [1, 2], None]]]], [['triangle pair', [[[[0, 1, 2], [2, 1, 3]], [[1, 2], [2, 1], [3, 2], [0, 1]]]], [[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]], ['triangle then quad', [[[[0, 1, 2], [2, 1, 3, 4]], [[1, 3], [3, 4], [2, 1], [4, 2]]]], [[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]], ['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]]], [['quad then triangle', [[[[0, 1, 2, 3], [3, 2, 4]], [[0, 1], [2, 4], [3, 2], [2, 3]]]], [[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]], ['tetrahedron', [[[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]], [[0, 2], [2, 0], [1, 3], [3, 1]]]], [[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]], ['flipped duplicate', [[[[0, 1, 2], [0, 1, 3]], [[0, 1]]]], ['duplicate-halfedge', [0, 1]]], ['quad diagonal not twin', [[[[0, 1, 2, 3], [0, 2, 4]], [[0, 2], [2, 4], [1, 2]]]], [[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]], ['pentagon', [[[[0, 1, 2, 3, 4]], [[3, 4], [4, 0], [0, 4]]]], [[0, [4, 0], [2, 3], None], [0, [0, 1], [3, 4], None], None]], ['cube', [[[[0, 3, 2, 1], [4, 5, 6, 7], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]], [[0, 3], [3, 0], [4, 5], [7, 6]]]], [[0, [3, 2], [1, 0], [3, 0]], [5, [0, 4], [7, 3], [0, 3]], [1, [5, 6], [7, 4], [5, 4]], [4, [6, 2], [3, 7], [6, 7]]]], ['missing queries', [[[[0, 1, 2], [2, 1, 3]], [[0, 3], [3, 0], [2, 0]]]], [None, None, [0, [0, 1], [1, 2], None]]]]]
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 fixture	Actual	Expected	Outcome
quad pair	`[[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]`	`[[0, [1, 2], [3, 0], None], [0, [3, 0], [1, 2], [3, 2]], [1, [2, 4], [5, 3], [2, 3]], [1, [5, 3], [2, 4], None], None]`	Passed
triangle pair	`[[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]`	`[[0, [2, 0], [0, 1], [2, 1]], [1, [1, 3], [3, 2], [1, 2]], [1, [2, 1], [1, 3], None], [0, [1, 2], [2, 0], None]]`	Passed
triangle then quad	`[[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]`	`[[1, [3, 4], [2, 1], None], [1, [4, 2], [1, 3], None], [1, [1, 3], [4, 2], [1, 2]], [1, [2, 1], [3, 4], None]]`	Passed
quad then triangle	`[[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]`	`[[0, [1, 2], [3, 0], None], [1, [4, 3], [3, 2], None], [1, [2, 4], [4, 3], [2, 3]], [0, [3, 0], [1, 2], [3, 2]]]`	Passed
tetrahedron	`[[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]`	`[[0, [2, 1], [1, 0], [2, 0]], [3, [0, 3], [3, 2], [0, 2]], [1, [3, 0], [0, 1], [3, 1]], [2, [1, 2], [2, 3], [1, 3]]]`	Passed
flipped duplicate	`['duplicate-halfedge', [0, 1]]`	`['duplicate-halfedge', [0, 1]]`	Passed
quad diagonal not twin	`[[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]`	`[[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]`	Passed

SHA-256 / fcac49718e7799a10674063afa16a5bd25a6dce9c5f442c4aa505ede7c13a15c

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.176766+00:00.

Case digest / 9af4fe0859ef53890476b769a5f9ca64a7ad4f68d7837a7260868c83940ac3db