"""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)