1use crate::transform::*;
4use glam::{Mat3, Mat4};
5use hecs::{Bundle, Entity, World};
6use std::{
7 collections::{HashMap, HashSet},
8 fmt,
9 ops::Mul,
10};
11
12#[derive(Clone, Copy, Debug, PartialEq, Eq)]
14pub enum HierarchyError {
15 MissingEntity(Entity),
17 Cycle(Entity),
19 DimensionMismatch(Entity),
21}
22
23impl fmt::Display for HierarchyError {
24 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
25 match self {
26 Self::MissingEntity(e) => write!(f, "missing scene entity {e:?}"),
27 Self::Cycle(e) => write!(f, "cycle in scene hierarchy at {e:?}"),
28 Self::DimensionMismatch(e) => write!(f, "incompatible or missing transform at {e:?}"),
29 }
30 }
31}
32
33impl std::error::Error for HierarchyError {}
34
35struct Node<M> {
36 local: M,
37 parent: Option<Entity>,
38 global: Option<M>,
39 visiting: bool,
40}
41
42#[derive(Default)]
59pub struct Scene {
60 pub world: World,
62 nodes_2d: HashMap<Entity, Node<Mat3>>,
63 nodes_3d: HashMap<Entity, Node<Mat4>>,
64 entities: Vec<Entity>,
65 path: Vec<Entity>,
66}
67
68impl Scene {
69 pub fn new() -> Self {
71 Self::default()
72 }
73
74 pub fn spawn_2d(&mut self, transform: Transform2D, components: impl Bundle) -> Entity {
76 let entity = self.world.spawn(components);
77 self.world
78 .insert(entity, (transform, GlobalTransform2D(transform.matrix())))
79 .expect("newly spawned entity exists");
80 entity
81 }
82
83 pub fn spawn_3d(&mut self, transform: Transform3D, components: impl Bundle) -> Entity {
85 let entity = self.world.spawn(components);
86 self.world
87 .insert(entity, (transform, GlobalTransform3D(transform.matrix())))
88 .expect("newly spawned entity exists");
89 entity
90 }
91
92 pub fn set_parent(
95 &mut self,
96 child: Entity,
97 parent: Option<Entity>,
98 ) -> Result<(), HierarchyError> {
99 self.require_entity(child)?;
100 if let Some(parent) = parent {
101 self.require_entity(parent)?;
102 let child_dim = self.dimension(child);
103 if child_dim == 0 || self.dimension(parent) != child_dim {
104 return Err(HierarchyError::DimensionMismatch(parent));
105 }
106 let mut seen = HashSet::new();
107 seen.insert(child);
108 let mut current = Some(parent);
109 while let Some(entity) = current {
110 self.require_entity(entity)?;
111 if !seen.insert(entity) {
112 return Err(HierarchyError::Cycle(entity));
113 }
114 current = self.world.get::<&Parent>(entity).ok().map(|p| p.0);
115 }
116 self.world
117 .insert_one(child, Parent(parent))
118 .expect("validated child");
119 } else {
120 let _ = self.world.remove_one::<Parent>(child);
121 }
122 Ok(())
123 }
124
125 pub fn despawn(&mut self, entity: Entity) -> Result<(), hecs::NoSuchEntity> {
127 let children: Vec<_> = self
128 .world
129 .query::<(Entity, &Parent)>()
130 .iter()
131 .filter_map(|(e, p)| (p.0 == entity).then_some(e))
132 .collect();
133 self.world.despawn(entity)?;
134 for child in children {
135 let _ = self.world.remove_one::<Parent>(child);
136 }
137 Ok(())
138 }
139
140 pub fn propagate(&mut self) -> Result<(), HierarchyError> {
144 if self.world.query::<&Parent>().iter().next().is_none() {
147 for (local, global) in self
148 .world
149 .query_mut::<(&Transform2D, &mut GlobalTransform2D)>()
150 {
151 global.0 = local.matrix();
152 }
153 for (local, global) in self
154 .world
155 .query_mut::<(&Transform3D, &mut GlobalTransform3D)>()
156 {
157 global.0 = local.matrix();
158 }
159 return Ok(());
160 }
161 self.nodes_2d.clear();
162 self.nodes_3d.clear();
163 for (entity, transform, parent) in self
164 .world
165 .query::<(Entity, &Transform2D, Option<&Parent>)>()
166 .iter()
167 {
168 self.nodes_2d.insert(
169 entity,
170 Node {
171 local: transform.matrix(),
172 parent: parent.map(|p| p.0),
173 global: None,
174 visiting: false,
175 },
176 );
177 }
178 for (entity, transform, parent) in self
179 .world
180 .query::<(Entity, &Transform3D, Option<&Parent>)>()
181 .iter()
182 {
183 self.nodes_3d.insert(
184 entity,
185 Node {
186 local: transform.matrix(),
187 parent: parent.map(|p| p.0),
188 global: None,
189 visiting: false,
190 },
191 );
192 }
193 resolve(
194 &self.world,
195 &mut self.nodes_2d,
196 &mut self.entities,
197 &mut self.path,
198 Mat3::IDENTITY,
199 )?;
200 resolve(
201 &self.world,
202 &mut self.nodes_3d,
203 &mut self.entities,
204 &mut self.path,
205 Mat4::IDENTITY,
206 )?;
207 for (entity, global) in self
208 .world
209 .query::<(Entity, &mut GlobalTransform2D)>()
210 .iter()
211 {
212 if let Some(node) = self.nodes_2d.get(&entity) {
213 global.0 = node.global.expect("resolved node");
214 }
215 }
216 for (entity, global) in self
217 .world
218 .query::<(Entity, &mut GlobalTransform3D)>()
219 .iter()
220 {
221 if let Some(node) = self.nodes_3d.get(&entity) {
222 global.0 = node.global.expect("resolved node");
223 }
224 }
225 Ok(())
226 }
227
228 fn require_entity(&self, entity: Entity) -> Result<(), HierarchyError> {
229 if self.world.contains(entity) {
230 Ok(())
231 } else {
232 Err(HierarchyError::MissingEntity(entity))
233 }
234 }
235
236 fn dimension(&self, entity: Entity) -> u8 {
237 u8::from(self.world.get::<&Transform2D>(entity).is_ok())
238 + 2 * u8::from(self.world.get::<&Transform3D>(entity).is_ok())
239 }
240}
241
242fn resolve<M: Copy + Mul<Output = M>>(
243 world: &World,
244 nodes: &mut HashMap<Entity, Node<M>>,
245 entities: &mut Vec<Entity>,
246 path: &mut Vec<Entity>,
247 identity: M,
248) -> Result<(), HierarchyError> {
249 entities.clear();
250 entities.extend(nodes.keys().copied());
251 for &entity in entities.iter() {
252 path.clear();
253 let mut current = entity;
254 let mut matrix = loop {
255 let node = nodes.get_mut(¤t).ok_or_else(|| {
256 if world.contains(current) {
257 HierarchyError::DimensionMismatch(current)
258 } else {
259 HierarchyError::MissingEntity(current)
260 }
261 })?;
262 if let Some(global) = node.global {
263 break global;
264 }
265 if node.visiting {
266 return Err(HierarchyError::Cycle(current));
267 }
268 node.visiting = true;
269 path.push(current);
270 if let Some(parent) = node.parent {
271 current = parent;
272 } else {
273 break identity;
274 }
275 };
276 for &child in path.iter().rev() {
277 let node = nodes.get_mut(&child).expect("visited node exists");
278 matrix = matrix * node.local;
279 node.global = Some(matrix);
280 node.visiting = false;
281 }
282 }
283 Ok(())
284}
285
286#[cfg(test)]
287mod tests {
288 use super::*;
289 use glam::{Vec2, Vec3};
290
291 #[test]
292 fn parent_rotation_and_scale_affect_child_translation() {
293 let mut scene = Scene::new();
294 let root = scene.spawn_2d(
295 Transform2D {
296 position: Vec2::new(10.0, 0.0),
297 rotation: std::f32::consts::FRAC_PI_2,
298 scale: Vec2::splat(2.0),
299 },
300 (),
301 );
302 let child = scene.spawn_2d(Transform2D::at(Vec2::X), ());
303 scene.set_parent(child, Some(root)).unwrap();
304 scene.propagate().unwrap();
305 let global = scene.world.get::<&GlobalTransform2D>(child).unwrap();
306 assert!(
307 global
308 .0
309 .transform_point2(Vec2::ZERO)
310 .abs_diff_eq(Vec2::new(10.0, 2.0), 0.00001)
311 );
312 }
313
314 #[test]
315 fn cycle_and_dimension_edits_are_atomic() {
316 let mut scene = Scene::new();
317 let a = scene.spawn_2d(Transform2D::default(), ());
318 let b = scene.spawn_2d(Transform2D::default(), ());
319 let c = scene.spawn_3d(Transform3D::default(), ());
320 scene.set_parent(b, Some(a)).unwrap();
321 assert!(matches!(
322 scene.set_parent(a, Some(b)),
323 Err(HierarchyError::Cycle(_))
324 ));
325 assert!(scene.world.get::<&Parent>(a).is_err());
326 assert!(matches!(
327 scene.set_parent(b, Some(c)),
328 Err(HierarchyError::DimensionMismatch(_))
329 ));
330 assert_eq!(scene.world.get::<&Parent>(b).unwrap().0, a);
331 }
332
333 #[test]
334 fn raw_cycles_and_stale_parents_are_reported() {
335 let mut scene = Scene::new();
336 let a = scene.spawn_3d(Transform3D::at(Vec3::X), ());
337 let b = scene.spawn_3d(Transform3D::at(Vec3::Y), ());
338 scene.world.insert_one(a, Parent(b)).unwrap();
339 scene.world.insert_one(b, Parent(a)).unwrap();
340 assert!(matches!(scene.propagate(), Err(HierarchyError::Cycle(_))));
341 scene.world.despawn(b).unwrap();
342 assert_eq!(scene.propagate(), Err(HierarchyError::MissingEntity(b)));
343 }
344
345 #[test]
346 fn despawn_detaches_children_and_reused_ids_do_not_reparent() {
347 let mut scene = Scene::new();
348 let root = scene.spawn_2d(Transform2D::at(Vec2::splat(5.0)), ());
349 let child = scene.spawn_2d(Transform2D::at(Vec2::ONE), ());
350 scene.set_parent(child, Some(root)).unwrap();
351 scene.despawn(root).unwrap();
352 scene.spawn_2d(Transform2D::at(Vec2::splat(100.0)), ());
353 scene.propagate().unwrap();
354 assert_eq!(
355 scene
356 .world
357 .get::<&GlobalTransform2D>(child)
358 .unwrap()
359 .0
360 .transform_point2(Vec2::ZERO),
361 Vec2::ONE
362 );
363 }
364
365 #[test]
366 fn deep_hierarchies_do_not_use_the_call_stack() {
367 let mut scene = Scene::new();
368 let mut parent = scene.spawn_3d(Transform3D::at(Vec3::X), ());
369 for _ in 0..5000 {
371 let child = scene.spawn_3d(Transform3D::at(Vec3::X), (Parent(parent),));
372 parent = child;
373 }
374 scene.propagate().unwrap();
375 assert_eq!(
376 scene
377 .world
378 .get::<&GlobalTransform3D>(parent)
379 .unwrap()
380 .0
381 .transform_point3(Vec3::ZERO)
382 .x,
383 5001.0
384 );
385 }
386
387 #[test]
388 fn removing_the_last_parent_keeps_both_dimensions_current() {
389 let mut scene = Scene::new();
390 let root = scene.spawn_2d(Transform2D::at(Vec2::splat(20.0)), ());
391 let child = scene.spawn_2d(Transform2D::at(Vec2::ONE), ());
392 let three = scene.spawn_3d(Transform3D::at(Vec3::ONE), ());
393 scene.set_parent(child, Some(root)).unwrap();
394 scene.propagate().unwrap();
395 scene.set_parent(child, None).unwrap();
396 scene.world.get::<&mut Transform2D>(child).unwrap().position = Vec2::splat(3.0);
397 scene.world.get::<&mut Transform3D>(three).unwrap().position = Vec3::splat(4.0);
398 scene.propagate().unwrap();
399 assert_eq!(
400 scene
401 .world
402 .get::<&GlobalTransform2D>(child)
403 .unwrap()
404 .0
405 .transform_point2(Vec2::ZERO),
406 Vec2::splat(3.0)
407 );
408 assert_eq!(
409 scene
410 .world
411 .get::<&GlobalTransform3D>(three)
412 .unwrap()
413 .0
414 .transform_point3(Vec3::ZERO),
415 Vec3::splat(4.0)
416 );
417 }
418}