nsi_intermediate/resolve/chain.rs
1//! Walking the graph: a geometry's chain to `.root`, and the
2//! placements a multi-parent geometry has.
3//!
4//! ɴsɪ's scene graph is a DAG, and every other answer in this module
5//! starts by asking which nodes stand between a geometry and the
6//! root.
7
8use super::*;
9
10/// One entry of a chain walk, and how it reached its parent.
11pub(super) struct ChainLink {
12 pub(super) handle: String,
13 /// The step to the parent was a `sourcemodels` connection.
14 pub(super) via_instancer: bool,
15}
16
17impl Scene {
18 /// The chain from `handle` up to and including `.root`, nearest
19 /// first.
20 ///
21 /// `.root` *is* an entry. ɴsɪ gathers attributes "until the scene
22 /// root is reached", and describes the root as "much like a
23 /// transform node" with its own `objects` and `geometryattributes`,
24 /// so a scene-wide `attributes` node bound to it must be found.
25 ///
26 /// Every walk up the `objects` hierarchy goes through here, so the
27 /// scenes with no single answer -- more than one parent, a cycle, a
28 /// node that never reaches the root -- are rejected in one place
29 /// rather than each caller re-deriving them.
30 pub(super) fn chain(
31 &self,
32 handle: &str,
33 ) -> Result<Vec<String>, ResolveError> {
34 Ok(self
35 .linked_chain(handle, true)?
36 .into_iter()
37 .map(|link| link.handle)
38 .collect())
39 }
40
41 /// The chain, refusing to pass through an `instances` node.
42 ///
43 /// Attribute gathering continues through one; transform composition
44 /// cannot, because an `instances` node holds one matrix per
45 /// instance rather than one for the prototype.
46 pub(super) fn transform_chain(
47 &self,
48 handle: &str,
49 ) -> Result<Vec<String>, ResolveError> {
50 Ok(self
51 .linked_chain(handle, false)?
52 .into_iter()
53 .map(|link| link.handle)
54 .collect())
55 }
56
57 /// The chain, recording for each entry whether the step to its
58 /// parent was an `instances` connection rather than a transform.
59 ///
60 /// [`Scene::relative_transform`] needs that: an `instances` node's
61 /// own matrix is not the prototype's, so a composition may not cross
62 /// one even when the walk may.
63 pub(super) fn linked_chain(
64 &self,
65 handle: &str,
66 through_instances: bool,
67 ) -> Result<Vec<ChainLink>, ResolveError> {
68 let mut chain = Vec::new();
69 let mut seen = HashSet::new();
70 let mut current = handle.to_string();
71
72 loop {
73 if !seen.insert(current.clone()) {
74 return Err(ResolveError::Cycle { handle: current });
75 }
76
77 if current == crate::ROOT {
78 chain.push(ChainLink {
79 handle: current,
80 via_instancer: false,
81 });
82 break;
83 }
84
85 // ɴsɪ gathers "through all the transform nodes it is
86 // connected to", so a direct placement is the path. An
87 // `instances` connection is only the way up when there is no
88 // direct one -- a prototype may be both, and that is not
89 // ambiguous.
90 let mut scene_parents = self
91 .edges_from(¤t)
92 .filter(|edge| edge.kind == EdgeKind::SceneMember);
93
94 let first = match scene_parents.next() {
95 Some(edge) => {
96 if let Some(second) = scene_parents.next() {
97 // ɴsɪ's lightweight instancing: one world
98 // transform per path, so no single answer.
99 let parents = [edge, second]
100 .into_iter()
101 .chain(scene_parents)
102 .map(|edge| edge.to().to_string())
103 .collect();
104 return Err(ResolveError::MultipleParents {
105 handle: current,
106 parents,
107 });
108 }
109 edge
110 }
111 None => {
112 // Reached only through an `instances` node, if at
113 // all.
114 let mut instancers = self
115 .edges_from(¤t)
116 .filter(|edge| edge.kind == EdgeKind::InstanceSource);
117
118 let Some(instancer) = instancers.next() else {
119 return Err(ResolveError::Detached { handle: current });
120 };
121
122 if !through_instances {
123 // An `instances` node holds one matrix per
124 // instance, not one for the prototype.
125 return Err(ResolveError::Instanced {
126 instancer: instancer.to().to_string(),
127 });
128 }
129
130 if let Some(second) = instancers.next() {
131 let parents = [instancer, second]
132 .into_iter()
133 .chain(instancers)
134 .map(|edge| edge.to().to_string())
135 .collect();
136 return Err(ResolveError::MultipleParents {
137 handle: current,
138 parents,
139 });
140 }
141
142 instancer
143 }
144 };
145
146 let parent = first.to().to_string();
147 chain.push(ChainLink {
148 handle: current,
149 via_instancer: first.kind == EdgeKind::InstanceSource,
150 });
151 current = parent;
152 }
153
154 Ok(chain)
155 }
156
157 /// Compose the transform chain applying to `handle`, from the node
158 /// itself up to `.root`.
159 ///
160 /// Includes `handle`'s own matrix when it carries one, so asking
161 /// about a transform and asking about its child differ by exactly
162 /// that node's matrix.
163 ///
164 /// Non-`f64` matrices are ignored: ɴsɪ's `transformationmatrix` is
165 /// documented as `doublematrix`, and silently reinterpreting an
166 /// `f32` one would be worse than skipping it.
167 ///
168 /// # Errors
169 ///
170 /// Every variant of [`ResolveError`]. Each is a scene with no single
171 /// correct world transform, and each would otherwise be answered
172 /// with a plausible wrong matrix.
173 pub fn world_transform(
174 &self,
175 handle: &str,
176 ) -> Result<[f64; 16], ResolveError> {
177 let chain = self.transform_chain(handle)?;
178 self.compose_along(&chain)
179 }
180
181 /// The node for `handle`, or `None` for a reserved handle nothing
182 /// has been set on yet.
183 ///
184 /// `.root` and `.global` exist whether or not they were created, so
185 /// they have no samples rather than being unknown. Without this the
186 /// answer flipped between `Err` and `Ok` depending on whether some
187 /// unrelated attribute had been set on `.root` first, and the error
188 /// text claimed no node was named `.root`.
189 pub(super) fn existing_node(
190 &self,
191 handle: &str,
192 ) -> Result<Option<&Node>, ResolveError> {
193 match self.node(handle) {
194 Some(node) => Ok(Some(node)),
195 None if crate::is_reserved(handle) => Ok(None),
196 None => Err(ResolveError::UnknownHandle {
197 handle: handle.to_string(),
198 }),
199 }
200 }
201
202 /// Compose the transforms along an already-walked path.
203 ///
204 /// The one composition [`Scene::world_transform`] and
205 /// [`Scene::placements`] both use, so the two cannot disagree about
206 /// multiplication order or about refusing a sampled node -- it was
207 /// a copy of this fold, and a reversed `mul` in the copy went
208 /// unnoticed because every placement fixture used translations,
209 /// which commute.
210 pub(super) fn compose_along(
211 &self,
212 path: &[String],
213 ) -> Result<[f64; 16], ResolveError> {
214 path.iter().try_fold(IDENTITY, |matrix, node| {
215 if self.has_motion_transform(node) {
216 Err(ResolveError::MotionSampledTransform {
217 handle: node.clone(),
218 })
219 } else {
220 Ok(match self.local_transform(node) {
221 Some(local) => mul(matrix, local),
222 None => matrix,
223 })
224 }
225 })
226 }
227
228 /// Every way `geometry` is placed in the scene.
229 ///
230 /// [`Scene::world_transform`] and [`Scene::geometry_binding`]
231 /// answer for *the* path and refuse a node with more than one
232 /// parent, because there is no single answer. This enumerates them
233 /// instead: one [`Placement`] per path, in the order the parents
234 /// were connected, each with the transform and the binding resolved
235 /// along that path.
236 ///
237 /// A singly-placed geometry yields exactly one placement, agreeing
238 /// with those two methods, so a backend can use this alone.
239 ///
240 /// # Errors
241 ///
242 /// [`ResolveError::Cycle`] for a path that revisits a node, and
243 /// [`ResolveError::Detached`] for a geometry that reaches no root
244 /// at all. A node reached only through an `instances` node is
245 /// *skipped* rather than refused -- an `instances` node carries one
246 /// matrix per instance, which [`Scene::instance_transforms`]
247 /// answers; see [`ResolveError::Instanced`].
248 pub fn placements(
249 &self,
250 geometry: &str,
251 ) -> Result<Vec<Placement>, ResolveError> {
252 self.placements_with(geometry, |path| self.compose_along(path))
253 }
254
255 /// The shared body of [`Scene::placements`] and
256 /// [`Scene::placements_at`], differing only in how a path composes.
257 pub(super) fn placements_with(
258 &self,
259 geometry: &str,
260 compose: impl Fn(&[String]) -> Result<[f64; 16], ResolveError>,
261 ) -> Result<Vec<Placement>, ResolveError> {
262 let mut paths = Vec::new();
263 self.walk_placements(geometry, &mut paths)?;
264
265 if paths.is_empty() {
266 // A prototype reached only through an `instances` node has
267 // no *direct* placement, and 3Delight draws it -- the
268 // instancer supplies its matrices. Calling that `Detached`
269 // said "not in the scene" about something that renders, and
270 // contradicted both this function's own documentation and
271 // `an_instancing_prototype_is_not_detached`. An empty list
272 // is the honest answer: no direct placements, ask
273 // `instance_transforms` for the instancer's.
274 let instanced = self
275 .edges_from(geometry)
276 .any(|edge| edge.kind == EdgeKind::InstanceSource);
277
278 return if instanced {
279 Ok(Vec::new())
280 } else {
281 Err(ResolveError::Detached {
282 handle: geometry.to_string(),
283 })
284 };
285 }
286
287 self.build_placements(paths, compose)
288 }
289
290 /// Resolve each walked path into a [`Placement`].
291 pub(super) fn build_placements(
292 &self,
293 paths: Vec<Vec<String>>,
294 compose: impl Fn(&[String]) -> Result<[f64; 16], ResolveError>,
295 ) -> Result<Vec<Placement>, ResolveError> {
296 paths
297 .into_iter()
298 .map(|path| {
299 let transform = compose(&path)?;
300 let gathered =
301 self.gathered_along(&path, &EdgeKind::AttributeBinding);
302 let binding = if gathered.is_empty() {
303 None
304 } else {
305 let shader =
306 |kind: &EdgeKind| self.shader_on(&gathered, kind);
307 Some(Binding {
308 surface_shader: shader(&EdgeKind::SurfaceShader),
309 displacement_shader: shader(
310 &EdgeKind::DisplacementShader,
311 ),
312 volume_shader: shader(&EdgeKind::VolumeShader),
313 attributes: gathered
314 .iter()
315 .map(|(_, _, edge)| edge.from().to_string())
316 .collect(),
317 })
318 };
319 Ok(Placement {
320 path,
321 transform,
322 binding,
323 })
324 })
325 .collect()
326 }
327
328 /// Every placement of `geometry`, with each transform interpolated
329 /// at `time`.
330 ///
331 /// [`Scene::placements`] refuses a motion-sampled node and
332 /// [`Scene::world_transform_interpolated_at`] refuses a node with
333 /// more than one parent, so a geometry with several *moving*
334 /// parents had no answer from either. This is that answer.
335 ///
336 /// A geometry animated by an `instances` node instead -- a crowd or
337 /// a particle system, where the *instancer's*
338 /// `transformationmatrices` are sampled -- is a different question,
339 /// and [`Scene::instance_transforms_at`] answers it. This one
340 /// returns an empty list for such a prototype, because it has no
341 /// direct placement.
342 ///
343 /// The end sample is held outside the sampled range, exactly as
344 /// [`Scene::world_transform_interpolated_at`] describes.
345 ///
346 /// # Errors
347 ///
348 /// As [`Scene::placements`], less
349 /// [`ResolveError::MotionSampledTransform`] -- the case this exists
350 /// to answer -- plus [`ResolveError::MissingSampleAtTime`] for a
351 /// time that names no sample, such as a NaN.
352 pub fn placements_at(
353 &self,
354 geometry: &str,
355 time: f64,
356 ) -> Result<Vec<Placement>, ResolveError> {
357 self.placements_with(geometry, |path| {
358 self.interpolate_along(path, time)
359 })
360 }
361
362 /// Depth-first over every parent, collecting root-ward paths.
363 ///
364 /// An explicit stack, not recursion: measured, the recursive form
365 /// aborted the process on a chain 40 000 deep on the main thread
366 /// and 10 000 deep on a spawned one -- and a stack overflow kills
367 /// the process rather than returning an error a backend could
368 /// handle. `chain` is iterative for the same reason.
369 pub(super) fn walk_placements(
370 &self,
371 geometry: &str,
372 out: &mut Vec<Vec<String>>,
373 ) -> Result<(), ResolveError> {
374 // (node, how many of its parents have been taken)
375 let mut stack: Vec<(String, usize)> = vec![(geometry.to_string(), 0)];
376 // The handles on the stack, for the cycle check. A set rather
377 // than scanning the stack, which was quadratic in the depth:
378 // 523 ms against 14 ms on a 20 000-node chain.
379 let mut on_path: HashSet<String> = HashSet::new();
380 on_path.insert(geometry.to_string());
381
382 while let Some((current, taken)) = stack.last().cloned() {
383 if taken == 0 && current == crate::ROOT {
384 out.push(
385 stack.iter().map(|(handle, _)| handle.clone()).collect(),
386 );
387 stack.pop();
388 on_path.remove(¤t);
389 continue;
390 }
391
392 // Only direct placements branch. An `instances` connection
393 // is not a path in this sense: the instancer holds a matrix
394 // per instance rather than one for the prototype.
395 let parent = self
396 .edges_from(¤t)
397 .filter(|edge| edge.kind == EdgeKind::SceneMember)
398 .nth(taken)
399 .map(|edge| edge.to().to_string());
400
401 let Some(parent) = parent else {
402 stack.pop();
403 on_path.remove(¤t);
404 continue;
405 };
406
407 // SAFETY: the loop read `stack.last()` above and has not
408 // popped since, so there is a last element.
409 stack.last_mut().expect("just read").1 += 1;
410
411 if !on_path.insert(parent.clone()) {
412 return Err(ResolveError::Cycle { handle: parent });
413 }
414 stack.push((parent, 0));
415 }
416
417 Ok(())
418 }
419}
420
421/// Every node under `.root`, with the world transform composed on the
422/// way down.
423///
424/// Returned by [`Scene::world_transforms`]. One entry per **path**:
425/// ɴsɪ's lightweight instancing puts one geometry under several
426/// parents, and each of those is a different object to a renderer with
427/// a different transform.
428pub struct WorldTransforms<'a> {
429 scene: &'a Scene,
430 /// `Enter` carries the transform of everything above the node;
431 /// `Leave` pops it off the ancestor set, which is what makes the
432 /// cycle check exact rather than a depth cap.
433 stack: Vec<Step<'a>>,
434 ancestors: HashSet<&'a str>,
435}
436
437enum Step<'a> {
438 Enter(&'a str, [f64; 16]),
439 Leave(&'a str),
440}
441
442impl<'a> Iterator for WorldTransforms<'a> {
443 type Item = (&'a str, [f64; 16]);
444
445 fn next(&mut self) -> Option<Self::Item> {
446 while let Some(step) = self.stack.pop() {
447 let (handle, above) = match step {
448 Step::Leave(handle) => {
449 self.ancestors.remove(handle);
450 continue;
451 }
452 Step::Enter(handle, above) => (handle, above),
453 };
454
455 // A node already on this path is a cycle, and the
456 // single-answer accessors refuse one; the branch stops
457 // here rather than looping.
458 if !self.ancestors.insert(handle) {
459 continue;
460 }
461
462 let here = match self.scene.local_transform(handle) {
463 Some(local) => mul(above, local),
464 None => above,
465 };
466
467 self.stack.push(Step::Leave(handle));
468 for edge in self.scene.edges_to_attribute(handle, "objects") {
469 self.stack.push(Step::Enter(edge.from(), here));
470 }
471
472 return Some((handle, here));
473 }
474 None
475 }
476}
477
478impl Scene {
479 /// Every node under `.root`, with its world transform, composing
480 /// each matrix once.
481 ///
482 /// [`Scene::world_transform`] answers for one geometry by walking
483 /// up to `.root`, which is right for one question and quadratic
484 /// for the whole scene: measured, a twenty-deep chain with 50 000
485 /// geometries under it costs 6.2 us per geometry -- the same
486 /// twenty matrices composed fifty thousand times -- of which the
487 /// multiply itself is under a tenth. This descends instead,
488 /// carrying the accumulated transform down, so each node's matrix
489 /// is composed once.
490 ///
491 /// One entry per path, so a geometry under two parents appears
492 /// twice, as it does in [`Scene::placements`] and as it must to a
493 /// renderer.
494 ///
495 /// Nodes are yielded in no particular order beyond a parent
496 /// preceding its children. A cycle ends the branch it is on rather
497 /// than looping; the single-answer accessors refuse it outright.
498 ///
499 /// A **motion-sampled** transform contributes its static value
500 /// here, which is `None` -- ask [`Scene::world_transform_samples`]
501 /// per geometry for those. This is the flat pass a backend makes
502 /// once, not the motion pass.
503 pub fn world_transforms(&self) -> WorldTransforms<'_> {
504 let mut stack = Vec::new();
505 for edge in self.edges_to_attribute(crate::ROOT, "objects") {
506 stack.push(Step::Enter(edge.from(), IDENTITY));
507 }
508 WorldTransforms {
509 scene: self,
510 stack,
511 ancestors: HashSet::new(),
512 }
513 }
514}