How to create an efficient immutable tree, with parent pointers

I'm constructing a "scenegraph", which is a hierarchical data structure of Shape nodes (e.g. sphere, cube, mesh, etc. not shown in example code). A Shape can own zero or more child Shape instances. This forms a tree, which is built fully and then passed immutably to a set of worker threads, that render separate parts of the image based on this scenegraph. There is no requirement for the scenegraph to change once it is built, so the threads only need read access.

My question involves the construction of the scenegrape. Initially, I had Shapes that own sub-Shapes. I.e. A Shape owns all of its children. Therefore I was not using pointers or references. This worked fine until I needed to add parent pointers.

Each child of a Shape must now maintain a pointer to its parent. I went down the path of using Arc (because eventually the scenegraph is shared between threads), and that let's me use a Weak ptr to a parent to avoid the cycle problem. But the implication of this is that the primary owning relationship, where Shapes own sub-Shapes, now has to be an Arc too, and this pointer is traversed many, many more times than the parent pointer.

It is my understanding that the features of Arc are only necessary during construction of this data structure and handing over to the thread pool. During rendering these Arc pointers is unfortunate overhead. The data structure is considered immutable at this point, so the features of Arc are no longer needed. They were only required during the building of the data structure, to support the creation of Weak parent pointers.

Interestingly, I couldn't find a way in safe code to set a child as owned by a Shape and set the parent pointer in the child. It's a kind of doubly-linked list, which I know is difficult in Rust. In the end I had to use a single line of unsafe to set the pointer in Shape::set_parent() below:

use std::sync::{Arc, Weak};

pub trait LocalIntersect {
    fn local_intersect(&self);
}

#[derive(Debug, Default)]
pub struct Shape {
    id: usize,
    members: Vec<Arc<Shape>>,
    parent: Option<Weak<Shape>>,
}

impl Shape {
    fn new(id: usize) -> Self {
        Self { id, members: vec![], parent: None }
    }

    fn add(&mut self, shape: Arc<Shape>) {
        self.members.push(shape);
    }

    fn set_parent(&self, parent: Weak<Shape>) {
        let this = self as *const Shape as *mut Shape;
        unsafe {
            (*this).parent = Some(parent);
        }
    }

    fn set_parent_to_all(&self, parent_weak: Weak<Shape>) {
        for member in &self.members {
            member.set_parent(parent_weak.clone());
        }
    }
}

impl LocalIntersect for Shape {
    fn local_intersect(&self) {
        // For now, check if there is a parent and if so, print its ID
        // (Later, we'll combine parent transforms, but not now)
        if let Some(parent_weak) = &self.parent {
            if let Some(parent) = parent_weak.upgrade() {
                println!("local_intersect {}, parent {}", self.id, parent.id);
            }
        }
    }
}

fn main() {
    let mut parent_shape = Shape::new(0);
    let child_shape = Shape::new(1);

    let child_arc = Arc::new(child_shape);

    // Add child to the parent's group
    parent_shape.add(Arc::clone(&child_arc));

    // Wrap the parent shape in Arc
    let parent_arc = Arc::new(parent_shape);

    // Set the parent pointer of each child in the group
    parent_arc.set_parent_to_all(Arc::downgrade(&parent_arc));

    // Share across threads (example with a thread)
    let shared_node = Arc::clone(&child_arc);
    let thread = std::thread::spawn(move || {
        shared_node.local_intersect();
    });
    thread.join().unwrap();

    // Output is:
    //   local_intersect 1, parent 0
}

Rust Playground

Given performance is a top priority for this application, is there an idiomatic way to handle this in Rust? Is this a good candidate for unsafe code? Should I drop Arc and Weak and just use normal child ownership and a raw pointer for the parent pointer? If so, how would I handle the dropping of this data structure later?

I could use something like id_tree or petgraph however those will also provide an overhead when looking up children or parents. I really just want a pointer that the renderer can directly follow back to the parent, without affecting the performance of the very common "get child" look-up.

I'm not new to Rust or C/C++ but I am new to writing unsafe Rust code.

EDIT: For example, in a C program I’d just add a raw parent pointer to all sub-Shapes prior to rendering, and null them all out afterwards before deallocating any Shapes, and it wouldn’t affect ownership or cause a dangling pointer problem. I’m looking for a similar process in Rust - just a nice, simple, fast parent pointer in an eventually immutable data structure, but without the chicken-and-egg issues.