FA-88541 / Mesh topology invariants / Open access
Neighbour flip state ignores the current face flip · case 01
Chains of alternately oriented faces are repaired incorrectly after the first flip.
ROOT CAUSE
The required neighbour state is just the direction mismatch, not XOR with the current face state.
VERIFIED REPAIR
want = flip[current] XOR same.
Unsuccessful approach: OR instead of XOR keeps flipped faces flipping their neighbours.
Case contract
Input: polygon faces. If any undirected edge has more than two incident faces return "non-manifold". Otherwise propagate orientation by breadth-first search from the lowest unvisited face of each component (that seed keeps its orientation). A neighbour across an edge used in the same direction must have the opposite flip state. Any conflict returns [false, []], else [true, sorted indices of faces to flip].
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=x
edge_faces={}
for fi,f in enumerate(faces):
n=len(f)
for i in range(n):
a,b=f[i],f[(i+1)%n]
edge_faces.setdefault((min(a,b),max(a,b)),[]).append((fi,a,b))
if any(len(v)>2 for v in edge_faces.values()): return 'non-manifold'
flip=[None]*len(faces)
for seed in range(len(faces)):
if flip[seed] is not None: continue
flip[seed]=0
queue=[seed]
while queue:
fi=queue.pop(0)
f=faces[fi]
n=len(f)
for i in range(n):
a,b=f[i],f[(i+1)%n]
for gj,c,d in edge_faces[(min(a,b),max(a,b))]:
if gj==fi: continue
same=1 if (c,d)==(a,b) else 0
want=same
if flip[gj] is None:
flip[gj]=want
queue.append(gj)
elif flip[gj]!=want:
return [False,[]]
return [True,[i for i in range(len(faces)) if flip[i]]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['consistent tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], [True, []]], ['one flipped face', [[[0, 2, 1], [0, 3, 1], [1, 2, 3], [0, 3, 2]]], [True, [1]]], ['mobius', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 0, 3]]], [False, []]], ['projective plane', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [1, 2, 4], [2, 3, 5], [3, 4, 1], [4, 5, 2], [5, 1, 3]]], [False, []]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], 'non-manifold'], ['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [True, [1]]], ['disk with two flips', [[[0, 1, 2], [0, 3, 2], [0, 3, 4], [0, 5, 4], [0, 5, 1]]], [True, [1, 3]]]], [['projective plane', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [1, 2, 4], [2, 3, 5], [3, 4, 1], [4, 5, 2], [5, 1, 3]]], [False, []]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], 'non-manifold'], ['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [True, [1]]], ['disk with two flips', [[[0, 1, 2], [0, 3, 2], [0, 3, 4], [0, 5, 4], [0, 5, 1]]], [True, [1, 3]]], ['two components second flipped', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2], [4, 5, 6], [4, 5, 7]]], [True, [5]]], ['cube one flipped', [[[0, 3, 2, 1], [4, 5, 6, 7], [0, 4, 5, 1], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]]], [True, [2]]], ['annulus', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 3, 0]]], [True, []]]], [['disk with two flips', [[[0, 1, 2], [0, 3, 2], [0, 3, 4], [0, 5, 4], [0, 5, 1]]], [True, [1, 3]]], ['two components second flipped', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2], [4, 5, 6], [4, 5, 7]]], [True, [5]]], ['cube one flipped', [[[0, 3, 2, 1], [4, 5, 6, 7], [0, 4, 5, 1], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]]], [True, [2]]], ['annulus', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 3, 0]]], [True, []]], ['chain of flips', [[[0, 1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 5]]], [True, [1, 3]]], ['quad grid', [[[0, 1, 4, 3], [1, 2, 5, 4], [3, 4, 7, 6], [4, 5, 8, 7]]], [True, []]], ['second component consistent', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [10, 11, 12], [10, 11, 13]]], [True, [6]]]], [['consistent tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], [True, []]], ['one flipped face', [[[0, 2, 1], [0, 3, 1], [1, 2, 3], [0, 3, 2]]], [True, [1]]], ['mobius', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 0, 3]]], [False, []]], ['two components second flipped', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2], [4, 5, 6], [4, 5, 7]]], [True, [5]]], ['chain of flips', [[[0, 1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 5]]], [True, [1, 3]]], ['quad grid', [[[0, 1, 4, 3], [1, 2, 5, 4], [3, 4, 7, 6], [4, 5, 8, 7]]], [True, []]], ['second component consistent', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [10, 11, 12], [10, 11, 13]]], [True, [6]]]], [['consistent tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], [True, []]], ['one flipped face', [[[0, 2, 1], [0, 3, 1], [1, 2, 3], [0, 3, 2]]], [True, [1]]], ['mobius', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 0, 3]]], [False, []]], ['projective plane', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [1, 2, 4], [2, 3, 5], [3, 4, 1], [4, 5, 2], [5, 1, 3]]], [False, []]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], 'non-manifold'], ['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [True, [1]]], ['cube one flipped', [[[0, 3, 2, 1], [4, 5, 6, 7], [0, 4, 5, 1], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]]], [True, [2]]]]]
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 |
|---|---|---|---|
| consistent tetrahedron | [True, []] | [True, []] | Passed |
| one flipped face | [False, []] | [True, [1]] | Failed |
| mobius | [False, []] | [False, []] | Passed |
| projective plane | [False, []] | [False, []] | Passed |
| book | non-manifold | non-manifold | Passed |
| flipped pair | [False, []] | [True, [1]] | Failed |
| disk with two flips | [False, []] | [True, [1, 3]] | Failed |
SHA-256 / 25ae014d475d761fce6f8c7f7646c8197892afe9b984c066fdb3dd095dfe7c6d
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=x
edge_faces={}
for fi,f in enumerate(faces):
n=len(f)
for i in range(n):
a,b=f[i],f[(i+1)%n]
edge_faces.setdefault((min(a,b),max(a,b)),[]).append((fi,a,b))
if any(len(v)>2 for v in edge_faces.values()): return 'non-manifold'
flip=[None]*len(faces)
for seed in range(len(faces)):
if flip[seed] is not None: continue
flip[seed]=0
queue=[seed]
while queue:
fi=queue.pop(0)
f=faces[fi]
n=len(f)
for i in range(n):
a,b=f[i],f[(i+1)%n]
for gj,c,d in edge_faces[(min(a,b),max(a,b))]:
if gj==fi: continue
same=1 if (c,d)==(a,b) else 0
want=flip[fi]|same
if flip[gj] is None:
flip[gj]=want
queue.append(gj)
elif flip[gj]!=want:
return [False,[]]
return [True,[i for i in range(len(faces)) if flip[i]]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['consistent tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], [True, []]], ['one flipped face', [[[0, 2, 1], [0, 3, 1], [1, 2, 3], [0, 3, 2]]], [True, [1]]], ['mobius', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 0, 3]]], [False, []]], ['projective plane', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [1, 2, 4], [2, 3, 5], [3, 4, 1], [4, 5, 2], [5, 1, 3]]], [False, []]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], 'non-manifold'], ['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [True, [1]]], ['disk with two flips', [[[0, 1, 2], [0, 3, 2], [0, 3, 4], [0, 5, 4], [0, 5, 1]]], [True, [1, 3]]]], [['projective plane', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [1, 2, 4], [2, 3, 5], [3, 4, 1], [4, 5, 2], [5, 1, 3]]], [False, []]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], 'non-manifold'], ['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [True, [1]]], ['disk with two flips', [[[0, 1, 2], [0, 3, 2], [0, 3, 4], [0, 5, 4], [0, 5, 1]]], [True, [1, 3]]], ['two components second flipped', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2], [4, 5, 6], [4, 5, 7]]], [True, [5]]], ['cube one flipped', [[[0, 3, 2, 1], [4, 5, 6, 7], [0, 4, 5, 1], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]]], [True, [2]]], ['annulus', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 3, 0]]], [True, []]]], [['disk with two flips', [[[0, 1, 2], [0, 3, 2], [0, 3, 4], [0, 5, 4], [0, 5, 1]]], [True, [1, 3]]], ['two components second flipped', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2], [4, 5, 6], [4, 5, 7]]], [True, [5]]], ['cube one flipped', [[[0, 3, 2, 1], [4, 5, 6, 7], [0, 4, 5, 1], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]]], [True, [2]]], ['annulus', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 3, 0]]], [True, []]], ['chain of flips', [[[0, 1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 5]]], [True, [1, 3]]], ['quad grid', [[[0, 1, 4, 3], [1, 2, 5, 4], [3, 4, 7, 6], [4, 5, 8, 7]]], [True, []]], ['second component consistent', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [10, 11, 12], [10, 11, 13]]], [True, [6]]]], [['consistent tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], [True, []]], ['one flipped face', [[[0, 2, 1], [0, 3, 1], [1, 2, 3], [0, 3, 2]]], [True, [1]]], ['mobius', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 0, 3]]], [False, []]], ['two components second flipped', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2], [4, 5, 6], [4, 5, 7]]], [True, [5]]], ['chain of flips', [[[0, 1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 5]]], [True, [1, 3]]], ['quad grid', [[[0, 1, 4, 3], [1, 2, 5, 4], [3, 4, 7, 6], [4, 5, 8, 7]]], [True, []]], ['second component consistent', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [10, 11, 12], [10, 11, 13]]], [True, [6]]]], [['consistent tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], [True, []]], ['one flipped face', [[[0, 2, 1], [0, 3, 1], [1, 2, 3], [0, 3, 2]]], [True, [1]]], ['mobius', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 0, 3]]], [False, []]], ['projective plane', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [1, 2, 4], [2, 3, 5], [3, 4, 1], [4, 5, 2], [5, 1, 3]]], [False, []]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], 'non-manifold'], ['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [True, [1]]], ['cube one flipped', [[[0, 3, 2, 1], [4, 5, 6, 7], [0, 4, 5, 1], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]]], [True, [2]]]]]
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 |
|---|---|---|---|
| consistent tetrahedron | [True, []] | [True, []] | Passed |
| one flipped face | [False, []] | [True, [1]] | Failed |
| mobius | [False, []] | [False, []] | Passed |
| projective plane | [False, []] | [False, []] | Passed |
| book | non-manifold | non-manifold | Passed |
| flipped pair | [False, []] | [True, [1]] | Failed |
| disk with two flips | [False, []] | [True, [1, 3]] | Failed |
SHA-256 / 03d4deb4edb433f8b5f88abc7d95cee2f5cb40ece53693952f26d0652a3455b4
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=x
edge_faces={}
for fi,f in enumerate(faces):
n=len(f)
for i in range(n):
a,b=f[i],f[(i+1)%n]
edge_faces.setdefault((min(a,b),max(a,b)),[]).append((fi,a,b))
if any(len(v)>2 for v in edge_faces.values()): return 'non-manifold'
flip=[None]*len(faces)
for seed in range(len(faces)):
if flip[seed] is not None: continue
flip[seed]=0
queue=[seed]
while queue:
fi=queue.pop(0)
f=faces[fi]
n=len(f)
for i in range(n):
a,b=f[i],f[(i+1)%n]
for gj,c,d in edge_faces[(min(a,b),max(a,b))]:
if gj==fi: continue
same=1 if (c,d)==(a,b) else 0
want=flip[fi]^same
if flip[gj] is None:
flip[gj]=want
queue.append(gj)
elif flip[gj]!=want:
return [False,[]]
return [True,[i for i in range(len(faces)) if flip[i]]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['consistent tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], [True, []]], ['one flipped face', [[[0, 2, 1], [0, 3, 1], [1, 2, 3], [0, 3, 2]]], [True, [1]]], ['mobius', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 0, 3]]], [False, []]], ['projective plane', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [1, 2, 4], [2, 3, 5], [3, 4, 1], [4, 5, 2], [5, 1, 3]]], [False, []]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], 'non-manifold'], ['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [True, [1]]], ['disk with two flips', [[[0, 1, 2], [0, 3, 2], [0, 3, 4], [0, 5, 4], [0, 5, 1]]], [True, [1, 3]]]], [['projective plane', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [1, 2, 4], [2, 3, 5], [3, 4, 1], [4, 5, 2], [5, 1, 3]]], [False, []]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], 'non-manifold'], ['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [True, [1]]], ['disk with two flips', [[[0, 1, 2], [0, 3, 2], [0, 3, 4], [0, 5, 4], [0, 5, 1]]], [True, [1, 3]]], ['two components second flipped', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2], [4, 5, 6], [4, 5, 7]]], [True, [5]]], ['cube one flipped', [[[0, 3, 2, 1], [4, 5, 6, 7], [0, 4, 5, 1], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]]], [True, [2]]], ['annulus', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 3, 0]]], [True, []]]], [['disk with two flips', [[[0, 1, 2], [0, 3, 2], [0, 3, 4], [0, 5, 4], [0, 5, 1]]], [True, [1, 3]]], ['two components second flipped', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2], [4, 5, 6], [4, 5, 7]]], [True, [5]]], ['cube one flipped', [[[0, 3, 2, 1], [4, 5, 6, 7], [0, 4, 5, 1], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]]], [True, [2]]], ['annulus', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 3, 0]]], [True, []]], ['chain of flips', [[[0, 1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 5]]], [True, [1, 3]]], ['quad grid', [[[0, 1, 4, 3], [1, 2, 5, 4], [3, 4, 7, 6], [4, 5, 8, 7]]], [True, []]], ['second component consistent', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [10, 11, 12], [10, 11, 13]]], [True, [6]]]], [['consistent tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], [True, []]], ['one flipped face', [[[0, 2, 1], [0, 3, 1], [1, 2, 3], [0, 3, 2]]], [True, [1]]], ['mobius', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 0, 3]]], [False, []]], ['two components second flipped', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2], [4, 5, 6], [4, 5, 7]]], [True, [5]]], ['chain of flips', [[[0, 1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 5]]], [True, [1, 3]]], ['quad grid', [[[0, 1, 4, 3], [1, 2, 5, 4], [3, 4, 7, 6], [4, 5, 8, 7]]], [True, []]], ['second component consistent', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [10, 11, 12], [10, 11, 13]]], [True, [6]]]], [['consistent tetrahedron', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2]]], [True, []]], ['one flipped face', [[[0, 2, 1], [0, 3, 1], [1, 2, 3], [0, 3, 2]]], [True, [1]]], ['mobius', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 0, 3]]], [False, []]], ['projective plane', [[[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5], [0, 5, 1], [1, 2, 4], [2, 3, 5], [3, 4, 1], [4, 5, 2], [5, 1, 3]]], [False, []]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], 'non-manifold'], ['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [True, [1]]], ['cube one flipped', [[[0, 3, 2, 1], [4, 5, 6, 7], [0, 4, 5, 1], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7]]], [True, [2]]]]]
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 |
|---|---|---|---|
| consistent tetrahedron | [True, []] | [True, []] | Passed |
| one flipped face | [True, [1]] | [True, [1]] | Passed |
| mobius | [False, []] | [False, []] | Passed |
| projective plane | [False, []] | [False, []] | Passed |
| book | non-manifold | non-manifold | Passed |
| flipped pair | [True, [1]] | [True, [1]] | Passed |
| disk with two flips | [True, [1, 3]] | [True, [1, 3]] | Passed |
SHA-256 / d47d3d9b6548c730e35d06de83b85d831693a06cb890e594606ef3733a678378
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:09.084693+00:00.
Case digest / 3cfd1beed278d1b5bc2f1a1d5f766b7cbf5570827d6d0cae6ce5c3c2cc1a3974