Scene Graph

Most games engines use a Scene Graph which is a huge Data Structure that contains all the objects in the game world which is used by the rendering engine to draw them on screen. The scene graph is essentially just a list of objects each with a model and some other graphical information including size and transform. Transform is a set of data used to describe an objects scale, position and rotation in the world, to turn an object we would modify its transform 1(https://www.haroldserrano.com/blog/the-purpose-of-a-scenograph-in-a-game-engine).

The Problem

The Dirty Flag problem arises when you have several objects properties that inherit from other objects. So for example, if we picture a pirate ship out at sea, on the deck of the ship is a crows nest. Atop that crows nest is a pirate, which has a squawking parrot on his shoulder. The ships transform sets its location in the sea, the crows nests transform positions it on the ship and the pirates transform positions it atop the crows nest etc. This means that when we move the ship within the sea each child object will move with it. This means that when the ship moves we don't have to manually move each other object to prevent them from sliding off. However, since the position of the parrot, as well as everything else, would need to be rendered every single frame it can really begin to impact the rendering efficiency.

There are a few ways we could approach this problem, most obviously being to cache object world transforms. We could store each objects' local and world transform and then when we render we only need to use the pre-calculated world transform if nothing moves then everything is still up to date. However, the problem with this is if you imagine the ship is constantly rocking so imagine its hit by a particularly large wave and the pirate moves across the nest and the parrot moves to his other shoulder we would have to recalculate the world transform of the ship and all its children recursively.

By simply moving four objects we have had to perform ten world calculations, which results in six useless calculations which are never used by the renderer, the parrots' position was calculated four times but only rendered once which could clearly create performance issue 3(http://gameprogrammingpatterns.com/dirty-flag.html).

The Solution

In order to resolve this problem we need to stop recalculating after every single movement, so we can simply add a flag to each and every object which represents the two states; "Set" and "Cleared" 2(https://gpgroup13.wordpress.com/a-dirty-flag-tutorial/).

When an object is moved we would set its flag to the "Set" state, then when we need to check the position of the object we check the flag. If the flag is set then we recalculate the objects' position based on how its moved and then set the flag to cleared. The sole purpose of the flag is to show whether an objects' position is up to date. Due to the involvement of caching this is the out of date data is commonly referred to as dirty which is where the dirty flag name comes from. Flag and Bit are synonymous in programming and therefore are interchangeable meaning you may also find sources referring to this as Dirty Bit 3(http://gameprogrammingpatterns.com/dirty-flag.html).

References

[1] https://www.haroldserrano.com/blog/the-purpose-of-a-scenograph-in-a-game-engine

[2] https://gpgroup13.wordpress.com/a-dirty-flag-tutorial/

[3] http://gameprogrammingpatterns.com/dirty-flag.html