FA-88556 / Mesh topology invariants / Open access

Orientation propagation runs through three-face fins · case 01

Non-manifold books get an orientability answer instead of "non-manifold".

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

ROOT CAUSE

The fin test only rejects edges with more than three faces.

VERIFIED REPAIR

Reject any edge with more than two incident faces.

Unsuccessful approach: Rejecting two incident faces rejects every closed mesh.

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)>3 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, []]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], 'non-manifold'], ['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, []]], ['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'], ['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]]], ['two components second flipped', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2], [4, 5, 6], [4, 5, 7]]], [True, [5]]]]]
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	`[False, []]`	`non-manifold`	Failed
flipped pair	`[True, [1]]`	`[True, [1]]`	Passed
disk with two flips	`[True, [1, 3]]`	`[True, [1, 3]]`	Passed

SHA-256 / 25bc8d5f346b234eaa627113e31d7824512c69395c813ebfda972b4f21c289e2

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

SHA-256 / ebbc9e79ab11df3cc8a436c4db40fc5fe84f8feab43a7134bc413273a7ddf5ba

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, []]], ['book', [[[0, 1, 2], [1, 0, 3], [0, 1, 4]]], 'non-manifold'], ['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, []]], ['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'], ['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]]], ['two components second flipped', [[[0, 2, 1], [0, 1, 3], [1, 2, 3], [0, 3, 2], [4, 5, 6], [4, 5, 7]]], [True, [5]]]]]
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 / 8fc3ffc83cc67c870f7b7bc5478438eb61039399155ad3e84fdeb533e0676e26

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

Case digest / c444006aec727fb21f9d753ecb797c68a1ca69e8b1dbfd012cbf23286e9b2d8b