euv_engine/spatial/struct.rs
1use super::*;
2
3/// A uniform-grid spatial hash for broad-phase collision culling in 2D.
4///
5/// Bodies are inserted by their world-space axis-aligned bounding box.
6/// A query returns all candidate indices whose AABBs overlap the query region,
7/// dramatically reducing narrow-phase collision checks from O(n²) to near O(n).
8#[derive(Clone, Data, Debug, New, PartialEq)]
9pub struct SpatialHashGrid2D {
10 /// The world-space size of each grid cell.
11 #[get(type(copy))]
12 #[get_mut(pub(crate))]
13 #[set(pub(crate))]
14 pub(crate) cell_size: f64,
15 /// The inverse of `cell_size`, precomputed for fast coordinate-to-cell hashing.
16 #[get(type(copy))]
17 #[set(pub(crate))]
18 #[new(skip)]
19 #[get(pub(crate))]
20 #[get_mut(pub(crate))]
21 pub(crate) inverse_cell_size: f64,
22 /// The hash map from cell key to the list of body indices occupying that cell.
23 #[get_mut(pub(crate))]
24 #[new(skip)]
25 pub(crate) cells: SpatialCellMap2D,
26}
27
28/// A uniform-grid spatial hash for broad-phase collision culling in 3D.
29///
30/// Bodies are inserted by their world-space axis-aligned bounding box.
31/// A query returns all candidate indices whose AABBs overlap the query region,
32/// dramatically reducing narrow-phase collision checks from O(n²) to near O(n).
33#[derive(Clone, Data, Debug, New, PartialEq)]
34pub struct SpatialHashGrid3D {
35 /// The world-space size of each grid cell.
36 #[get(type(copy))]
37 #[get_mut(pub(crate))]
38 #[set(pub(crate))]
39 pub(crate) cell_size: f64,
40 /// The inverse of `cell_size`, precomputed for fast coordinate-to-cell hashing.
41 #[get(type(copy))]
42 #[set(pub(crate))]
43 #[new(skip)]
44 #[get(pub(crate))]
45 #[get_mut(pub(crate))]
46 pub(crate) inverse_cell_size: f64,
47 /// The hash map from cell key to the list of body indices occupying that cell.
48 #[get_mut(pub(crate))]
49 #[new(skip)]
50 pub(crate) cells: SpatialCellMap3D,
51}
52
53/// One inserted body inside a 2D quadtree, stored with its exact
54/// world-space axis-aligned bounding box.
55///
56/// Carrying the box is what makes the structure a *correct* broad phase: a
57/// quadtree query prunes whole nodes by region overlap, then confirms each
58/// surviving candidate with an exact box-vs-box test instead of reporting
59/// every body that merely shares a node.
60#[derive(Clone, Copy, Data, Debug, New, PartialEq)]
61pub struct QuadTreeEntry2D {
62 /// The caller-owned body index, returned verbatim by queries.
63 #[get(type(copy))]
64 pub(crate) index: usize,
65 /// The minimum corner of the body's world-space bounding box.
66 #[get(type(copy))]
67 #[get_mut(pub(crate))]
68 #[set(pub(crate))]
69 pub(crate) min: Vector2D,
70 /// The maximum corner of the body's world-space bounding box.
71 #[get(type(copy))]
72 #[get_mut(pub(crate))]
73 #[set(pub(crate))]
74 pub(crate) max: Vector2D,
75}
76
77/// One node of the 2D quadtree, holding an axis-aligned region plus the
78/// entries that could not be pushed further down.
79///
80/// A node has either four child handles (subdivided) or none (leaf); children
81/// live in the parent's flat arena rather than behind `Box` pointers, so every
82/// node is reachable through a single shared borrow and the structure stays
83/// `Clone`/`Debug` derivable without interior mutability.
84#[derive(Clone, Data, Debug, New, PartialEq)]
85pub struct QuadTreeNode2D {
86 /// The minimum corner of the region this node covers.
87 #[get(type(copy))]
88 #[get_mut(pub(crate))]
89 #[set(pub(crate))]
90 pub(crate) min: Vector2D,
91 /// The maximum corner of the region this node covers.
92 #[get(type(copy))]
93 #[get_mut(pub(crate))]
94 #[set(pub(crate))]
95 pub(crate) max: Vector2D,
96 /// The subdivision level, `0` at the root and incrementing per split.
97 #[get(type(copy))]
98 #[get_mut(pub(crate))]
99 #[set(pub(crate))]
100 pub(crate) depth: usize,
101 /// The child node handles, all unset until the node subdivides.
102 #[set(pub(crate))]
103 #[get_mut(pub(crate))]
104 pub(crate) children: QuadTreeChildren2D,
105 /// A flag that is `true` once the node owns four valid child handles.
106 #[get(type(copy))]
107 #[set(pub(crate))]
108 pub(crate) leaf: bool,
109 /// A flag that is `true` once this node retains an entry which is not fully
110 /// contained by the node's own region.
111 ///
112 /// Such an entry stays in the parent forever, so a region-overlap prune is
113 /// unsound for this node: the body can sit entirely outside the node's
114 /// region and still overlap a query. Marking the node `loose` makes the
115 /// query skip the region prune and fall back to the exact box test, which
116 /// is what keeps a body larger than the root region findable.
117 #[get(type(copy))]
118 #[set(pub(crate))]
119 pub(crate) loose: bool,
120 /// The entries stored directly in this node, including any body that is
121 /// too large for, or straddles the boundary of, a single child region.
122 #[set(pub(crate))]
123 pub(crate) entries: QuadTreeEntryList2D,
124}
125
126/// A 2D quadtree broad-phase acceleration structure, interface-compatible
127/// with [`SpatialHashGrid2D`].
128///
129/// Bodies are inserted by their world-space axis-aligned bounding box. A node
130/// subdivides into four children once its entry count exceeds the capacity and
131/// its depth is below the maximum; an entry whose box straddles a split
132/// boundary stays in the parent node, so no body is ever duplicated and every
133/// query visits each body exactly once.
134///
135/// Unlike the uniform grid, the quadtree concentrates resolution where bodies
136/// are dense, which makes it the better structure for scenes with strongly
137/// clustered content. A body larger than the root region is still inserted and
138/// still returned by every query overlapping it — it simply resides at the
139/// root and is confirmed by its exact box test.
140#[derive(Clone, Data, Debug, PartialEq)]
141pub struct QuadTree2D {
142 /// The arena of all live nodes; node 0 is always the root.
143 #[get_mut(pub(crate))]
144 #[set(pub(crate))]
145 pub(crate) nodes: QuadTreeNodeList2D,
146 /// The number of entries a node may hold before subdividing.
147 #[get(type(copy))]
148 #[get_mut(pub(crate))]
149 pub(crate) capacity: usize,
150 /// The deepest subdivision level a node may reach.
151 #[get(pub(crate), type(copy))]
152 #[get_mut(pub(crate))]
153 #[set(pub(crate))]
154 pub(crate) max_depth: usize,
155 /// The total number of inserted bodies across every node.
156 #[get(pub(crate), type(copy))]
157 #[set(pub(crate))]
158 #[get_mut(pub(crate))]
159 pub(crate) count: usize,
160}