Editing Scene graph (section)

==Scene graph implementation==
The simplest form of scene graph uses an [[Array data structure|array]] or [[linked list]] [[data structure]], and displaying its shapes is simply a matter of linearly iterating the nodes one by one. Other common operations, such as checking to see [[Point location problem|which shape intersects the mouse pointer]] are also done via linear searches. For small scene graphs, this tends to suffice.

===Scene graph operations and dispatch===
Applying an operation on a scene graph requires some way of dispatching an operation based on a node's type. For example, in a render operation, a transformation group node would accumulate its transformation by matrix multiplication, vector displacement, [[quaternions]] or [[Euler angles]].  After which a leaf node sends the object off for rendering to the renderer.  Some implementations might render the object directly, which invokes the underlying rendering [[API]], such as [[DirectX]] or [[OpenGL]]. But since the underlying implementation of the [[rendering API]] usually lacks portability, one might separate the scene graph and rendering systems instead. In order to accomplish this type of dispatching, several different approaches can be taken.

In object-oriented languages such as [[C++]], this can easily be achieved by [[virtual functions]], where each represents an operation that can be performed on a node. Virtual functions are simple to write, but it is usually impossible to add new operations to nodes without access to the source code. Alternatively, the ''[[visitor pattern]]'' can be used. This has a similar disadvantage in that it is similarly difficult to add new node types.

Other techniques involve the use of RTTI ([[Run-Time Type Information]]). The operation can be realised as a class that is passed to the current node; it then queries the node's type using RTTI and looks up the correct operation in an array of [[Callback (computer programming)|callback]]s or [[Function object|functor]]s. This requires that the map of types to callbacks or functors be initialized at runtime, but offers more flexibility, speed and extensibility.

Variations on these techniques exist, and new methods can offer added benefits. One alternative is scene graph rebuilding, where the scene graph is rebuilt for each of the operations performed. This, however, can be very slow, but produces a highly optimised scene graph. It demonstrates that a good scene graph implementation depends heavily on the application in which it is used.

====Traversals====
[[Tree traversal|Traversals]] are the key to the power of applying operations to scene graphs. A traversal generally consists of starting at some arbitrary node (often the root of the scene graph), applying the operation(s) (often the updating and rendering operations are applied one after the other), and recursively moving down the scene graph (tree) to the child nodes, until a leaf node is reached. At this point, many scene graph engines then traverse back up the tree, applying a similar operation. For example, consider a render operation that takes transformations into account: while recursively traversing down the scene graph hierarchy, a pre-render operation is called. If the node is a transformation node, it adds its own transformation to the current transformation matrix. Once the operation finishes traversing all the children of a node, it calls the node's post-render operation so that the transformation node can undo the transformation. This approach drastically reduces the necessary amount of matrix multiplication.{{citation needed|date=December 2015}}

Some scene graph operations are actually more efficient when nodes are traversed in a different order – this is where some systems implement scene graph rebuilding to reorder the scene graph into an easier-to-parse format or tree.

For example, in 2D cases, scene graphs typically render themselves by starting at the tree's root node and then recursively draw the child nodes. The tree's leaves represent the most foreground objects. Since drawing proceeds from back to front with closer objects simply overwriting farther ones, the process is known as employing the [[Painter's algorithm]]. In 3D systems, which often employ [[depth buffer]]s, it is more efficient to draw the closest objects first, since farther objects often need only be depth-tested instead of actually rendered, because they are occluded by nearer objects.