FA-88551 / Mesh topology invariants / Open access
Each new component seed is flipped · case 01
Every face of every component is reported as needing a flip.
ROOT CAUSE
The seed of a component starts in the flipped state.
VERIFIED REPAIR
Seeds keep their orientation (state 0).
Unsuccessful approach: Seeding by face-index parity flips arbitrary components.
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]=1
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]]], ['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]]]], [['one flipped face', [[[0, 2, 1], [0, 3, 1], [1, 2, 3], [0, 3, 2]]], [True, [1]]], ['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]]], ['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]]]], [['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [True, [1]]], ['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, []]], ['disk with two flips', [[[0, 1, 2], [0, 3, 2], [0, 3, 4], [0, 5, 4], [0, 5, 1]]], [True, [1, 3]]], ['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]]]], [['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]]], ['two components second flipped', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2], [4, 5, 6], [4, 5, 7]]], [True, [5]]], ['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]]]]]
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, [0, 1, 2, 3]] | [True, []] | Failed |
| one flipped face | [True, [0, 2, 3]] | [True, [1]] | Failed |
| mobius | [False, []] | [False, []] | Passed |
| projective plane | [False, []] | [False, []] | Passed |
| book | non-manifold | non-manifold | Passed |
| flipped pair | [True, [0]] | [True, [1]] | Failed |
| second component consistent | [True, [0, 1, 2, 3, 4, 5]] | [True, [6]] | Failed |
SHA-256 / 2c9fdd98b9ebc5125d8a9c1ebc83f589e1550b60b12008783b0d4ffd3b2c3191
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]=seed%2
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]]], ['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]]]], [['one flipped face', [[[0, 2, 1], [0, 3, 1], [1, 2, 3], [0, 3, 2]]], [True, [1]]], ['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]]], ['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]]]], [['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [True, [1]]], ['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, []]], ['disk with two flips', [[[0, 1, 2], [0, 3, 2], [0, 3, 4], [0, 5, 4], [0, 5, 1]]], [True, [1, 3]]], ['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]]]], [['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]]], ['two components second flipped', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2], [4, 5, 6], [4, 5, 7]]], [True, [5]]], ['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]]]]]
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 |
| second component consistent | [True, [5]] | [True, [6]] | Failed |
SHA-256 / cdc06514e7b463535e25c7160e1938aff8f6e8e6c849e1beaffa2dcd6af09e6e
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]]], ['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]]]], [['one flipped face', [[[0, 2, 1], [0, 3, 1], [1, 2, 3], [0, 3, 2]]], [True, [1]]], ['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]]], ['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]]]], [['flipped pair', [[[0, 1, 2], [0, 1, 3]]], [True, [1]]], ['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, []]], ['disk with two flips', [[[0, 1, 2], [0, 3, 2], [0, 3, 4], [0, 5, 4], [0, 5, 1]]], [True, [1, 3]]], ['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]]]], [['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]]], ['two components second flipped', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2], [4, 5, 6], [4, 5, 7]]], [True, [5]]], ['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]]]]]
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 |
| second component consistent | [True, [6]] | [True, [6]] | Passed |
SHA-256 / ab2a9c8b1116b0443ca3152c068586fbe42afee3e279bf4e46a74f600575abba
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.084661+00:00.
Case digest / e9fe65d2d6dcf8259721375544b87956196e04126da18d468c13adcd1dedffc4