Scene graph

In vector-based graphics editing, each leaf node in a scene graph represents some atomic unit of the document, usually a shape such as an ellipse or Bezier path.

If differences are needed, a common type declaration in C++ would be to make a generic node class, and then derive layers and groups as subclasses.

For this reason, many large scene graph systems use geometry instancing to reduce memory costs and increase speed.

This allows a reduced memory budget and increased speed, since when a new knight node is created, the appearance data needs not be duplicated.

The simplest form of scene graph uses an array or linked list data structure, and displaying its shapes is simply a matter of linearly iterating the nodes one by one.

Virtual functions are simple to write, but it is usually impossible to add new operations to nodes without access to the source code.

This requires that the map of types to callbacks or functors be initialized at runtime, but offers more flexibility, speed and extensibility.

Since drawing proceeds from back to front with closer objects simply overwriting farther ones, the process is known as employing the Painter's algorithm.

Bounding Volume Hierarchies (BVHs) are useful for numerous tasks – including efficient culling and speeding up collision detection between objects.

[neutrality is disputed] Very large drawings, or scene graphs that are generated solely at runtime (as happens in ray tracing rendering programs), require defining of group nodes in a more automated fashion.

These boxes are grouped hierarchically so that ray intersection tests (as part of visibility determination) can be efficiently computed.

Depending on the particulars of the application's drawing performance, a large part of the scene graph's design can be impacted by rendering efficiency considerations.

In 3D video games such as Quake, binary space partitioning (BSP) trees are heavily favored to minimize visibility tests.

Scene graphs 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.

The HOOPS 3D Graphics System appears to have been the first commercial scene graph library provided by a single software vendor.

IRIS Inventor 1.0 (1992) was released by SGI, which was a high level scene graph built on top of Performer.

It was followed up with Open Inventor in 1994, another iteration of the high level scene graph built on top of newer releases of Performer.

X3D is a royalty-free open standards file format and run-time architecture to represent and communicate 3D scenes and objects using XML.

It is an ISO-ratified standard that provides a system for the storage, retrieval and playback of real-time graphics content embedded in applications, all within an open architecture to support a wide array of domains and user scenarios.