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