codexbounding-volume-hierarchy-query-pruning.py
bounding-volume-hierarchy-query-pruning.py
"""Exact box query, hierarchy pruning and a false broad-phase candidate.
Run from _media with Python 3.14, matplotlib 3.10.7 and numpy 2.3.5:
MPLBACKEND=Agg MPLCONFIGDIR=/tmp/codex-wiki-matplotlib python3.14 ../bounding-volume-hierarchy-query-pruning.py
"""
import json
from pathlib import Path
import matplotlib.pyplot as plt
import numpy as np
from matplotlib.patches import Polygon, Rectangle
TRIANGLES = {
"A": np.array([(0, 0), (2, 0), (0, 2)], dtype=float),
"B": np.array([(1.5, 1.5), (3.5, 1.5), (3.5, 3.5)]),
"C": np.array([(6, 0), (8, 0), (6, 2)], dtype=float),
"D": np.array([(6, 3), (8, 3), (8, 5)], dtype=float),
}
CHILDREN = {"root": ("L", "R"), "L": ("A", "B"), "R": ("C", "D")}
QUERY = (np.array([1.6, 1.6]), np.array([1.8, 1.8]))
BLUE, GREEN, GRAY = "#2467a4", "#147d69", "#7c848b"
def bounds_and_traversal():
bounds = {n: (p.min(axis=0), p.max(axis=0)) for n, p in TRIANGLES.items()}
for n in ("L", "R", "root"):
children = [bounds[c] for c in CHILDREN[n]]
bounds[n] = (np.min([b[0] for b in children], axis=0),
np.max([b[1] for b in children], axis=0))
visited, accepted, candidates = [], [], []
def visit(n):
visited.append(n)
lo, hi = bounds[n]
if not np.all(np.maximum(lo, QUERY[0]) <= np.minimum(hi, QUERY[1])):
return
accepted.append(n)
if n in CHILDREN:
for c in CHILDREN[n]:
visit(c)
else:
candidates.append(n)
visit("root")
assert visited == ["root", "L", "A", "B", "R"]
assert accepted == ["root", "L", "A", "B"]
assert candidates == ["A", "B"]
assert QUERY[0].sum() > TRIANGLES["A"].sum(axis=1).max()
hit_point = np.array([7 / 4, 13 / 8])
assert np.all(QUERY[0] <= hit_point) and np.all(hit_point <= QUERY[1])
assert hit_point[1] <= hit_point[0] and hit_point[1] >= 1.5 and hit_point[0] <= 3.5
return bounds, visited, candidates
def rectangle(ax, box, **kwargs):
lo, hi = box
ax.add_patch(Rectangle(lo, *(hi - lo), **kwargs))
def draw_scene(ax, bounds):
for name in ("root", "L", "R"):
rectangle(ax, bounds[name], fill=False, ec=GRAY, lw=1.5)
for name, p in TRIANGLES.items():
color = BLUE if name == "A" else GREEN if name == "B" else GRAY
rectangle(ax, bounds[name], fill=False, ec=color, lw=1.2, linestyle="--")
ax.add_patch(Polygon(p, fc=color, ec=color, alpha=.22, lw=1.5))
ax.text(*p.mean(axis=0), name, ha="center", va="center", weight="bold", color=color)
rectangle(ax, QUERY, fc="#ffcf66", ec="#995c00", lw=2, zorder=6)
ax.annotate("Q", xy=(1.7, 1.7), xytext=(4.4, 2.5), weight="bold",
arrowprops={"arrowstyle": "->", "color": "#995c00"})
ax.text(7, 5.18, "R: reject", ha="center", color=GRAY)
ax.set(xlim=(-.4, 8.4), ylim=(-.4, 5.6), xlabel="x", ylabel="y")
ax.set_aspect("equal")
ax.set_xticks([0, 2, 4, 6, 8])
ax.grid(alpha=.15)
ax.set_title("Query misses all of R", fontsize=12)
def draw_zoom(ax):
p = TRIANGLES["B"]
ax.add_patch(Polygon(p, fc=GREEN, ec=GREEN, alpha=.23, lw=2))
ax.axvline(2, color=BLUE, linestyle="--", lw=1.7)
ax.axhline(2, color=BLUE, linestyle="--", lw=1.7)
rectangle(ax, QUERY, fill=False, ec="#995c00", lw=2.5, zorder=5)
ax.text(1.7, 1.71, "Q", ha="center", va="center", color="#995c00", weight="bold")
ax.scatter([7 / 4], [13 / 8], color=GREEN, s=35, zorder=7)
ax.annotate("Point in Q and B", xy=(7 / 4, 13 / 8), xytext=(1.91, 1.46),
ha="center", fontsize=9, color=GREEN,
arrowprops={"arrowstyle": "->", "color": GREEN})
ax.text(1.91, 1.91, "A's box", fontsize=9, color=BLUE, ha="center")
ax.text(1.7, 2.16, "A lies in x + y ≤ 2\n(all outside this close-up)",
fontsize=9, ha="center", color=BLUE)
ax.set(xlim=(1.38, 2.1), ylim=(1.38, 2.3), xlabel="x", ylabel="y")
ax.set_aspect("equal")
ax.set_xticks([1.5, 1.6, 1.8, 2])
ax.set_yticks([1.5, 1.6, 1.8, 2])
ax.grid(alpha=.15)
ax.set_title("Close-up: only B is a true hit", fontsize=12)
def draw_tree(ax):
locations = {"root": (.5, .86), "L": (.25, .53), "R": (.75, .53),
"A": (.1, .19), "B": (.4, .19), "C": (.65, .19), "D": (.9, .19)}
labels = {"root": "1 root\npass", "L": "2 L\npass", "R": "5 R\nreject",
"A": "3 A\ncandidate\nshape misses", "B": "4 B\ncandidate\nshape hits",
"C": "C\nskipped", "D": "D\nskipped"}
for parent, children in CHILDREN.items():
x, y = locations[parent]
for child in children:
cx, cy = locations[child]
ax.annotate("", xy=(cx, cy + .1), xytext=(x, y - .09),
arrowprops={"arrowstyle": "->", "color": GRAY,
"linestyle": "--" if parent == "R" else "-"})
for name, (x, y) in locations.items():
color = BLUE if name == "A" else GREEN if name == "B" else GRAY
bg = "#f0f1f2" if name in ("R", "C", "D") else "white"
ax.text(x, y, labels[name], ha="center", va="center", fontsize=9.5,
bbox={"boxstyle": "round,pad=.4", "facecolor": bg,
"edgecolor": color, "linewidth": 1.5})
ax.set(xlim=(-.03, 1.04), ylim=(-.06, 1.06))
ax.axis("off")
ax.set_title("Left-first traversal; numbers give test order", fontsize=12)
ax.text(.5, -.04, "5 box tests → 2 shape tests → 1 hit", ha="center", fontsize=10.5)
def main():
plt.rcParams.update({"font.size": 10, "figure.facecolor": "white", "axes.facecolor": "white"})
bounds, visited, candidates = bounds_and_traversal()
fig, axes = plt.subplots(1, 3, figsize=(13, 5.5),
gridspec_kw={"width_ratios": [1.05, .75, 1.2]})
draw_scene(axes[0], bounds)
draw_zoom(axes[1])
draw_tree(axes[2])
fig.suptitle("Closed query Q = [1.6, 1.8] × [1.6, 1.8]: box overlap leaves candidates", fontsize=14)
fig.tight_layout(rect=(0, .03, 1, .94), w_pad=2)
output = Path(Path(__file__).stem + ".png")
fig.savefig(output, dpi=110, facecolor="white", transparent=False)
plt.close(fig)
print(json.dumps({"output": str(output), "visited": visited, "candidates": candidates,
"skipped": ["C", "D"], "box_tests": 5, "shape_tests": 2,
"hits": ["B"], "hit_point": [7 / 4, 13 / 8]}))
if __name__ == "__main__":
main()