Scene Graph

In this chapter, we will talk about the scene graph. A scene graph is not a class or an object, it's more like a pattern that allows you to create inheritance. This pattern is used a lot in game engines. For example, it is used in animation to manage bones. If I move my arm, my hand needs to move too. To obtain this result, I need a hierarchy with parents and children. Thanks to it, my hand will be a child of my arm that is also a child of my body. This hierarchy has the consequence of representing objects in global and local space. Global space is based on position/rotation and scale based on the world and local space is based on its parent. So, if I only move my hand, its local and global position will change but not the local and global position of my arm. However, if I move my arm, its local and global position will change but also the global position of my hand. Scene graphs can take a lot of forms: register or not the parent, list or contiguous buffer to store the children, flags... Firstly, we will see a quick example of it. In a second time, we will see simple optimizations to improve it. So, talk less, code more ! ;D

First of all, let’s create a transform. Transform will contain local and global space information about our entities


struct Transform
{
    /*SPACE INFORMATION*/
    //Local space information
    glm::vec3 pos = { 0.0f, 0.0f, 0.0f };
    glm::vec3 eulerRot = { 0.0f, 0.0f, 0.0f };
    glm::vec3 scale = { 1.0f, 1.0f, 1.0f };

    //Global space information concatenate in matrix
    glm::mat4 modelMatrix = glm::mat4(1.0f);
};

In this example, we use the Euler angle system. The Euler system is easy to use and understand but it contains a lot of undesirable effects: Gimbal lock, shortest angle between to angle thanks to lerp is wrong, cost and size... To avoid it, we need to use quaternion but it needs to be hidden because it's hard to represent a rotation thanks to it. To have a better understanding of this chapter we will use the Euler angle but I invite you to do some research on quaternion.

Now we can represent local and global space information about an object. We will make create a class called Entity. This class will simply wrap the space information with a model for the visual demonstration.


class Entity : public Model
{
public:
[...]

    Transform transform;

    // constructor, expects a filepath to a 3D model.
    Entity(string const& path, bool gamma = false) : Model(path, gamma)
    {}
};

The scene graph is still missing. So, let's add it into the Entity class.


/*SCENE GRAPH*/
std::list<std::unique_ptr<Entity>> children;
    Entity* parent = nullptr;

As we said, scene graphs can take a lot of forms: use std::vector instead of std::list, don't register its parent to simplify the size of the class... In our example we used std::list. We don't want our entity address to change at all. My parents’ address always needs to be valid. Then, I used std::unique_ptr because it's the cleanest approach to avoid a leak. Memory leak appears happens if you allocate memory thanks to new or malloc and forget to call delete or free when datas disappears. Information is still in memory but you cannot have access to it. If you want more information about it, many tutorials talk about it more clearly.

We need now to create a function to add a child to our entity. This function will be easy:: 1: Add entity; 2: Register parent of this new entity as the current entity


template<typename... TArgs>
void addChild(const TArgs&... args)
{
    children.emplace_back(std::make_unique<Entity>(args...));
    children.back()->parent = this;
}

A variadic template allows us to create an entity with any constructor that you want to use without overloading the addChild function. I used it in this example to awake your curiosity and show you a simple use of it.

Ok, perfect! It's almost done, courage! Now we have scene graphs and space information but something is still missing. When we want to send space information to our shader, we need a model matrix. However, we don't see how to compute it thanks to our parents and our local information. First, we need a function to create a local model matrix that represents an object in space based on its parent. This function will be added to the transform class.


glm::mat4 getLocalModelMatrix()
{
    const glm::mat4 transformX = glm::rotate(glm::mat4(1.0f),
                         glm::radians(eulerRot.x),
                         glm::vec3(1.0f, 0.0f, 0.0f));
    const glm::mat4 transformY = glm::rotate(glm::mat4(1.0f),
                         glm::radians(eulerRot.y),
                         glm::vec3(0.0f, 1.0f, 0.0f));
    const glm::mat4 transformZ = glm::rotate(glm::mat4(1.0f),
                         glm::radians(eulerRot.z),
                         glm::vec3(0.0f, 0.0f, 1.0f));

    // Y * X * Z
    const glm::mat4 roationMatrix = transformY * transformX * transformZ;

    // translation * rotation * scale (also know as TRS matrix)
    return glm::translate(glm::mat4(1.0f), pos) *
                roationMatrix *
                glm::scale(glm::mat4(1.0f), scale);
}

To combine multiple model matrices, we need to multiply them. So if I multiply the local model matrix of my hand with the model matrix of the world with arm and arm with hand, I will obtain the global matrix of my hand! So, let's implement a function in entity class that will do it for us:


void updateSelfAndChild()
{
    if (parent)
        modelMatrix = parent->modelMatrix * getLocalModelMatrix();
    else
        modelMatrix = getLocalModelMatrix();

    for (auto&& child : children)
    {
        child->updateSelfAndChild();
    }
}

Now, if I update the world, all of my entities contained will also be updated and our global model matrix will be computed. Finally, we just need to add some code in the main function to add multiple moons with the same local distance and scale and code in the main loop to move the first entity.


/*BEFOR THE MAIN LOOP*/

// load entities
// -----------
const char* pathStr = "resources/objects/planet/planet.obj";
Entity ourEntity(FileSystem::getPath(pathStr));
ourEntity.transform.pos.x = 10;
const float scale = 0.75;
ourEntity.transform.scale = { scale, scale, scale };

{
    Entity* lastEntity = &ourEntity;

    for (unsigned int i = 0; i < 10; ++i)
    {
        lastEntity->addChild(FileSystem::getPath(pathStr));
        lastEntity = lastEntity->children.back().get();

        //Set tranform values
        lastEntity->transform.pos.x = 10;
        lastEntity->transform.scale = { scale, scale, scale };
    }
}
ourEntity.updateSelfAndChild();

/*IN THE MAIN LOOP*/

// draw our scene graph
Entity* lastEntity = &ourEntity;
while (lastEntity->children.size())
{
    ourShader.setMat4("model", lastEntity->transform.modelMatrix);
    lastEntity->Draw(ourShader);
    lastEntity = lastEntity->children.back().get();
}

ourEntity.transform.eulerRot.y += 20 * deltaTime;
ourEntity.updateSelfAndChild();

We can see this result thanks to this code.

Optimization

Being pragmatic is essential to implement a new feature but now let's see how to optimize it. Firstly, in the main loop, we always update the model matrix even if it doesn't move. In programming, a pattern called a dirty flag can help us. A dirty flag is a simple boolean called "isDirty" that allows us to know if an entity was moved during the previous frame. So, if the user scales, rotates or translates it, we need to set this flag on. Don't forget, the model matrix is based on the parent model matrix. So if I change it, I also need to compute all its children's matrix. This flag will be set off in the update function when the model matrix was recomputed.

This pattern is very powerful but can be integrated easily only if you encapsulate your class correctly. I haven’t done it to give you an example of rigid code without the possibility to evolve and change easily. This code requires the programmer to code its functionality perfectly and is difficult to change, improve or optimize. But in production, time is a precious resource and you sometimes need to implement the feature without optimizing. One day, if your feature becomes the performance bottleneck, you need to change it easily. Encapsulation, private/protected, getter/setter is C++ advantage that allows you to do it. Encapsulation has its downsides too. It can increase the size of your class and reduce its visibility. It can also be laborious if you create a getter/setter for all your members. An illarouse video show the c++ limit but keep in mind this example and make do the balance in function of your situation.

Let's remake do again transform function with encapsulation and dirty flag


class Transform
{
protected:
    //Local space information
    glm::vec3 m_pos = { 0.0f, 0.0f, 0.0f };
    glm::vec3 m_eulerRot = { 0.0f, 0.0f, 0.0f }; //In degrees
    glm::vec3 m_scale = { 1.0f, 1.0f, 1.0f };

    //Global space information concatenate in matrix
    glm::mat4 m_modelMatrix = glm::mat4(1.0f);

    //Dirty flag
    bool m_isDirty = true;

protected:
    glm::mat4 getLocalModelMatrix()
    {
        const glm::mat4 transformX = glm::rotate(glm::mat4(1.0f),
                    glm::radians(m_eulerRot.x),
                    glm::vec3(1.0f, 0.0f, 0.0f));
        const glm::mat4 transformY = glm::rotate(glm::mat4(1.0f),
                    glm::radians(m_eulerRot.y),
                    glm::vec3(0.0f, 1.0f, 0.0f));
        const glm::mat4 transformZ = glm::rotate(glm::mat4(1.0f),
                    glm::radians(m_eulerRot.z),
                    glm::vec3(0.0f, 0.0f, 1.0f));

        // Y * X * Z
        const glm::mat4 roationMatrix = transformY * transformX * transformZ;

        // translation * rotation * scale (also know as TRS matrix)
        return glm::translate(glm::mat4(1.0f), m_pos) *
                    roationMatrix *
                    glm::scale(glm::mat4(1.0f), m_scale);
    }
public:

    void computeModelMatrix()
    {
        m_modelMatrix = getLocalModelMatrix();
        m_isDirty = false;
    }

    void computeModelMatrix(const glm::mat4& parentGlobalModelMatrix)
    {
        m_modelMatrix = parentGlobalModelMatrix * getLocalModelMatrix();
        m_isDirty = false;
    }

    void setLocalPosition(const glm::vec3& newPosition)
    {
        m_pos = newPosition;
        m_isDirty = true;
    }

    [...]

    const glm::vec3& getLocalPosition()
    {
        return m_pos;
    }

    [...]

    const glm::mat4& getModelMatrix()
    {
        return m_modelMatrix;
    }

    bool isDirty()
    {
        return m_isDirty;
    }
};


class Entity : public Model
{
public:
    //Scene graph
    std::list<std::unique_ptr<Entity>> children;
    Entity* parent = nullptr;

    //Space information
    Transform transform;

    // constructor, expects a filepath to a 3D model.
    Entity(string const& path, bool gamma = false) : Model(path, gamma)
    {}

    //Add child. Argument input is argument of any constructor that you create.
    //By default you can use the default constructor and don't put argument input.
    template<typename... TArgs>
    void addChild(const TArgs&... args)
    {
        children.emplace_back(std::make_unique<Entity>(args...));
        children.back()->parent = this;
    }

    //Update transform if it was changed
    void updateSelfAndChild()
    {
        if (transform.isDirty())
        {
            forceUpdateSelfAndChild();
            return;
        }

        for (auto&& child : children)
        {
            child->updateSelfAndChild();
        }
    }

    //Force update of transform even if local space don't change
    void forceUpdateSelfAndChild()
    {
        if (parent)
            transform.computeModelMatrix(parent->transform.getModelMatrix());
        else
            transform.computeModelMatrix();

        for (auto&& child : children)
        {
            child->forceUpdateSelfAndChild();
        }
    }
};

Perfect! Another solution to improve performance can be memorizing the local Model matrix. Thanks to it, we avoid recomputing all child local model matrices if the parent is moved. This solution improves performance but transforms become heavier. This size is really important for your hardware. We will see why in the limitation subchapter. You can find the code here.

Limitation

Do you ever hear about data oriented design ? No ? Let's talk brevely about it !

This design is based on how your hardware works. In your computer, data is aligned into your memory. When you use data like a variable, this data is sent to the cache. The cache is a very fast memory but without a lot of space. This memory is localized into your CPU. For example, if you want to make a cake, you need to go to a supermarket (hard disk) to buy ingredients. A supermarket is very big but is also very far from your home. When you buy your ingredients, you store them in your fridge (RAM). Your fridge contains ingredients that you need to live but I hope for you that you don't live only with cake ^^ It is also small but near to your kitchen worktop. And finally, your kitchen worktop (the cache) is small and can't contain all your ingredients but is very near to your preparation. It's the same for the PC! When you need to process data, your system will copy your data but also all datas after in cache (depending on your cache line size). So, if all your datas are not contiguous in your memory, you will be as slow as if you need to take eggs one by one in your fridge to make your cake. std::list is a noncontiguous array. std::map will probably make the job better but inheritance cannot be aligned into your memory because it's a tree. So, if you want to make RTS for example, with an independent unit, you probably don't need or don't want a scene graph to manage your entities.

std::map is tree and is aligned in memory but scene graph will jump into this memory and will be slower than don't use inheritance.

You know now what a Scene graph is and how to use it with its limitations. In the next chapter, we will talk about frustum culling with a scene graph.

Additional resources

walterkuppens article about scene graph: An article by Walter Kuppens with another approach of the scene graph.
webglfundamentals article and demonstration about scene graph: An article with animated webGL code and animated demonstration

Autor

Article by: Six Jonathan
Contact: e-mail
Date: 09/2021

Scene Graph

Guest-Articles/2021/Scene/Scene-Graph

Optimization

Limitation

Additional resources

Autor