FA-88536 / Mesh topology invariants / Open access

Orientation propagation treats opposite edge directions as a mismatch · case 01

Consistent neighbours are flipped and a consistent mesh reports flips everywhere.

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

ROOT CAUSE

The shared edge is considered same-direction when the neighbour stores it reversed.

VERIFIED REPAIR

A neighbour needs flipping relative to the current face when it stores the shared edge in the same direction.

Unsuccessful approach: Folding the current flip state into the direction test double-counts the flip.

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)==(b,a) 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]]]], [['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]]], ['annulus', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 3, 0]]], [True, []]]], [['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]]], ['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, []]], ['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]]], ['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]]], ['disk with two flips', [[[0, 1, 2], [0, 3, 2], [0, 3, 4], [0, 5, 4], [0, 5, 1]]], [True, [1, 3]]], ['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	`[False, []]`	`[True, []]`	Failed
one flipped face	`[False, []]`	`[True, [1]]`	Failed
mobius	`[True, [1]]`	`[False, []]`	Failed
projective plane	`[False, []]`	`[False, []]`	Passed
book	`non-manifold`	`non-manifold`	Passed
flipped pair	`[True, []]`	`[True, [1]]`	Failed
disk with two flips	`[False, []]`	`[True, [1, 3]]`	Failed

SHA-256 / fb3b52e0e3ddd118a55fbcdec6b4476ab82351cd5c8f91ecac509b80faba18ba

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) and flip[fi]==0 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]]]], [['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]]], ['annulus', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 3, 0]]], [True, []]]], [['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]]], ['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, []]], ['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]]], ['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]]], ['disk with two flips', [[[0, 1, 2], [0, 3, 2], [0, 3, 4], [0, 5, 4], [0, 5, 1]]], [True, [1, 3]]], ['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 / 17366fa933e87c4d8f8730411516a1aee9ec6bb0642b2a83afd4e0088d7098f0

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]]]], [['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]]], ['annulus', [[[0, 3, 4, 1], [1, 4, 5, 2], [2, 5, 3, 0]]], [True, []]]], [['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]]], ['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, []]], ['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]]], ['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]]], ['disk with two flips', [[[0, 1, 2], [0, 3, 2], [0, 3, 4], [0, 5, 4], [0, 5, 1]]], [True, [1, 3]]], ['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 / a8537f388ccc3ce7152076a7b769393715ac38d5ca5bcb52a59e79246ad737e1

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

Case digest / 94d6ba73c3bc0cac193f675d739c78b4ff51891bfb50f36fdc873004d1df6d29