For the 3D rendering part, I know support full scene graphs (unidirectional: from parent to child, but not from child to parent).

Originally, I only used scene graphs for models (a subset of my world objects), since model formats like .OBJ contain hierarchies of models. In practice, my Model class contains a vector of SubModels (determined by the model file). This allows for instance the repositioning of furniture relative to the room.

On top of that, I know added to the base class WorldObject, a vector of other WorldObjects (determined by the user). This allows for instance the repositioning of lights relative to the camera (like a flashlight).

I do not want to gather the camera and lights from the scene graphs. Therefore, I store them in my scene itself.

In the game loop of my engine, I update my scripts -> update and propagate (dirty) transforms -> render (among other things).

The problem is that lights must be located in the scene and could be located as child of some other world object. Consequently, I attempt to update their transforms twice:

// 1. Traverse the scene graphs (root world objects) which can contain lights as childs.
m_world->ForEachModel([](WorldObject &world_object) {
    world_object.UpdateTransform();
});
// 2. Traverse the camera (no transformations will be re-calculated).
    m_camera->UpdateTransform();
// 3. Traverse the lights (no transformations will be re-calculated).
m_world->ForEachLight([](WorldObject &world_object) {
    world_object.UpdateTransform();
});

I start with the scene graphs, since the updated ancestor transforms will be propagated as well. Then, I explicitly go over the lights and camera. In this order (1->2->3), transformations will not be re-calculated, since dirty bits will be toggled as opposed to (2->3->1) order. The latter order will first update the parent-to-object and object-to-parent transforms and afterwards possibly pass updated parent-to-world and world-to-parent transforms of the ancestor in the scene graph. So the cached object-to-world and world-to-object transforms will be updated twice.

With my order (1->2->3), I only incur the overhead of a virtual function call and and an is-dirty check. This of course does not drop my framerate, but it does not feel like a clean design.

Edit: I realize that I only use scene graphs on world objects for transforms not for anything else (i.e. rendering). For the latter I still use flat vectors. So instead of a design issue, I rather have a question: how and where do you handle relative movement? Scripting?

Assuming flat arrays in the scene, how do you obtain relative movement?

Should all scripts that operate on single transforms (like the motor and mouse look at) operate on an array of transforms as well?

Since the flag is checked then you don't update the transform twice

For my engine as well as rendering pipeline binding, I think it makes more sense to flatten everything (except for a model and its submodels, but this actually depends how you look at it).

I could use composition instead of inheritance to create a TransformGroup (or even WorldObjectGroup) which provides all operations a Transform provides but applies it to a collection of Transforms. That way:

• I can keep related Transforms together for all scripts;
• I need to define such a TransformGroup only once instead of for every script that modifies a Transform;
• I can decouple my scripting from my internal World representation;
• The function for updating a Transform will only be called once during every frame (independent of the dirty bit which I of course keep using to eliminate unnecessary matrix multiplications and constructions).

TransformGroup transform(camera->GetTransform());
transform.AddTransform(spot_light->GetTransform());
        
SharedPtr< BehaviorScript > controller_script(new FPSInputControllerScript(transform));
AddScript(controller_script);

I don't understand this problem of relative transform, since the game object (or actor or scene object or entity ....) has the local transform, it contains a pointer of the parent, so you compute the relative transform with the current parent and when you change the parent you update the local transform.

Some food for thought of engine programmers:

Should you have a scene graph in the rendering engine itself? Just explicitly update the transformation of such objects. relative movement is extremely rare in practice and should be dealt as an exception, not as part of common engine data structure.

Therefore, I do not offer relative movement for my WorldObjects. If the user of the engine wants to impose relative movement, he must create TransformGroups (which are just scene graphs) and use them in his scripting.