Building thread safe Quad Tree (for 3d Terrain rendering)


#1

This is not necessarily a graphics questions, although im using Vulcano right know but my problem is not just how it will work with it.

In the end I want seamless experience on the screen.

struct TerrainPatch {
parent_node: RefCell<Option>,
vertex_buffer: Arc<CpuAccessibleBuffer<[Vertex]>>,
vertex_data: RefCell<Vec>,
transform: Matrix4
}

struct QuadTree {
parent_node: RefCell<Option>,
leaf_nodes: [ RefCell; 4],
depth: i32
}

I’m also thinking of double buffer based approach? Means I will have two root structure with shared nodes, once the engine has build one tree it will swap quickly root pointer to make it next render-able?


#2

What exactly is your question? Do you need help with API design? Do you run into performance problems?
You provide very little context for us the talk about, just a few struct definitions… on which topic: backticks (```) allow you to make code blocks

fn like_this() {
  let it: be = "awesome";
}

What exactly are you struggling with?


#3

Lets start with the problem facing due to “cannot move out of borrowed content” while trying to access inner fields of struct.

I tried Arc<RefCell<Option>> and some other combinations but still facing nooby issues.

Can u help me achieve the most flexible combo of above 3?


#4

Note that if you want to make your things thread safe you have to use Mutex/RwLock + Arc, not RefCell + Rc


#5

We can’t read your original code examples, since they have been mangled by Markdown; go look over your original post. You need to edit your original post (click on the pencil at the bottom right of your text) and add ``` marks around your code blocks.


#6

As @jimb mentions, please help us help you by making your code more readable to us.

Secondly, your “cannot move” error is very hard to debug without more context. How are you using the two data structures you posted?
Could you maybe provide a minimal example on the Rust playground?

Third, in general, “cannot move” errors occur when you use things via &references, aka “Borrows”. Borrows impose the guarantee “you can look, but don’t touch”, because otherwise you could create dangling pointers for other users of the same borrow.
These errors are also very common when people try to write data structures with self-references, such as many tree implementations need. This is known to be hard/impossible-without-unsafe in Rust, because all those self-references are effectively multiple mutable pointers to overlapping parts of the tree, exactly what Rust tries to prevent.
Without more context/code examples, it is impossible for us to say exactly where you are going off track.
You might want to look at the Rental crate, which was written exactly to help with the black magic of self-references in Rust.

Fourth, I’m doing my best to find some breadcrumbs to understand your problem. A CpuAccessibleBuffer seems to imply you are dealing with GPU datastructures. I don’t know much about those, but in general, it can be tricky to “explain” those to rustc, because they usually have a lot of extra memory safety constraints that are hard to fit into Rust’s ownership model.

Is this a “I’m trying rust for the learning/fun” exercise? Or are you writing “production” code? This influences how much shortcuts we might suggest to get everything working.
If it’s the first case, please understand that self-referential structs on the GPU is probably one of the trickiest problems you can pick in Rust, because they violate virtually all core assumptions that rust relies on.

Edit: you may also be interested in the other topic on 3D programming and self-referential structs: How to write software without self-referential structs?