Scene graph

A scene graph is a data structure that is commonly used in the development of computer graphic applications. It is an object-oriented data structure, with which the logic, in many cases, the spatial arrangement of two or three dimensional scene to be displayed is described.

The term scene graph is just blurred defined. This is because that specific scene graph usually application- driven to be developed. So the programmers use the basic idea, but adapt them to the specific needs of the application. Fixed rules that functions must meet a scene graph, there is not therefore.

Hierarchical modeling

From a graph theoretical point of view scene graph is a connected directed graph that has no loops ( directed tree ) whose root node (the " universe " ) contains the entire scene. This root are subordinate child node containing individual objects in the scene. These nodes can be root of another tree, so a further hierarchy of objects in turn.

This approach allows for the hierarchical modeling of objects in a scene. Each node of the scene graph usually has a transformation matrix. For manipulation of this matrix the associated object itself, but also the objects of all child nodes is transformed. A distinction in this case between the object coordinates ( coordinates of an object relative to the parent object ) and world coordinates ( coordinates of an object with respect to the origin of the universe - the root of the scene graph ). By this construction and a hierarchical view of the manipulation of a scene is significantly simplified. One does not have every item of an object transform individually, but simply transforms the totality of all items.

As an example, the modeling of a car with four wheels may serve. A node in the scene graph representing the object car. This node has four child nodes, each of which contains an object of type wheel. If the position or the position of the car node is changed, then the change also affects all the child nodes, so in this case the wheels from. A manual recalculating the position of the wheels is not necessary.

Bounding volume hierarchies

Often the scene graph can be used to render the scenes of an application more efficiently or to accelerate calculations such as collision queries. To this end, a hierarchy of bounding volumes is carried out together with a scene graph. Each node has a bounding volume is therefore also assigned, indicating the spatial extent of the node, including child nodes. As a bounding volumes are simple geometric objects such as axis-parallel square ( AABBs ), focused on the object cube ( OBBs ) or used balls.

With the help of the bounding volumes elements are then determined before rendering all invisible (ie, not lying in the view frustum ). If a node has already been classified as not visible, is a review of its child nodes no longer necessary. Thus, with very little effort, the amount of geometry that is potentially visible and will be rendered therefore be reduced.

Known scene graph systems

  • VRML
  • X3D
  • Computer Graphics
Transformation (function)
759011
de