# Scene with Node graph thread safe, with important efficeny

I will try to be as explicit as I can, and I apologize for my grammar...

I am working on a game engine (specifically on the Render part) and I am facing some conception choice that will involve a lot of code and I would like to do the good one on first try. I am actually working on the Scene graph. I have to specify, that the engine have to be thread safe, and c++11/14 compliant while limiting the user mistake (not allowing engine user moving a pointer that shouldn't be moved...). So my issue is that I do not know how to give the access too engine user and keep the thread safety without killing performance with 10000 of cache misses or if it is needed to be able to search for a specific Node (when you build the tree don't you know wich Node you will use?).

Actually I started with a tree of Node something very standar

Each Node know all of its child and they know their parents. For efficiency purpose every Node who will contain meshes, with associated texture will stock them in a Scene object who will old a pointer on every Node who hold a mesh (for querying the scene transformation matrix of the mesh). The scene will also hold the root Node of the scene.

My question is How should I handle the link between A Node and its family?

One of the solution I thinked about is to use the Observer design pattern. Use shared_ptr between Node and it's family then only provide NodeObserver to the engine user. But with this solution I don't know how to link the scene ressource holding to the nodes because a shared_ptr will introduce unbreakable cycle and a wear_ptr will introduce to much cache_miss and to much synchronization (at least a lock on every Node every frame...) I could use a naked pointer stored into the Scene object, and at the end of its life Node destructor should removeit from the Scene?

I will be very happy if anyone know how to do that. Thank you in advance for your time and your help.

I can't give you a complete solution as I never bothered to try to make a universal, thread-safe scene graph (a bit too ambitious given the teams and environments I worked with), but I think this answer will provide a huge potential puzzle piece.

Kill the Scene Root!

I don't use the concept of a "scene root". If I did, every single thing I insert to the scene would have to be inserted to the scene root and store all kinds of links with all kinds of shared data. I do have a tree component like this:

struct CTreeNode
{
// I often need bottom-up traversal where the user
// selects a child/leaf and then wants immediate access
// to its parent, so I store a parent link.
int parent;

int next_sibling;
int first_child;
};


... but I only use that and attach that to an entity when I genuinely need parenting, like in a bone or rigid body hierarchy. And the root of that is not the scene root, so there's little shared data. The root for a robot might be its pelvis/hips, not the root of the entire scene. We basically take this:

... and turn it into this:

And that might seem like it's just trading a "scene root child list" for a "flat scene list", but the second doesn't have to be a linked structure; it can be a totally different data structure and data type. You could use an unrolled list or tbb::concurrent_vector or something else very friendly for concurrency and memcpy and so forth if you're aiming to try to make these central data structures thread-safe. You don't have to get tunnel visioned on trying to make the entire tree and manipulations on a single node thread-safe if this flat "root child list" is stored in a separate data structure from the tree nodes.

Different Characteristics, Common Cases and Rare Cases

The root child list is very different in nature from the rest of the branches/children since it's usually going to store a massive list of analogical children and inserting/removing children would potentially be an extremely common case (possibly occurring every single frame), while the branches in the scene will often have much fewer children and may rarely ever need to modify the hierarchy. The average number of children the root node need could be in the range of hundreds of thousands to millions, while the average for everything else that needs to serve as a parent is 3. Those are radically different requirements.

There's very few reasons for a bone hierarchy to ever change. You might just load the skeletal data for a character and that's that, the parent/child relationships never change beyond that point. Meanwhile you might be inserting and removing elements to/from the scene many, many times per frame. When you have radically different use characteristics like that, it often helps to use a different data structure.

It makes things a lot easier if you don't try to use one node data structure to rule them all here and treat the "flat scene list" as a separate concept/data structure without an actual "scene root" because, again, the data structure and usage and common case/rare case characteristics are vastly different between the analogical scene root child list and, say, the children's children. Trying to cram that all into one analogical "node" structure for everything is likely to cause more grief than help, and especially if you're trying to multithread hierarchical manipulation and traversal.

And I think if you start with that concept of eliminating the idea of a scene root which every single thing in your scene/game world is parented to, it should help a whole lot if you are trying to multithread manipulations and access of the graph. That'll give you many independent graphs with little shared data instead of one graph with shared root data for everything.

Implicit Scene Root

If you want to actually do the analogical "whole scene transformation", you can special case that and multiply everything by a matrix without storing parent/child links for every single thing in your scene. If you need to display a scene outline in your level editor, again you can special case and pretend like the scene root exists by doing flat iteration over the entities in your scene that don't have a tree node component attached or have, say, -1 stored for the parent (which in my case indicates a root). You don't actually have to have a real root node for the entire scene and link everything to it and store all this extra shared data. You can deduce that implicitly that every entity without a tree node attached or with a null parent (or parent set to -1 if you use indices like me) is an immediate child of the analogical scene root (which isn't actually stored as a node in memory).

Caching Preorder Traversal

Another thing that mitigates cache misses since linked structure traversal is inherently not very cache-friendly usually is that I have a function which outputs a flat array of indices using preorder traversal of the tree (which, again, is a small tree with an entity in the scene as its root, not the entire massive scene as its root), and each set of child indices is sorted. I generally don't traverse the tree except to output this flat array of indices whenever the tree has changed. Since the indices are gathered using preorder traversal, you can update motion matrices in a straight sequential fashion over the resulting array while processing things in proper order (parents before children).

shared_ptr/weak_ptr

On the use of shared_ptr/weak_ptr, I generally don't bother and just refer to things by index when components depend on each other. Again with my tree node:

struct CTreeNode
{
int parent;
int next_sibling;
int first_child;
};


... the links just use plain old integers as indices to entities. What I do is when the node is destroyed (I can register destructors for a component type through the component registry -- can't use C++ dtors directly since the ECS uses a C API for interop with many different languages), I just update the links to exclude the node, removing it from its parent and setting the links of its children to -1 (null, i.e.).

Now I could see how shared_ptr might become very helpful in a multithreading context to ensure that the lifetime of a resource is extended until after a thread is finished processing it, but I always found the benefits of shared_ptr to often be outweighed by its cons (easy to introduce logical leaks by accident, expensive atomic ref counts, having to heap allocate everything including the ref counter, etc). Instead I often found it useful to just make sure all systems do their processing from a "process" callback/event, even systems running in other threads. If they try to destroy/remove any entity/component during these processing events, the removal is deferred until a small time slice (very short-lived lock) when systems are no longer processing.

I find that much easier to deal with and so much cheaper and just much more predictable to reason about when things should be destroyed in between system processing instead of at the granular level of all shared pointers to a resource being released whenever and from wherever (hard to predict when/where that will be in a complex codebase if you're using shared ownership a lot). I find it so much easier to have an explicit "removal" function I can count on to remove components and entities, but also knowing that's safe to use because it's not actually going to remove a component if systems are still being processed (in the same thread or other threads). If you can unify your codebase this way as opposed to having "rogue threads" storing their own persistent references to game state for who knows how long, life becomes so much easier.

Because in my cases at least, a scene entity/component should be removed when the user requests to remove it from the editor unless there are systems still processing, at which point it should be removed as soon as possible when they're not. Explicit removal is so much easier in these cases than implicit and hoping that every relevant part of your system will release those strong references soon after.

Another thing about shared_ptr in a team environment at least is that once you publicly expose a shared_ptr to something in some interface (using shared_ptr for implementation details is not nearly as problematic), you can't stop it from spreading. You can't prevent people (at least not forcefully, maybe with very careful standards) from storing more shared_ptrs to the same resource, including third party plugin developers writing code completely outside of your team's control, and it only takes one of them to be careless and forget to release the shared_ptr to extend a resource's lifetime far longer than appropriate, introducing logical leaks into your application, and I've had that happen a lot in the past where third parties ended up storing a shared_ptr to something expensive like a mesh, at which point it wasn't freed at the right time when the user requested to remove it (not even close). So I've always been weary about its usage, since it can easily be misused in horrific ways to the point where it can become impossible to reason about when anything will ever be freed and destroyed since code that's not even in your team's control could be extending the lifetime of objects way, way longer than they should persist.

A tree structure like a scene graph is diametrically opposed to the operation of multithreaded programming. What happens if someone adds or removes a single node? The whole thing collapses. It's also a bit unpleasant because it already causes lots of cache misses.

So first off I would forget about using a scene graph, or at least using it directly. Any safe way of using it is going to be way too slow. That's not to say that you can't have both a scene graph and a specific collision structure, though.

I would recommend a flat structure ie an area that has all of the transforms calculated out. Then each frame you recalculate everything in a second buffer (perhaps what you are using as the actual scene graph) and then copy everything over in one memcopy to the collision structure.

It's a big topic to cover in an answer to an online question so if none of this makes any sense then this is a good place to get started: http://realtimecollisiondetection.net/

• Hello thank you for your answer. I (and my teachers) do believe that scene graph is the only way to attend the scene management. the first problem with multi threading system is the modification of the graph sturcture who should be synchronized, wich is completely doable. The second one is make sure that people having access to node who are now removed from the graph cannot intend to do bad things. Also i am not working at all on the collision thing problem, that will be managed somewhere else with the scene graph as parameter, because it knows where things are. – Quentin Huot-Marchand Aug 4 '16 at 14:09
• Scene graph is a separate issue from collision detection. If you keep your data in a scene graph I can tell you from personal experience it will be very slow. Entering synchronized code during the render process will be far too slow. You need to have lockless waitless multithreading to get reasonable performance for collision detection.... – Yudrist Aug 4 '16 at 20:39