wisp/render/
scene_walk.rs

1//! Shared scene traversal + transform helpers (M-TEXT.0 / AUT-74).
2//!
3//! Before this module, `sprite_pipeline`, `graphics_pipeline`,
4//! `mesh_pipeline`, and `text_pipeline` each duplicated the same
5//! pre-order subtree walk: stack-based DFS, exclude-set filter,
6//! visibility skip, parent-world transform accumulation, and a local
7//! `mat3_to_mat4` helper. This module owns those mechanics so the
8//! upcoming text backends (`AtlasText`, `FlexibleText`) and any
9//! future pipeline pick them up for free.
10//!
11//! No behavior change: every existing pipeline calls
12//! [`walk_visible_subtree`] with the same `(id, node, world)` callback
13//! semantics it had before.
14
15use std::collections::HashSet;
16
17use glam::{Mat3, Mat4, Vec4};
18
19use crate::scene::{Node, NodeId, Stage};
20
21/// Walk every visible node in the subtree rooted at `start` in
22/// pre-order, calling `visit` with the node id, the borrowed
23/// [`Node`], and its world-space transform (parent's world × local).
24///
25/// Nodes whose ids are in `exclude` (and their descendants) are
26/// skipped entirely — used by the auto-dispatch advanced-blend
27/// renderer to walk the scene "minus" the dispatched subtrees.
28/// Invisible nodes (`container.visible = false`) skip themselves
29/// *and* their subtree, matching previous per-pipeline behavior.
30///
31/// Children are pushed in *reverse* insertion order so siblings pop
32/// in insertion order — locked-in z-order semantics.
33pub(crate) fn walk_visible_subtree<F>(
34    stage: &Stage,
35    start: NodeId,
36    exclude: &HashSet<NodeId>,
37    mut visit: F,
38) where
39    F: FnMut(NodeId, &Node, Mat4),
40{
41    let mut stack: Vec<(NodeId, Mat4)> = vec![(start, Mat4::IDENTITY)];
42    while let Some((id, parent_world)) = stack.pop() {
43        if exclude.contains(&id) {
44            continue;
45        }
46        let Some(node) = stage.get(id) else {
47            continue;
48        };
49        let container = node.container();
50        if !container.visible {
51            continue;
52        }
53        let local = mat3_to_mat4(container.transform.to_mat3());
54        let world = parent_world * local;
55
56        visit(id, node, world);
57
58        // Push children in reverse so siblings pop in insertion order.
59        for child in container.children().rev().collect::<Vec<_>>() {
60            stack.push((child, world));
61        }
62    }
63}
64
65/// Lift a 2-D affine [`Mat3`] into a 4-D homogeneous [`Mat4`] for
66/// the WGPU-side vertex shaders that consume `mat4`s.
67///
68/// Lives here instead of being copy-pasted in every pipeline.
69#[must_use]
70pub(crate) fn mat3_to_mat4(m: Mat3) -> Mat4 {
71    Mat4::from_cols(
72        Vec4::new(m.x_axis.x, m.x_axis.y, 0.0, 0.0),
73        Vec4::new(m.y_axis.x, m.y_axis.y, 0.0, 0.0),
74        Vec4::new(0.0, 0.0, 1.0, 0.0),
75        Vec4::new(m.z_axis.x, m.z_axis.y, 0.0, 1.0),
76    )
77}
78
79#[cfg(test)]
80mod tests {
81    use super::*;
82    use crate::scene::{Container, Stage};
83
84    #[test]
85    fn traversal_visits_every_visible_node_in_preorder() {
86        let mut stage = Stage::new();
87        let root = stage.root();
88        let a = stage.add_child(root, Container::default()).unwrap();
89        let b = stage.add_child(a, Container::default()).unwrap();
90        let c = stage.add_child(b, Container::default()).unwrap();
91        let d = stage.add_child(root, Container::default()).unwrap();
92
93        let mut order = Vec::new();
94        walk_visible_subtree(&stage, root, &HashSet::new(), |id, _, _| order.push(id));
95        assert_eq!(order, vec![root, a, b, c, d]);
96    }
97
98    #[test]
99    fn excluded_subtree_is_skipped() {
100        let mut stage = Stage::new();
101        let root = stage.root();
102        let a = stage.add_child(root, Container::default()).unwrap();
103        let b = stage.add_child(a, Container::default()).unwrap();
104        let _c = stage.add_child(b, Container::default()).unwrap();
105        let d = stage.add_child(root, Container::default()).unwrap();
106
107        let mut exclude = HashSet::new();
108        exclude.insert(a);
109
110        let mut order = Vec::new();
111        walk_visible_subtree(&stage, root, &exclude, |id, _, _| order.push(id));
112        // a, b, c never visited; root and d still are.
113        assert_eq!(order, vec![root, d]);
114    }
115
116    #[test]
117    fn invisible_node_skips_itself_and_descendants() {
118        let mut stage = Stage::new();
119        let root = stage.root();
120        let hidden_container = Container {
121            visible: false,
122            ..Container::default()
123        };
124        let hidden = stage.add_child(root, hidden_container).unwrap();
125        let _child_of_hidden = stage.add_child(hidden, Container::default()).unwrap();
126        let visible = stage.add_child(root, Container::default()).unwrap();
127
128        let mut order = Vec::new();
129        walk_visible_subtree(&stage, root, &HashSet::new(), |id, _, _| order.push(id));
130        assert_eq!(order, vec![root, visible]);
131    }
132
133    #[test]
134    fn world_transform_accumulates_along_chain() {
135        use crate::scene::Transform;
136        let mut stage = Stage::new();
137        let root = stage.root();
138        let child = Container {
139            transform: Transform {
140                position: glam::Vec2::new(0.5, 0.0),
141                ..Transform::default()
142            },
143            ..Container::default()
144        };
145        let cid = stage.add_child(root, child).unwrap();
146
147        let grand = Container {
148            transform: Transform {
149                position: glam::Vec2::new(0.5, 0.0),
150                ..Transform::default()
151            },
152            ..Container::default()
153        };
154        let gid = stage.add_child(cid, grand).unwrap();
155
156        let mut worlds = Vec::new();
157        walk_visible_subtree(&stage, root, &HashSet::new(), |id, _, world| {
158            worlds.push((id, world.w_axis));
159        });
160        // Grandchild's world translation = (0.5 + 0.5, 0).
161        let (id, w) = worlds.into_iter().find(|(id, _)| *id == gid).unwrap();
162        assert_eq!(id, gid);
163        assert!((w.x - 1.0).abs() < 1e-6);
164    }
165
166    #[test]
167    fn mat3_to_mat4_preserves_2d_affine_block() {
168        let m = Mat3::from_cols(
169            glam::Vec3::new(2.0, 0.0, 0.0),
170            glam::Vec3::new(0.0, 3.0, 0.0),
171            glam::Vec3::new(5.0, 7.0, 1.0),
172        );
173        let lifted = mat3_to_mat4(m);
174        // Top-left scale.
175        assert!((lifted.x_axis.x - 2.0).abs() < f32::EPSILON);
176        assert!((lifted.y_axis.y - 3.0).abs() < f32::EPSILON);
177        // Translation lands in z-axis (column 3 lower-left).
178        assert!((lifted.w_axis.x - 5.0).abs() < f32::EPSILON);
179        assert!((lifted.w_axis.y - 7.0).abs() < f32::EPSILON);
180        // z-axis identity.
181        assert!((lifted.z_axis.z - 1.0).abs() < f32::EPSILON);
182    }
183}
wisp/render/scene_walk.rs

wisp/render/
scene_walk.rs
