"""Branching networks grown by space colonization: vascular trees, roots, corals.
Blood vessels, the airways of lungs, the roots and crowns of plants grow toward the
tissue or the space they serve. The space colonization algorithm (Runions, Lane and
Prusinkiewicz 2007) grows a tree toward attraction points scattered in the volume (the
cells that call for vessels, the light the crown seeks): at each step, every point
pulls the node of the tree nearest to it within the influence distance ``d_i``; each
pulled node grows a branch of length ``D`` toward the mean direction of its points, and
the points closer to the tree than the kill distance ``d_k`` are reached and removed.
The growth stops when no point is left within reach of the tree.
The radii follow Murray's law (1926): the radius of a vessel to the power ``n`` is the
sum of those of its branches, from tips of radius ``r_t``: ``n = 3`` minimizes the work
of a laminar flow and the volume of blood (Murray), ``n = 2`` keeps the cross-section
area (the pipe model of trees, da Vinci's rule). A root then has the radius ``r_t
N^(1/n)`` for the ``N`` tips it feeds. In a periodic box the tree grows on the torus.
"""
from __future__ import annotations
from dataclasses import dataclass
from typing import ClassVar
import numpy as np
from scipy.spatial import cKDTree
from morphogen._utils import check_positive
from morphogen.domain import Domain
from morphogen.models.base import Model, param, register
from morphogen.models.union import PrimitiveUnion
from morphogen.orientations import uniform_unit_vectors
from morphogen.primitives import Segments
from morphogen.seeding import SeedLike, make_rng
ROOT_POSITIONS = ("face", "center", "random")
[docs]
def murray_radii(parents: np.ndarray, tip: float, exponent: float) -> np.ndarray:
"""Radius of the segment ending at each node: ``tip`` for the tips, and Murray's law
``r^n = sum of r_child^n`` above (the parents come before their children)."""
n = len(parents)
flow = np.zeros(n)
has_child = np.zeros(n, dtype=bool)
has_child[parents[parents >= 0]] = True
flow[~has_child] = tip**exponent
for i in range(n - 1, -1, -1):
if parents[i] >= 0:
flow[parents[i]] += flow[i]
return flow ** (1.0 / exponent)
@dataclass
class _Tree:
positions: np.ndarray # nodes (unwrapped), in order of growth
parents: np.ndarray # -1 for the roots
reached: int # attraction points reached
steps: int
[docs]
@register
@dataclass(frozen=True)
class BranchingNetwork(Model):
"""Branching network grown toward ``n_attractors`` random points by space
colonization (segments of ``step``), with Murray's law for the radii."""
name = "branching"
phases: ClassVar[dict[int, str]] = {0: "tissue", 1: "vessels"}
count_label = "segments"
n_attractors: int = param(2000, doc="Attraction points in the domain", kind="int")
step: float = param(0.02, doc="Length of the branch segments", unit="length")
influence: float | None = param(
None, doc="Distance within which a point pulls the tree (default: 8 steps)", unit="length"
)
kill: float | None = param(
None, doc="Distance at which the tree reaches a point (default: 2 steps)", unit="length"
)
roots: int = param(1, doc="Number of trees", kind="int")
root_position: str = param(
"face", doc="face (on the lower face along the axis), center (one tree) or random",
kind="str",
) # fmt: skip
tip_radius: float = param(0.004, doc="Radius of the tips", unit="length")
murray_exponent: float = param(3.0, doc="Exponent n of Murray's law (3: vessels, 2: trees)")
max_steps: int = param(2000, doc="Largest number of growth steps", kind="int")
axis: int = param(2, doc="Axis of the face of the roots (0: x, 1: y, 2: z)", kind="int")
def _validate(self) -> None:
if self.n_attractors < 1:
raise ValueError("n_attractors: at least one point")
d = check_positive(self.step, "step")
if not self.kill_distance < self.influence_distance:
raise ValueError("kill: closer than the influence distance")
if self.kill_distance < 0.5 * d:
raise ValueError("kill: at least half a step (or the tree misses points)")
if self.roots < 1:
raise ValueError("roots: at least one tree")
if self.root_position not in ROOT_POSITIONS:
raise ValueError(f"root_position: one of {list(ROOT_POSITIONS)}")
if self.root_position == "center" and self.roots != 1:
raise ValueError("root_position: center grows one tree")
check_positive(self.tip_radius, "tip_radius")
if not 1.0 <= self.murray_exponent <= 4.0:
raise ValueError("murray_exponent: from 1 to 4")
if self.max_steps < 1:
raise ValueError("max_steps: at least one step")
if self.axis not in (0, 1, 2):
raise ValueError("axis: 0, 1 or 2")
@property
def influence_distance(self) -> float:
return 8.0 * self.step if self.influence is None else float(self.influence)
@property
def kill_distance(self) -> float:
return 2.0 * self.step if self.kill is None else float(self.kill)
# -- growth --------------------------------------------------------------------------
def _roots(self, rng, size: np.ndarray) -> np.ndarray:
if self.root_position == "center":
return 0.5 * size[None, :]
roots = rng.random((self.roots, 3)) * size
if self.root_position == "face":
roots[:, self.axis] = 0.0
return roots
[docs]
def grow(self, rng, size: np.ndarray, periodic: bool) -> _Tree:
"""Grow the trees in the box ``[0, size)`` (on the torus if ``periodic``)."""
box = size if periodic else None
def wrap(p):
if not periodic:
return p
w = np.mod(p, size)
w[w >= size] = 0.0
return w
def towards(points, nodes):
v = points - nodes
if periodic:
v -= size * np.round(v / size)
return v
points = rng.random((self.n_attractors, 3)) * size
positions = [self._roots(rng, size)]
parents = [np.full(len(positions[0]), -1, dtype=np.int64)]
n_nodes = len(positions[0])
alive = np.ones(len(points), dtype=bool)
d, di, dk = self.step, self.influence_distance, self.kill_distance
def reach(new): # the points close to new nodes are reached
idx = np.flatnonzero(alive)
if idx.size:
dist, _ = cKDTree(wrap(new), boxsize=box).query(
points[idx], k=1, distance_upper_bound=dk
)
alive[idx[np.isfinite(dist)]] = False
reach(positions[0])
steps = 0
for steps in range(1, self.max_steps + 1): # noqa: B007 (the count is returned)
idx = np.flatnonzero(alive)
if not idx.size:
break
pos = np.concatenate(positions)
tree = cKDTree(wrap(pos), boxsize=box)
dist, near = tree.query(points[idx], k=1, distance_upper_bound=di)
pulled = np.isfinite(dist)
if not pulled.any():
break
near = near[pulled]
v = towards(points[idx[pulled]], wrap(pos)[near])
v /= np.maximum(np.linalg.norm(v, axis=1), 1e-300)[:, None]
nodes = np.unique(near)
pull = np.zeros((len(pos), 3))
np.add.at(pull, near, v)
pull = pull[nodes]
norm = np.linalg.norm(pull, axis=1)
balanced = norm < 1e-9 # opposite pulls: a random direction
if balanced.any():
pull[balanced] = uniform_unit_vectors(rng, int(balanced.sum()))
norm[balanced] = 1.0
new = pos[nodes] + d * pull / norm[:, None]
# no node on top of another (a node pulled the same way twice)
gap, _ = tree.query(wrap(new), k=1)
fresh = gap > 0.25 * d
if not fresh.any():
break
new, nodes = new[fresh], nodes[fresh]
positions.append(new)
parents.append(nodes)
n_nodes += len(new)
reach(new)
return _Tree(
np.concatenate(positions),
np.concatenate(parents),
int((~alive).sum()),
steps,
)
[docs]
def generate(self, domain: Domain, seed: SeedLike = None) -> PrimitiveUnion:
rng, seed_info = make_rng(seed)
size = domain.lengths
tree = self.grow(rng, size, domain.periodic)
radii = murray_radii(tree.parents, self.tip_radius, self.murray_exponent)
child = np.flatnonzero(tree.parents >= 0)
start = tree.positions[tree.parents[child]]
end = tree.positions[child]
if domain.periodic: # each segment from its end inside the box
offset = np.floor(start / size) * size
start, end = start - offset, end - offset
segments = Segments(start + domain.lower, end + domain.lower, radii[child], round_caps=True)
has_child = np.zeros(len(tree.parents), dtype=bool)
has_child[tree.parents[tree.parents >= 0]] = True
roots = np.flatnonzero(tree.parents < 0)
counts = np.bincount(tree.parents[child], minlength=len(tree.parents))
summary = {
"n_tips": int((~has_child).sum()),
"n_branchings": int((counts >= 2).sum()),
"total_length": float(np.linalg.norm(end - start, axis=1).sum()),
"root_radius": float(radii[roots].max()),
"reached_fraction": tree.reached / self.n_attractors,
"growth_steps": tree.steps,
}
return PrimitiveUnion(
domain, segments=segments, model=self, seed=seed_info, metadata={"summary": summary}
)
[docs]
def expected_count(self, domain: Domain) -> float | None:
return None
[docs]
def theory(self, domain: Domain | None = None) -> dict[str, float]:
"""The radius of a root feeding ``N`` tips is ``r_t N^(1/n)``: the exponent of
Murray's law and the area ratio of a symmetric branching, ``2^(1 - 2/n)``."""
n = self.murray_exponent
return {
"murray_exponent": n,
"symmetric_area_ratio": 2.0 ** (1.0 - 2.0 / n),
"symmetric_radius_ratio": 2.0 ** (-1.0 / n),
}