Crate scene_graph

scene-graph

This crate provides a Scene Graph structure, similar to the one used in engines like Unity or Unreal. It is fast, performant, and easy to manipulate.

Quick Start

To install, add the following to your Cargo.toml:

scene-graph = "0.1.0"

or run:

cargo add scene-graph

Here’s a basic SceneGraph example:

use scene_graph::SceneGraph;

fn main() {
    let mut sg: SceneGraph<&'static str> = SceneGraph::new("root");

    sg.attach_at_root("first child");
    // note that insertion order is honored.
    let second_child_handle = sg.attach_at_root("second child");

    // collect the nodes
    let nodes = Vec::from_iter(sg.iter().map(|(_parent, node)| *node));

    // note that the "root" is not seen in an `iter` operation.
    assert_eq!(nodes, ["first child", "second child"]);

    sg.attach(second_child_handle, "first grand-child").unwrap();
    sg.attach(second_child_handle, "second grand-child").unwrap();

    sg.attach_at_root("weird third way younger child");

    let nodes = Vec::from_iter(sg.iter().map(|(_parent, node)| *node));

    // note the iteration order -- because we `iter` depth first, we'll get the youngest child last.
    assert_eq!(
        nodes,
        [
            "first child",
            "second child",
            "first grand-child",
            "second grand-child",
            "weird third way younger child"
        ]
    );
}

SceneGraph’s iter function returns a tuple of the parent’s value and the current node’s value in a depth first traversal. SceneGraph is designed, primarily, for trees of Transforms, and its iter is the best way to iterate over those transforms to resolve a scene graph of local transforms into world space transforms.

Detaching Nodes

Nodes in a scene graph can be detached by calling detach, which will return a new SceneGraph<T> where the root is the node provided. A SceneGraph<T> can be attached to another SceneGraph<T> via SceneGraph::attach_graph. If that functionality isn’t needed, users can instead use remove to simply remove the node and drop it entirely.

Detaching the children of a node without removing that node is simple as well – iter_detach will return an iterator which detaches each descendent of the node.

Comparison to petgraph

SceneGraph is similar to a petgraph::stable_graph::StableGraph, but has a few differences.

SceneGraph, on an M1 Mac, is slightly faster at iterating over nodes than petgraphs is, but with a tradeoff for creating nodes lagging a bit.

benches	scene-graph	petgraph
adding and removing a node	52 ns	8.56 ns
iter 50k nodes	217 µs	299.49 µs
iter 64 nodes	311 ns	456.49 ns

However, this is not where scene-graph’s utility really shines – scene-graph was written with the goal of quick iteration in mind, unlike petgraph, which is a general purpose graphing utility. For example, there is no simply equivalent in petgraph to the iter function.

// in `scene-graph`
for (parent, child) in sg.iter() {
    todo!();
}

// in `petgraph`
petgraph::visit::depth_first_search(&petgraph_sg, Some(root_idx), |event| match event {
    petgraph::visit::DfsEvent::Discover(_, _) => todo!(),
    petgraph::visit::DfsEvent::TreeEdge(_, _) => todo!(),
    petgraph::visit::DfsEvent::BackEdge(_, _) => todo!(),
    petgraph::visit::DfsEvent::CrossForwardEdge(_, _) => todo!(),
    petgraph::visit::DfsEvent::Finish(_, _) => todo!(),
});

However, petgraph offers many algorithms which scene-graph completely lacks. For example, finding the distance between two nodes in the graph is simple in petgraph and completely in users’ hands in scene-graph.

Dependencies

This crate depends on thiserror for convenience and thunderdome for its backing Arena allocator. Experimentation proved thunderdome to be both the easiest to work with and the fastest among options.

MSRV

This crate has no MSRV yet. If it sees good adoption, an MSRV policy will be decided.

License

Dual-licensed under MIT or APACHE 2.0.

Structs

DetachedNode

A detached node from a scene graph.

Node

A wrapper around the values given to the SceneGraph. This struct includes the data on the relationships to other nodes, in addition to the value placed at the node.

NodeDoesNotExist

The node does not exist.

ParentNodeNotFound

The parent node requested was not found.

SceneGraph

The core structure of scene-graph. This forms a rose tree, similar to a geneological tree. In this crate, we use geneological terms like parent, child, and sibling to describe node relationships.

SceneGraphChildIter

An iterator over only the immediate children of a node in a SceneGraph. See iter_direct_children for more information.

SceneGraphDetachIter

An iterator over the children of a node in a SceneGraph. See iter_detach and iter_detach_all for more information.

SceneGraphIter

An iterator over the SceneGraph. See iter for more information.

SceneGraphIterMut

A mutable iterator over the children of a node in a SceneGraph. See SceneGraph::iter_mut for more information.

Enums

NodeIndex

A node index into the SceneGraph.