Skip to main content

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(&current)
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(&current)
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(&current);
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(&current)
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(&current);
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}