"""Balanced octrees of a box, refined where a level set needs it, and their conforming
tetrahedralization.
The box is split into root cells (about ``size`` wide); a cell whose lines do not resolve
the level set (the test of :func:`morphogen.mesh.exact.adaptive_mesh` on its 27 lines of
three points: edges, middle lines of its faces and axes) is split into eight, down to the
smallest size. The octree is then balanced: two leaves that touch (by a face, an edge or a
corner, across the periodic faces too) differ by one level at most. Its tetrahedra are cones
from the centres of the leaves over their faces, each face (or quarter of a face, where the
leaf across it is finer) a fan from its centre over its corners and the nodes in the middle
of its sides: the same triangles on both sides of every face, so the mesh is conforming, and
on opposite faces of the box along the periodic axes, which match. Every tetrahedron joins
the centre of a leaf to a quarter of one of its faces at least: their shapes are bounded.
"""
from __future__ import annotations
import itertools
import numpy as np
from morphogen.mesh.tetra import tet_volumes
#: The 27 points of a cell, in half cells from its lower corner (index ``9 a + 3 b + c``)
LATTICE = np.array(list(itertools.product(range(3), repeat=3)), dtype=np.int64)
#: The eight children of a cell
CHILDREN = np.array(list(itertools.product(range(2), repeat=3)), dtype=np.int64)
#: The 26 neighbours of a cell
NEIGHBOURS = np.array([d for d in itertools.product((-1, 0, 1), repeat=3) if any(d)])
def _others(axis: int) -> tuple[int, int]:
return tuple(d for d in range(3) if d != axis) # type: ignore[return-value]
def _lines() -> list[tuple[int, list[int]]]:
"""The 27 lines of three points of :data:`LATTICE` (9 along each axis): the axis and
the indices of their points in order."""
out = []
for d in range(3):
b, c = _others(d)
for u, v in itertools.product(range(3), repeat=2):
idx = []
for t in range(3):
p = [0, 0, 0]
p[d], p[b], p[c] = t, u, v
idx.append(9 * p[0] + 3 * p[1] + p[2])
out.append((d, idx))
return out
LINES = _lines()
def _segments() -> np.ndarray:
"""The segments between points of :data:`LATTICE` that the tetrahedra of a cell, or of
its children, may take as edges: those between neighbours (the unit squares and cubes
of the lattice, their diagonals included) and those between corners (the edges of the
cell, the diagonals of its faces and its own)."""
corner = np.all(LATTICE % 2 == 0, axis=1)
out = []
for a, b in itertools.combinations(range(len(LATTICE)), 2):
d = np.abs(LATTICE[a] - LATTICE[b]).max()
if d == 1 or (d == 2 and corner[a] and corner[b]):
out.append((a, b))
return np.asarray(out, dtype=np.int64)
#: The 186 segments of :data:`LATTICE` that may be edges of tetrahedra (:func:`_segments`)
SEGMENTS = _segments()
[docs]
class Octree:
"""Leaves ``(level, i, j, k)`` of an octree over ``n`` root cells along each axis of the
box ``[lower, upper]`` (a leaf of level ``l`` is ``2^l`` times smaller than a root cell),
periodic along ``axes``, at most ``maxlevel`` deep."""
def __init__(self, lower, upper, n, axes, maxlevel: int):
self.lower = np.asarray(lower, dtype=float)
self.upper = np.asarray(upper, dtype=float)
self.n = np.asarray(n, dtype=np.int64)
self.h = (self.upper - self.lower) / self.n
self.axes = np.asarray(axes, dtype=bool)
self.maxlevel = int(maxlevel)
self._base = int(self.n.max() << (self.maxlevel + 2)) + 1
grid = np.meshgrid(*(np.arange(k) for k in self.n), indexing="ij")
self.ijk = np.stack(grid, axis=-1).reshape(-1, 3).astype(np.int64)
self.level = np.zeros(len(self.ijk), dtype=np.int64)
self._keys = None
# -- leaves -----------------------------------------------------------------------------
def _key(self, level, ijk) -> np.ndarray:
m = self._base
return ((np.asarray(level) * m + ijk[:, 0]) * m + ijk[:, 1]) * m + ijk[:, 2]
def _sorted_keys(self) -> np.ndarray:
if self._keys is None:
self._keys = np.sort(self._key(self.level, self.ijk))
return self._keys
[docs]
def is_leaf(self, level, ijk) -> np.ndarray:
"""Whether the cells ``(level, ijk)`` (in the box) are leaves."""
keys = self._sorted_keys()
k = self._key(level, ijk)
pos = np.minimum(np.searchsorted(keys, k), len(keys) - 1)
return keys[pos] == k
[docs]
def wrap(self, level, ijk) -> tuple[np.ndarray, np.ndarray]:
"""Cell indices wrapped along the periodic axes, and whether they lie in the box."""
count = self.n[None, :] << np.asarray(level)[..., None]
out = np.where(self.axes, np.mod(ijk, count), ijk)
return out, np.all((out >= 0) & (out < count), axis=1)
[docs]
def sizes(self, level) -> np.ndarray:
"""The sides of cells of the levels (rows)."""
return self.h[None, :] / (1 << np.asarray(level))[:, None]
[docs]
def points(self, level, ijk) -> np.ndarray:
"""The 27 points of the cells, ``(k, 27, 3)``."""
cell = self.sizes(level)
origin = self.lower + ijk * cell
return origin[:, None, :] + LATTICE[None, :, :] * (0.5 * cell[:, None, :])
[docs]
def split(self, mask) -> np.ndarray:
"""Leaves replaced by their eight children; the indices of the children."""
level, ijk = self.level[mask], self.ijk[mask]
kids = (2 * ijk[:, None, :] + CHILDREN[None, :, :]).reshape(-1, 3)
keep = ~mask
self.level = np.concatenate([self.level[keep], np.repeat(level + 1, 8)])
self.ijk = np.concatenate([self.ijk[keep], kids])
self._keys = None
return np.arange(len(self.level) - len(kids), len(self.level))
# -- refinement -------------------------------------------------------------------------
[docs]
def refine(self, test) -> list[int]:
"""Split the leaves for which ``test(points)`` (of their 27 points ``(k, 27, 3)``,
and their sides ``(k, 3)``) is true, then their children, down to ``maxlevel``;
returns the number of leaves split at each level."""
todo = np.arange(len(self.level))
counts = []
while todo.size:
level = self.level[todo]
split = np.asarray(test(self.points(level, self.ijk[todo]), self.sizes(level)))
split &= level < self.maxlevel
counts.append(int(split.sum()))
if not split.any():
break
mask = np.zeros(len(self.level), dtype=bool)
mask[todo[split]] = True
todo = self.split(mask)
return counts
[docs]
def balance(self) -> int:
"""Split leaves until any two that touch (across the periodic faces too) differ by
one level at most; returns the number of splits."""
total = 0
while True:
mask = np.zeros(len(self.level), dtype=bool)
for lv in range(2, self.maxlevel + 1):
sel = np.flatnonzero(self.level == lv)
if not sel.size:
continue
for d in NEIGHBOURS:
nb, inside = self.wrap(lv, self.ijk[sel] + d)
nb = nb[inside]
for up in range(2, lv + 1): # the coarse leaves that hold the neighbours
anc = nb >> up
hit = self.is_leaf(lv - up, anc)
if hit.any():
mask |= np.isin(self._key(self.level, self.ijk),
self._key(lv - up, anc[hit])) # fmt: skip
if not mask.any():
return total
total += int(mask.sum())
self.split(mask)
# -- tetrahedra -------------------------------------------------------------------------
[docs]
def tetrahedra(self):
"""The conforming tetrahedralization of the leaves (see the module): nodes,
positive tetrahedra, the triangles of the faces of the box with their references
(1-6: x0, x1, y0, y1, z0, z1), and the integer coordinates of the nodes (in quarters
of the smallest cells)."""
r = 1 << (self.maxlevel + 1) # node units per root cell
unit = (r >> self.level)[:, None] # sides of the leaves, in node units
total = self.n * r
# the corners of the leaves (folded along the periodic axes): the nodes in the
# middle of the sides of coarser faces
corners = (self.ijk[:, None, :] + CHILDREN[None, :, :]) * unit[:, None, :]
corner_keys = np.unique(self._node_key(self._fold(corners.reshape(-1, 3), total)))
centres = self.ijk * unit + unit // 2
faces = []
plain = np.ones(len(self.level), dtype=bool) # leaves of six plain faces: Kuhn
for d in range(3):
b, c = _others(d)
for s in (0, 1):
step = np.zeros(3, dtype=np.int64)
step[d] = 2 * s - 1
nb, inside = self.wrap(self.level, self.ijk + step)
child = 2 * nb
child[:, d] += 1 - s # the children of the neighbour along the face
finer = inside & (self.level < self.maxlevel)
finer[finer] = self.is_leaf(self.level[finer] + 1, child[finer])
origin = self.ijk * unit
origin[:, d] += s * unit[:, 0]
middles = self._middles(origin, unit, d, corner_keys, total)
plain &= ~finer & ~middles.any(axis=1)
faces.append((d, s, finer, origin, middles))
tri_nodes, tet_apex, box_ref = [], [], []
for d, s, finer, origin, middles in faces:
b, c = _others(d)
# the squares: whole faces (fanned when they have middles), or their quarters
whole = np.flatnonzero(~finer)
squares = [(whole, origin[whole], unit[whole, 0], middles[whole],
self.ijk[whole][:, [b, c]])] # fmt: skip
quarter = np.flatnonzero(finer)
half = unit[quarter, 0] // 2
for qb, qc in itertools.product(range(2), repeat=2):
shift = np.zeros((len(quarter), 3), dtype=np.int64)
shift[:, b], shift[:, c] = qb * half, qc * half
index = 2 * self.ijk[quarter][:, [b, c]] + (qb, qc)
squares.append((quarter, origin[quarter] + shift, half,
np.zeros((len(quarter), 4), dtype=bool), index)) # fmt: skip
for leaves, o, u, mids, index in squares:
if not len(leaves):
continue
tri = _square_triangles(o, u, b, c, mids, index)
k = tri.shape[1]
plane = o[:, d]
on_box = np.where((plane == 0) | (plane == total[d]), 1 + 2 * d + s, 0)
keep = ~plain[leaves] | (on_box > 0) # Kuhn leaves: their box faces only
tri_nodes.append(tri[keep].reshape(-1, 3, 3))
apex = np.where(plain[leaves][:, None], -1, centres[leaves]) # no cone
tet_apex.append(np.repeat(apex[keep], k, axis=0))
box_ref.append(np.repeat(on_box[keep], k))
tri_nodes = np.concatenate(tri_nodes)
tet_apex = np.concatenate(tet_apex)
box_ref = np.concatenate(box_ref)
valid = np.all(tri_nodes[:, :, 0] >= 0, axis=1) # the empty slots of the fans
tri_nodes, tet_apex, box_ref = tri_nodes[valid], tet_apex[valid], box_ref[valid]
kuhn = self._kuhn(np.flatnonzero(plain), unit)
cone = tet_apex[:, 0] >= 0
coords = np.concatenate([tri_nodes.reshape(-1, 3), tet_apex[cone], kuhn.reshape(-1, 3)])
keys = self._node_key(coords)
_, first, inverse = np.unique(keys, return_index=True, return_inverse=True)
ints = coords[first]
nodes = self.lower + ints * (self.h / r)
for d in range(3): # the faces of the box exactly
nodes[ints[:, d] == total[d], d] = self.upper[d]
m = len(tri_nodes)
tri = inverse[: 3 * m].reshape(m, 3)
n_cone = int(cone.sum())
apex = inverse[3 * m : 3 * m + n_cone]
tets = np.concatenate([np.column_stack([tri[cone], apex]),
inverse[3 * m + n_cone :].reshape(-1, 4)]) # fmt: skip
flip = tet_volumes(nodes, tets) < 0
tets[flip] = tets[flip][:, [0, 2, 1, 3]]
boundary = box_ref > 0
tri, refs = tri[boundary], box_ref[boundary]
# outwards
axis, side = (refs - 1) // 2, (refs - 1) % 2
a, b, c = nodes[tri[:, 0]], nodes[tri[:, 1]], nodes[tri[:, 2]]
normal = np.cross(b - a, c - a)[np.arange(len(tri)), axis]
flip = (normal > 0) != (side == 1)
tri[flip] = tri[flip][:, [0, 2, 1]]
return nodes, tets, tri, refs, ints
def _middles(self, origin, unit, d, corner_keys, total) -> np.ndarray:
"""Whether the middles of the four sides of the faces (lower corners ``origin``,
sides ``unit``, normal to ``d``) are nodes (corners of finer leaves)."""
b, c = _others(d)
h = unit[:, 0] // 2
out = np.zeros((len(origin), 4), dtype=bool)
offsets = ((h, 0), (unit[:, 0], h), (h, unit[:, 0]), (0, h))
for q, (ob, oc) in enumerate(offsets):
m = origin.copy()
m[:, b] += ob
m[:, c] += oc
key = self._node_key(self._fold(m, total))
pos = np.minimum(np.searchsorted(corner_keys, key), len(corner_keys) - 1)
out[:, q] = (corner_keys[pos] == key) & (unit[:, 0] >= 4)
return out
def _kuhn(self, leaves, unit) -> np.ndarray:
"""The six tetrahedra (node coordinates, ``(6 k, 4, 3)``) of the Kuhn triangulation
of leaves: the paths along the axes from a corner to the opposite one, reflected
where the index of the leaf is odd (its faces split along the diagonals of
:func:`_square_triangles`)."""
if not len(leaves):
return np.zeros((0, 4, 3), dtype=np.int64)
odd = self.ijk[leaves] % 2 == 1
origin = self.ijk[leaves] * unit[leaves]
out = []
for perm in itertools.permutations(range(3)):
corner = np.zeros(3, dtype=np.int64)
path = [corner.copy()]
for axis in perm:
corner[axis] += 1
path.append(corner.copy())
out.append(np.stack([origin + np.where(odd, 1 - p, p) * unit[leaves] for p in path],
axis=1)) # fmt: skip
return np.concatenate(out)
def _node_key(self, coords) -> np.ndarray:
m = int((self.n.max() << (self.maxlevel + 1)) + 2)
c = np.asarray(coords, dtype=np.int64)
return (c[:, 0] * m + c[:, 1]) * m + c[:, 2]
def _fold(self, coords, total) -> np.ndarray:
return np.where(self.axes, np.mod(coords, total), coords)
def _square_triangles(origin, u, b, c, middles, index) -> np.ndarray:
"""Triangles ``(k, 8, 3, 3)`` (node coordinates; empty slots -1) of squares of lower
corners ``origin`` and sides ``u`` in the plane of the axes ``b`` and ``c``: fans from
their centres over their corners and the ``middles`` of their sides that are nodes, or
when none is, two triangles split by the diagonal of the Kuhn triangulation of the cells
on either side (through the corner of parities ``index % 2``, the indices of the square
in its plane, among the cells of its size): the same seen from both sides."""
k = len(origin)
u = np.asarray(u, dtype=np.int64)
eb = np.zeros(3, dtype=np.int64)
ec = np.zeros(3, dtype=np.int64)
eb[b], ec[c] = 1, 1
uu = u[:, None]
corners = [origin, origin + uu * eb, origin + uu * (eb + ec), origin + uu * ec]
h = uu // 2
mids = [origin + h * eb, origin + uu * eb + h * ec, origin + h * eb + uu * ec, origin + h * ec]
centre = origin + h * (eb + ec)
out = np.full((k, 8, 3, 3), -1, dtype=np.int64)
fan = middles.any(axis=1)
for q in range(4):
has = middles[:, q]
p0, p1, m = corners[q], corners[(q + 1) % 4], mids[q]
out[fan, 2 * q, 0] = centre[fan]
out[fan, 2 * q, 1] = p0[fan]
out[fan, 2 * q, 2] = np.where(has[fan, None], m[fan], p1[fan])
both = fan & has
out[both, 2 * q + 1, 0] = centre[both]
out[both, 2 * q + 1, 1] = m[both]
out[both, 2 * q + 1, 2] = p1[both]
flat = ~fan
same = (index[:, 0] % 2) == (index[:, 1] % 2) # the diagonal (0, 0)-(1, 1)
c0, c1, c2, c3 = (x[flat] for x in corners)
sm = same[flat][:, None]
out[flat, 0] = np.stack([c0, c1, np.where(sm, c2, c3)], axis=1)
out[flat, 1] = np.stack([np.where(sm, c0, c1), c2, c3], axis=1)
return out