steel_worldgen/structure/
box_octree.rs

1//! Spatial index for jigsaw piece bounds. Port of `StructureLayoutOptimizer`'s
2//! `BoxOctree` — nearby-box queries instead of scanning every placed piece.
3
4use std::mem;
5
6use glam::IVec3;
7use steel_utils::BoundingBox;
8
9const SUBDIVIDE_THRESHOLD: usize = 10;
10const MAXIMUM_DEPTH: u32 = 3;
11
12/// Vanilla `AABB.of(BoundingBox).deflate(0.25)` in quarter-block fixed point.
13///
14/// Piece AABB uses `[min, max + 1)`; deflate shrinks each axis by `0.25` on both
15/// sides → `[min + 0.25, max + 0.75]`, encoded as `[min * 4 + 1, max * 4 + 3]`.
16#[derive(Clone, Copy, Debug, Eq, PartialEq)]
17pub(crate) struct DeflatedQuarters {
18    min_x: i32,
19    min_y: i32,
20    min_z: i32,
21    max_x: i32,
22    max_y: i32,
23    max_z: i32,
24}
25
26impl DeflatedQuarters {
27    #[inline]
28    pub(crate) const fn from_piece(bbox: BoundingBox) -> Self {
29        Self {
30            min_x: bbox.min_x() * 4 + 1,
31            min_y: bbox.min_y() * 4 + 1,
32            min_z: bbox.min_z() * 4 + 1,
33            max_x: bbox.max_x() * 4 + 3,
34            max_y: bbox.max_y() * 4 + 3,
35            max_z: bbox.max_z() * 4 + 3,
36        }
37    }
38
39    /// Vanilla boundary AABB is `[min, max + 1)` without deflate.
40    #[inline]
41    pub(crate) const fn boundary_from(bbox: BoundingBox) -> Self {
42        Self {
43            min_x: bbox.min_x() * 4,
44            min_y: bbox.min_y() * 4,
45            min_z: bbox.min_z() * 4,
46            max_x: bbox.max_x() * 4 + 4,
47            max_y: bbox.max_y() * 4 + 4,
48            max_z: bbox.max_z() * 4 + 4,
49        }
50    }
51
52    #[inline]
53    pub(crate) const fn is_empty(self) -> bool {
54        self.min_x >= self.max_x || self.min_y >= self.max_y || self.min_z >= self.max_z
55    }
56
57    #[inline]
58    pub(crate) const fn contains(self, inner: Self) -> bool {
59        self.min_x <= inner.min_x
60            && self.min_y <= inner.min_y
61            && self.min_z <= inner.min_z
62            && self.max_x >= inner.max_x
63            && self.max_y >= inner.max_y
64            && self.max_z >= inner.max_z
65    }
66
67    #[inline]
68    pub(crate) const fn intersects(self, other: Self) -> bool {
69        self.min_x < other.max_x
70            && self.max_x > other.min_x
71            && self.min_y < other.max_y
72            && self.max_y > other.min_y
73            && self.min_z < other.max_z
74            && self.max_z > other.min_z
75    }
76}
77
78/// Octree of axis-aligned boxes for fast intersection queries during jigsaw assembly.
79#[derive(Debug, Clone)]
80pub struct BoxOctree {
81    boundary: BoundingBox,
82    boundary_quarters: DeflatedQuarters,
83    size: IVec3,
84    depth: u32,
85    inner_boxes: Vec<StoredBox>,
86    children: Vec<BoxOctree>,
87}
88
89#[derive(Clone, Copy, Debug, Eq, PartialEq)]
90struct StoredBox {
91    bbox: BoundingBox,
92    deflated: DeflatedQuarters,
93}
94
95impl StoredBox {
96    const fn new(bbox: BoundingBox) -> Self {
97        Self {
98            bbox,
99            deflated: DeflatedQuarters::from_piece(bbox),
100        }
101    }
102}
103
104impl BoxOctree {
105    #[must_use]
106    pub fn new(boundary: BoundingBox) -> Self {
107        Self::with_depth(boundary, DeflatedQuarters::boundary_from(boundary), 0)
108    }
109
110    fn with_depth(
111        boundary: BoundingBox,
112        boundary_quarters: DeflatedQuarters,
113        parent_depth: u32,
114    ) -> Self {
115        let size = IVec3::new(
116            round_away_from_zero(boundary.width()),
117            round_away_from_zero(boundary.height()),
118            round_away_from_zero(boundary.depth()),
119        );
120        Self {
121            boundary,
122            boundary_quarters,
123            size,
124            depth: parent_depth + 1,
125            inner_boxes: Vec::new(),
126            children: Vec::new(),
127        }
128    }
129
130    #[inline]
131    pub fn add_box(&mut self, bbox: BoundingBox) {
132        if self.depth < MAXIMUM_DEPTH && self.inner_boxes.len() > SUBDIVIDE_THRESHOLD {
133            self.subdivide();
134        }
135
136        if !self.children.is_empty() {
137            for child in &mut self.children {
138                if child.boundary_intersects(bbox) {
139                    child.add_box(bbox);
140                }
141            }
142            return;
143        }
144
145        if self.inner_boxes.iter().any(|stored| stored.bbox == bbox) {
146            return;
147        }
148        self.inner_boxes.push(StoredBox::new(bbox));
149    }
150
151    /// Vanilla jigsaw placement uses `AABB.of(bb).deflate(0.25)` before collision checks.
152    #[inline]
153    pub fn within_bounds_but_not_intersecting_children(&self, candidate: BoundingBox) -> bool {
154        let deflated = DeflatedQuarters::from_piece(candidate);
155        if deflated.is_empty() {
156            return false;
157        }
158        self.boundary_quarters.contains(deflated) && !self.intersects_deflated(deflated, candidate)
159    }
160
161    #[inline]
162    fn intersects_deflated(&self, deflated: DeflatedQuarters, candidate: BoundingBox) -> bool {
163        if !self.children.is_empty() {
164            return self.children.iter().any(|child| {
165                child.boundary_quarters.intersects(deflated)
166                    && child.intersects_deflated(deflated, candidate)
167            });
168        }
169        self.inner_boxes
170            .iter()
171            .any(|stored| candidate.intersects(stored.bbox) && deflated.intersects(stored.deflated))
172    }
173
174    #[inline]
175    fn boundary_intersects(&self, candidate: BoundingBox) -> bool {
176        self.boundary.intersects(candidate)
177    }
178
179    fn subdivide(&mut self) {
180        assert!(
181            self.children.is_empty(),
182            "BoxOctree: tried to subdivide when children already exist"
183        );
184
185        let min = self.boundary.min_corner();
186        let max = self.boundary.max_corner();
187        let half_x = self.size.x / 2;
188        let half_y = self.size.y / 2;
189        let half_z = self.size.z / 2;
190
191        let child_bounds = [
192            BoundingBox::new(
193                IVec3::new(min.x, min.y, min.z),
194                IVec3::new(min.x + half_x, min.y + half_y, min.z + half_z),
195            ),
196            BoundingBox::new(
197                IVec3::new(min.x, min.y, min.z + half_z),
198                IVec3::new(min.x + half_x, min.y + half_y, max.z),
199            ),
200            BoundingBox::new(
201                IVec3::new(min.x + half_x, min.y, min.z),
202                IVec3::new(max.x, min.y + half_y, min.z + half_z),
203            ),
204            BoundingBox::new(
205                IVec3::new(min.x + half_x, min.y, min.z + half_z),
206                IVec3::new(max.x, min.y + half_y, max.z),
207            ),
208            BoundingBox::new(
209                IVec3::new(min.x, min.y + half_y, min.z),
210                IVec3::new(min.x + half_x, max.y, min.z + half_z),
211            ),
212            BoundingBox::new(
213                IVec3::new(min.x, min.y + half_y, min.z + half_z),
214                IVec3::new(min.x + half_x, max.y, max.z),
215            ),
216            BoundingBox::new(
217                IVec3::new(min.x + half_x, min.y + half_y, min.z),
218                IVec3::new(max.x, max.y, min.z + half_z),
219            ),
220            BoundingBox::new(
221                IVec3::new(min.x + half_x, min.y + half_y, min.z + half_z),
222                IVec3::new(max.x, max.y, max.z),
223            ),
224        ];
225
226        self.children = child_bounds
227            .into_iter()
228            .map(|boundary| {
229                Self::with_depth(
230                    boundary,
231                    DeflatedQuarters::boundary_from(boundary),
232                    self.depth,
233                )
234            })
235            .collect();
236
237        let inner_boxes = mem::take(&mut self.inner_boxes);
238        for stored in inner_boxes {
239            for child in &mut self.children {
240                if child.boundary_intersects(stored.bbox) {
241                    child.add_box(stored.bbox);
242                }
243            }
244        }
245    }
246}
247
248const fn round_away_from_zero(value: i32) -> i32 {
249    if value >= 0 { value } else { -value }
250}
251
252#[cfg(test)]
253mod tests {
254    use super::*;
255
256    #[test]
257    fn distant_boxes_do_not_collide() {
258        let boundary = BoundingBox::new(IVec3::ZERO, IVec3::new(100, 100, 100));
259        let mut tree = BoxOctree::new(boundary);
260        tree.add_box(BoundingBox::new(IVec3::ZERO, IVec3::new(5, 5, 5)));
261        tree.add_box(BoundingBox::new(
262            IVec3::new(50, 50, 50),
263            IVec3::new(55, 55, 55),
264        ));
265
266        let candidate = BoundingBox::new(IVec3::new(10, 10, 10), IVec3::new(15, 15, 15));
267        assert!(tree.within_bounds_but_not_intersecting_children(candidate));
268    }
269
270    #[test]
271    fn nearby_boxes_collide() {
272        let boundary = BoundingBox::new(IVec3::ZERO, IVec3::new(100, 100, 100));
273        let mut tree = BoxOctree::new(boundary);
274        tree.add_box(BoundingBox::new(IVec3::ZERO, IVec3::new(5, 5, 5)));
275
276        let candidate = BoundingBox::new(IVec3::new(4, 4, 4), IVec3::new(8, 8, 8));
277        assert!(!tree.within_bounds_but_not_intersecting_children(candidate));
278    }
279}
steel_worldgen/structure/box_octree.rs

steel_worldgen/structure/
box_octree.rs
