oxiphysics_gpu/bvh/
types.rs

1// Copyright 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3
4//! Core BVH types: AABB, primitives, nodes, flat nodes, and ray-hit results.
5
6// ============================================================================
7// Aabb
8// ============================================================================
9
10/// An axis-aligned bounding box stored as two `[f32; 3]` corners.
11#[derive(Debug, Clone, PartialEq)]
12pub struct Aabb {
13    /// Minimum corner (component-wise).
14    pub min: [f32; 3],
15    /// Maximum corner (component-wise).
16    pub max: [f32; 3],
17}
18
19impl Aabb {
20    /// Construct an `Aabb` from explicit min/max corners.
21    pub fn new(min: [f32; 3], max: [f32; 3]) -> Self {
22        Self { min, max }
23    }
24
25    /// Construct a degenerate `Aabb` that contains exactly one point.
26    pub fn point(p: [f32; 3]) -> Self {
27        Self { min: p, max: p }
28    }
29
30    /// Return the smallest `Aabb` that contains both `a` and `b`.
31    pub fn merge(a: &Aabb, b: &Aabb) -> Aabb {
32        Aabb {
33            min: [
34                a.min[0].min(b.min[0]),
35                a.min[1].min(b.min[1]),
36                a.min[2].min(b.min[2]),
37            ],
38            max: [
39                a.max[0].max(b.max[0]),
40                a.max[1].max(b.max[1]),
41                a.max[2].max(b.max[2]),
42            ],
43        }
44    }
45
46    /// Returns `true` if this box overlaps `other` (touching counts).
47    pub fn intersects(&self, other: &Aabb) -> bool {
48        self.min[0] <= other.max[0]
49            && self.max[0] >= other.min[0]
50            && self.min[1] <= other.max[1]
51            && self.max[1] >= other.min[1]
52            && self.min[2] <= other.max[2]
53            && self.max[2] >= other.min[2]
54    }
55
56    /// Returns `true` if point `p` lies inside or on the surface of this box.
57    pub fn contains(&self, p: [f32; 3]) -> bool {
58        p[0] >= self.min[0]
59            && p[0] <= self.max[0]
60            && p[1] >= self.min[1]
61            && p[1] <= self.max[1]
62            && p[2] >= self.min[2]
63            && p[2] <= self.max[2]
64    }
65
66    /// Surface area of the box (sum of all six face areas).
67    pub fn surface_area(&self) -> f32 {
68        let dx = self.max[0] - self.min[0];
69        let dy = self.max[1] - self.min[1];
70        let dz = self.max[2] - self.min[2];
71        2.0 * (dx * dy + dy * dz + dz * dx)
72    }
73
74    /// Geometric centre of the box.
75    pub fn center(&self) -> [f32; 3] {
76        [
77            0.5 * (self.min[0] + self.max[0]),
78            0.5 * (self.min[1] + self.max[1]),
79            0.5 * (self.min[2] + self.max[2]),
80        ]
81    }
82
83    /// Return a copy of this box expanded uniformly by `margin` on every side.
84    pub fn expand(&self, margin: f32) -> Aabb {
85        Aabb {
86            min: [
87                self.min[0] - margin,
88                self.min[1] - margin,
89                self.min[2] - margin,
90            ],
91            max: [
92                self.max[0] + margin,
93                self.max[1] + margin,
94                self.max[2] + margin,
95            ],
96        }
97    }
98}
99
100// ============================================================================
101// BvhPrimitive
102// ============================================================================
103
104/// A leaf primitive: an AABB together with the logical object it belongs to.
105#[derive(Debug, Clone)]
106pub struct BvhPrimitive {
107    /// Bounding box of the primitive.
108    pub aabb: Aabb,
109    /// Caller-defined identifier (returned by queries).
110    pub object_id: usize,
111}
112
113impl BvhPrimitive {
114    /// Construct a `BvhPrimitive`.
115    pub fn new(aabb: Aabb, object_id: usize) -> Self {
116        Self { aabb, object_id }
117    }
118}
119
120// ============================================================================
121// BvhNode
122// ============================================================================
123
124/// A node in the recursive BVH tree.
125#[derive(Debug)]
126pub struct BvhNode {
127    /// Bounding box that contains all children / primitives.
128    pub aabb: Aabb,
129    /// Left subtree (internal nodes only).
130    pub left: Option<Box<BvhNode>>,
131    /// Right subtree (internal nodes only).
132    pub right: Option<Box<BvhNode>>,
133    /// Indices into `Bvh::primitives` (leaf nodes only).
134    pub primitives: Vec<usize>,
135}
136
137impl BvhNode {
138    /// Returns `true` if this node is a leaf (holds primitives directly).
139    pub fn is_leaf(&self) -> bool {
140        self.left.is_none() && self.right.is_none()
141    }
142}
143
144// ============================================================================
145// Flat BVH node
146// ============================================================================
147
148/// A single node in the linearised (flat) BVH representation.
149///
150/// Layout:
151/// * If `count == 0` this is an **internal** node.
152///   - The **left** child is always at index `node_idx + 1` (i.e. stored
153///     immediately after the parent in DFS pre-order).
154///   - `left_first` holds the index of the **right** child.
155/// * If `count > 0` this is a **leaf**; `left_first` is the start index into
156///   the accompanying primitive-index slice and `count` is the number of
157///   entries.
158#[derive(Debug, Clone)]
159pub struct FlatBvhNode {
160    /// Bounding box of this node.
161    pub aabb: Aabb,
162    /// Right-child index (internal) or first-primitive index (leaf).
163    pub left_first: u32,
164    /// 0 for internal nodes; number of primitives for leaf nodes.
165    pub count: u32,
166}
167
168// ============================================================================
169// RayHit
170// ============================================================================
171
172/// Result of a closest-hit ray traversal.
173#[derive(Debug, Clone)]
174pub struct RayHit {
175    /// Object ID of the closest hit primitive.
176    pub object_id: usize,
177    /// Ray parameter at which the hit occurred.
178    pub t: f32,
179}
180
181// ============================================================================
182// GpuRay
183// ============================================================================
184
185/// A ray for GPU BVH traversal.
186#[derive(Debug, Clone, Copy, PartialEq)]
187pub struct GpuRay {
188    /// Ray origin.
189    pub origin: [f32; 3],
190    /// Ray direction (does not need to be normalised).
191    pub direction: [f32; 3],
192    /// Maximum ray parameter (hit farther than this is ignored).
193    pub max_t: f32,
194}
195
196impl GpuRay {
197    /// Construct a new ray.
198    pub fn new(origin: [f32; 3], direction: [f32; 3], max_t: f32) -> Self {
199        Self {
200            origin,
201            direction,
202            max_t,
203        }
204    }
205}
206
207// ============================================================================
208// BVH statistics types
209// ============================================================================
210
211/// Runtime statistics about a BVH tree.
212#[derive(Debug, Clone)]
213pub struct BvhStats {
214    /// Total number of nodes (internal + leaf).
215    pub node_count: usize,
216    /// Number of leaf nodes.
217    pub leaf_count: usize,
218    /// Number of internal nodes.
219    pub internal_count: usize,
220    /// Maximum tree depth.
221    pub max_depth: usize,
222    /// Total number of primitives stored across all leaves.
223    pub total_primitives: usize,
224    /// Average primitives per leaf.
225    pub avg_primitives_per_leaf: f32,
226}
227
228/// Extended BVH tree statistics including average fan-out.
229#[derive(Debug, Clone)]
230pub struct BvhTreeStatistics {
231    /// Total node count.
232    pub node_count: usize,
233    /// Number of leaf nodes.
234    pub leaf_count: usize,
235    /// Number of internal nodes.
236    pub internal_count: usize,
237    /// Maximum depth from root (1-indexed).
238    pub max_depth: usize,
239    /// Total number of primitives across all leaves.
240    pub total_primitives: usize,
241    /// Average number of children per internal node (fan-out).
242    /// For a binary tree this is at most 2.
243    pub avg_fanout: f32,
244    /// Total surface area of all leaf AABBs.
245    pub total_leaf_surface_area: f32,
246}
247
248// ============================================================================
249// Morton / LBVH types
250// ============================================================================
251
252/// LBVH primitive: AABB + Morton code.
253#[derive(Debug, Clone)]
254pub struct LbvhPrimitive {
255    /// Bounding box.
256    pub aabb: Aabb,
257    /// Caller-defined object ID.
258    pub object_id: usize,
259    /// 30-bit Morton code computed from the AABB centroid.
260    pub morton: u32,
261}
262
263/// A cluster of Morton-coded primitives, with a pre-computed bounding radius.
264#[derive(Debug, Clone)]
265pub struct MortonCluster {
266    /// Indices of the primitives in this cluster (into the parent slice).
267    pub indices: Vec<usize>,
268    /// Axis-aligned bounding box of the cluster.
269    pub aabb: Aabb,
270    /// Bounding sphere radius (centred at the AABB centre).
271    pub radius: f32,
272}
oxiphysics_gpu/bvh/types.rs

oxiphysics_gpu/bvh/
types.rs
