Scene graph

A scene graph (also called a scenegraph) is a general data structure commonly used by vector-based graphics editing applications. Examples of such programs include AutoCAD, Adobe Illustrator and Corel Draw. The scene graph contains the pictorial data items being edited and displayed.

Each node in a scene graph represents some atomic unit of the document, usually a shape such as an ellipse or Bezier[?] path. Although shapes themselves (particularly paths) can be decomposed further into nodes such as spline points, it is practical to think of the scene graph as composed of shapes rather than drilling further down.

The simplest type of scene graph uses an array or linked list, and displaying its shapes is simply a matter of linearly iterating the nodes one by one. Other common operations, such as checking to see which shape intersects the mouse pointer (e.g., in a GUI-based app) are also done via linear searches. For small scenegraphs, this tends to suffice.

Larger scenegraphs cause linear operations to become noticeably slow and thus more complex underlying data structures are used, the most popular being a tree. In this case, the scenegraph can contain smaller scenegraphs as nodes, and formal type declarations of such structures often include themselves recursively as members.

These "subscenegraphs", depending on the application, can be known to the user and even user-defined and editable. A common feature, for instance, is the ability to group related shapes into a compound shape which can then be moved, transformed, selected, etc. as easily as a single shape. An operation applied to a group automatically propogates its effect to all of its members. In many programs, associating a geometrical transformation matrix at each group level and concatenating such matrices together is an efficient and natural way to process such operations.

Another useful and user-driven group node concept is the layer. A layer acts like a transparent sheet upon which any number of shapes and shape groups can be placed upon. The document then becomes a set of layers, any of which can be conveniently made invisible, dimmed, and/or locked (made read-only). Some applications place all layers in a linear list while others support sublayers (i.e., layers within layers, to any desired depth).

Internally, there may be no real structural difference between layers and groups at all, since they are both just nested scenegraphs. If differences are needed, a common type declaration in C++ Would be to make a generic scenegraph class, and then derive layers and groups as subclasses. A visibility member, for example, would be a feature of a layer but not necessarily of a group.

Very large drawings, or scene graphs that are generated solely at runtime (as happens in raytracing rendering programs), require defining of group nodes in a more automated fashion. A raytracer, for example, will take a scene description of a 3D model and build an internal representation that breaks up its individual parts into bounding boxes (also called bounding slabs). These boxes are grouped hierarchically so that ray intersection tests (as part of visibility determination) can be efficiently computed. A group box that does not intersect an eye ray, for example, can entirely skip having to test any of its members.

A similar efficiency holds in 2D applications as well. If the user has magnified a document so that only part of it is visible on his computer screen, and then scrolls said document, it is useful to use a bounding box (or in this case, a bounding rectangle scheme) to quickly determine which scenegraph elements are visible and thus actually need to be drawn.

In 2D cases, scenegraphs typically render themselves by starting at the tree's root node and then recursively drawing 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 buffers, it is more efficient to draw the closest objects first, since farther objects often need only be depth-tested instead of actually rendered.

Depending on the particulars of the application's drawing performance, a large part of the scenegraph's design can be impacted by rendering efficiency considerations. In 3D video games such as Quake, for example, BSP (Binary Space Partition) trees are heavily favored to minimize visibility tests. BSP trees, however, take a very long time to compute from design scenegraphs, and must be recomputed if the design scenegraph changes.

Scenegraphs for dense regular objects such as heightfields and polygon meshes tend to employ quadtrees[?] and octrees[?], which are specialized variants of a 3D bounding box hierarchy. Since a heightfield occupies a box volume itself, recursively subdividing this box into eight subboxes (hence the 'oct' in octree) until individual heightfield elements are reached is efficient and natural. A quadtree is simply a 2D octree.