Source code for acoustic_spaces.engine.early

"""Early reflections: exact specular paths with their delay, direction and band energies.

Two ways to find the candidate image sources, then one exact check:

- ``ray_traced_candidates``: deterministic specular rays from the source; every sequence
  of planes a ray hits becomes a candidate. The cost grows with the number of rays, not
  with the number of surfaces, so this suits large models (the default).
- ``exhaustive_candidates``: every sequence of planes up to the maximum order, pruned to
  images in front of the next plane. Complete, but grows as planes ** order.

``find_paths`` then traces each candidate back from the listener: the path must hit the
expected planes in order and reach the source unobstructed. Paths found are exact
whichever way they were proposed. A path through the edge where two planes meet (a
corner of a box, with the listener and source placed symmetrically) is kept once. A
path that reflects exactly at the foot of a wall standing on the surface (or in a
corner, at the foot of a wall standing in it), or on the line where such walls meet,
and goes on behind them, crosses them there as it does just to one side of the point:
of the two sides, one that agrees with the walls the legs' own intersection tests meet
and where the surfaces it reflects off go on, then the one where it crosses fewer
(past a wall's free end, none; see :func:`_crossed_here`). No path reflects off two
coincident planes (a wall drawn as one face for each room) at one point, and openings
are holes: no path reflects off one.

A path may pass straight through surfaces that let sound through (partitions, doors,
openings): its energy is then multiplied by their transmission, band by band.
"""

from __future__ import annotations

import dataclasses
import itertools
import math
from dataclasses import dataclass, field

import numpy as np

from acoustic_spaces import products
from acoustic_spaces.directivity import Directivity
from acoustic_spaces.engine.coherent import (
    ground_factors,
    reflection_phases,
    sample_frequencies,
)
from acoustic_spaces.engine.model import (
    MAX_CROSSINGS,
    PLANE_TOLERANCE,
    TraceModel,
    source_weights,
)
from acoustic_spaces.engine.turbulence import Wander

#: Distance (metres) below which a point counts as lying on a plane.
_ON_PLANE = 1e-9
#: Tolerance, relative to the model size, within which a point lies in a plane (a mesh's
#: faces need not lie in theirs to rounding): for a path reflecting where planes meet.
_EDGE_TOLERANCE = 1e-7
#: A ray traced on the CPU meets no face nearer its start than this share of the diagonal
#: of the model's box (``Bvh::min_distance``).
_RAY_START = 1e-9
#: Upper bound on candidates for the exhaustive search.
MAX_CANDIDATES = 2_000_000


def ray_start(mesh) -> float:
    """Distance (metres) from its start within which a ray traced on the CPU meets no
    face of ``mesh`` (:data:`_RAY_START` of the diagonal of its box,
    ``TraceModel.bvh.min_distance``): the path traced back from a listener misses a
    reflection whose last leg is shorter, and the rays of a source nearer a surface go
    through it."""
    return _RAY_START * math.hypot(*np.ptp(mesh.vertices, axis=0).tolist())


[docs] @dataclass class EarlyReflections: """Paths from one source to one listener: specular (order 0 is the direct sound), and diffracted at an edge when edge diffraction is on.""" order: np.ndarray # (n,) reflections along the path delay_s: np.ndarray # (n,) distance_m: np.ndarray # (n,) direction: np.ndarray # (n, 3) unit vectors from the listener towards the arrival energy: np.ndarray # (n, bands) time-integrated intensity, unit-energy source points: list[np.ndarray] = field(default_factory=list) # every corner, source first faces: list[np.ndarray] = field(default_factory=list) # faces hit, source side first #: (n,) the edge a path bends over (an index of the model's diffracting edges, see #: :func:`~acoustic_spaces.engine.diffraction.find_edges`), -1 for specular paths, #: -2 for a path over the crests of the terrain #: (:mod:`~acoustic_spaces.engine.crests`), or -3 for the path that carries the #: sound of the solver for whole rows (:mod:`~acoustic_spaces.engine.row_paths`). edge: np.ndarray | None = None #: (n,) how many surfaces that let sound through a path passes, openings aside. crossings: np.ndarray | None = None #: (n, C, M) in the lowest C bands, where the paths add in pressure (see #: :mod:`~acoustic_spaces.engine.coherent`): each path's pressure at M frequencies #: in each band (:func:`~acoustic_spaces.engine.coherent.sample_frequencies`), #: relative to its delay and to its level in the band, which its energy gives (the #: mean of its squared magnitude over a band's frequencies is 1). None when the #: paths add in energy in every band. spectrum: np.ndarray | None = None #: (n,) which of the uncorrelated points of a line or surface source each path comes #: from (outdoors, where those paths carry a spectrum): in the coherent bands the #: paths of one point add in pressure, those of different points in energy. point: np.ndarray | None = None #: Outdoors in turbulence, how the eddies delay the paths at random #: (:class:`~acoustic_spaces.engine.turbulence.Wander`): on average two paths' #: pressures add with their coherence factor. None without turbulence, and at a #: moment of it (:meth:`frozen`). wander: Wander | None = None #: (n, bands) at a moment of turbulence, each path's delay (s) in each band beyond #: ``delay_s``, its delay in the highest band (the eddies part paths near the #: ground less at low frequencies); None otherwise. lag: np.ndarray | None = None #: Where the paths carry a :attr:`spectrum`: for each path, the cosine of the angle #: at which it meets the face of each of its reflections (as :attr:`faces`), whose #: phase its spectrum takes from that face's absorption #: (:func:`~acoustic_spaces.engine.coherent.reflection_phases`), so that re-weighting #: for other absorption can turn it (:func:`~acoustic_spaces.engine.reweight. #: turned_paths`); NaN for a reflection whose phase comes from elsewhere (a ground's #: impedance). Empty without a spectrum. cosines: list[np.ndarray] = field(default_factory=list) #: (n,) in the bands above the coherent ones, the phase factor a rendered response #: gives each path beyond the one held from those bands #: (:func:`~acoustic_spaces.engine.coherent.with_own_phases`); None outside one. own_phase: np.ndarray | None = None #: (n, C, K) where a path carries the field the parabolic equation gives over the open #: ground (outdoors in wind or temperature gradients, out of the shadow): in each #: coherent band its pressure, unnormalised, relative to its delay, at the frequencies #: of the layout (:func:`~acoustic_spaces.engine.fine.fine_frequencies`) the equation #: ran at there (in the lowest band down to an octave below it, in its top band #: through the upper crossover too where a response is rendered or the band filters #: read it); NaN where a path has none. Its band's shape is drawn from these and #: its neighbours' (:func:`~acoustic_spaces.engine.coherent.shaped`); its level stays #: the one its energy gives. None when no path carries one. fine: np.ndarray | None = None #: (n,) the delay (s) past :attr:`delay_s` whose phase :attr:`fine`'s samples follow #: on average (:func:`~acoustic_spaces.engine.fine.reference_delay`), relative to #: which they are interpolated; 0 for paths without them. None with :attr:`fine`. fine_delay: np.ndarray | None = None def __post_init__(self) -> None: if self.edge is None: self.edge = np.full(len(self.order), -1, dtype=np.int64) if self.crossings is None: self.crossings = np.zeros(len(self.order), dtype=np.int64) if self.point is None: self.point = np.zeros(len(self.order), dtype=np.int64) def __len__(self) -> int: return len(self.order) def __getitem__(self, index) -> EarlyReflections: """The paths ``index`` picks (a slice, indices or a boolean mask).""" rows = np.arange(len(self))[index] return EarlyReflections( order=self.order[rows], delay_s=self.delay_s[rows], distance_m=self.distance_m[rows], direction=self.direction[rows], energy=self.energy[rows], points=[self.points[i] for i in rows] if self.points else [], faces=[self.faces[i] for i in rows] if self.faces else [], edge=self.edge[rows], crossings=self.crossings[rows], spectrum=None if self.spectrum is None else self.spectrum[rows], point=self.point[rows], wander=None if self.wander is None else self.wander[rows], lag=None if self.lag is None else self.lag[rows], cosines=[self.cosines[i] for i in rows] if self.cosines else [], own_phase=None if self.own_phase is None else self.own_phase[rows], fine=None if self.fine is None else self.fine[rows], fine_delay=None if self.fine_delay is None else self.fine_delay[rows], ) @property def coherent_bands(self) -> int: """How many of the lowest bands the paths add in pressure in.""" return 0 if self.spectrum is None else self.spectrum.shape[1]
[docs] def frozen(self, seed: int) -> EarlyReflections: """The paths at a moment of the turbulent air drawn with ``seed``: each delayed in each band as the eddies have it then, adding in pressure (the same paths without turbulence).""" if self.wander is None: return self roots = self.wander_roots() return self.at_moment(roots, _draws(roots, seed))
[docs] def wander_roots(self) -> list: """How the eddies delay the paths, band by band, as :meth:`~acoustic_spaces.engine.turbulence.Wander.roots` (empty without turbulence).""" if self.wander is None: return [] from acoustic_spaces.materials.bands import band_centres, resolution_of centres = band_centres(resolution_of(self.energy.shape[1])) return self.wander.roots(centres, self.point)
[docs] def at_moment(self, roots: list, draws: list[np.ndarray]) -> EarlyReflections: """The paths delayed as :meth:`~acoustic_spaces.engine.turbulence.Wander.delays` has it for the normal variables ``draws`` (one array per group of ``roots``, :meth:`wander_roots`).""" if self.wander is None: return self # No path arrives before it leaves the source, however the eddies draw. delays = np.maximum(self.delay_s[:, None] + Wander.delays(roots, draws, len(self)), 0.0) return dataclasses.replace( self, delay_s=delays[:, -1], wander=None, lag=delays - delays[:, -1:], )
@property def diffracted(self) -> np.ndarray: """(n,) True for paths that bend over an edge or the terrain's crests, and for the one that carries the sound of the solver for whole rows.""" return self.edge != -1 @classmethod def empty(cls, bands: int) -> EarlyReflections: return cls( order=np.zeros(0, dtype=np.int64), delay_s=np.zeros(0), distance_m=np.zeros(0), direction=np.zeros((0, 3)), energy=np.zeros((0, bands)), ) @classmethod def concatenate(cls, parts: list[EarlyReflections], bands: int) -> EarlyReflections: parts = [p for p in parts if len(p)] if not parts: return cls.empty(bands) shaped = [p.spectrum for p in parts if p.spectrum is not None] spectrum = None if shaped: # Paths without a spectrum have no phase of their own. spectrum = np.concatenate( [ np.ones((len(p), *shaped[0].shape[1:]), dtype=complex) if p.spectrum is None else p.spectrum for p in parts ] ) out = cls( order=np.concatenate([p.order for p in parts]), delay_s=np.concatenate([p.delay_s for p in parts]), distance_m=np.concatenate([p.distance_m for p in parts]), direction=np.concatenate([p.direction for p in parts]), energy=np.concatenate([p.energy for p in parts]), points=[x for p in parts for x in p.points], faces=[x for p in parts for x in p.faces], edge=np.concatenate([p.edge for p in parts]), crossings=np.concatenate([p.crossings for p in parts]), spectrum=spectrum, point=np.concatenate([p.point for p in parts]), wander=Wander.stacked([p.wander for p in parts], [len(p) for p in parts]), lag=_lags(parts, bands), cosines=_cosines(parts), fine=_fines(parts), fine_delay=_fine_delays(parts), ) return out.sorted()
[docs] def sorted(self) -> EarlyReflections: """The same paths in order of arrival.""" return self[np.argsort(self.delay_s, kind="stable")]
def _cosines(parts: list[EarlyReflections]) -> list[np.ndarray]: """The parts' :attr:`~EarlyReflections.cosines` one after the other (NaN for the reflections of paths without them); empty when no part has them.""" if all(not p.cosines for p in parts): return [] out = [] for p in parts: if p.cosines: out.extend(p.cosines) elif p.faces: out.extend(np.full(len(f), np.nan) for f in p.faces) else: out.extend(np.zeros(0) for _ in range(len(p))) return out def _fines(parts: list[EarlyReflections]) -> np.ndarray | None: """The parts' :attr:`~EarlyReflections.fine` one above the other (NaN for paths without one); None when no part has one.""" fines = [p.fine for p in parts if p.fine is not None] if not fines: return None shape = fines[0].shape[1:] return np.concatenate( [ np.full((len(p), *shape), np.nan, dtype=complex) if p.fine is None else p.fine for p in parts ] ) def _fine_delays(parts: list[EarlyReflections]) -> np.ndarray | None: """The parts' :attr:`~EarlyReflections.fine_delay` one after the other (zero for paths without one); None when no part has one.""" if all(p.fine_delay is None for p in parts): return None return np.concatenate( [np.zeros(len(p)) if p.fine_delay is None else p.fine_delay for p in parts] ) def _lags(parts: list[EarlyReflections], bands: int) -> np.ndarray | None: """The parts' :attr:`~EarlyReflections.lag` one above the other (zero for paths without one); None when no part has one.""" if all(p.lag is None for p in parts): return None return np.concatenate([np.zeros((len(p), bands)) if p.lag is None else p.lag for p in parts]) def _draws(roots: list, seed: int) -> list[np.ndarray]: """Normal variables for each group of ``roots`` (see :meth:`EarlyReflections.at_moment`), drawn with ``seed``.""" rng = np.random.default_rng(seed) return [rng.standard_normal(len(rows)) for rows, _ in roots] def ray_traced_candidates( model: TraceModel, source: np.ndarray, max_order: int, rays: int, threads: int = 0 ) -> list[np.ndarray]: """Plane sequences hit by ``rays`` specular rays, which pass through surfaces that let sound through (forking where those also reflect); entry k-1 has shape (n, k).""" from acoustic_spaces import _native if max_order <= 0: return [] passing = np.zeros(0, dtype=np.uint8) if model.transmission is not None: # 0: reflects, 1: reflects and lets sound through, 2: lets it through only. through = np.any(model.transmission > 0.0, axis=1) passing = np.where(model.partition, 1, np.where(through, 2, 0)).astype(np.uint8) faces = _native.specular_sequences( model.bvh, np.asarray(source, dtype=np.float64), int(rays), int(max_order), int(threads), passing, ) planes = np.where(faces >= 0, model.face_plane[np.maximum(faces, 0)], -1) out = [] for k in range(1, max_order + 1): prefix = planes[:, :k] prefix = prefix[np.all(prefix >= 0, axis=1)] out.append( _distinct_rows(prefix, model.plane_count) if len(prefix) else np.zeros((0, k), np.int64) ) return out def _distinct_rows(rows: np.ndarray, base: int) -> np.ndarray: """The distinct rows of ``rows`` (n, k), whole numbers from 0 to ``base`` - 1, in ascending order: what ``np.unique(rows, axis=0)`` gives, through one number per row (each row read as a number in base ``base``) where those fit in 64 bits.""" k = rows.shape[1] if base**k > np.iinfo(np.int64).max: return np.unique(rows, axis=0) key = rows[:, 0].astype(np.int64) for column in range(1, k): key = key * base + rows[:, column] key = np.unique(key) out = np.empty((len(key), k), dtype=rows.dtype) for column in range(k - 1, -1, -1): key, out[:, column] = np.divmod(key, base) return out def exhaustive_candidates( model: TraceModel, source: np.ndarray, max_order: int, limit: int = MAX_CANDIDATES ) -> list[np.ndarray]: """Every plane sequence whose images stay in front of the next plane (outdoors, not the planes of the open sky, which reflects nothing).""" normals, offsets = model.plane_normal, model.plane_offset sky = None if model.sky is not None: sky = np.ones(model.plane_count, dtype=bool) np.logical_and.at(sky, model.face_plane, model.sky) seqs = np.zeros((1, 0), dtype=np.int64) images = np.asarray(source, dtype=np.float64)[None, :] out = [] total = 0 for _ in range(max_order): # Starting from empty arrays keeps one (0, k) entry for an order with no sequence # left (a single reflecting plane leaves none from the second order on). new_seqs = [np.zeros((0, seqs.shape[1] + 1), dtype=np.int64)] new_images = [np.zeros((0, 3))] chunk = max(1, 4_000_000 // max(1, model.plane_count)) for start in range(0, len(seqs), chunk): s, img = seqs[start : start + chunk], images[start : start + chunk] distance = products.product(img, normals.T) - offsets # (n, planes) ok = model.in_front(distance, _ON_PLANE) if s.shape[1]: ok[np.arange(len(s)), s[:, -1]] = False if sky is not None: ok[:, sky] = False rows, cols = np.nonzero(ok) new_seqs.append(np.column_stack([s[rows], cols])) new_images.append(model.mirror(img[rows], cols)) seqs = np.concatenate(new_seqs).astype(np.int64) images = np.concatenate(new_images) total += len(seqs) if total > limit: raise ValueError( f"more than {limit} image sources up to order {len(out) + 1}; lower " "max_order or use the ray_tracing early method" ) out.append(seqs) return out def _perpendicular(model, a: np.ndarray, b: np.ndarray) -> np.ndarray: """Whether the planes ``a`` and ``b`` are perpendicular: reflections off them commute.""" dot = np.einsum("ij,ij->i", model.plane_normal[a], model.plane_normal[b]) return np.abs(dot) < 1e-9 def _image_points( model: TraceModel, seqs: np.ndarray, chain: list, source, listener, tolerance: float ) -> tuple[np.ndarray, np.ndarray]: """(n, k + 2, 3) the points of the paths from ``source`` to ``listener`` off the plane sequences ``seqs`` (n, k) as the image method places them, back from the listener towards each of the source's images ``chain[j]`` (off the first j planes) in turn, and (n,) whether each such path can be: it meets every plane from the front (farther than ``tolerance`` from it), crossing it on the way to its image, but in the corner of two perpendicular planes, where it reflects off both at one point. Where a path cannot be, its points are not its.""" n, k = seqs.shape points = np.empty((n, k + 2, 3)) points[:, 0], points[:, k + 1] = source, listener possible = np.ones(n, dtype=bool) current = np.broadcast_to(listener, (n, 3)).copy() for j in range(k, 0, -1): plane = seqs[:, j - 1] normal = model.plane_normal[plane] near = np.einsum("ij,ij->i", normal, current) - model.plane_offset[plane] far = np.einsum("ij,ij->i", normal, chain[j]) - model.plane_offset[plane] two_sided = model.plane_two_sided[plane] front = np.where(two_sided, np.abs(near) > tolerance, near > tolerance) # In the corner where it meets the plane of the next reflection, perpendicular # to it, the path reflects off both at one point. corner = np.zeros(n, dtype=bool) if j < k: behind = np.where(two_sided, np.abs(far) > tolerance, far < -tolerance) corner = (np.abs(near) <= tolerance) & behind & _perpendicular(model, plane, seqs[:, j]) possible &= (front & (near * far < 0.0)) | corner t = near / np.where(possible, near - far, 1.0) current = current + t[:, None] * (chain[j] - current) points[:, j] = current return points, possible def _height_over_plane(model: TraceModel, points: np.ndarray, planes: np.ndarray) -> np.ndarray: """The distance (m) of ``points`` (..., 3) from the planes ``planes`` (...), the two broadcast together, negative behind a plane (against its normal).""" normals = model.plane_normal[planes] return np.einsum("...k,...k->...", points, normals) - model.plane_offset[planes] def _height_over_face(model: TraceModel, points: np.ndarray, faces: np.ndarray) -> np.ndarray: """The distance (m) of ``points`` (..., 3) from the planes the faces ``faces`` (...) themselves lie in (:attr:`TraceModel.face_planes`), the two broadcast together, negative behind one (against its plane's normal).""" normal, offset = model.face_planes return np.einsum("...k,...k->...", points, normal[faces]) - offset[faces] def _cross(u: np.ndarray, v: np.ndarray) -> np.ndarray: """``np.cross`` of 3-vectors (..., 3), without its overhead.""" u0, u1, u2 = u[..., 0], u[..., 1], u[..., 2] v0, v1, v2 = v[..., 0], v[..., 1], v[..., 2] return np.stack([u1 * v2 - u2 * v1, u2 * v0 - u0 * v2, u0 * v1 - u1 * v0], axis=-1) def _over(model: TraceModel, faces: np.ndarray, points: np.ndarray) -> np.ndarray: """Whether each of ``points`` (p, 3) projected onto the face of ``faces`` (p,) beside it lies on it (p,), its edges included: on the triangle, or no farther from it than the least distance at which a ray meets a face (``model.bvh.min_distance``, a billionth of the model's diagonal). The model's tolerance for planes is no room past an edge: a face a path meets where it ends is another one's, however near its plane.""" mesh = model.room.mesh tri = mesh.vertices[mesh.faces[faces]] a, b, c = tri[:, 0], tri[:, 1], tri[:, 2] n = _cross(b - a, c - a) area2 = np.einsum("ij,ij->i", n, n) # Barycentric coordinates of the points projected onto the triangles. w_a = np.einsum("ij,ij->i", _cross(c - b, points - b), n) / area2 w_b = np.einsum("ij,ij->i", _cross(a - c, points - c), n) / area2 w_c = 1.0 - w_a - w_b # Beside the triangle: how far the projected point lies from the nearest side. at = w_a[:, None] * a + w_b[:, None] * b + w_c[:, None] * c beside = np.full(len(at), np.inf) for p, q in ((a, b), (b, c), (c, a)): side = q - p along = np.einsum("ij,ij->i", at - p, side) / np.maximum( np.einsum("ij,ij->i", side, side), 1e-300 ) gap = at - p - np.clip(along, 0.0, 1.0)[:, None] * side beside = np.minimum(beside, np.linalg.norm(gap, axis=1)) return ((w_a >= 0.0) & (w_b >= 0.0) & (w_c >= 0.0)) | (beside <= model.bvh.min_distance) def _faces_at( model: TraceModel, plane: int, point: np.ndarray, tolerance: float, own: bool = True ) -> np.ndarray: """The faces of ``plane`` that ``point`` lies on (edges included, :func:`_over`), in ascending order: it lies within ``tolerance`` of the plane or, with ``own``, of the face's own plane (see :attr:`TraceModel.face_planes`). Openings are holes: no point lies on one.""" height = abs(model.plane_normal[plane] @ point - model.plane_offset[plane]) if height > tolerance + (2.0 * model.plane_spread[plane] if own else 0.0): return np.empty(0, dtype=np.int64) candidates = np.flatnonzero((model.face_plane == plane) & ~model.transparent) if height > tolerance: # off the plane, but maybe on a face that is not in it normal, offset = model.face_planes near = np.abs(normal[candidates] @ point - offset[candidates]) <= tolerance candidates = candidates[near] if len(candidates) == 0: return candidates at = np.broadcast_to(point, (len(candidates), 3)) return candidates[_over(model, candidates, at)] def _face_at( model: TraceModel, plane: int, point: np.ndarray, tolerance: float, own: bool = True ) -> int: """The first of the faces of ``plane`` that ``point`` lies on (:func:`_faces_at`), or -1.""" faces = _faces_at(model, plane, point, tolerance, own) return int(faces[0]) if len(faces) else -1 def _goes_on( model: TraceModel, plane: int, point: np.ndarray, way: np.ndarray, tolerance: float ) -> bool: """Whether a face of ``plane`` that ``point`` lies on (:func:`_faces_at`) goes on from it along ``way`` (in the plane, of any length): ``way`` leaves the face across none of its edges that the point lies within ``tolerance`` of, or beyond (a way along an edge, to the plane tolerance, stays on the face). With no way (zero) a face the point lies on is enough.""" faces = _faces_at(model, plane, point, tolerance) if len(faces) == 0: return False mesh = model.room.mesh corner = mesh.vertices[mesh.faces[faces]] # (f, 3, 3) side = np.roll(corner, -1, axis=1) - corner # each edge, from its first corner side /= np.maximum(np.linalg.norm(side, axis=2, keepdims=True), 1e-300) inward = np.roll(corner, -2, axis=1) - corner # to the corner across the edge inward -= np.einsum("fej,fej->fe", inward, side)[..., None] * side inward /= np.maximum(np.linalg.norm(inward, axis=2, keepdims=True), 1e-300) depth = np.einsum("fej,fej->fe", point - corner, inward) out = np.einsum("fej,j->fe", inward, way) < -PLANE_TOLERANCE * np.linalg.norm(way, axis=0) return bool(np.any(~np.any((depth <= tolerance) & out, axis=1))) #: Points looked up at once in a plane's grid of faces (:func:`_faces_under`). _CHUNK = 1024 #: A face whose box covers more cells of its plane's grid than this is tried for every #: point (:func:`_face_grid`). _GRID_CELLS = 64 def _face_grid(model: TraceModel, plane: int, tolerance: float): """The faces of ``plane`` binned for :func:`_faces_under` (worked out once for each plane and ``tolerance``, in :attr:`TraceModel.face_grids`): each face's box, grown by more than the room :func:`_over` leaves round its edges (the intersection test's least distance, no more than ``tolerance``: the triangle scaled about its centroid by 1 + 3 ``tolerance`` / its least height holds it, and that moves no corner farther along an axis than 3 ``tolerance`` / least height times the box's largest side) and by ``tolerance`` and twice the plane's spread, then doubled and added the model's rounding (:attr:`TraceModel.height_error`); and a grid of square cells across the two axes the plane faces least, listing the faces whose boxes overlap each (those that overlap more than :data:`_GRID_CELLS` of them, or with no finite box, listed apart, for every point).""" key = (int(plane), float(tolerance)) grid = model.face_grids.get(key) if grid is not None: return grid faces = np.flatnonzero(model.face_plane == plane) mesh = model.room.mesh tri = mesh.vertices[mesh.faces[faces]] a, b, c = tri[:, 0], tri[:, 1], tri[:, 2] n = _cross(b - a, c - a) longest = np.linalg.norm(np.stack([b - a, c - b, a - c]), axis=2).max(axis=0) least = np.sqrt(np.einsum("ij,ij->i", n, n)) / np.maximum(longest, 1e-300) low, high = tri.min(axis=1), tri.max(axis=1) with np.errstate(divide="ignore", invalid="ignore"): grow = 3.0 * tolerance / least * (high - low).max(axis=1) grow = np.where(np.isfinite(grow), grow, np.inf) grow = 2.0 * (grow + tolerance + 2.0 * model.plane_spread[plane]) + model.height_error low, high = low - grow[:, None], high + grow[:, None] axes = np.delete(np.arange(3), np.argmax(np.abs(model.plane_normal[plane]))) finite = np.isfinite(grow) start, cell, shape = np.zeros(2), 1.0, (0, 0) first = np.zeros(2, dtype=np.int64) listed = np.zeros(0, dtype=np.int64) apart = np.flatnonzero(~finite) if finite.any(): start = low[finite][:, axes].min(axis=0) span = high[finite][:, axes].max(axis=0) - start size = (high - low)[finite][:, axes].max(axis=1) cell = max( float(np.median(size)), float(np.sqrt(span[0] * span[1] / (4 * np.count_nonzero(finite)))), float(np.finfo(float).tiny), ) shape = tuple(int(x) for x in np.maximum(np.ceil(span / cell), 1)) lo = np.clip(np.floor((low[:, axes] - start) / cell), 0, np.array(shape) - 1) hi = np.clip(np.floor((high[:, axes] - start) / cell), 0, np.array(shape) - 1) lo = np.where(finite[:, None], lo, 0).astype(np.int64) count = np.where(finite[:, None], hi, 0).astype(np.int64) - lo + 1 cells = count.prod(axis=1) binned = finite & (cells <= _GRID_CELLS) apart = np.flatnonzero(~binned) which = np.flatnonzero(binned) each = np.repeat(which, cells[which]) step = np.arange(len(each)) - np.repeat( np.cumsum(cells[which]) - cells[which], cells[which] ) at = (lo[each, 0] + step // count[each, 1]) * shape[1] + lo[each, 1] + step % count[each, 1] order = np.argsort(at, kind="stable") listed = each[order] first = np.searchsorted(at[order], np.arange(shape[0] * shape[1] + 1)) grid = (faces, low, high, axes, start, cell, shape, first, listed, apart) model.face_grids[key] = grid return grid def _faces_under(model: TraceModel, plane: int, points: np.ndarray, tolerance: float): """Pairs of the ``points`` (m, 3) and faces of ``plane``, as (p,) rows of ``points`` and (p,) faces, among which are all those where a point projected onto the face lies on it (edges included, :func:`_over`), within ``tolerance`` and twice the plane's spread of the face's own plane: those whose grown boxes hold the point (see :func:`_face_grid`; ``tolerance`` is no less than the intersection test's least distance).""" faces, low, high, axes, start, cell, shape, first, listed, apart = _face_grid( model, plane, tolerance ) m = len(points) index = np.floor((points[:, axes] - start) / cell) inside = np.all((index >= 0) & (index < np.array(shape)), axis=1) at = np.where(inside, index[:, 0] * shape[1] + index[:, 1], 0).astype(np.int64) count = np.where(inside, first[at + 1] - first[at], 0) rows = np.repeat(np.arange(m), count) step = np.arange(len(rows)) - np.repeat(np.cumsum(count) - count, count) local = listed[np.repeat(first[at], count) + step] if len(apart): rows = np.concatenate([rows, np.repeat(np.arange(m), len(apart))]) local = np.concatenate([local, np.tile(apart, m)]) held = np.all((low[local] <= points[rows]) & (points[rows] <= high[local]), axis=1) return rows[held], faces[local[held]] def _height_near(model: TraceModel, points, planes, tolerance: float) -> np.ndarray: """The distance (m) of ``points`` (..., 3) from the planes ``planes`` (...), the two broadcast together, as :func:`_height_over_plane` gives it; but where a plane's faces do not all lie in it (:attr:`TraceModel.plane_spread`) and the point lies within ``tolerance`` and twice that spread of it, the one of least size of that and the point's distances from the own planes (:attr:`TraceModel.face_planes`) of the plane's faces it lies over (edges included, :func:`_over`; of equal ones the first face's): a point on any face of the plane lies on it, and its side is taken from the faces there.""" height = _height_over_plane(model, points, planes) spread = model.plane_spread[planes] near = np.nonzero((spread > 0.0) & (np.abs(height) <= tolerance + 2.0 * spread)) if len(near[0]) == 0: return height points = np.broadcast_to(points, (*height.shape, 3))[near] planes = np.broadcast_to(planes, height.shape)[near] merged = height[near] normal, offset = model.face_planes for plane in np.unique(planes): on = np.flatnonzero(planes == plane) for part in np.array_split(on, -(-len(on) // _CHUNK)): rows, faces = _faces_under(model, plane, points[part], tolerance) at = points[part][rows] own = np.einsum("ij,ij->i", at, normal[faces]) - offset[faces] over = _over(model, faces, at) rows, faces, own = rows[over], faces[over], own[over] order = np.lexsort((faces, np.abs(own), rows)) rows, own = rows[order], own[order] least = np.flatnonzero(np.diff(rows, prepend=-1) != 0) rows, own = part[rows[least]], own[least] closer = np.abs(own) < np.abs(merged[rows]) height[tuple(i[rows[closer]] for i in near)] = own[closer] return height def find_paths( model: TraceModel, source: np.ndarray, listener: np.ndarray, candidates: list[np.ndarray], *, speed_of_sound: float, air: np.ndarray, max_delay_s: float, directivity: Directivity | None = None, orientation: np.ndarray | None = None, coherent: int = 0, max_partitions: int | None = None, ) -> EarlyReflections: """Validate candidate plane sequences for one listener; add the direct sound. Each path's energy is weighted by the source's ``directivity`` (default: omni) in the direction it leaves the source; ``orientation`` has the source's forward, left and up axes as columns. In the lowest ``coherent`` bands each path also carries the phase of its reflections (:mod:`~acoustic_spaces.engine.coherent`). With ``max_partitions``, a reflected path that passes through more partitions (:attr:`TraceModel.partition`) is left out, as the stochastic late tracer leaves it to the late part (ray-traced candidates find no such path but where planes are shared, as the floor of rooms in a row). """ source = np.asarray(source, dtype=np.float64) listener = np.asarray(listener, dtype=np.float64) bands = model.absorption.shape[1] tolerance = _EDGE_TOLERANCE * float(np.ptp(model.room.mesh.vertices, axis=0).max()) counted = np.column_stack([~model.transparent, model.partition]) parts = [] direct = np.zeros((1, 0), dtype=np.int64) for seqs in [direct, *candidates]: if len(seqs) == 0: continue k = seqs.shape[1] # Image chain: level j is the source mirrored across the first j planes. chain = [np.broadcast_to(source, (len(seqs), 3)).copy()] for j in range(k): chain.append(model.mirror(chain[-1], seqs[:, j])) distance = np.linalg.norm(chain[-1] - listener, axis=1) keep = distance / speed_of_sound <= max_delay_s seqs, chain, distance = seqs[keep], [c[keep] for c in chain], distance[keep] n = len(seqs) if n == 0: continue # Trace back from the listener towards each image in turn. current = np.broadcast_to(listener, (n, 3)).copy() valid = np.ones(n, dtype=bool) faces = np.full((n, k), -1, dtype=np.int64) points = [None] * (k + 1) points[k] = current.copy() ignore = np.full(n, -1, dtype=np.int64) through = np.ones((n, bands)) # Per path: the faces crossed that are not openings, and the partitions. crossings = np.zeros((n, 2), dtype=np.int64) # The reflections at the current point (from reflection ``first`` on, more than # one in a corner) and the point the path came to them from. before = current.copy() first = np.full(n, k - 1, dtype=np.int64) for j in range(k - 1, -1, -1): plane = seqs[:, j] # A reflection point on an edge already lies on the next plane's face too: the # path reflects off both at the same point (a corner), so there is nothing to # trace. One in that plane off its faces is no corner: the path goes on to it. # Nor is one beside the plane (farther than the least distance at which a ray # meets a face) from which the path does not go on to a face of it: on the # side of the image it heads for, or meeting the plane past its faces. at = np.full(n, -1, dtype=np.int64) if j < k - 1: near = np.flatnonzero(valid) height = _height_near(model, current[near], plane[near], tolerance) there = _height_over_plane(model, chain[j + 1][near], plane[near]) beside = np.abs(height) > model.bvh.min_distance held = (np.abs(height) <= tolerance) & (~beside | (height * there < 0.0)) for i, h, t, far in zip( near[held], height[held], there[held], beside[held], strict=True ): if far: crossing = current[i] + h / (h - t) * (chain[j + 1][i] - current[i]) if _face_at(model, plane[i], crossing, tolerance) < 0: continue at[i] = _face_at(model, plane[i], current[i], tolerance) corner = at >= 0 trace = valid & ~corner start = current delta = chain[j + 1] - current length = np.linalg.norm(delta, axis=1) direction = delta / np.maximum(length, 1e-300)[:, None] face, current, share, crossed = _towards_plane( model, current, direction, length, ignore, plane, trace, tolerance, counted ) through *= share crossings += crossed hit = face >= 0 if j < k - 1: # The path leaves the reflections at ``start`` for this plane. rows = np.flatnonzero(trace & hit) planes = np.where(np.arange(j + 1, k) <= first[rows, None], seqs[rows, j + 1 :], -1) turns, share, crossed = _turn( model, planes, faces[rows, j + 1 :], before[rows], start[rows], current[rows], tolerance, counted, ) valid[rows] &= turns through[rows] *= share crossings[rows] += crossed before[trace], first[trace] = start[trace], j valid &= hit | corner face[corner] = at[corner] faces[:, j] = face points[j] = current.copy() ignore = face delta = source - current length = np.linalg.norm(delta, axis=1) direction = delta / np.maximum(length, 1e-300)[:, None] share, crossed = model.passes( current, direction, length * (1.0 - 1e-9), ignore, counted=counted ) through *= share crossings += crossed if k: # The path leaves the last reflections for the source. rows = np.flatnonzero(valid & np.any(through > 0.0, axis=1)) planes = np.where(np.arange(k) <= first[rows, None], seqs[rows], -1) ends = np.broadcast_to(source, (len(rows), 3)) turns, share, crossed = _turn( model, planes, faces[rows], before[rows], current[rows], ends, tolerance, counted ) valid[rows] &= turns through[rows] *= share crossings[rows] += crossed valid &= np.any(through > 0.0, axis=1) if max_partitions is not None and k > 0: valid &= crossings[:, 1] <= max_partitions if not valid.any(): continue idx = np.flatnonzero(valid) # Plane sequences that commute (perpendicular planes) make the same mirror off # the same surfaces: one path. Other mirrors' images of a source near where their # planes meet lie as near each other, and are paths of their own; so are paths # off other surfaces that make the same mirror (in two rooms as deep either side # of a partition: off the partition and one room's end wall, or the other's). # Two paths with one mirror off the same surfaces in another order still count # as one (from the fourth order on in such rooms). key = np.hstack( [_mirrors(model, seqs[idx], tolerance), _surfaces(model, seqs[idx], tolerance)] ) _, unique = np.unique(key, axis=0, return_index=True) idx = idx[np.sort(unique)] found_points, found_faces = [p[idx] for p in points], faces[idx] _apart( model, seqs[idx], found_points, found_faces, crossings[idx], source, listener, tolerance, counted, ) parts.append( assemble_paths( model, source, listener, found_points, found_faces, distance[idx], through[idx], crossings[idx, 0], speed_of_sound=speed_of_sound, air=air, directivity=directivity, orientation=orientation, coherent=coherent, ) ) found = EarlyReflections.concatenate(parts, bands) if model.room.outdoor is not None and model.room.outdoor.terrain is not None: from acoustic_spaces.engine.terrain import terrain_paths found = terrain_paths( model, found, source, listener, speed_of_sound=speed_of_sound, air=air, max_delay_s=max_delay_s, directivity=directivity, orientation=orientation, coherent=coherent, ) return found def _apart( model: TraceModel, seqs, points: list, faces, crossings, source, listener, tolerance, counted ) -> None: """The paths off the plane sequences ``seqs`` (n, k) through ``points`` (k + 1 arrays of (n, 3), the listener last) and ``faces`` (n, k), as :func:`find_paths` has found them, where they reflect off two planes at one point that the search joined into a corner (a reflection point within ``tolerance``, the model's tolerance for planes, of the next plane) and the image method places that path's points apart (farther than the intersection test's least distance, or the rounding of the coordinates where that is larger): in place, those points, in the order of the planes or in another that gives the same image (one that swaps only perpendicular planes), and the faces they lie on, where that path can be, each point lies on a face of its plane and its legs cross the faces the path's ``crossings`` (n, 2) count (of ``counted``, as :func:`find_paths` counts them), nothing solid. The corner lies up to the tolerance from where the path meets each plane; the share of sound the path lets through stays the corner's.""" n, k = faces.shape if k < 2 or n == 0: return joined = np.zeros(n, dtype=bool) for j in range(k - 1): joined |= np.all(points[j] == points[j + 1], axis=1) if not joined.any(): return least = max(model.bvh.min_distance, model.height_error) orders = [(o, np.argsort(o)) for o in itertools.permutations(range(k))] for i in np.flatnonzero(joined): seq = seqs[i] for order, where in orders: swapped = [(a, b) for a in range(k) for b in range(a + 1, k) if where[a] > where[b]] if not all(_perpendicular(model, seq[[a]], seq[[b]])[0] for a, b in swapped): continue planes = seq[list(order)][None, :] chain = [np.asarray(source, dtype=np.float64)[None, :]] for j in range(k): chain.append(model.mirror(chain[-1], planes[:, j])) exact, possible = _image_points(model, planes, chain, source, listener, least) legs = np.linalg.norm(np.diff(exact[0, 1:-1], axis=0), axis=1) if not possible[0] or np.any(legs <= least): continue on = [_face_at(model, int(planes[0, j]), exact[0, j + 1], tolerance) for j in range(k)] if min(on) < 0 or not _clear(model, exact[0], on, crossings[i], least, counted): continue for j in range(k): points[j][i] = exact[0, j + 1] faces[i] = on break def _clear(model: TraceModel, points, faces, crossings, least, counted) -> bool: """Whether the legs between ``points`` (k + 2, 3: the source, the reflection points off ``faces`` and the listener) let sound through and cross the faces ``crossings`` counts (of ``counted``), each traced from its start to ``least`` short of its end.""" crossed = np.zeros_like(crossings) for j in range(len(points) - 1): way = points[j + 1] - points[j] length = float(np.linalg.norm(way)) if length <= 2.0 * least: continue ignore = faces[j - 1] if j else -1 share, hit = model.passes(points[j], way / length, length - least, ignore, counted=counted) if not np.any(share > 0.0): return False crossed += hit[0] return bool(np.array_equal(crossed, crossings)) def _mirrors(model: TraceModel, seqs: np.ndarray, tolerance: float) -> np.ndarray: """(n, 12) where the planes of each sequence of ``seqs`` (n, k), mirroring in turn, take four points (a corner of the model's box and the three its largest extent from it along the axes), in steps of ``tolerance``: the same for the sequences that make one mirror, wherever a source lies.""" vertices = model.room.mesh.vertices size = float(np.ptp(vertices, axis=0).max()) marks = vertices.min(axis=0) + size * np.vstack([np.zeros(3), np.eye(3)]) moved = np.tile(marks, (len(seqs), 1)) for j in range(seqs.shape[1]): moved = model.mirror(moved, np.repeat(seqs[:, j], 4)) return np.round(moved.reshape(len(seqs), 12) / tolerance) def _surfaces(model: TraceModel, seqs: np.ndarray, tolerance: float) -> np.ndarray: """(n, k) the surfaces each sequence of ``seqs`` (n, k) reflects off, whatever their order and however often: numbers of the planes' own mirrors (the two sides of a partition are one surface), greatest first, -1 for no further one.""" planes = np.arange(model.plane_count) _, surface = np.unique(_mirrors(model, planes[:, None], tolerance), axis=0, return_inverse=True) met = np.sort(surface.reshape(-1)[seqs], axis=1) met[:, 1:][met[:, 1:] == met[:, :-1]] = -1 return -np.sort(-met, axis=1) def _along_at_planes(model: TraceModel, source, listener, planes: np.ndarray) -> np.ndarray: """(k, n, 3) for each of the k reflections of n paths off the planes ``planes`` (n, k) from ``source`` to ``listener`` a vector along the path where it meets that reflection's plane, for the angle between the two: the way the path leaves the reflection, from the source's image in the planes towards the listener, turned back by each plane after it. The image gives the angles wherever the reflection points lie: a point that the search took onto a plane, or two reflections it joined into a corner, lie up to its tolerance for planes from where the path meets the plane, and a leg about as short heads elsewhere than the path.""" n, k = planes.shape image = np.broadcast_to(np.asarray(source, dtype=np.float64), (n, 3)).copy() for j in range(k): image = model.mirror(image, planes[:, j]) way = np.asarray(listener, dtype=np.float64) - image along = np.zeros((k, n, 3)) for j in range(k - 1, -1, -1): along[j] = way normal = model.plane_normal[planes[:, j]] way = way - 2.0 * np.einsum("ij,ij->i", normal, way)[:, None] * normal return along def assemble_paths( model: TraceModel, source: np.ndarray, listener: np.ndarray, points: list[np.ndarray], faces: np.ndarray, distance: np.ndarray, through: np.ndarray, crossings: np.ndarray, *, speed_of_sound: float, air: np.ndarray, directivity: Directivity | None = None, orientation: np.ndarray | None = None, coherent: int = 0, ) -> EarlyReflections: """Paths of one order k from ``source`` to ``listener`` with their energies: their reflection points ``points`` (k + 1 arrays of (n, 3), the listener last), the faces they reflect off (n, k), their lengths (n,), the share of sound the surfaces they pass let through (n, bands) and how many they cross (n,), as :func:`find_paths` finds them.""" n, k = faces.shape bands = model.absorption.shape[1] dist = distance energy = np.exp(-np.outer(dist, air)) / (4.0 * np.pi * dist[:, None] ** 2) energy *= through spectrum = None if coherent: spectrum = np.ones((n, *sample_frequencies(bands, coherent).shape), complex) cosines = np.full((n, k), np.nan) # Reflections off surfaces with an impedance (a ground's) take its spherical # wave's reflection factor, in every band: its energy averaged over each band, # and in the coherent bands its pressure; on a ground with zones, those of the # grounds round the reflection. grounds = bool(k) and model.factor_faces(faces).any() factor = None before = np.broadcast_to(source, (n, 3)) if coherent or grounds: normals = model.plane_normal[model.face_plane[faces]] along = _along_at_planes(model, source, listener, model.face_plane[faces]) for j in range(k): incoming = points[j] - before energy *= model.reflection(faces[:, j], incoming, j + 1, impedance=True) if coherent or grounds: cosine = np.abs(np.einsum("ij,ij->i", normals[:, j], along[j])) / np.maximum( np.linalg.norm(along[j], axis=1), 1e-300 ) if coherent: spectrum *= reflection_phases(model, faces[:, j], cosine, coherent) own = ~model.factor_faces(faces[:, j]) if grounds else slice(None) cosines[own, j] = cosine[own] if grounds: following = points[j + 1] if j + 1 < k else listener ends = (before, points[j], np.broadcast_to(following, before.shape)) q = ground_factors(model, faces[:, j], cosine, dist, ends=ends) factor = q if factor is None else factor * q before = points[j] if factor is not None: gain = np.mean(np.abs(factor) ** 2, axis=2) # (n, bands) energy *= gain if coherent: level = np.sqrt(gain[:, :coherent, None]) spectrum *= np.where( level > 0.0, factor[:, :coherent] / np.where(level > 0.0, level, 1.0), 1.0 ) first = points[0] if k else np.broadcast_to(listener, (n, 3)) departure = first - source departure /= np.maximum(np.linalg.norm(departure, axis=1), 1e-300)[:, None] energy *= source_weights(directivity, orientation, departure, energy.shape[1], distances=dist) last = points[k - 1] if k else np.broadcast_to(source, (n, 3)) arrival = last - listener arrival /= np.maximum(np.linalg.norm(arrival, axis=1), 1e-300)[:, None] path_points = [ np.vstack([source, *[points[j][i] for j in range(k)], listener]) for i in range(n) ] return EarlyReflections( order=np.full(n, k, dtype=np.int64), delay_s=dist / speed_of_sound, distance_m=dist, direction=arrival, energy=energy, points=path_points, faces=[faces[i].copy() for i in range(n)], crossings=crossings, spectrum=spectrum, cosines=[cosines[i].copy() for i in range(n)] if coherent else [], ) def _towards_plane(model, start, direction, length, ignore, plane, trace, tolerance, counted): """For the rays from ``start`` (n, 3) along ``direction`` up to ``length`` where ``trace`` holds: the face of ``plane`` (n,) each meets first, passing straight through openings and faces of other planes that let sound through, or -1; where it meets it (the start where it does not); the share of sound that passes the faces on the way (n, bands); and how many of them it crossed of each column of ``counted`` (F, m), (n, m). A hit on another face exactly where it meets the expected plane counts as on the plane (whether the path goes on across that face there, :func:`_turn` says): one within ``tolerance`` of the plane, in which the image the ray heads for is mirrored, not of the own plane of one of its faces (where they do not all lie in the plane, :attr:`TraceModel.plane_spread`), over a face of it (:func:`_face_at`), on a ray whose two ends lie on either side of the plane (one that does not cross the plane reflects nowhere off it) and that meets that face's own plane on a face of the plane: a ray that met another face beside the line where the two join meets it past the edge.""" n = len(start) ends = start + direction * np.asarray(length, dtype=float)[:, None] across = _height_over_plane(model, start, plane) * _height_over_plane(model, ends, plane) < 0.0 bands = model.absorption.shape[1] transparent = model.transparent face = np.full(n, -1, dtype=np.int64) end = start.copy() share = np.ones((n, bands)) crossed = np.zeros((n, counted.shape[1]), dtype=np.int64) position = start.copy() remaining = np.asarray(length, dtype=float).copy() skip = np.asarray(ignore, dtype=np.int64).copy() alive = np.flatnonzero(trace) for _ in range(MAX_CROSSINGS + 1): if len(alive) == 0: break t, hit = model.intersect(position[alive], direction[alive], remaining[alive], skip[alive]) found = hit >= 0 rows, hit, t = alive[found], hit[found], t[found] position[rows] += direction[rows] * t[:, None] remaining[rows] -= t on_plane = (model.face_plane[hit] == plane[rows]) & ~transparent[hit] normal, offset = model.face_planes for i in np.flatnonzero(~on_plane & across[rows]): row = rows[i] other = _face_at(model, plane[row], position[row], tolerance, own=False) if other < 0: continue height = float(np.einsum("k,k->", normal[other], position[row])) - offset[other] slope = float(np.einsum("k,k->", normal[other], direction[row])) if slope == 0.0: continue crossing = position[row] - (height / slope) * direction[row] if _face_at(model, plane[row], crossing, tolerance) >= 0: hit[i], on_plane[i] = other, True face[rows[on_plane]] = hit[on_plane] end[rows[on_plane]] = position[rows[on_plane]] rows, hit = rows[~on_plane], hit[~on_plane] if model.transmission is None: break through = model.transmission[hit] share[rows] *= through crossed[rows] += counted[hit] skip[rows] = hit alive = rows[np.any(through > 0.0, axis=1)] return face, end, share, crossed def _crossed_here(model, reflecting, before, point, after, tolerance, near): """For a path that reflects off the planes ``reflecting`` (r,) at ``point``, coming from ``before`` and going on to ``after``: the faces it crosses right at the point, where neither leg's intersection test meets them, as a wall standing on the floor where the path reflects off the floor, or the walls meeting there. Returns them (k,), those on the leg arriving at the point first, and (k,) whether the leg arriving at it is the one that crosses each. The planes the path crosses near the point are those within ``tolerance`` of it that ``before`` and ``after`` lie on either side of, both farther than the intersection test's least distance (``before`` may be a reflection less than ``tolerance`` from the point, in a corner), and that it does not reflect off there; of coincident ones (within the model's plane tolerance; a wall drawn as one face for each room) only one counts, as the intersection test meets only one of them beside the point. Those right at the point are the ones that the leg crossing them meets within ``near`` (2,) of it: the distance from its end within which the leg that arrives at the point meets no face, and from its start for the leg that leaves it; where the point lies on the side of ``after`` already, that leg is the one arriving. The legs' own tests meet the others (see :func:`_meets_face`). Which faces the path crosses right at the point is decided as on one side of it, the path moved off it along all the surfaces it meets there: across the plane of incidence for one surface (or coincident ones), along the line where two meet; not at all where three or more meet. Those surfaces are the planes ``reflecting`` and every other plane with a face (not an opening) within ``tolerance`` of the point that is not one of those crossed near it or parallel to one, nor crossed by the path (see :func:`_on_either_side`), as the floor beside a reflection in its corner with a wall; each faces the side of whichever of ``before`` and ``after`` is farther from it. On each side, a plane crossed is covered where its faces cover it beside the point that way (see :func:`_cover`). The side taken is one where those the legs' tests meet are covered as they meet them, then one where the faces the path reflects off go on ``tolerance`` / 2 along that way (see :func:`_on_faces`), then the one with fewer covered right at the point; their faces are the ones crossed. Where the faces the path reflects off go on past the point on one side of a face's plane only (see :func:`_side_reflected`), it reflects on that side, so the leg from the other side crosses that face; elsewhere the leg arriving where the point lies on the side of ``after`` already. Distances from a plane are those of :func:`_height_near` (from the faces a point lies over, where they are not all in the plane).""" least = model.bvh.min_distance planes = np.arange(model.plane_count) normals = model.plane_normal height, below, above = _height_near( model, np.stack([point, before, after])[:, None], planes, tolerance ) arriving = (point - before) / max(np.linalg.norm(point - before), 1e-300) leaving = (after - point) / max(np.linalg.norm(after - point), 1e-300) arrives = height * above > 0.0 slope = np.abs(np.where(arrives, normals @ arriving, normals @ leaving)) crossing = _on_either_side(below, above, least) crossing[reflecting] = False here = crossing & (np.abs(height) <= np.where(arrives, near[0], near[1]) * slope) none = np.zeros(0, dtype=np.int64), np.zeros(0, dtype=bool) if not here.any(): return none # Those right at the point first, so that of coincident planes one of them counts. crossed: list[int] = [] for q in np.concatenate([np.flatnonzero(here), np.flatnonzero(crossing & ~here)]): if abs(height[q]) <= tolerance and all( abs(normals[q] @ normals[c]) < 1.0 - PLANE_TOLERANCE for c in crossed ): crossed.append(int(q)) at_point = here[crossed] # The surfaces the path meets there without crossing them, and the way along them. others = [ q for q in np.flatnonzero(np.abs(height) <= tolerance) if q not in reflecting and all(abs(normals[q] @ normals[c]) < 1.0 - PLANE_TOLERANCE for c in crossed) and _face_at(model, q, point, tolerance) >= 0 ] others = np.array(others, dtype=np.int64) others = others[~_on_either_side(below[others], above[others], tolerance)] surfaces = np.concatenate([reflecting, others]) farther = np.where( np.abs(below[surfaces]) >= np.abs(above[surfaces]), below[surfaces], above[surfaces] ) front = normals[surfaces] * np.sign(farther)[:, None] _, size, axes = np.linalg.svd(front) rank = np.count_nonzero(size > PLANE_TOLERANCE) along = np.zeros(3) if rank < 3: along = axes[2] if rank == 2 else np.cross(axes[0], arriving) along /= max(np.linalg.norm(along), 1e-300) step = tolerance / 2 cover = np.array([_cover(model, q, point, front, along, step) for q in crossed]) traced = [ _meets_face( model, q, point, -arriving if arrives[q] else leaving, abs(height[q]) / max(slope[q], 1e-300) + least, ) for q in np.array(crossed)[~at_point] ] choice = min( ( not np.array_equal(cover[~at_point, side] >= 0, traced), not _on_faces(model, reflecting, point + (1 - 2 * side) * step * along), np.count_nonzero(cover[at_point, side] >= 0), side, ) for side in (0, 1) ) faces = cover[at_point, choice[-1]] faces = faces[faces >= 0] arrive = arrives[model.face_plane[faces]] for i, face in enumerate(faces): side = _side_reflected(model, reflecting, model.face_plane[face], point, after, tolerance) if side: arrive[i] = side > 0 order = np.argsort(~arrive, kind="stable") return faces[order], arrive[order] def _cover(model, plane, point, front, along, step): """The faces of ``plane`` (-1 for none; not openings) that cover it beside ``point`` (moved onto it) right in front of surfaces facing ``front`` (s, 3), on the side of ``along`` and on the other. In ``plane``, the ways in front of all the surfaces make a wedge, to which a surface parallel to ``plane`` (within the model's plane tolerance) adds no side; the point tested lies ``step`` from ``point`` in the middle of it, on both sides. Where all the surfaces face the same way in ``plane`` (one surface, or coincident ones), the wedge is half of it, and the points tested lie also ``step`` to either side of that one: the one on the side of ``along`` for that side and the other for the other; where ``along`` (unit, or zero) runs along the way to neither side beyond the plane tolerance, both for each side, covered (by the face under the first) where faces cover both. With no wedge, or one with nothing in it, nothing covers it.""" normal = model.plane_normal[plane] away = front - np.outer(front @ normal, normal) size = np.linalg.norm(away, axis=1) away = away[size > PLANE_TOLERANCE] / size[size > PLANE_TOLERANCE, None] if len(away) == 0: return -1, -1 # In front of each surface lies half of ``plane``: the ways within a quarter turn of # the way in front. Where those halves overlap, with angles from the first way in # front, is the wedge: from a quarter turn short of the largest angle to a quarter # turn past the smallest. across = np.cross(normal, away[0]) angle = np.arctan2(away @ across, away @ away[0]) low, high = angle.max() - np.pi / 2, angle.min() + np.pi / 2 if low >= high: return -1, -1 middle = (low + high) / 2 up = np.cos(middle) * away[0] + np.sin(middle) * across point = point - (normal @ point - model.plane_offset[plane]) * normal near = model.bvh.min_distance if np.abs(angle).max() > PLANE_TOLERANCE: face = _face_at(model, plane, point + step * up, near) return face, face if across @ along < 0.0: across = -across faces = [_face_at(model, plane, point + step * (up + way), near) for way in (across, -across)] if abs(across @ along) <= PLANE_TOLERANCE: both = faces[0] if min(faces) >= 0 else -1 return both, both return faces[0], faces[1] def _meets_face(model, plane, start, direction, reach) -> bool: """Whether the intersection test meets a face (not an opening) of ``plane``, or of a plane coincident with it (within the model's plane tolerance), on the way from ``start`` along ``direction`` (unit) up to ``reach``.""" normal = model.plane_normal[plane] skip = -1 for _ in range(MAX_CROSSINGS + 1): t, face = model.intersect(start[None], direction[None], np.array([reach]), np.array([skip])) if face[0] < 0: return False if abs(model.plane_normal[model.face_plane[face[0]]] @ normal) >= 1.0 - PLANE_TOLERANCE: if not model.transparent[face[0]]: return True start, reach, skip = start + t[0] * direction, reach - t[0], face[0] return False def _on_faces(model, planes, point) -> bool: """Whether the foot of ``point`` on each of ``planes`` (r,) lies on a face of it (edges included, to the intersection test's least distance; not an opening).""" normals = model.plane_normal[planes] heights = normals @ point - model.plane_offset[planes] near = model.bvh.min_distance return all( _face_at(model, r, point - h * n, near) >= 0 for r, h, n in zip(planes, heights, normals, strict=True) ) def _side_reflected(model, reflecting, plane, point, after, tolerance) -> int: """On which side of ``plane`` a path reflects off the planes ``reflecting`` (r,) at ``point``, which lies in ``plane`` as well, going on to ``after``, judged by where their faces go on (see :func:`_on_faces`): 1 where they go on only on the side of ``after``, -1 only on the other side, 0 on both or neither. The points tested lie ``tolerance`` from ``point`` either way along all of ``reflecting``, as directly off ``plane`` as that allows; 0 too where that leaves them no farther from ``plane`` than the intersection test's least distance (as where ``plane`` holds the line the planes meet in).""" normal = model.plane_normal[plane] towards = normal * np.sign(normal @ after - model.plane_offset[plane]) normals = model.plane_normal[reflecting] way = towards - normals.T @ np.linalg.lstsq(normals.T, towards, rcond=None)[0] size = np.linalg.norm(way) if tolerance * size <= model.bvh.min_distance: return 0 way /= size return int(_on_faces(model, reflecting, point + tolerance * way)) - int( _on_faces(model, reflecting, point - tolerance * way) ) #: Room for rounding where an end of one arc is tested against another arc #: (:func:`_arcs_meet`). _ARC_ROUNDING = 1e-9 def _arcs_meet(across: np.ndarray, least: np.ndarray, use: np.ndarray) -> np.ndarray: """(p,) whether some unit vector d of a plane has ``across[p, k]`` . d >= ``least[p, k]`` for every k that ``use`` (p, K) marks, where ``across`` (p, K, 2) are unit vectors: each such bound leaves an arc of the unit circle (all of it up to -1, none of it above 1), and the arcs of a row have a direction in common. Where they have one and are not each the whole circle, what they have in common ends, going round to the left, where one of the arcs does, so those ends are the directions tried.""" least = np.where(use, least, -np.inf) cut = (least > -1.0) & (least <= 1.0) along = np.where(cut, least, 0.0) aside = np.sqrt(1.0 - along**2) ends = np.stack( [ along * across[..., 0] - aside * across[..., 1], along * across[..., 1] + aside * across[..., 0], ], axis=-1, ) reach = ( ends[:, :, None, 0] * across[:, None, :, 0] + ends[:, :, None, 1] * across[:, None, :, 1] ) held = np.all(reach >= least[:, None, :] - _ARC_ROUNDING, axis=2) return ~np.any(least > 1.0, axis=1) & (np.any(cut & held, axis=1) | ~np.any(cut, axis=1)) def _inner_corner(model, planes, fronts, point, tolerance) -> np.ndarray: """(n,) whether the faces of ``planes`` (n, r; -1 for none; two or more a row, which meet at ``point`` (n, 3)) make a corner there that a path reflects in, off all of them at that one point, where ``fronts`` (n, r, 3) are the planes' normals towards the side the path keeps to (zero for a plane the path runs in, which has no such side). A path that reflects off a plane near the point does so on the path's side of each of the other planes that have a side. A plane with no face there and one past any of those others makes no such corner: at an outer edge, the plane of the wall under a roof's edge has its faces below that edge and none over it, where sound from above the roof would meet it, so that a path through the edge is no reflection off the two. A plane with no face round the point leaves the corner one. The faces are looked for on the circle of twice ``tolerance`` about the point in the plane (the point itself may lie ``tolerance`` to either side of the other planes): the directions from the point in which that circle lies on a triangle of the plane (edges included to the intersection test's least distance), on the path's side of every other plane by more than twice that distance, or past one of them by as much (:func:`_arcs_meet`). Another plane counts where the circle reaches that far to both sides of it: not one nearly parallel to the plane.""" least = model.bvh.min_distance radius, clear = 2.0 * tolerance, 2.0 * least valid = planes >= 0 safe = np.maximum(planes, 0) normals = model.plane_normal[safe] side = np.sign(np.einsum("nrk,nrk->nr", fronts, normals)) towards = normals * side[:, :, None] # The point's own height over each plane, towards the path. height = side * _height_over_plane(model, point[:, None], safe) mesh = model.room.mesh inner = np.ones(len(planes), dtype=bool) for a in range(planes.shape[1]): # Along plane a, each other plane's normal towards the path: across the line the # two planes meet in. normal = normals[:, a] across = towards - np.einsum("nrk,nk->nr", towards, normal)[:, :, None] * normal[:, None] size = np.linalg.norm(across, axis=2) bounds = valid & (radius * size > clear + np.abs(height)) rows = np.flatnonzero(valid[:, a] & bounds.any(axis=1)) if len(rows) == 0: continue normal, size, bounds = normal[rows], np.where(bounds, size, 1.0)[rows], bounds[rows] across = across[rows] / size[:, :, None] # Two axes of plane a at the point, and in them the other planes' normals and how # far along each a direction lies clear of that plane, before it and past it. ahead = across[np.arange(len(rows)), np.argmax(bounds, axis=1)] beside = _cross(normal, ahead) lines = np.stack( [np.einsum("mrk,mk->mr", across, ahead), np.einsum("mrk,mk->mr", across, beside)], axis=-1, ) before = (clear - height[rows]) / (radius * size) past = (clear + height[rows]) / (radius * size) # The faces of plane a near the point: their corners in those axes, their edges' # normals into them, and how far along each a direction lies on the face. own = planes[rows, a] at, faces = [], [] for plane in np.unique(own): held = np.flatnonzero(own == plane) for part in np.array_split(held, -(-len(held) // _CHUNK)): found, under = _faces_under(model, plane, point[rows[part]], tolerance) solid = ~model.transparent[under] at.append(part[found[solid]]) faces.append(under[solid]) at, faces = np.concatenate(at), np.concatenate(faces) corners = mesh.vertices[mesh.faces[faces]] - point[rows[at]][:, None] corners = np.stack( [ np.einsum("pvk,pk->pv", corners, ahead[at]), np.einsum("pvk,pk->pv", corners, beside[at]), ], axis=-1, ) edge = np.roll(corners, -1, axis=1) - corners third = np.roll(corners, -2, axis=1) - corners inward = np.stack([-edge[..., 1], edge[..., 0]], axis=-1) turn = np.sign(inward[..., 0] * third[..., 0] + inward[..., 1] * third[..., 1]) inward *= (turn / np.maximum(np.linalg.norm(edge, axis=2), 1e-300))[..., None] on = (inward[..., 0] * corners[..., 0] + inward[..., 1] * corners[..., 1] - least) / radius on[np.any(turn == 0.0, axis=1)] = 2.0 # a face without area: in no direction every = np.ones((len(at), 3), dtype=bool) front = _arcs_meet( np.concatenate([inward, lines[at]], axis=1), np.concatenate([on, before[at]], axis=1), np.concatenate([every, bounds[at]], axis=1), ) behind = np.zeros(len(at), dtype=bool) for b in range(planes.shape[1]): behind |= bounds[at, b] & _arcs_meet( np.concatenate([inward, -lines[at, b : b + 1]], axis=1), np.concatenate([on, past[at, b : b + 1]], axis=1), np.ones((len(at), 4), dtype=bool), ) faces_before = np.zeros(len(rows), dtype=bool) faces_before[at[front]] = True faces_past = np.zeros(len(rows), dtype=bool) faces_past[at[behind]] = True inner[rows[faces_past & ~faces_before]] = False return inner def _turn(model, planes, faces, before, point, after, tolerance, counted): """Paths that reflect off ``planes`` (n, r; -1 for none; more than one in a corner), off their faces ``faces`` (n, r), at ``point`` (n, 3), coming from ``before`` (n, 3) and going on to ``after`` (n, 3): (n,) whether each turns back off every one of those planes, as a reflection does, rather than going on across one: in a corner, ``before`` and ``after`` on either side of it, both farther from it than the intersection test's least distance (not ``tolerance``, within which the corner's point may lie off it); anywhere, the leg from the point to ``before`` or to ``after`` crossing it farther from both of its ends than the intersection test's least distance (in a corner the point may lie past a plane the path reflects off just before, and the leg's own test does not meet the face it leaves, or meets another face of that plane as one it passes through). Nor does a path turn off two coincident planes (within the model's plane tolerance; a wall drawn as one face for each room) at one point: it would go on through the wall there, or come back as off one of them. Nor does it turn off planes whose faces make no corner on its side of them (see :func:`_inner_corner`), as at an outer edge of a building: its side of each plane is that of the farther of ``before`` and ``after``, where that lies farther from the plane than the least distance, and none otherwise. Also the share of sound (n, bands) and the crossings (n, m) of the faces each crosses right at the point (see :func:`_crossed_at`). The leg leaving the point meets no face nearer to it than the intersection test's least distance; the one arriving meets every face on its way but one right where it meets the plane (:func:`_towards_plane`), and the point then lies in that face's plane. Sides and distances are those of the plane that each of ``faces`` itself lies in (:attr:`TraceModel.face_planes`; its plane where the face lies in it): the face the leg arriving met, or the face of the plane under the point (:func:`_face_at`) where the leg met another face there or the point is a corner. None within :attr:`TraceModel.height_error` of a plane (the rounding of the model's coordinates) counts as farther than the least distance, as for a leg that runs that close along the plane.""" least = model.bvh.min_distance valid = planes >= 0 safe = np.maximum(planes, 0) normals = model.plane_normal[safe] own = np.where(valid, faces, 0) here, below, above = _height_over_face(model, np.stack([point, before, after])[:, :, None], own) corner = np.count_nonzero(valid, axis=1) > 1 off = max(least, model.height_error) across = corner[:, None] & _on_either_side(below, above, off) for end, there in ((before, below), (after, above)): way = end - point way /= np.maximum(np.linalg.norm(way, axis=1), 1e-300)[:, None] slope = np.abs(np.einsum("nrk,nk->nr", model.face_planes[0][own], way)) across |= _on_either_side(here, there, np.maximum(least * slope, model.height_error)) coincident = np.abs(normals @ normals.transpose(0, 2, 1)) >= 1.0 - PLANE_TOLERANCE coincident &= valid[:, :, None] & valid[:, None, :] & (planes[:, :, None] != planes[:, None, :]) turns = ~np.any(valid & across, axis=1) & ~np.any(coincident, axis=(1, 2)) rows = np.flatnonzero(corner & turns) if len(rows): farther = np.where(np.abs(below) >= np.abs(above), below, above)[rows] sides = np.where(valid[rows] & (np.abs(farther) > off), np.sign(farther), 0.0) fronts = model.face_planes[0][own[rows]] * sides[:, :, None] turns[rows] = _inner_corner(model, planes[rows], fronts, point[rows], tolerance) near = np.full((len(point), 2), least) share, crossed, _, _ = _crossed_at( model, planes, before, point, after, tolerance, counted, near ) return turns, share, crossed def _on_either_side(below, above, tolerance) -> np.ndarray: """Whether two points at heights ``below`` and ``above`` over a plane (any shape, negative behind it) lie on either side of it, both farther from it than ``tolerance``.""" far = np.minimum(np.abs(below), np.abs(above)) > tolerance return far & (below * above < 0.0) def _crossed_at(model, planes, before, point, after, tolerance, counted, near): """For paths that reflect off ``planes`` (n, r; -1 for none) at ``point`` (n, 3), coming from ``before`` (n, 3) and going on to ``after`` (n, 3): the faces each crosses right at the point, where neither leg's intersection test meets them (see :func:`_crossed_here`, with ``near`` (n, 2)), looked for where a chord across the turn, from ``tolerance`` back along the leg arriving to ``tolerance`` along the one leaving, meets a face. Returns the share of sound they let through (n, bands; 0 where one lets nothing through), how many of them each crosses of each column of ``counted`` (F, m), (n, m), the first of them on the way (n,), -1 for none, and whether the leg arriving at the point is the one that crosses it (n,).""" n = len(point) bands = model.absorption.shape[1] arriving = point - before arriving /= np.maximum(np.linalg.norm(arriving, axis=1), 1e-300)[:, None] leaving = after - point leaving /= np.maximum(np.linalg.norm(leaving, axis=1), 1e-300)[:, None] start = point - tolerance * arriving chord = point + tolerance * leaving - start length = np.linalg.norm(chord, axis=1) direction = chord / np.maximum(length, 1e-300)[:, None] share = np.ones((n, bands)) crossed = np.zeros((n, counted.shape[1]), dtype=np.int64) first = np.full(n, -1, dtype=np.int64) first_arrives = np.zeros(n, dtype=bool) _, face = model.intersect(start, direction, length, np.full(n, -1, dtype=np.int64)) for row in np.flatnonzero(face >= 0): reflecting = planes[row][planes[row] >= 0] faces, arrives = _crossed_here( model, reflecting, before[row], point[row], after[row], tolerance, near[row] ) if len(faces) == 0: continue share[row] *= 0.0 if model.transmission is None else model.transmission[faces].prod(axis=0) crossed[row] += counted[faces].sum(axis=0) first[row], first_arrives[row] = faces[0], arrives[0] return share, crossed, first, first_arrives