The problem is:
How do you implement a Scene Graph in an ECS architecture?
What is a Scene graph
It is a hierarchical data structure that helps manage spatial relationships between objects in a scene. In game engines, they are used to manage hierarchical transformations, where a parent's transformation (position, rotation, scale) affects its children.
One key feature of a scene graph is that objects are arranged in a tree-like structure, where transformations propagate from parent to child. For example, if a robot's arm rotates, its hand and attached tools rotate.
OOP vs ECS differences
In object-oriented programming, implementing a scene graph is straightforward because objects can reference their parents and children. It allows for simple, recursive traversal and updates of hierarchical transformations.
In contrast, in ECS, entities are represented by IDs (like uint64), which are simple numeric values with no built-in structure or relationships. This raises the question, how do you propagate transformations in a hierarchy when all you have are IDs?
I searched for answers online and could not find anything helpful. So, I devised a crazy idea: Traversing the scene graph by levels.
Traversing the scene graph by levels in ECS
A scene graph is a tree with different levels, correct?
- The root node is at level 0
- Children are at level 1
- Grandchildren are at level 2, and so on.
I thought, "What if I could use these levels to simplify traversal?"
For example:
- First, fetch all entities at level 0 and update their transforms.
- Then, fetch all entities at level 1 and update their transforms, applying the transformations of their parents.
- Continue this process for level 2, level 3, and so on.
So, I introduced a component in my engine that tracks entities' parent IDs and their current level in the hierarchy:
struct HierarchyComponent{
var parent: EntityID
var level: Int
}
Whenever a child is assigned a parent, the system calculates and assigns the child's level as the parent's level + 1.
For example, a car entity, wheel entity, and a rim entity start at level 0. If the wheel is attached to the car, the wheel's level is updated to 1. If the rim is linked to the wheel, the rim's level becomes 2.
Traversing and propagating hierarchy transformation works as follows:
- First, process the car (level 0) and calculate its world transform.
- Then, process the wheel (level 1) and combine its local transform with the car's world transform.
- Finally, process the rim (level 2) and combine its local transform with the wheel's transform.
This approach ensures that parent transforms are always processed before their children, eliminating the need for recursive traversal.
Results
To get this working, I needed to modify the F1 model in Blender. I ended up breaking it up into F1 car body, steering, wheels as shown below.