FA-88441 / Mesh topology invariants / Open access

Half-edge prev pointer is stored reversed · case 01

prev returns the twin direction of the real previous half-edge.

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

ROOT CAUSE

prev is built as (f[i], f[i-1]) instead of (f[i-1], f[i]).

VERIFIED REPAIR

prev is the half-edge ending at the current start vertex.

Unsuccessful approach: Using (f[i-1], f[i-2]) returns the half-edge two steps back.

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],f[(i-1)%n]))
    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]]]], ['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]]]], ['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]]]], [['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], [0, 3], None], [0, [3, 0], [2, 1], [3, 2]], [1, [2, 4], [3, 5], [2, 3]], [1, [5, 3], [4, 2], 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]`	Failed
triangle pair	`[[0, [2, 0], [1, 0], [2, 1]], [1, [1, 3], [2, 3], [1, 2]], [1, [2, 1], [3, 1], None], [0, [1, 2], [0, 2], 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]]`	Failed
triangle then quad	`[[1, [3, 4], [1, 2], None], [1, [4, 2], [3, 1], None], [1, [1, 3], [2, 4], [1, 2]], [1, [2, 1], [4, 3], 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]]`	Failed
quad then triangle	`[[0, [1, 2], [0, 3], None], [1, [4, 3], [2, 3], None], [1, [2, 4], [3, 4], [2, 3]], [0, [3, 0], [2, 1], [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], [0, 1], [2, 0]], [3, [0, 3], [2, 3], [0, 2]], [1, [3, 0], [1, 0], [3, 1]], [2, [1, 2], [3, 2], [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]]]`	Failed
flipped duplicate	`['duplicate-halfedge', [0, 1]]`	`['duplicate-halfedge', [0, 1]]`	Passed
quad diagonal not twin	`[[1, [2, 4], [0, 4], None], [1, [4, 0], [2, 0], None], [0, [2, 3], [1, 0], None]]`	`[[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]`	Failed

SHA-256 / c4869df6b0d25d442f32535898398cb5ba4de2d0fdb4ad403f966f2f5cc6c24b

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-2)%n]))
    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]]]], ['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]]]], ['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]]]], [['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, 2], None], [0, [3, 0], [1, 0], [3, 2]], [1, [2, 4], [5, 4], [2, 3]], [1, [5, 3], [2, 3], 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]`	Failed
triangle pair	`[[0, [2, 0], [0, 2], [2, 1]], [1, [1, 3], [3, 1], [1, 2]], [1, [2, 1], [1, 2], None], [0, [1, 2], [2, 1], 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]]`	Failed
triangle then quad	`[[1, [3, 4], [2, 4], None], [1, [4, 2], [1, 2], None], [1, [1, 3], [4, 3], [1, 2]], [1, [2, 1], [3, 1], 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]]`	Failed
quad then triangle	`[[0, [1, 2], [3, 2], None], [1, [4, 3], [3, 4], None], [1, [2, 4], [4, 2], [2, 3]], [0, [3, 0], [1, 0], [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, 2], [2, 0]], [3, [0, 3], [3, 0], [0, 2]], [1, [3, 0], [0, 3], [3, 1]], [2, [1, 2], [2, 1], [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]]]`	Failed
flipped duplicate	`['duplicate-halfedge', [0, 1]]`	`['duplicate-halfedge', [0, 1]]`	Passed
quad diagonal not twin	`[[1, [2, 4], [4, 2], None], [1, [4, 0], [0, 4], None], [0, [2, 3], [0, 3], None]]`	`[[1, [2, 4], [4, 0], None], [1, [4, 0], [0, 2], None], [0, [2, 3], [0, 1], None]]`	Failed

SHA-256 / f4fb7e0a90074d8867e590827b1d28db1476d34b5a6ef4d9a6cc52323e573a52

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]]]], ['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]]]], ['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]]]], [['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 / 7c3056ae99cbb1789f06fca05ba3a999de4bb41e9487391a22bcc5082d8c7dea

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

Case digest / 1df12fe5e6a7c2736d375075a47b7d32fe08d0245488b4fbebd94edc41d097bc