"""Regularization of cell complexes: removal of the features smaller than a length.
A tessellation has edges, facets and pieces of every size; a mesh must resolve them with
elements of their size, or with flat elements. Following the idea of Quey, Dawson and
Barbe (2011), the features smaller than ``delta`` are removed before meshing:
* *caps* — pieces that rise less than ``delta`` above a face of the box (cells that
barely cross it) — are flattened onto that face: their other facets become faces of
the box for the neighbouring pieces. A cap that overhangs its facet on the face cannot
be flattened this way; it joins the cell of the neighbour with which it shares its
largest facet (its volume changes cell, the geometry is kept);
* short edges are contracted to a point, the shortest first; when contracting an edge
alone would leave an invalid piece (a tiny facet with several short edges), its nearest
neighbours are contracted with it.
Each change is kept only if every piece it touches remains a valid star polyhedron (the
cones from its centroid over its facets have positive volumes) touching the faces of the
box by facets, not along lines. The vertices on the faces of the box stay on them. The
faces of a periodic complex remain exact translates of each other: a vertex of a face
moves and merges together with its periodic images, and the facet of a flattened cap's
cell on the opposite face is split as the cap's facet was. The facets become slightly
non-planar.
The whole cells of a periodic tessellation (``CellComplex.whole``) have no caps: only their
short edges are contracted, every vertex moving and merging together with its
translates, so that the facets bounding their union remain pairs of translates.
"""
from __future__ import annotations
import heapq
import numpy as np
from scipy.spatial import cKDTree
from morphogen.mesh.polyhedra import CellComplex
class _Complex:
"""Mutable copy of a cell complex."""
def __init__(self, cx: CellComplex):
self.cx = cx
self.V = cx.vertices.copy()
self.facets = [list(map(int, f)) for f in cx.facets]
self.fp = [list(map(int, p)) for p in cx.facet_pieces]
self.fbox = [int(b) for b in cx.facet_box]
self.pfac = [set(map(int, pf)) for pf in cx.piece_facets]
self.alive_f = [True] * len(self.facets)
self.alive_p = [True] * len(self.pfac)
self.cell = np.array(cx.piece_cell, dtype=np.int64)
self.lower, self.upper = cx.lower, cx.upper
self.size = cx.upper - cx.lower
self.whole = bool(cx.whole)
self.tol = 1e-9 * float(self.size.max())
self.vfac: list[set] = [set() for _ in range(len(self.V))]
for f, loop in enumerate(self.facets):
for v in loop:
self.vfac[v].add(f)
# -- geometry ------------------------------------------------------------------------
def planes(self, v: int) -> set:
"""Faces of the box (axis, side) containing vertex ``v`` (none for whole cells)."""
out = set()
if self.whole:
return out
for d in range(3):
if abs(self.V[v, d] - self.lower[d]) <= self.tol:
out.add((d, 0))
elif abs(self.V[v, d] - self.upper[d]) <= self.tol:
out.add((d, 1))
return out
def oriented(self, f: int, p: int) -> list:
return self.facets[f] if self.fp[f][0] == p else self.facets[f][::-1]
def piece_vertices(self, p: int) -> list:
return sorted({v for f in self.pfac[p] for v in self.facets[f]})
def piece_ok(self, p: int, min_volume: float) -> bool:
"""Closed star polyhedron: every edge of its facets is shared by two facets in
opposite directions, and the cones from its centroid over the facet fans have
positive volumes."""
if len(self.pfac[p]) < 4:
return False
edges: dict = {}
for f in self.pfac[p]:
loop = self.oriented(f, p)
for a, b in zip(loop, loop[1:] + loop[:1], strict=True):
edges[(a, b)] = edges.get((a, b), 0) + 1
for (a, b), count in edges.items():
if count != 1 or edges.get((b, a), 0) != 1:
return False
# an edge on a face of the box belongs to a facet of the piece on that face (a
# piece touching the box along a line only is not a valid subdomain)
box_edges = set()
for f in self.pfac[p]:
if self.fbox[f] > 0:
loop = self.facets[f]
box_edges.update(zip(loop, loop[1:] + loop[:1], strict=True))
box_edges.update(zip(loop[1:] + loop[:1], loop, strict=True))
for f in self.pfac[p]:
if self.fbox[f] > 0:
continue
loop = self.facets[f]
for a, b in zip(loop, loop[1:] + loop[:1], strict=True):
if (a, b) not in box_edges and self.planes(a) & self.planes(b):
return False
verts = self.piece_vertices(p)
g = self.V[verts].mean(axis=0)
total = 0.0
for f in self.pfac[p]:
loop = self.oriented(f, p)
if len(set(loop)) < 3:
return False
pts = self.V[loop]
c = pts.mean(axis=0)
nxt = np.roll(pts, -1, axis=0)
vol = np.cross(pts - c, nxt - c) @ (g - c) / 6.0
# outward triangles: the centroid lies behind them
if np.any(vol >= -min_volume):
return False
total -= vol.sum()
return total > 0
def facet_area(self, f: int) -> float:
p = self.V[self.facets[f]]
c = p.mean(axis=0)
return 0.5 * float(np.linalg.norm(np.cross(p - c, np.roll(p, -1, axis=0) - c).sum(axis=0)))
# -- edits ---------------------------------------------------------------------------
def snapshot(self, facets, pieces, verts):
verts = set(verts)
for f in facets:
verts.update(self.facets[f])
return (
{
f: (list(self.facets[f]), self.alive_f[f], list(self.fp[f]), self.fbox[f])
for f in facets
},
{p: (set(self.pfac[p]), self.alive_p[p]) for p in pieces},
{v: (self.V[v].copy(), set(self.vfac[v])) for v in verts},
)
def restore(self, snap):
fs, ps, vs = snap
for f, (loop, alive, fp, fb) in fs.items():
self.facets[f], self.alive_f[f], self.fp[f], self.fbox[f] = loop, alive, fp, fb
for p, (pf, alive) in ps.items():
self.pfac[p], self.alive_p[p] = pf, alive
for v, (x, vf) in vs.items():
self.V[v], self.vfac[v] = x, vf
def clean_facet(self, f: int) -> None:
"""Remove repeated vertices; kill the facet if fewer than three remain."""
loop = self.facets[f]
out = [v for i, v in enumerate(loop) if v != loop[i - 1]] if len(loop) > 1 else loop
if len(out) > 1 and out[0] == out[-1]:
out = out[:-1]
self.facets[f] = out
if len(set(out)) < 3 or len(set(out)) != len(out):
self.kill_facet(f)
def kill_facet(self, f: int) -> None:
if not self.alive_f[f]:
return
self.alive_f[f] = False
for p in self.fp[f]:
if p >= 0:
self.pfac[p].discard(f)
for v in set(self.facets[f]):
self.vfac[v].discard(f)
def add_vertex(self, x) -> int:
self.V = np.vstack([self.V, np.asarray(x, dtype=float)[None, :]])
self.vfac.append(set())
return len(self.V) - 1
def add_facet(self, loop: list, pieces: list, box: int) -> int:
f = len(self.facets)
self.facets.append(list(loop))
self.fp.append(list(pieces))
self.fbox.append(int(box))
self.alive_f.append(True)
for p in pieces:
if p >= 0:
self.pfac[p].add(f)
for v in loop:
self.vfac[v].add(f)
return f
def discard_new(self, n_vertices: int, n_facets: int) -> None:
"""Forget the vertices and facets added since the counts given (after restore)."""
for f in range(n_facets, len(self.facets)):
self.alive_f[f] = False
for v in range(n_vertices, len(self.V)):
self.vfac[v] = set()
def merge(self, a: int, b: int, x) -> None:
"""Vertex ``b`` disappears into ``a``, moved to ``x``."""
self.V[a] = x
for f in list(self.vfac[b]):
self.facets[f] = [a if v == b else v for v in self.facets[f]]
self.vfac[a].add(f)
self.vfac[b] = set()
for f in list(self.vfac[a]):
if self.alive_f[f]:
self.clean_facet(f)
def _translates(cx: _Complex) -> dict:
"""Translates of the vertices of whole cells: ``v -> {offset: copy}``. They are exact
but for rounding, while distinct vertices are farther apart than the tolerance of
their assembly (an edge may be shorter than a micrometre of a unit box)."""
from morphogen.mesh.polyhedra import torus_classes
labels, shift = torus_classes(cx.V, cx.lower, cx.size, 0.1 * cx.tol)
members: dict = {}
for v, lab in enumerate(labels.tolist()):
members.setdefault(lab, []).append(v)
out: dict = {}
for group in members.values():
if len(group) < 2:
continue
for v in group:
out[v] = {tuple(int(k) for k in shift[u] - shift[v]): u for u in group if u != v}
return out
def _images(cx: _Complex) -> dict:
"""Periodic images of the vertices of the faces: ``v -> {offset: image}``."""
if cx.whole:
return _translates(cx)
on = [v for v in range(len(cx.V)) if cx.planes(v)]
if not on:
return {}
tree = cKDTree(cx.V[on])
out: dict = {}
for v in on:
for d, side in cx.planes(v):
shift = np.zeros(3)
shift[d] = cx.size[d] if side == 0 else -cx.size[d]
dist, j = tree.query(cx.V[v] + shift)
if dist <= 1e3 * cx.tol:
key = tuple(int(s) for s in np.sign(shift))
out.setdefault(v, {})[key] = on[j]
# images across several faces (box edges and corners): compose the offsets
changed = True
while changed:
changed = False
for v, imgs in list(out.items()):
for k1, w in list(imgs.items()):
for k2, u in out.get(w, {}).items():
k = tuple(np.add(k1, k2))
if any(k) and k not in imgs and u != v and max(map(abs, k)) <= 1:
imgs[k] = u
changed = True
return out
def _touching(cx: _Complex, verts) -> set:
pieces = set()
for v in verts:
for f in cx.vfac[v]:
pieces.update(p for p in cx.fp[f] if p >= 0)
return pieces
def _opposite_facet(cx: _Complex, f: int, off: tuple, images: dict) -> int | None:
"""The facet of the opposite face whose vertices are the images of those of ``f``."""
imgs = [images.get(v, {}).get(off) for v in cx.facets[f]]
if any(i is None for i in imgs):
return None
d = int(np.flatnonzero(off)[0])
ref = 2 * d + 1 + (1 if off[d] > 0 else 0)
cand = [
g
for g in set.intersection(*(cx.vfac[i] for i in imgs))
if cx.alive_f[g] and cx.fbox[g] == ref and set(cx.facets[g]) == set(imgs)
]
return cand[0] if len(cand) == 1 else None
def _relabel(cx: _Complex, p: int) -> bool:
"""Give a piece to the cell of the neighbour with which it shares its largest facet."""
best, cell = 0.0, None
for f in cx.pfac[p]:
q = cx.fp[f][1] if cx.fp[f][0] == p else cx.fp[f][0]
if q >= 0 and cx.cell[q] != cx.cell[p]:
area = cx.facet_area(f)
if area > best:
best, cell = area, cx.cell[q]
if cell is None:
return False
cx.cell[p] = cell
return True
def _flatten_caps(cx: _Complex, delta: float, min_volume: float, images: dict) -> tuple:
"""Flatten the pieces that rise less than ``delta`` above a face of the box. In a
periodic complex, the facet of the same cell on the opposite face is split alike (new
vertices, images of the flattened ones), so that opposite faces remain translates.
The caps that cannot be flattened (overhanging the face) join a neighbouring cell.
Returns the numbers of flattened and relabelled caps."""
done = relabelled = 0
for p in range(len(cx.pfac)):
if not cx.alive_p[p]:
continue
box_facets = [f for f in cx.pfac[p] if cx.fbox[f] > 0]
verts = cx.piece_vertices(p)
best = None
for ref in {cx.fbox[f] for f in box_facets}:
d, side = (ref - 1) // 2, (ref - 1) % 2
plane = cx.lower[d] if side == 0 else cx.upper[d]
height = float(np.max(np.abs(cx.V[verts, d] - plane)))
if height < delta and (best is None or height < best[0]):
best = (height, d, side, plane, ref)
if best is None:
continue
_, d, side, plane, ref = best
moved = [v for v in verts if abs(cx.V[v, d] - plane) > cx.tol]
opposite, off = None, None
if images:
# a piece on one face only, whose other vertices lie inside the box
if len(box_facets) == 1 and not any(cx.planes(v) for v in moved):
off = tuple(int(k == d) * (1 if side == 0 else -1) for k in range(3))
opposite = _opposite_facet(cx, box_facets[0], off, images)
if opposite is None:
relabelled += _relabel(cx, p)
continue
facets = set(cx.pfac[p])
pieces = _touching(cx, moved) | {p}
if opposite is not None:
pieces.add(cx.fp[opposite][0])
for q in pieces:
facets |= cx.pfac[q]
snap = cx.snapshot(facets, pieces, moved)
n_vertices, n_facets = len(cx.V), len(cx.facets)
for v in moved:
cx.V[v, d] = plane
# the piece disappears: its facets on the face go, the others join the face
joined = []
for f in list(cx.pfac[p]):
if cx.fbox[f] > 0:
cx.kill_facet(f)
continue
other = cx.fp[f][1] if cx.fp[f][0] == p else cx.fp[f][0]
if cx.fp[f][0] == p: # the loop pointed away from p, into the other piece
cx.facets[f] = cx.facets[f][::-1]
cx.fp[f] = [other, -1]
cx.fbox[f] = ref
if cx.facet_area(f) <= 1e-12 * float(cx.size.max()) ** 2:
cx.kill_facet(f)
else:
joined.append(f)
cx.pfac[p] = set()
cx.alive_p[p] = False
new_images = []
if opposite is not None:
# the facet of the cell on the opposite face, split as the joined facets
owner, ref_b = cx.fp[opposite][0], cx.fbox[opposite]
cx.kill_facet(opposite)
shift = np.zeros(3)
shift[d] = off[d] * cx.size[d]
back = tuple(-k for k in off)
for v in sorted({v for f in joined for v in cx.facets[f]} & set(moved)):
u = cx.add_vertex(cx.V[v] + shift)
images[v], images[u] = {off: u}, {back: v}
new_images += [v, u]
for f in joined: # the outward normal of the opposite face is reversed
cx.add_facet([images[v][off] for v in cx.facets[f]][::-1], [owner, -1], ref_b)
if all(cx.piece_ok(q, min_volume) for q in pieces if q != p and cx.alive_p[q]):
done += 1
else:
cx.restore(snap)
cx.discard_new(n_vertices, n_facets)
for v in new_images:
images.pop(v, None)
relabelled += _relabel(cx, p)
return done, relabelled
def _contract(cx: _Complex, cluster: set, min_volume: float, images: dict) -> list | None:
"""Contract a set of vertices to one point, with their periodic images; the change is
kept if every piece it touches remains valid. Returns the vertices kept (the point
and its images), or None."""
planes = {v: cx.planes(v) for v in cluster}
union = set().union(*planes.values())
if len({d for d, _ in union}) < len(union):
return None # opposite faces of the box
most = max(len(s) for s in planes.values())
# the most constrained vertex, with the most periodic images
keep = min(cluster, key=lambda v: (-len(planes[v]), -len(images.get(v, {})), v))
if not all(s <= planes[keep] for s in planes.values()):
return None # on different faces of the box
# the point: the mean of the most constrained vertices, on their faces
target = cx.V[[v for v in cluster if len(planes[v]) == most]].mean(axis=0)
for d, side in union:
target[d] = cx.lower[d] if side == 0 else cx.upper[d]
groups = [(keep, [v for v in cluster if v != keep])]
if images and (union or cx.whole):
# a vertex of a face (of whole cells: any vertex) moves with its images, and the
# images merge alike
ik = images.get(keep, {})
on_faces = [images.get(v, {}) for v in cluster if v != keep and (planes[v] or cx.whole)]
if not all(set(iv) <= set(ik) for iv in on_faces):
return None # the images differ: the faces differ here
for off, image in ik.items():
groups.append((image, [iv[off] for iv in on_faces if off in iv]))
verts = {v for keep_v, gone in groups for v in [keep_v, *gone]}
pieces = _touching(cx, verts)
facets = set()
for q in pieces:
facets |= cx.pfac[q]
for v in verts:
facets |= cx.vfac[v]
snap = cx.snapshot(facets, pieces, verts)
origin = cx.V[keep].copy()
for keep_v, gone in groups:
x = target + (cx.V[keep_v] - origin) # the same move for the images
cx.V[keep_v] = x
for v in gone:
cx.merge(keep_v, v, x)
if all(cx.piece_ok(q, min_volume) for q in pieces if cx.alive_p[q] and cx.pfac[q]):
return [keep_v for keep_v, _ in groups]
cx.restore(snap)
return None
def _neighbours(cx: _Complex, cluster: set) -> set:
out = set()
for v in cluster:
for f in cx.vfac[v]:
loop = cx.facets[f]
i = loop.index(v)
out.update((loop[i - 1], loop[(i + 1) % len(loop)]))
return out - cluster
def _collapse_edges(
cx: _Complex, delta: float, min_volume: float, images: dict, max_cluster: int = 6
) -> int:
"""Contract the edges shorter than ``delta`` (with their periodic images), the
shortest first. When contracting an edge alone would leave an invalid piece (several
tiny edges around a small facet), its nearest neighbours are contracted with it, up to
``max_cluster`` vertices within ``delta`` of their centre."""
heap = []
def push(a, b):
length = float(np.linalg.norm(cx.V[a] - cx.V[b]))
if length < delta:
heapq.heappush(heap, (length, min(a, b), max(a, b)))
for f, loop in enumerate(cx.facets):
if cx.alive_f[f]:
for a, b in zip(loop, loop[1:] + loop[:1], strict=True):
push(a, b)
done = 0
while heap:
_, a, b = heapq.heappop(heap)
if a == b or not cx.vfac[a] or not cx.vfac[b]:
continue
if not any(b in cx.facets[f] for f in cx.vfac[a]):
continue # no longer an edge
cluster = {a, b}
kept = _contract(cx, cluster, min_volume, images)
while kept is None and len(cluster) < max_cluster:
centre = cx.V[list(cluster)].mean(axis=0)
near = _neighbours(cx, cluster)
if not near:
break
w = min(near, key=lambda v: float(np.linalg.norm(cx.V[v] - centre)))
if np.linalg.norm(cx.V[w] - centre) >= delta:
break
cluster.add(w)
kept = _contract(cx, cluster, min_volume, images)
if kept is None:
continue
done += len(cluster) - 1
for keep_v in kept:
for f in list(cx.vfac[keep_v]):
loop = cx.facets[f]
i = loop.index(keep_v)
push(keep_v, loop[i - 1])
push(keep_v, loop[(i + 1) % len(loop)])
return done
def _fix_t_junctions(cx: _Complex) -> int:
"""Insert into every facet edge the vertices lying on it, so that neighbouring facets
are subdivided alike."""
used = sorted({v for f, loop in enumerate(cx.facets) if cx.alive_f[f] for v in loop})
if not used:
return 0
tree = cKDTree(cx.V[used])
added = 0
changed = True
while changed:
changed = False
for f, loop in enumerate(cx.facets):
if not cx.alive_f[f]:
continue
out = []
for a, b in zip(loop, loop[1:] + loop[:1], strict=True):
out.append(a)
pa, pb = cx.V[a], cx.V[b]
ab = pb - pa
length2 = float(ab @ ab)
near = tree.query_ball_point(0.5 * (pa + pb), 0.5 * np.sqrt(length2) + cx.tol)
inside = []
for k in near:
w = used[k]
if w in (a, b):
continue
t = float((cx.V[w] - pa) @ ab) / length2
if 0.0 < t < 1.0 and np.linalg.norm(pa + t * ab - cx.V[w]) <= 1e3 * cx.tol:
inside.append((t, w))
for _, w in sorted(inside):
if w not in out and w not in loop:
out.append(w)
cx.vfac[w].add(f)
added += 1
changed = True
cx.facets[f] = out
return added
[docs]
def regularize(cx: CellComplex, delta: float) -> CellComplex:
"""Complex without the caps and edges smaller than ``delta`` (see the module)."""
if not delta > 0:
return cx
m = _Complex(cx)
min_volume = 1e-15 * float(np.prod(m.size))
images = _images(m) if cx.periodic else {}
caps, relabelled = (0, 0) if m.whole else _flatten_caps(m, delta, min_volume, images)
edges = _collapse_edges(m, delta, min_volume, images)
tj = _fix_t_junctions(m)
# compact
alive_f = [f for f in range(len(m.facets)) if m.alive_f[f]]
alive_p = [p for p in range(len(m.pfac)) if m.alive_p[p] and m.pfac[p]]
fmap = {f: k for k, f in enumerate(alive_f)}
pmap = {p: k for k, p in enumerate(alive_p)}
used = sorted({v for f in alive_f for v in m.facets[f]})
vmap = {v: k for k, v in enumerate(used)}
return CellComplex(
vertices=m.V[used],
facets=[np.array([vmap[v] for v in m.facets[f]], dtype=np.int64) for f in alive_f],
facet_pieces=np.array(
[[pmap[p] if p >= 0 else -1 for p in m.fp[f]] for f in alive_f], dtype=np.int64
),
facet_box=np.array([m.fbox[f] for f in alive_f], dtype=np.int64),
piece_cell=m.cell[alive_p],
piece_facets=[
np.array(sorted(fmap[f] for f in m.pfac[p]), dtype=np.int64) for p in alive_p
],
lower=cx.lower,
upper=cx.upper,
periodic=cx.periodic,
whole=cx.whole,
metadata={
**cx.metadata,
"regularization": float(delta),
"flattened_caps": caps,
"relabelled_caps": relabelled,
"contracted_edges": edges,
"t_junctions": tj,
},
)