Def. A scene graph is a n-ary tree where  each leaf is  either a geometrical object or a property (sometimes);  the structure reflects a physical relation between the objects.

Example:

Properties in scene graphs can be either physical properties (color, surface properties, transparency, etc.) or geometrical properties, i.e. transformations. While descending in the tree: physical properties are inherited, unless redefined, transformations are composed .

• Going from a parent to a child node:

glPushMatrix();

• Going from a child back to the parent:

 glPopMatrix(); 

• OpenInventor, DataViewer, VTK, etc.
• Each type of node in the tree is represented by a class.
• All of them are derived from a base class, Object.
• Each of them implements a function draw or render or display with the same name and list of parameters.
• The draw is defined as an abstract function in the Object class and is virtual in general.
• The base class also specifies some properties that can be applied to any node in the graph (color, rotation, etc.)

• The leaf nodes are geometrical classes.
• A class contains a set of features that describe dimensions, spatial position, and special properties of the geometrical object. For example, for a sphere, it would contain the radius and the center.
• The draw function for a leaf node generates a list of OpenGL commands specific to that object and using the properties defined by the node.

• Non-terminal nodes in the graph are usually known as containers.
• They contain at least an array of Object pointers that will be links to the children.
• The actual objects to which these will point are either other containers, or geometrical objects.
• The draw function for the containers applies the locally defined properties and transformations and calls the draw function for each child.
• Since the draw function is virtual, the container doesn’t have to know the class of each child.

• Base class: DVobject.
• Geometrical classes: DVlines, DVtriangles, DVspheres, etc.
• In DV, geometrical objects are designed to contain large amounts of data for easy integration with numerical applications..
• A whole surface could fit in just 1 DVtriangles object.

• They are all derived from DVcontainerbase.
• Simple containers draw all of their children.
• Animation containers: selection (flip-book) and interpolation (key-frame).
• Selection containers call the draw function of just 1 child at a time based on a frame number.
• Interpolation containers call the draw function for all of the children after applying a transformation based on the frame number and on an array of transformations defined for a set of key frames.

Binary Space Partitioning Trees

• A BSP tree is a recursive sub-division of space that treats each line segment (or polygon, in 3D) as a cutting plane which is used to categorize all remaining objects in the space as either being in "front" or in "back" of that plane.
• It has applications in hidden surface removal and ray tracing.

Quadtrees and Octrees

• Def. Multi-resolution representation in 2D (quadtrees) or 3D (octrees).
• General idea: recursively divide the space into 4 square cells (2D) or 8 cubic cells (3D) of equal size.
• 3D cells are also called voxels. Each of them is either empty or full (belongs to the object or not). Divide the size of the cell by 2 at each step.
• Applications: medical imaging, fluid modeling, etc.

Quadtree

Octree

Metaballs (Blobs)

• Each voxel is a ball. If two balls are close enough, they merge like drops of water.
• Used for modeling fluffy objects, fluids, animated characters, etc.

Constructive Solid Geometry (CSG)

• The scene can also be represented as a tree, but the container nodes define logical operations on the subtrees:
• union (merge)
• intersection
• difference