Source code for morphogen.mesh.polyhedra

"""Exact cells of Voronoi and Laguerre (power) tessellations restricted to a box.

The cell of germ ``g_i`` (weight ``w_i``) is the convex polyhedron of the points whose
power distance ``|x - g_i|^2 - w_i`` is the smallest: the intersection of the
half-spaces ``2 (g_j - g_i) . x <= |g_j|^2 - |g_i|^2 - w_j + w_i`` bounded by the
bisector planes of its neighbours. Each cell is computed as a half-space intersection
(Qhull) with the planes of nearby germs, then checked: no other germ may be closer to one
of its vertices, otherwise the missing germs are added and the cell computed again.

Restricted to the box, a tessellation is a complex of convex *pieces*: one per cell, or
several for the cells of a periodic tessellation that cross the faces of the box (one
piece per periodic image). Pieces share their *facets*: bisector polygons between two
pieces, or polygons on the faces of the box. Vertices computed by neighbouring pieces are
merged, so that the facets are shared exactly; for periodic tessellations, the vertices
of opposite faces of the box are made translates of each other.

A periodic tessellation can also be taken as a set of *whole cells* (:func:`periodic_cells`):
each cell once, around its germ in the box, uncut. Their union fills the volume of the
box and tiles space by the translations of the box; its boundary is made of facets
between a cell and a translate of another one, which come in pairs of translates, so
that a mesh of the union naturally has matching nodes on them (periodization at the
design rather than at the meshing).
"""

from __future__ import annotations

import itertools
import math
from dataclasses import dataclass, field

import numpy as np
from scipy.optimize import linprog
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import connected_components
from scipy.spatial import HalfspaceIntersection, QhullError, cKDTree

#: Box faces: x0, x1, y0, y1, z0, z1 (references 1 to 6).
BOX_FACES = ((0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1))


[docs] @dataclass class CellComplex: """Convex pieces of the cells of a tessellation restricted to a box. ``facets[f]`` is a loop of vertex indices, counter-clockwise around the normal that points from piece ``facet_pieces[f, 0]`` to piece ``facet_pieces[f, 1]`` (``-1``: outside the box, for the facets on its faces). ``facet_box[f]`` is 0 inside the box, 1-6 on the faces x0, x1, y0, y1, z0, z1. ``piece_cell[p]`` is the cell (germ index) of piece ``p``, ``piece_facets[p]`` its facets. ``whole``: the pieces are the whole cells of a periodic tessellation (:func:`periodic_cells`); the facets with no second piece then bound their union, and ``facet_shift[f]`` is the translation (in box lengths) of the cell beyond them. """ vertices: np.ndarray facets: list[np.ndarray] facet_pieces: np.ndarray facet_box: np.ndarray piece_cell: np.ndarray piece_facets: list[np.ndarray] lower: np.ndarray upper: np.ndarray periodic: bool = False metadata: dict = field(default_factory=dict) whole: bool = False facet_shift: np.ndarray | None = None @property def n_vertices(self) -> int: return len(self.vertices) @property def n_facets(self) -> int: return len(self.facets) @property def n_pieces(self) -> int: return len(self.piece_cell)
[docs] def facet_vectors(self) -> tuple[np.ndarray, np.ndarray]: """Area vectors (normal times area, oriented as the loops) and centroids.""" area = np.zeros((self.n_facets, 3)) centre = np.zeros((self.n_facets, 3)) for f, loop in enumerate(self.facets): p = self.vertices[loop] c = p.mean(axis=0) q = np.roll(p, -1, axis=0) cross = np.cross(p - c, q - c) a = 0.5 * cross.sum(axis=0) tri_area = 0.5 * np.linalg.norm(cross, axis=1) total = tri_area.sum() area[f] = a # area-weighted centroid of the fan triangles centre[f] = ( ((p + q + c) / 3.0 * tri_area[:, None]).sum(axis=0) / total if total > 0 else c ) return area, centre
[docs] def piece_volumes(self) -> np.ndarray: """Volumes of the pieces (divergence theorem over their facets).""" area, centre = self.facet_vectors() flux = np.einsum("ij,ij->i", area, centre) / 3.0 vol = np.zeros(self.n_pieces) np.add.at(vol, self.facet_pieces[:, 0], flux) inner = self.facet_pieces[:, 1] >= 0 np.add.at(vol, self.facet_pieces[inner, 1], -flux[inner]) return vol
[docs] def cell_volumes(self, n_cells: int | None = None) -> np.ndarray: """Volume of each cell inside the box (summed over its pieces).""" n = int(self.piece_cell.max()) + 1 if n_cells is None else int(n_cells) out = np.zeros(n) np.add.at(out, self.piece_cell, self.piece_volumes()) return out
[docs] def grain_boundary_area(self) -> float: """Area of the facets between different cells.""" area, _ = self.facet_vectors() a, b = self.facet_pieces[:, 0], self.facet_pieces[:, 1] inner = (b >= 0) & (self.piece_cell[a] != self.piece_cell[np.maximum(b, 0)]) return float(np.linalg.norm(area[inner], axis=1).sum())
[docs] def interface_facets(self) -> np.ndarray: """Facets between pieces of different cells (grain boundaries).""" a, b = self.facet_pieces[:, 0], self.facet_pieces[:, 1] return np.flatnonzero((b >= 0) & (self.piece_cell[a] != self.piece_cell[np.maximum(b, 0)]))
[docs] def edges(self) -> np.ndarray: """Unique edges (sorted vertex pairs) of the facets.""" pairs = [np.stack([loop, np.roll(loop, -1)], axis=1) for loop in self.facets] e = np.sort(np.concatenate(pairs), axis=1) return np.unique(e, axis=0)
[docs] def summary(self) -> dict: e = self.edges() lengths = np.linalg.norm(self.vertices[e[:, 0]] - self.vertices[e[:, 1]], axis=1) return { "n_cells": int(np.unique(self.piece_cell).size), "n_pieces": self.n_pieces, "n_facets": self.n_facets, "n_vertices": self.n_vertices, "shortest_edge": float(lengths.min()) if lengths.size else float("nan"), }
# -- geometry of one piece ------------------------------------------------------------------- def _chebyshev_centre(a: np.ndarray, b: np.ndarray) -> tuple[np.ndarray, float]: """Centre and radius of the largest ball inside ``a x <= b``.""" norms = np.linalg.norm(a, axis=1) res = linprog( c=[0.0, 0.0, 0.0, -1.0], A_ub=np.column_stack([a, norms]), b_ub=b, bounds=[(None, None)] * 3 + [(0.0, None)], method="highs", ) if res.status != 0: return np.zeros(3), 0.0 return res.x[:3], float(res.x[3]) def _loop_on_plane(points: np.ndarray, normal: np.ndarray) -> np.ndarray: """Order of planar points counter-clockwise around ``normal``.""" c = points.mean(axis=0) u = points[0] - c if np.linalg.norm(u) < 1e-300: u = np.array([1.0, 0.0, 0.0]) n = normal / np.linalg.norm(normal) u = u - n * (u @ n) if np.linalg.norm(u) < 1e-300: u = np.cross(n, [1.0, 0.0, 0.0]) if np.linalg.norm(u) < 1e-12: u = np.cross(n, [0.0, 1.0, 0.0]) u /= np.linalg.norm(u) v = np.cross(n, u) d = points - c return np.argsort(np.arctan2(d @ v, d @ u), kind="stable") def _piece(a: np.ndarray, b: np.ndarray, interior: np.ndarray, tol: float): """Vertices of ``a x <= b`` and, for each plane, its facet (vertex indices ordered counter-clockwise around the outward normal ``a``), or ``None`` if empty.""" try: hs = HalfspaceIntersection(np.column_stack([a, -b]), interior) except QhullError: try: hs = HalfspaceIntersection(np.column_stack([a, -b]), interior, qhull_options="QJ") except QhullError: return None pts = hs.intersections # merge duplicates (degenerate vertices are produced once per simplicial facet) labels = _merge_points(pts, tol) n_v = int(labels.max()) + 1 sums = np.zeros((n_v, 3)) np.add.at(sums, labels, pts) verts = sums / np.bincount(labels, minlength=n_v)[:, None] norms = np.linalg.norm(a, axis=1) dist = (verts @ a.T - b) / norms # (n_vertices, n_planes), <= 0 inside facets = {} for k in range(len(b)): on = np.flatnonzero(np.abs(dist[:, k]) <= 4.0 * tol) if on.size >= 3: loop = on[_loop_on_plane(verts[on], a[k])] facets[k] = loop if len(facets) < 4: return None return verts, facets # -- the complex ----------------------------------------------------------------------------- class _UnionFind: def __init__(self, n: int): self.parent = np.arange(n) def find(self, i: int) -> int: root = i while self.parent[root] != root: root = self.parent[root] while self.parent[i] != root: self.parent[i], i = root, self.parent[i] return root def union(self, i: int, j: int) -> None: ri, rj = self.find(i), self.find(j) if ri != rj: self.parent[max(ri, rj)] = min(ri, rj) def _merge_points(points: np.ndarray, tol: float) -> np.ndarray: """Cluster index of each point (points closer than ``tol`` are merged).""" if len(points) == 0: return np.zeros(0, dtype=np.int64) pairs = cKDTree(points).query_pairs(tol, output_type="ndarray") n = len(points) graph = coo_matrix((np.ones(len(pairs)), (pairs[:, 0], pairs[:, 1])), shape=(n, n)) _, labels = connected_components(graph, directed=False) return labels
[docs] def power_complex( germs, weights=None, lower=(0.0, 0.0, 0.0), upper=(1.0, 1.0, 1.0), periodic: bool = False, *, neighbours: int = 30, ) -> CellComplex: """Exact cells of the power diagram of ``germs`` (Voronoi without ``weights``) restricted to the box ``[lower, upper]``, periodic or not.""" lower = np.asarray(lower, dtype=float) upper = np.asarray(upper, dtype=float) size = upper - lower g = np.asarray(germs, dtype=float).reshape(-1, 3) - lower n = len(g) if n == 0: raise ValueError("power_complex: no germs") w = np.zeros(n) if weights is None else np.asarray(weights, dtype=float).reshape(n) scale = float(size.max()) tol = 1e-9 * scale if periodic: g = np.mod(g, size) shifts = np.array(list(itertools.product((-1, 0, 1), repeat=3)), dtype=float) pts = (g[None, :, :] + shifts[:, None, :] * size).reshape(-1, 3) ids = np.tile(np.arange(n), len(shifts)) wts = np.tile(w, len(shifts)) else: pts, ids, wts = g, np.arange(n), w wmax = float(wts.max()) lift = np.sqrt(np.maximum(wmax - wts, 0.0)) tree = cKDTree(np.column_stack([pts, lift])) # largest power distance from a point of the box to its cell: bounds the germs whose # cells reach the box (sampled on a grid, plus the sampling error) m = max(4, min(40, round(2.0 * n ** (1.0 / 3.0)) + 4)) axes = [np.linspace(0.0, s, m) for s in size] grid = np.stack(np.meshgrid(*axes, indexing="ij"), axis=-1).reshape(-1, 3) d, _ = tree.query(np.column_stack([grid, np.zeros(len(grid))])) power_max = float(np.max(d**2)) - wmax spacing = float(np.linalg.norm(size / (m - 1))) reach = math.sqrt(max(power_max + wmax, 0.0)) + spacing outside = np.maximum(np.maximum(-pts, pts - size), 0.0) candidates = np.flatnonzero(np.linalg.norm(outside, axis=1) <= reach + tol) box_a = np.array([[-1, 0, 0], [1, 0, 0], [0, -1, 0], [0, 1, 0], [0, 0, -1], [0, 0, 1]], float) box_b = np.array([0.0, size[0], 0.0, size[1], 0.0, size[2]]) k = min(neighbours, len(pts) - 1) raw = [] # (candidate, vertices, {plane key: loop}) for c in candidates: pc, wc = pts[c], wts[c] _, near = tree.query(np.concatenate([pc, [lift[c]]]), k=k + 1) near = [j for j in np.atleast_1d(near) if j != c and j < len(pts)] while True: nb = np.asarray(near, dtype=np.int64) a = np.vstack([2.0 * (pts[nb] - pc), box_a]) if nb.size else box_a.copy() b = np.concatenate( [(pts[nb] ** 2).sum(axis=1) - pc @ pc - wts[nb] + wc, box_b] if nb.size else [box_b] ) inside = ( np.all(pc > tol) and np.all(pc < size - tol) and (nb.size == 0 or np.all(a[: nb.size] @ pc < b[: nb.size] - tol * scale)) ) if inside: centre, radius = pc, 1.0 else: centre, radius = _chebyshev_centre(a, b) if radius <= 10.0 * tol: piece = None break piece = _piece(a, b, centre, tol) if piece is None: break verts, _ = piece # a vertex closer (in power distance) to another germ: that germ was missing dist, owner = tree.query(np.column_stack([verts, np.zeros(len(verts))])) own = ((verts - pc) ** 2).sum(axis=1) - wc + wmax missing = set( int(o) for o, dd, oo in zip(owner, dist**2, own, strict=True) if dd < oo - 1e-9 * scale**2 and o != c ) missing -= set(near) if not missing: break near += sorted(missing) if piece is None: continue verts, facets = piece keyed = {} for plane, loop in facets.items(): key = ("n", int(nb[plane])) if plane < nb.size else ("b", plane - nb.size + 1) keyed[key] = loop raw.append((int(c), verts, keyed)) return _assemble(raw, ids, size, lower, periodic, tol)
[docs] def periodic_cells( germs, weights=None, lower=(0.0, 0.0, 0.0), upper=(1.0, 1.0, 1.0), *, neighbours: int = 30, ) -> CellComplex: """Whole cells of the periodic power diagram of ``germs`` (Voronoi without ``weights``) of period ``upper - lower``: one piece per non-empty cell, around its germ brought into the box (see the module). Facets between two cells of the set are shared; the others bound the union and come in pairs of translates.""" lower = np.asarray(lower, dtype=float) upper = np.asarray(upper, dtype=float) size = upper - lower g = np.mod(np.asarray(germs, dtype=float).reshape(-1, 3) - lower, size) g[g >= size] = 0.0 n = len(g) if n == 0: raise ValueError("periodic_cells: no germs") w = np.zeros(n) if weights is None else np.asarray(weights, dtype=float).reshape(n) scale = float(size.max()) tol = 1e-9 * scale shifts = np.array(list(itertools.product((-1, 0, 1), repeat=3)), dtype=np.int64) pts = (g[None, :, :] + shifts[:, None, :] * size).reshape(-1, 3) ids = np.tile(np.arange(n), len(shifts)) image = np.repeat(shifts, n, axis=0) wts = np.tile(w, len(shifts)) zero = int(np.flatnonzero(np.all(shifts == 0, axis=1))[0]) wmax = float(wts.max()) lift = np.sqrt(np.maximum(wmax - wts, 0.0)) tree = cKDTree(np.column_stack([pts, lift])) box_a = np.array([[-1, 0, 0], [1, 0, 0], [0, -1, 0], [0, 1, 0], [0, 0, -1], [0, 0, 1]], float) voronoi = bool(np.all(w == w[0])) raw = [] for c in range(n): own_index = zero * n + c pc, wc = pts[own_index], wts[own_index] # a box around the germ keeps the first intersections bounded; it must not bound # the cell in the end box_b = np.concatenate( [[-(pc[d] - 2.0 * size[d]), pc[d] + 2.0 * size[d]] for d in range(3)] ) k = min(neighbours, len(pts) - 1) _, near = tree.query(np.concatenate([pc, [lift[own_index]]]), k=k + 1) near = [int(j) for j in np.atleast_1d(near) if j != own_index and j < len(pts)] piece = None for _ in range(20): nb = np.asarray(near, dtype=np.int64) a = np.vstack([2.0 * (pts[nb] - pc), box_a]) b = np.concatenate([(pts[nb] ** 2).sum(axis=1) - pc @ pc - wts[nb] + wc, box_b]) centre, radius = (pc, 1.0) if voronoi else _chebyshev_centre(a, b) if radius <= 10.0 * tol: piece = None break piece = _piece(a, b, centre, tol) if piece is None: break verts, facets = piece dist, owner = tree.query(np.column_stack([verts, np.zeros(len(verts))])) own = ((verts - pc) ** 2).sum(axis=1) - wc + wmax missing = { int(o) for o, dd, oo in zip(owner, dist**2, own, strict=True) if dd < oo - 1e-9 * scale**2 and o != own_index } - set(near) bounded = all(plane < nb.size for plane in facets) if not missing and bounded: break if missing: near += sorted(missing) else: # the box bounds the cell: more neighbours k = min(2 * k, len(pts) - 1) _, more = tree.query(np.concatenate([pc, [lift[own_index]]]), k=k + 1) near = [int(j) for j in np.atleast_1d(more) if j != own_index and j < len(pts)] else: raise RuntimeError("periodic_cells: a cell could not be closed by its neighbours") if piece is None: continue # an empty Laguerre cell verts, facets = piece keyed = {int(nb[plane]): loop for plane, loop in facets.items() if plane < nb.size} raw.append((c, verts, keyed)) return _assemble_whole(raw, ids, image, size, lower, tol)
def _merge_periodic(points: np.ndarray, size: np.ndarray, tol: float) -> np.ndarray: """Cluster index of points on the torus of period ``size`` (closer than ``tol``).""" pairs = cKDTree(points, boxsize=size).query_pairs(tol, output_type="ndarray") n = len(points) graph = coo_matrix((np.ones(len(pairs)), (pairs[:, 0], pairs[:, 1])), shape=(n, n)) return connected_components(graph, directed=False)[1]
[docs] def torus_classes(points: np.ndarray, lower, size, tol: float) -> tuple[np.ndarray, np.ndarray]: """Points that are translates of each other by the periods ``size``: the class of each point and its translation (in periods) from the first point of its class.""" p = np.asarray(points, dtype=float) - np.asarray(lower, dtype=float) size = np.asarray(size, dtype=float) wrapped = np.mod(p, size) wrapped[wrapped >= size] = 0.0 labels = _merge_periodic(wrapped, size, tol) first = np.full(int(labels.max()) + 1 if len(labels) else 0, -1) first[labels[::-1]] = np.arange(len(labels))[::-1] shift = np.rint((p - p[first[labels]]) / size).astype(np.int64) return labels, shift
def _assemble_whole(raw, ids, image, size, lower, tol) -> CellComplex: """Vertices and facets of whole cells: the vertices are translates of torus points by whole periods, so that the facets bounding the union are exact translates.""" all_pts = np.concatenate([v for _, v, _ in raw]) offsets = np.cumsum([0] + [len(v) for _, v, _ in raw]) labels, shift = torus_classes(all_pts, np.zeros(3), size, 50.0 * tol) n_lab = int(labels.max()) + 1 # one position per torus point (the mean of its copies brought back by their shifts) base = all_pts - shift * size sums = np.zeros((n_lab, 3)) np.add.at(sums, labels, base) canonical = sums / np.bincount(labels, minlength=n_lab)[:, None] key_index: dict = {} vertex_of = np.empty(len(all_pts), dtype=np.int64) for i, (lab, s) in enumerate(zip(labels.tolist(), map(tuple, shift.tolist()), strict=True)): vertex_of[i] = key_index.setdefault((lab, s), len(key_index)) verts = np.empty((len(key_index), 3)) for (lab, s), v in key_index.items(): verts[v] = canonical[lab] + np.asarray(s) * size piece_of = {c: p for p, (c, _, _) in enumerate(raw)} facet_index: dict = {} facets: list[np.ndarray] = [] facet_pieces: list[list[int]] = [] facet_shift: list[tuple] = [] piece_facets: list[list[int]] = [] for p, (c, _, keyed) in enumerate(raw): mine = [] for j, loop in keyed.items(): gl = vertex_of[offsets[p] + loop] gl = gl[np.concatenate([[True], gl[1:] != gl[:-1]])] if gl.size > 1 and gl[0] == gl[-1]: gl = gl[:-1] if np.unique(gl).size < 3: continue other, s = int(ids[j]), tuple(int(v) for v in image[j]) if s == (0, 0, 0): key = ("in", min(c, other), max(c, other)) if key in facet_index: f = facet_index[key] facet_pieces[f][1] = p merged = np.union1d(facets[f], gl) if merged.size != np.unique(facets[f]).size: facets[f] = _reloop(verts, merged, facets[f]) mine.append(f) continue facet_pieces.append([p, -2 if other in piece_of else -3]) else: key = ("out", c, other, s) facet_pieces.append([p, -1]) f = len(facets) facet_index[key] = f facets.append(gl) facet_shift.append(s) mine.append(f) piece_facets.append(mine) facet_pieces = np.array(facet_pieces, dtype=np.int64) # boundary facets without their translate, interior facets with one side: slivers # of degenerate vertices (dropped if their area is below the tolerance) drop = set(np.flatnonzero(facet_pieces[:, 1] < -1).tolist()) for key, f in facet_index.items(): if ( key[0] == "out" and ("out", key[2], key[1], tuple(-v for v in key[3])) not in facet_index ): drop.add(f) scale = float(size.max()) if any(_loop_area(verts[facets[f]]) > 1e-6 * scale**2 for f in drop): raise RuntimeError( "periodic_cells: a facet has no counterpart; the tessellation is degenerate" ) keep = np.array([f not in drop for f in range(len(facets))]) remap = np.cumsum(keep) - 1 cx = CellComplex( vertices=verts + lower, facets=[f for f, k in zip(facets, keep, strict=True) if k], facet_pieces=facet_pieces[keep], facet_box=np.zeros(int(keep.sum()), dtype=np.int64), piece_cell=np.array([ids[c] for c, _, _ in raw], dtype=np.int64), piece_facets=[ np.array([remap[f] for f in pf if keep[f]], dtype=np.int64) for pf in piece_facets ], lower=lower, upper=lower + size, periodic=True, whole=True, facet_shift=np.array( [s for s, k in zip(facet_shift, keep, strict=True) if k], dtype=np.int64 ).reshape(-1, 3), ) _orient_and_close(cx) return cx def _assemble(raw, ids, size, lower, periodic, tol) -> CellComplex: """Global vertices and shared facets of the pieces.""" scale = float(size.max()) # global vertices: merge the copies computed by neighbouring pieces all_pts = np.concatenate([v for _, v, _ in raw]) offsets = np.cumsum([0] + [len(v) for _, v, _ in raw]) labels = _merge_points(all_pts, 50.0 * tol) n_v = int(labels.max()) + 1 sums = np.zeros((n_v, 3)) np.add.at(sums, labels, all_pts) verts = sums / np.bincount(labels, minlength=n_v)[:, None] for d in range(3): # exactly on the faces of the box verts[np.abs(verts[:, d]) <= 100.0 * tol, d] = 0.0 verts[np.abs(verts[:, d] - size[d]) <= 100.0 * tol, d] = size[d] if periodic: _match_periodic_faces(verts, size, 1e3 * tol) piece_of = {c: p for p, (c, _, _) in enumerate(raw)} facet_index: dict = {} facets: list[np.ndarray] = [] facet_pieces: list[list[int]] = [] facet_box: list[int] = [] piece_facets: list[list[int]] = [] for p, (c, _, keyed) in enumerate(raw): mine = [] for key, loop in keyed.items(): gl = labels[offsets[p] + loop] gl = gl[np.concatenate([[True], gl[1:] != gl[:-1]])] if gl.size > 1 and gl[0] == gl[-1]: gl = gl[:-1] if np.unique(gl).size < 3: continue if key[0] == "b": f = len(facets) facets.append(gl) facet_pieces.append([p, -1]) facet_box.append(key[1]) mine.append(f) continue other = key[1] pair = (min(c, other), max(c, other)) if pair in facet_index: f = facet_index[pair] facet_pieces[f][1] = p # the loop seen from the second piece: union of the two vertex sets merged = np.union1d(facets[f], gl) if merged.size != np.unique(facets[f]).size: facets[f] = _reloop(verts, merged, facets[f]) else: f = len(facets) facet_index[pair] = f facets.append(gl) facet_pieces.append([p, -2 if other in piece_of else -3]) facet_box.append(0) mine.append(f) piece_facets.append(mine) facet_pieces = np.array(facet_pieces, dtype=np.int64) unmatched = np.flatnonzero(facet_pieces[:, 1] < -1) if unmatched.size: # facets whose second piece was not computed: tiny sliver facets of a vertex # shared by several cells, dropped (their area is below the tolerance) area = np.array([_loop_area(verts[facets[f]]) for f in unmatched]) if np.any(area > 1e-6 * scale**2): raise RuntimeError( "power_complex: a facet has a single piece; the tessellation is degenerate" ) drop = set(unmatched.tolist()) keep = np.array([f not in drop for f in range(len(facets))]) remap = np.cumsum(keep) - 1 facets = [f for f, k in zip(facets, keep, strict=True) if k] facet_pieces = facet_pieces[keep] facet_box = [b for b, k in zip(facet_box, keep, strict=True) if k] piece_facets = [[int(remap[f]) for f in pf if keep[f]] for pf in piece_facets] complex_ = CellComplex( vertices=verts + lower, facets=facets, facet_pieces=facet_pieces, facet_box=np.array(facet_box, dtype=np.int64), piece_cell=np.array([ids[c] for c, _, _ in raw], dtype=np.int64), piece_facets=[np.array(pf, dtype=np.int64) for pf in piece_facets], lower=lower, upper=lower + size, periodic=periodic, ) _orient_and_close(complex_) return complex_ def _loop_area(p: np.ndarray) -> float: 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))) def _reloop(verts, members, reference) -> np.ndarray: """Loop of ``members`` (coplanar) oriented as the loop ``reference``.""" p = verts[reference] c = p.mean(axis=0) normal = np.cross(p - c, np.roll(p, -1, axis=0) - c).sum(axis=0) return members[_loop_on_plane(verts[members], normal)] def _match_periodic_faces(verts: np.ndarray, size: np.ndarray, tol: float) -> None: """Make the vertices of opposite faces of the box exact translates of each other.""" for axis in range(3): others = [d for d in range(3) if d != axis] lo = np.flatnonzero(verts[:, axis] == 0.0) hi = np.flatnonzero(verts[:, axis] == size[axis]) if lo.size == 0 or hi.size == 0: continue dist, near = cKDTree(verts[lo][:, others]).query(verts[hi][:, others]) ok = dist <= tol verts[hi[ok][:, None], others] = verts[lo[near[ok]]][:, others] def _orient_and_close(cx: CellComplex) -> None: """Orient every facet from its first piece outwards, and check that every piece is a closed surface (each edge shared by two of its facets, in opposite directions).""" centres = np.zeros((cx.n_pieces, 3)) for p, pf in enumerate(cx.piece_facets): centres[p] = np.concatenate([cx.vertices[cx.facets[f]] for f in pf]).mean(axis=0) for f, loop in enumerate(cx.facets): p = cx.vertices[loop] c = p.mean(axis=0) normal = np.cross(p - c, np.roll(p, -1, axis=0) - c).sum(axis=0) if normal @ (c - centres[cx.facet_pieces[f, 0]]) < 0: cx.facets[f] = loop[::-1].copy() bad = 0 for p, pf in enumerate(cx.piece_facets): edges = {} for f in pf: loop = cx.facets[f] if cx.facet_pieces[f, 0] == p else cx.facets[f][::-1] for a, b in zip(loop, np.roll(loop, -1), strict=True): edges[(int(a), int(b))] = edges.get((int(a), int(b)), 0) + 1 for (a, b), count in edges.items(): if count != 1 or edges.get((b, a), 0) != 1: bad += 1 break cx.metadata["open_pieces"] = bad