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 cell_size: f64,
15 /// The inverse of `cell_size`, precomputed for fast coordinate-to-cell hashing.
16 #[get(type(copy), pub(crate))]
17 #[set(pub(crate))]
18 #[new(skip)]
19 #[get_mut(pub(crate))]
20 pub(crate) inverse_cell_size: f64,
21 /// The hash map from cell key to the list of body indices occupying that cell.
22 #[get_mut(pub(crate))]
23 #[new(skip)]
24 #[set(pub(crate))]
25 pub 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 cell_size: f64,
40 /// The inverse of `cell_size`, precomputed for fast coordinate-to-cell hashing.
41 #[get(type(copy), pub(crate))]
42 #[set(pub(crate))]
43 #[new(skip)]
44 #[get_mut(pub(crate))]
45 pub(crate) inverse_cell_size: f64,
46 /// The hash map from cell key to the list of body indices occupying that cell.
47 #[get_mut(pub(crate))]
48 #[new(skip)]
49 #[set(pub(crate))]
50 pub 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 #[set(pub(crate))]
65 #[get_mut(pub(crate))]
66 pub index: usize,
67 /// The minimum corner of the body's world-space bounding box.
68 #[get(type(copy))]
69 #[get_mut(pub(crate))]
70 #[set(pub(crate))]
71 pub min: Vector2D,
72 /// The maximum corner of the body's world-space bounding box.
73 #[get(type(copy))]
74 #[get_mut(pub(crate))]
75 #[set(pub(crate))]
76 pub max: Vector2D,
77}
78
79/// One node of the 2D quadtree, holding an axis-aligned region plus the
80/// entries that could not be pushed further down.
81///
82/// A node has either four child handles (subdivided) or none (leaf); children
83/// live in the parent's flat arena rather than behind `Box` pointers, so every
84/// node is reachable through a single shared borrow and the structure stays
85/// `Clone`/`Debug` derivable without interior mutability.
86#[derive(Clone, Data, Debug, New, PartialEq)]
87pub struct QuadTreeNode2D {
88 /// The minimum corner of the region this node covers.
89 #[get(type(copy))]
90 #[get_mut(pub(crate))]
91 #[set(pub(crate))]
92 pub min: Vector2D,
93 /// The maximum corner of the region this node covers.
94 #[get(type(copy))]
95 #[get_mut(pub(crate))]
96 #[set(pub(crate))]
97 pub max: Vector2D,
98 /// The subdivision level, `0` at the root and incrementing per split.
99 #[get(type(copy))]
100 #[get_mut(pub(crate))]
101 #[set(pub(crate))]
102 pub depth: usize,
103 /// The child node handles, all unset until the node subdivides.
104 #[set(pub(crate))]
105 #[get_mut(pub(crate))]
106 pub children: QuadTreeChildren2D,
107 /// A flag that is `true` once the node owns four valid child handles.
108 #[get(type(copy))]
109 #[set(pub(crate))]
110 #[get_mut(pub(crate))]
111 pub leaf: bool,
112 /// A flag that is `true` once this node retains an entry which is not fully
113 /// contained by the node's own region.
114 ///
115 /// Such an entry stays in the parent forever, so a region-overlap prune is
116 /// unsound for this node: the body can sit entirely outside the node's
117 /// region and still overlap a query. Marking the node `loose` makes the
118 /// query skip the region prune and fall back to the exact box test, which
119 /// is what keeps a body larger than the root region findable.
120 #[get(type(copy))]
121 #[set(pub(crate))]
122 #[get_mut(pub(crate))]
123 pub loose: bool,
124 /// The entries stored directly in this node, including any body that is
125 /// too large for, or straddles the boundary of, a single child region.
126 #[set(pub(crate))]
127 #[get(pub(crate))]
128 #[get_mut(pub(crate))]
129 pub(crate) entries: QuadTreeEntryList2D,
130}
131
132/// A 2D quadtree broad-phase acceleration structure, interface-compatible
133/// with [`SpatialHashGrid2D`].
134///
135/// Bodies are inserted by their world-space axis-aligned bounding box. A node
136/// subdivides into four children once its entry count exceeds the capacity and
137/// its depth is below the maximum; an entry whose box straddles a split
138/// boundary stays in the parent node, so no body is ever duplicated and every
139/// query visits each body exactly once.
140///
141/// Unlike the uniform grid, the quadtree concentrates resolution where bodies
142/// are dense, which makes it the better structure for scenes with strongly
143/// clustered content. A body larger than the root region is still inserted and
144/// still returned by every query overlapping it — it simply resides at the
145/// root and is confirmed by its exact box test.
146#[derive(Clone, Data, Debug, PartialEq)]
147pub struct QuadTree2D {
148 /// The arena of all live nodes; node 0 is always the root.
149 #[get_mut(pub(crate))]
150 #[set(pub(crate))]
151 pub nodes: QuadTreeNodeList2D,
152 /// The number of entries a node may hold before subdividing.
153 #[get(type(copy))]
154 #[get_mut(pub(crate))]
155 #[set(pub(crate))]
156 pub capacity: usize,
157 /// The deepest subdivision level a node may reach.
158 #[get(pub(crate), type(copy))]
159 #[get_mut(pub(crate))]
160 pub max_depth: usize,
161 /// The total number of inserted bodies across every node.
162 #[get(type(copy))]
163 #[set(pub(crate))]
164 #[get_mut(pub(crate))]
165 pub count: usize,
166}