# 3D Theory - Scene Graph Model

A scene graph is a data structure used to hold the elements that make up a scene. It may be either a tree or a Directed Acyclic Graph (DAG).

The tree and DAG are similar, except that in the DAG the branches may possibly grow back together.

VRML is a DAG because the DEF/USE constructs allows the branches grow back together, XML supports a tree only. Java3d does not allow most nodes to be parented by more than one node, although some attributes may be owned by different nodes.

Different terminology is used for VRML, Java3d, XML etc. So here is a conversion chart:

 VRML Java3d OO XML tree or DAG DAG tree tree what are nodes called? Node node Object Element what are the units of data in the nodes? Field data objects Attribute Attribute

#### Tree

Like a tree in a forest, start at the root and move outward towards the leaves. Unlike most trees that grow, these trees are normally shown with the root at the top and the branches at the bottom.

A node is a part of this tree that may have other nodes or leaves underneath it, a leaf cannot have other nodes or leaves under it.

Since tree branches don't grow back together, there is only one path from a leaf to the root of the tree. There are no "cycles", if you move outward along the branches, you never loop back around to end up at the root again.

#### A Directed Acyclic Graph (DAG)

see graph theory

In mathematical terms, a directed, acyclic graph. Directed means that the parent-child relationship is one-way, Acyclic means that there can't be loops, i.e. child can't be one of its own ancestors.

Like a tree, except maybe the branches grow back together sometimes, so that following a different sequence of branches outwards from the root might lead you to the exact same leaf. Branches never grow in a loop, though, so as long as you keep moving outwards, you always end up at a leaf eventually.

#### Nodes

The scene graph contains 'nodes' such as shape, light, camera, etc. The relationships between the parent and child is known as an edge, but this terminology could be confusing in this context as the term 'edge' is used when we are talking about mesh shapes.

The tree structure is important because it allows the scope of influence of scene parameters to be clear and unambiguous.

Nodes which have an unspecified number of children below them are known as Group nodes. One of the most important type of nodes is a Transform Group, this modifies all of the shapes below it by transforming their vertices through a 4x4 matrix. See Matrix Algebra