Source code for acoustic_spaces.geometry.checks

"""Mesh cleanup and the checks that tell a user whether a model is fit to simulate."""

from __future__ import annotations

from collections import deque
from dataclasses import dataclass, field

import numpy as np

from acoustic_spaces.geometry.mesh import RoomMesh

#: Vertices closer than this (metres) are merged.
MERGE_TOLERANCE_M = 1e-6
#: Faces smaller than this (square metres) are dropped as degenerate.
MIN_FACE_AREA_M2 = 1e-10
#: A vertex closer than this (metres) to an open edge of another face, between its ends,
#: splits that edge (a T-junction).
T_JUNCTION_TOLERANCE_M = 1e-5


[docs] @dataclass class MeshReport: vertices: int faces: int merged_vertices: int #: Faces cleaning removed: degenerate ones, and copies of another face. removed_degenerate_faces: int boundary_edges: int non_manifold_edges: int inconsistent_edges: int surface_area_m2: float volume_m3: float | None bounds_min: tuple[float, float, float] bounds_max: tuple[float, float, float] notes: list[str] = field(default_factory=list) #: True when face normals point into the room, False outward, None when unknown #: (open model or inconsistent orientation). normals_inward: bool | None = None #: Edges shared by three or another odd number of faces: where a partition or an #: opening between two rooms meets the walls, or a crack. odd_edges: int = 0 #: Volume of each room (m3): the separate volumes of air the faces enclose, two or #: more where partitions or openings divide the model (see #: :mod:`acoustic_spaces.geometry.cells`). room_volumes_m3: tuple[float, ...] = () #: Faces with no room or solid on either side: a hole joins the room behind them to #: the outside, or they stand outside the model. open_faces: int = 0 @property def closed(self) -> bool: """True when the faces enclose at least one room and every face has a room or a solid (the inside of a closed pillar) on one side at least. Free-standing panels inside a room leave it closed.""" return self.faces > 0 and len(self.room_volumes_m3) > 0 and self.open_faces == 0 @property def rooms(self) -> int: return len(self.room_volumes_m3) def summary(self) -> str: lo, hi = np.array(self.bounds_min), np.array(self.bounds_max) size = " x ".join(f"{d:.2f}" for d in hi - lo) if self.closed: state = "closed" if self.rooms > 1: volumes = ", ".join(f"{v:.2f}" for v in self.room_volumes_m3) state += f", {self.rooms} rooms of {volumes} m3" elif self.faces: state = f"open: {self.boundary_edges} boundary edges" if self.odd_edges: state += f", {self.odd_edges} edges shared by an odd number of faces" if self.open_faces: state += f", {self.open_faces} faces with no room on either side" else: state = "no faces" lines = [ f"{self.faces} triangles, {self.vertices} vertices, extent {size} m", f"surface area {self.surface_area_m2:.2f} m2" + (f", volume {self.volume_m3:.2f} m3" if self.volume_m3 is not None else ""), state, ] if self.non_manifold_edges: lines.append(f"{self.non_manifold_edges} edges shared by more than two faces") if self.inconsistent_edges: lines.append(f"{self.inconsistent_edges} edges with inconsistent face orientation") if self.merged_vertices: lines.append(f"merged {self.merged_vertices} duplicate vertices") if self.removed_degenerate_faces: lines.append(f"removed {self.removed_degenerate_faces} degenerate or repeated faces") lines.extend(self.notes) return "\n".join(lines)
[docs] def clean_mesh(mesh: RoomMesh) -> tuple[RoomMesh, int, int]: """Merge duplicate vertices, drop degenerate faces, copies of a face and the vertices no face uses, split faces at T-junctions and orient the faces alike. A copy is a face with the same corners as an earlier one, turning the same way: the same face given twice, which would leave every edge of it shared by three faces and the model with no inside. Two faces with the same corners turning opposite ways both stay: that is where two closed models touch, each with its own face. A face whose edge runs past a corner of the faces on its other side (a T-junction, which CAD exporters leave, or close with a zero-area sliver that is dropped here) is split at that corner, so the faces share the edge and the model can close. Faces that meet along an edge are turned to agree with each other, so a closed model with a few faces flipped by its exporter still has a volume and an inside test that works; each connected part keeps the orientation most of its area had. Returns the cleaned mesh, the number of merged vertices and of removed faces. """ keys = np.round(mesh.vertices / MERGE_TOLERANCE_M).astype(np.int64) _, first, inverse = np.unique(keys, axis=0, return_index=True, return_inverse=True) inverse = inverse.reshape(-1) vertices = mesh.vertices[first] faces = inverse[mesh.faces] merged = len(mesh.vertices) - len(vertices) tri = vertices[faces] area = 0.5 * np.linalg.norm(np.cross(tri[:, 1] - tri[:, 0], tri[:, 2] - tri[:, 0]), axis=1) distinct = ( (faces[:, 0] != faces[:, 1]) & (faces[:, 1] != faces[:, 2]) & (faces[:, 0] != faces[:, 2]) ) keep = distinct & (area > MIN_FACE_AREA_M2) # Copies: the corners from the lowest on, which keeps the way they turn. kept = np.flatnonzero(keep) lowest = np.argmin(faces[kept], axis=1) turned = faces[kept[:, None], (lowest[:, None] + np.arange(3)) % 3] _, once = np.unique(turned, axis=0, return_index=True) keep[kept] = False keep[kept[once]] = True faces, labels = _split_t_junctions(vertices, faces[keep], mesh.face_labels[keep]) tri = vertices[faces] area = 0.5 * np.linalg.norm(np.cross(tri[:, 1] - tri[:, 0], tri[:, 2] - tri[:, 0]), axis=1) faces = _orient_faces(faces, area) # A stray point of the file, or a corner only degenerate faces had, would count # wherever the model's extent is taken from its vertices. used, faces = np.unique(faces, return_inverse=True) faces = faces.reshape(-1, 3).astype(np.int64, copy=False) cleaned = RoomMesh(vertices[used], faces, labels, list(mesh.labels)) return cleaned, merged, int(np.count_nonzero(~keep))
def _edge_counts(faces: np.ndarray) -> tuple[np.ndarray, np.ndarray, np.ndarray]: """Every face edge (the three of face i are rows i, n + i and 2n + i) as corner pairs, the index of its undirected edge, and how many faces share each of those.""" directed = np.concatenate([faces[:, [0, 1]], faces[:, [1, 2]], faces[:, [2, 0]]]) key = directed.min(axis=1) * (int(faces.max(initial=0)) + 1) + directed.max(axis=1) _, edge, counts = np.unique(key, return_inverse=True, return_counts=True) return directed, edge.reshape(-1), counts def open_edges_of(faces: np.ndarray) -> tuple[np.ndarray, np.ndarray]: """The edges that only one of the faces has: (E, 2) their corners (vertex indices, in the order the face runs along them) and (E,) that face.""" directed, edge, counts = _edge_counts(faces) rows = np.flatnonzero(counts[edge] == 1) return directed[rows], rows % len(faces) def _split_t_junctions( vertices: np.ndarray, faces: np.ndarray, labels: np.ndarray ) -> tuple[np.ndarray, np.ndarray]: """The faces split at the vertices of odd edges that lie on their edges, with their labels. An odd edge is one shared by an odd number of faces: an open edge, which no other face shares, or one of three faces along a line that the edge of a fourth runs past. Each end of one within ``T_JUNCTION_TOLERANCE_M`` of another face's edge, between its ends, becomes a corner of that face: it turns into a fan of faces from its opposite corner, in the same orientation. The edge may be open too, or shared: a partition drawn between two rooms ends on the edge where their floors meet. A face whose own opposite corner lies on the edge has no area at that tolerance: an exporter's sliver closing the T-junction, which the split closes instead, so it is dropped. A face with T-junctions on more than one edge is split one edge per pass. """ for _ in range(8): if len(faces) == 0: break directed, edge, counts = _edge_counts(faces) odd_rows = np.flatnonzero(counts[edge] % 2 == 1) if len(odd_rows) == 0: break # Only the ends of odd edges can lie on another edge: sorted along x, the ones # within an edge's reach are one slice. ends = np.unique(directed[odd_rows]) order = np.argsort(vertices[ends, 0], kind="stable") ends, xs = ends[order], vertices[ends[order], 0] n = len(faces) # The edges with an end of an odd edge within reach of their x range, besides # their own two. x = vertices[directed, 0] first = np.searchsorted(xs, x.min(axis=1) - T_JUNCTION_TOLERANCE_M) reach = np.searchsorted(xs, x.max(axis=1) + T_JUNCTION_TOLERANCE_M, side="right") reach -= first own = np.isin(directed, ends).sum(axis=1) rows = np.flatnonzero(reach > own) hit_row, hit_end, hit_t = _ends_on_edges(vertices, directed, ends, rows, first, reach) # Each face is split along the first of its edges (in the order of ``directed``) # that has an end on it. hit_face = hit_row % n _, once = np.unique(hit_face, return_index=True) replaced: dict[int, list[list[int]]] = {} for row in np.sort(hit_row[once]).tolist(): on = slice(*np.searchsorted(hit_row, [row, row + 1]).tolist()) near, t = hit_end[on], hit_t[on] face, k = row % n, row // n # the face runs a -> b from its corner k a, b = directed[row] c = int(faces[face, (k + 2) % 3]) if c in near: replaced[face] = [] continue corners = [int(a), *near[np.argsort(t)].tolist(), int(b)] replaced[face] = [[p, q, c] for p, q in zip(corners[:-1], corners[1:], strict=True)] if not replaced: break kept = np.setdiff1d(np.arange(n), list(replaced)) new = [f for split in replaced.values() for f in split] new_labels = [labels[face] for face, split in replaced.items() for _ in split] faces = np.concatenate([faces[kept], np.array(new, dtype=faces.dtype).reshape(-1, 3)]) labels = np.concatenate([labels[kept], np.array(new_labels, dtype=labels.dtype)]) return faces, labels #: (edge, end) pairs tested at once in :func:`_split_t_junctions`, to bound its memory. _PAIRS_PER_BLOCK = 1 << 18 def _ends_on_edges( vertices: np.ndarray, directed: np.ndarray, ends: np.ndarray, rows: np.ndarray, first: np.ndarray, reach: np.ndarray, ) -> tuple[np.ndarray, np.ndarray, np.ndarray]: """The ends (``ends``, sorted along x) that lie on the edges ``rows`` of ``directed``, within ``T_JUNCTION_TOLERANCE_M`` of the edge and farther than that from both its ends: the edge's row, the end and where along the edge it lies (0 at its first corner, 1 at its second), in the order of the rows and, for each, of the ends. Edge ``row`` is tested against the ``reach[row]`` ends from ``first[row]`` on, those within its x range.""" sizes = reach[rows] blocks = np.searchsorted( np.cumsum(sizes), np.arange(1, sizes.sum() // _PAIRS_PER_BLOCK + 1) * _PAIRS_PER_BLOCK ) out_row, out_end, out_t = [], [], [] for part in np.split(np.arange(len(rows)), blocks): row, size = rows[part], sizes[part] pair_row = np.repeat(row, size) step = np.arange(int(size.sum())) - np.repeat(np.cumsum(size) - size, size) end = ends[np.repeat(first[row], size) + step] pa, pb = vertices[directed[pair_row, 0]], vertices[directed[pair_row, 1]] d = pb - pa length = np.linalg.norm(d, axis=1) point = vertices[end] t = np.einsum("ij,ij->i", point - pa, d) / length**2 off = np.linalg.norm(point - (pa + t[:, None] * d), axis=1) inside = ( (off < T_JUNCTION_TOLERANCE_M) & (t * length > T_JUNCTION_TOLERANCE_M) & ((1.0 - t) * length > T_JUNCTION_TOLERANCE_M) ) out_row.append(pair_row[inside]) out_end.append(end[inside]) out_t.append(t[inside]) return np.concatenate(out_row), np.concatenate(out_end), np.concatenate(out_t) def _orient_faces(faces: np.ndarray, areas: np.ndarray) -> np.ndarray: """The faces with their corner order reversed where needed to agree with their neighbours. Two faces sharing an edge agree when they run along it in opposite directions. The orientation spreads from one face of each connected part to the rest, breadth first, across every edge that exactly two faces share; each part then keeps the orientation that most of its area (``areas``, one per face) had. Edges shared by more than two faces pass nothing on, and a part that cannot be oriented (a Moebius strip) keeps the edges where its orientation clashes. """ count = len(faces) if count == 0: return faces.copy() # Every edge of every face, and the faces on both sides of each two-face edge. directed, edge, counts = _edge_counts(faces) owner = np.tile(np.arange(count), 3) shared = np.flatnonzero(counts[edge] == 2) pairs = shared[np.argsort(edge[shared], kind="stable")].reshape(-1, 2) a, b = owner[pairs[:, 0]], owner[pairs[:, 1]] # Running the same way along their edge, one of the two faces has to turn. clash = np.all(directed[pairs[:, 0]] == directed[pairs[:, 1]], axis=1) # Neighbours of each face, as ranges of one sorted list. ends = np.concatenate([a, b]) order = np.argsort(ends, kind="stable") start = np.searchsorted(ends[order], np.arange(count + 1)).tolist() neighbours = np.concatenate([b, a])[order].tolist() clashes = np.concatenate([clash, clash])[order].tolist() turn = [False] * count seen = [False] * count for seed in range(count): if seen[seed]: continue seen[seed] = True part, queue = [seed], deque([seed]) while queue: face = queue.popleft() for k in range(start[face], start[face + 1]): other = neighbours[k] if not seen[other]: seen[other] = True turn[other] = turn[face] != clashes[k] part.append(other) queue.append(other) turned = np.array([turn[f] for f in part]) if areas[part][turned].sum() > areas[part][~turned].sum(): for f in part: turn[f] = not turn[f] out = faces.copy() flip = np.array(turn) out[flip] = out[flip][:, ::-1] return out
[docs] def check_mesh(mesh: RoomMesh, merged: int = 0, removed: int = 0) -> MeshReport: """Topology, size and orientation checks on a cleaned mesh.""" faces = mesh.faces directed, edge, counts = _edge_counts(faces) # Faces agree along an edge when as many run along it one way as the other. way = np.where(directed[:, 0] < directed[:, 1], 1.0, -1.0) balance = np.bincount(edge, weights=way, minlength=len(counts)) boundary = int(np.count_nonzero(counts == 1)) non_manifold = int(np.count_nonzero(counts > 2)) odd = int(np.count_nonzero((counts > 2) & (counts % 2 == 1))) # Where three faces meet (a partition and the wall it divides), they cannot all agree. inconsistent = int(np.count_nonzero((counts > 1) & (counts % 2 == 0) & (balance != 0))) cells = mesh.cells() rooms = tuple(float(v) for v in cells.room_volumes) open_faces = int(np.count_nonzero(cells.open_faces)) volume = None inward = None notes: list[str] = [] if rooms and open_faces == 0: volume = float(sum(rooms)) # Faces with a room on one side only: do their normals point into it? face_room = cells.face_room one_sided = (face_room >= 0).sum(axis=1) == 1 front = face_room[one_sided, 0] >= 0 if len(front) and front.all(): inward = True notes.append("face normals point into the room") elif len(front) and not front.any(): inward = False notes.append("face normals point outward") lo = mesh.vertices.min(axis=0) if len(mesh.vertices) else np.zeros(3) hi = mesh.vertices.max(axis=0) if len(mesh.vertices) else np.zeros(3) return MeshReport( vertices=len(mesh.vertices), faces=len(faces), merged_vertices=merged, removed_degenerate_faces=removed, boundary_edges=boundary, non_manifold_edges=non_manifold, inconsistent_edges=inconsistent, surface_area_m2=float(mesh.face_areas().sum()), volume_m3=volume, bounds_min=tuple(float(v) for v in lo), bounds_max=tuple(float(v) for v in hi), notes=notes, normals_inward=inward, odd_edges=odd, room_volumes_m3=rooms, open_faces=open_faces, )
[docs] def points_inside(mesh: RoomMesh, points: np.ndarray) -> np.ndarray: """Whether each point lies inside a room of a closed mesh (any of its rooms, when partitions or openings divide it; see :mod:`acoustic_spaces.geometry.cells`).""" return room_of(mesh, points) >= 0
[docs] def room_of(mesh: RoomMesh, points: np.ndarray) -> np.ndarray: """The room each point lies in (an index into the rooms of ``mesh.cells()``), or -1 outside every room. Generalised winding numbers: the signed solid angles that a room's faces subtend at the point add up to 4 pi inside it and 0 outside.""" from acoustic_spaces.geometry.cells import room_of as cell_room_of return cell_room_of(mesh.vertices, mesh.faces, mesh.cells(), points)
[docs] def distance_to_surface(mesh: RoomMesh, points: np.ndarray) -> np.ndarray: """Distance from each point to the nearest triangle of the mesh (metres).""" points = np.atleast_2d(np.asarray(points, dtype=np.float64)) tri = mesh.triangles a, b, c = tri[:, 0], tri[:, 1], tri[:, 2] ab, ac = b - a, c - a out = np.empty(len(points)) for k, p in enumerate(points): out[k] = np.sqrt(_squared_distance_to_triangles(p, a, ab, ac).min(initial=np.inf)) return out
[docs] def triangle_gaps(one: np.ndarray, other: np.ndarray) -> np.ndarray: """The least distance (metres) between each of the triangles ``one`` (n, 3, 3: the three corners of each) and the one of ``other`` at its place: nothing where the two touch or cross.""" one = np.asarray(one, dtype=np.float64).reshape(-1, 3, 3) other = np.asarray(other, dtype=np.float64).reshape(-1, 3, 3) best = np.full(len(one), np.inf) for these, those in ((one, other), (other, one)): a = those[:, 0] ab, ac = those[:, 1] - a, those[:, 2] - a for k in range(3): # A corner to the face; and nothing where the edge from it goes through the face. best = np.minimum(best, _squared_distance_to_triangles(these[:, k], a, ab, ac)) edge = these[:, (k + 1) % 3] - these[:, k] best = np.where(_crosses(these[:, k], edge, a, ab, ac), 0.0, best) for j in range(3): for k in range(3): best = np.minimum( best, _squared_segment_gaps( one[:, j], one[:, (j + 1) % 3] - one[:, j], other[:, k], other[:, (k + 1) % 3] - other[:, k], ), ) return np.sqrt(best)
def _crosses( start: np.ndarray, line: np.ndarray, a: np.ndarray, ab: np.ndarray, ac: np.ndarray ) -> np.ndarray: """Whether each segment from ``start`` along ``line`` goes through its triangle (a, a + ab, a + ac): its ends lie on the two sides of the triangle's plane, or one of them in it, and the point of the segment in the plane lies in the triangle. A segment in the plane goes through nothing; where rounding leaves its ends just off the plane, on its two sides, the point looked for is still one of the segment, so that a segment outside the triangle does not go through it.""" normal = np.cross(ab, ac) before = ((start - a) * normal).sum(axis=1) after = before + (line * normal).sum(axis=1) with np.errstate(divide="ignore", invalid="ignore"): point = start - a + line * (before / (before - after))[:, None] area = (normal * normal).sum(axis=1) u = (np.cross(point, ac) * normal).sum(axis=1) / area v = (np.cross(ab, point) * normal).sum(axis=1) / area return (before * after <= 0) & (u >= 0) & (v >= 0) & (u + v <= 1) def _squared_segment_gaps(p: np.ndarray, d: np.ndarray, q: np.ndarray, e: np.ndarray) -> np.ndarray: """Squared least distance between each segment from ``p`` along ``d`` and its segment from ``q`` along ``e`` (the nearest points of the two, each kept on its segment).""" r = p - q dd, ee, de = (d * d).sum(axis=1), (e * e).sum(axis=1), (d * e).sum(axis=1) dr, er = (d * r).sum(axis=1), (e * r).sum(axis=1) across = dd * ee - de * de with np.errstate(divide="ignore", invalid="ignore"): s = np.where(across > 0, np.clip((de * er - dr * ee) / across, 0.0, 1.0), 0.0) t = (de * s + er) / ee s = np.where( t < 0, np.clip(-dr / dd, 0.0, 1.0), np.where(t > 1, np.clip((de - dr) / dd, 0.0, 1.0), s), ) # A segment of no length is its start. s, t = np.nan_to_num(s), np.clip(np.nan_to_num(t), 0.0, 1.0) apart = r + d * s[:, None] - e * t[:, None] return (apart * apart).sum(axis=1) #: Most pairs of a point and a triangle that :func:`triangles_near` measures at once. _PAIRS = 1_000_000
[docs] def triangles_near( triangles: np.ndarray, points: np.ndarray, reach: float ) -> tuple[np.ndarray, np.ndarray, np.ndarray]: """The pairs of one of ``points`` and one of ``triangles`` (n, 3, 3: the three corners of each) no farther apart than ``reach`` metres: the points' indices, the triangles' and the distances (metres), in no order. Only the points in a triangle's box, grown by the reach, are measured against it: along the axis that leaves the fewest, each box takes the run of the sorted points that its span holds.""" points = np.atleast_2d(np.asarray(points, dtype=np.float64)) tri = np.asarray(triangles, dtype=np.float64).reshape(-1, 3, 3) found: tuple[list, list, list] = ([], [], []) if len(points) and len(tri): low, high = tri.min(axis=1) - reach, tri.max(axis=1) + reach runs = [] for axis in range(3): order = np.argsort(points[:, axis], kind="stable") along = points[order, axis] first = np.searchsorted(along, low[:, axis], side="left") count = np.searchsorted(along, high[:, axis], side="right") - first runs.append((int(count.sum()), order, first, count)) _, order, first, count = min(runs, key=lambda run: run[0]) ends = np.cumsum(count) start = 0 while start < len(tri): done = int(ends[start - 1]) if start else 0 stop = max(start + 1, int(np.searchsorted(ends, done + _PAIRS, side="right"))) held = count[start:stop] triangle = np.repeat(np.arange(start, stop), held) place = np.arange(len(triangle)) - np.repeat(np.cumsum(held) - held, held) point = order[np.repeat(first[start:stop], held) + place] inside = ((points[point] >= low[triangle]) & (points[point] <= high[triangle])).all( axis=1 ) triangle, point = triangle[inside], point[inside] a = tri[triangle, 0] distance = np.sqrt( _squared_distance_to_triangles( points[point], a, tri[triangle, 1] - a, tri[triangle, 2] - a ) ) near = distance <= reach for kept, values in zip(found, (point, triangle, distance), strict=True): kept.append(values[near]) start = stop if not found[0]: return np.zeros(0, dtype=np.int64), np.zeros(0, dtype=np.int64), np.zeros(0) return tuple(np.concatenate(values) for values in found)
def _squared_distance_to_triangles( p: np.ndarray, a: np.ndarray, ab: np.ndarray, ac: np.ndarray ) -> np.ndarray: """Squared distance from p to each triangle (a, a + ab, a + ac).""" n = np.cross(ab, ac) nn = np.einsum("ij,ij->i", n, n) ap = p - a # Inside the prism over the triangle: the distance to the plane. with np.errstate(divide="ignore", invalid="ignore"): d_plane = np.einsum("ij,ij->i", ap, n) ** 2 / nn u = np.einsum("ij,ij->i", np.cross(ap, ac), n) / nn v = np.einsum("ij,ij->i", np.cross(ab, ap), n) / nn inside = (u >= 0) & (v >= 0) & (u + v <= 1) & (nn > 0) # Otherwise the nearest point is on an edge. best = np.full(len(a), np.inf) for start, edge in ((a, ab), (a, ac), (a + ab, ac - ab)): ee = np.einsum("ij,ij->i", edge, edge) with np.errstate(divide="ignore", invalid="ignore"): t = np.clip(np.einsum("ij,ij->i", p - start, edge) / ee, 0.0, 1.0) t = np.where(ee > 0, t, 0.0) closest = start + edge * t[:, None] best = np.minimum(best, np.einsum("ij,ij->i", p - closest, p - closest)) return np.where(inside, d_plane, best)