Dev:Source/GameEngine/SceneGraph

Game Engine - Scene Graph

This is an overview of the game engine's scene graph design and of how it currently works.

The Scene Graph is a structure to hold the game objects' transform data in an hierarchical fashion according to their relations. Its purpose is to update all objects' transforms, computing the final world coordinates for each object. There is legacy code to support culling.

All active objects should be in the scene graph. Objects with a parent/child relation are connected nodes in the graph. All nodes have spatial information (position, orientation, scale and a bounding box), and the type of relation that they have to the parent (normal, vertex, bone, etc). The nodes have a series of controllers and callbacks to interface with other systems that can also control the objects' transforms (logic, animation and physics).

The scene graph is built dynamically from the blender structures every time the game engine is run. This happens in the internal DataConversion step.

The prefix for Scene Graph source classes is SG, most of it is located at source/gameengine/SceneGraph.

SG_DList double circular linked list

SG_QList another double circular linked list for storing an object in two lists. The idea here is that the SG_Nodes at the end of the hierarchy will inherit two lists (both double linked and circular) as elements. The lists can be used as a downcast pointer to the end element itself, SG_Node. eg: SG_Node* n->AddFront() or QAddFront() for the second list.

SG_IObject base object that can be part of the scenegraph. It holds a 'ClientObject' - an interface to associate arbitrary external objects with the node -, a 'ClientInfo' that in practice is used to store a KX_Scene, SG_Callbacks - used on the 'ClientObject' for Replication, Destruction, UpdateTransform, Schedule and Reschedule updates so that the external object may be synchronized -, and a set of SG_Controllers with functions to update their simulation time.

SG_Spatial spatial information for a node: position, rotation, scale in local and world coordinates. It also contains a link to the node's parent, being an interface implemented by the specific parenting type. This class is responsible for keeping track of when the node was/needs to be updated. Finally it has a radius and BoundingBox (supporting conversion from and to AA and O) for use in culling, however, the view culling is no longer made with the GE SceneGraph, but with Bullet.

SG_Node a node contains a pointer to its parent and to its children. Any pointer may be null as any node can be a root node and/or have no children. The class has functions for management of this structure. It is effectively the 'graph' part of the scene graph.

SG_Controller an interface for hooking systems that affect a node's transforms. Implementing classes are: KX_CameraIpoSGController, KX_IpoSGController, KX_LightIpoSGController, KX_MaterialIpoController, KX_ObColorIpoSGController, KX_WorldIpoController

SG_ParentRelation abstract interface to define how children react to parent nodes. Implementations must define an UpdateChildCoordinates function to update the child's global coordinates. Implementations:

KX_NormalParentRelation - the child's coordinates are defined relative to the parent's

KX_SlowParentRelation - the child's coordinates are interpolated to the parent's according to a 'relax' parameter

KX_VertexParentRelation - only the child's location is relative to the parent's. orientation and scale are not propagated.

KX_BoneParentRelation - the child's coordinates follow a bone's position, orientation and scale

SG_Tree a binary tree with nodes and bbox. It is currently not being used. The tree is a BVH (has a bounding box spatial hierarchy) with the purpose of being used for culling. It is constructed by the SG_TreeFactory.

SG_BBox holds the minimum and maximum axis aligned points of a node's bounding box in world coordinates. Has functions to test intersections and compute the BB volume.

Building the Scene Graph

The scene graph is built from blender data every time the game engine is started.

A game object version, derived from KX_Object, is created for all blender objects that are supported. These new objects have an SG_Node and the current transform as local.

If the object has a parent, a parentinversenode is created to keep the object from gluing to the parent's transform space and to keep it's local coordinates independent from the offset (loc,rot,scale..) to the parent.

The child is parented to the inverse node, that will later be connected to the child's parent.

After all objects/nodes are built, the parent inverse links are connected to the parent, effectively building the graph.

Design

The SG_Nodes form a graph, describing the hierarchy of all objects' transforms. The graph is used to compute the objects' final world matrix for each frame and keeping all the independent systems that affect or use the objects' position in sync.

Somewhat apart, there is the SG_Tree structure, a binary BVH based on the objects' Bounding Box that links to the SG_Nodes. This structure intends to be used for culling, but it is not currently being used.

A scenegraph node has a set of controllers - an interface for systems that can modify the object's transform. Examples are the animation system, physics and logic.

The controllers are called to update the object's transforms via a callback system. There are callbacks to update the node's transform and to schedule, replicate and destroy a node. This design also serves the purpose of keeping the other independent systems (physics, anim, etc) synchronized.

This controller-callback design is no longer being complied with and only animation is using it.

---> ToDo - Stages and the main loop <---

The scenegraph ultimately computes for every object, every frame, a 4x4 transform matrix (from object to world space) that is used by the Rasterizer. The matrix is OpenGL compatible (column major).

Transforms

The scene graph currently handles transforms by storing independent components: location, orientation and scale.

Every frame, all objects' world transforms are calculated relative to their parents' and their own local components. Supported parent relation types are: normal, vertex, bone and 'slowparent'.

At the end, a 4x4 matrix is computed from the individual components for use in OpenGL.

Culling

The SceneGraph considers a BVH (Bounding Volume Hierarchy) structure, in the form of an optimized Huffman binary tree, to use for culling and possibly for other spatial intersection queries.

The binary tree structure, SG_Tree, is built of other SG_Tree subtrees that link to the SG_Node Graph structure that, in turn, holds the spatial information.

The algorithm to generate the tree, in SG_TreeFactory, is O(n³) and unmaintained . It was replaced by bullet's facility to build the spatial structure and test intersections with the view frustum before the 2.49 release 51b414. All the SG_Tree, factory and bbox structure is no longer being used.

Questions

What to do when a child has its parent in an hidden layer?

(from a bf-committers mail)
what are those 'depsgraph hacks' checkboxes at object properties panel > Relations Extras ? --brita_

Ton added these as a way of telling to depsgraph to tag objects or their object-data block to get calculated one more time. It's a quick hack aimed at providing an optional way to fix a very limited number of pseudo-cyclic scenarios. Does it work? Only in a very limited number of cases, but hopefully enough to tide us over until the real problem gets solved... --aligorith

Can you give me a concrete example? should I check if the GE scenegraph is also respecting this checkboxes or it doesn't apply? --brita_

Check the usage of DList and Qlist

SG_Tree and BB_Box are not used? - can they be removed? Should they be replaced instead?

Problems

Transforms

Calculating the world space transform based only on independent components causes several problems in cases where a child is supposed to inherit a scaled rotation or a negative scale, shear, or any kind of non rigid body transform.

T41184 propose for changing the use of independent components to a 4x4 matrix with advantages and disadvantages.

Math Library

The scene graph is currently using the Motion Toolkit for the mathematical computation of transforms. The version we are using is from 2002! with several patches on top. It is limited, not optimized and uses doubles instead of floats, contrasting with the rest of blender and what should be used in a GPU. It is an extra library with no extra functionality. Possible replacements:

• an updated version of MoTo - The updated version is quite different, it is template based (not forcing doubles), optimized and has support for several new concepts: diagonals, planes, dual quats, bounding boxes. It has recent activity (march 2014) http://code.google.com/p/motion-toolkit/ source moved to https://github.com/dtecta/motion-toolkit
• BLI_math (in C)
• Eigen3 - optimized, http://eigen.tuxfamily.org/
• bullet2 - optimized

T41184 propose for replacing the MoTo library along with the independent components

Slow parent

I think it makes more sense to have an object parented to another according to whether it makes sense or not for the object to be in the other's transform space (following it's scale, orientation..). I think of this as a 'tight' connection, as if the child totally belongs to / is part of the parent. If the child is instead meant to track another object, it should not be its child, it should follow it according to some function/logic.

Slow parenting is currently calculated in the scene graph as a slerp. I think this would be better implemented with a 'constraint' controller, allowing:

• a better user interface: the current one is quite hidden and not very flexible
• more constraint types and tweaking
• more flexibility in the code as well, by having this out of the scenegraph and instead on a step meant to update an object's location taking time and whatever factors into account
• more accuracy - currently, the slerp is not using a time delta and may be run several times per frame according to scene graph needs

What I am proposing here is

1) move slow parent out of the scene graph (code wise)

2) provide a better (more visible and flexible) interface for the user

3) implement a new controller that reproduces this functionality, and more

I think that this functionality also fits nicely as a track constraint or a rigid body joint.

Interesting functionality would be to define this as a spring, instead of as a slerp, or even define the function with a python expression or f-curve