Scene graph
Encyclopedia
A scene graph is a general data structure
commonly used by vector-based graphics editing
applications and modern computer games. Examples of such programs include Acrobat 3D, Adobe Illustrator
, AutoCAD
, CorelDRAW
, OpenSceneGraph
, OpenSG
, VRML97, and X3D
.
The scene graph is a structure that arranges the logical and often (but not necessarily) spatial representation of a graphical scene.
The definition of a scene graph is fuzzy because programmers who implement scene graphs in applications — and, in particular, the games industry — take the basic principles and adapt these to suit particular applications. This means there is no consensus as to what a scene graph should be.
A scene graph is a collection of nodes in a graph
or tree
structure. A node may have many children but often only a single parent, with the effect of a parent applied to all its child nodes; an operation performed on a group automatically propagates its effect to all of its members. In many programs, associating a geometrical transformation matrix (see also transformation
and matrix) at each group level and concatenating such matrices together is an efficient and natural way to process such operations. A common feature, for instance, is the ability to group related shapes/objects into a compound object that can then be moved, transformed, selected, etc. as easily as a single object.
It also happens that in some scene graphs, a node can have a relation to any node including itself, or at least an extension that refers to another node (for instance Pixar
's PhotoRealistic RenderMan
because of its usage of Reyes rendering
algorithm, or Adobe Systems
's Acrobat 3D for advanced interactive manipulation).
or Bezier path
. Although shapes themselves (particularly paths) can be decomposed further into nodes such as spline nodes
, it is practical to think of the scene graph as composed of shapes rather than going to a lower level of representation.
Another useful and user-driven node concept is the layer. A layer acts like a transparent sheet upon which any number of shapes and shape groups can be placed. The document then becomes a set of layers, any of which can be conveniently made invisible, dimmed, 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 nodes of a scene graph. 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. A visibility member, for example, would be a feature of a layer, but not necessarily of a group.
For instance, a game might define a logical relationship between a knight and a horse so that the knight is considered an extension to the horse. The scene graph would have a 'horse' node with a 'knight' node attached to it.
As well as describing the logical relationship, the scene graph may also describe the spatial relationship of the various entities: the knight moves through 3D space as the horse moves.
In these large applications, memory requirements are major considerations when designing a scene graph. For this reason, many large scene graph systems use instancing to reduce memory costs and increase speed. In our example above, each knight is a separate scene node, but the graphical representation of the knight (made up of a 3D mesh, textures, materials and shaders) is instanced. This means that only a single copy of the data is kept, which is then referenced by any 'knight' nodes in the scene graph. This allows a reduced memory budget and increased speed, since when a new knight node is created, the appearance data does not need to be duplicated.
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 which shape intersects the mouse pointer
(e.g., in a GUI
-based applications
) are also done via linear searches. For small scene graphs, this tends to suffice.
Larger scene graphs cause linear operations to become noticeably slow and thus more complex underlying data structures are used, the most popular and common form being a tree. In these scene graphs, the composite design pattern
is often employed to create the hierarchical representation of group nodes and leaf nodes.
Group nodes — Can have any number of child nodes attached to it. Group nodes include transformations and switch nodes.
Leaf nodes — Are nodes that are actually rendered
or see the effect of an operation. These include objects, sprites, sounds, lights and anything that could be considered 'rendered' in some abstract sense.
. After which a leaf node sends the object off for rendering to the renderer. Some implementations might render the object directly, which provokes 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 callbacks or 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.
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.
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 buffers, 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.
(BVHs) are useful for numerous tasks — including efficient culling and speeding up collision detection between objects. A BVH is a spatial structure, but doesn't have to partition the geometry (see spatial partitioning below).
A BVH is a tree of bounding volume
s (often spheres, axis-aligned bounding boxes or oriented bounding boxes). At the bottom of the hierarchy, the size of the volume is just large enough to encompass a single object tightly (or possibly even some smaller fraction of an object in high resolution BVHs). As one ascends the hierarchy, each node has its own volume that tightly encompasses all the volumes beneath it. At the root of the tree is a volume that encompasses all the volumes in the tree (the whole scene).
BVHs are useful for speeding up collision detection between objects. If an object's bounding volume does not intersect a volume higher in the tree, it cannot intersect any object below that node (so they are all rejected very quickly).
Obviously, there are some similarities between BVHs and scene graphs. A scene graph can easily be adapted to include/become a BVH — if each node has a volume associated or there is a purpose-built 'bound node' added in at convenient location in the hierarchy. This may not be the typical view of a scene graph, but there are benefits to including a BVH in a scene graph.
and scene graphs is by creating a scene leaf node that contains the spatial partitioning data. This data is usually static and generally contains non-moving level data in some partitioned form. Some systems may have the systems and their rendering separately. This is fine and there are no real advantages to either method. In particular, it is bad to have the scene graph contained within the spatial partitioning system, as the scene graph is better thought of as the grander system to the spatial partitioning.
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. 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 testing 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 in it, it is useful to use a bounding box (or in this case, a bounding rectangle scheme) to quickly determine which scene graph elements are visible and thus actually need to be drawn.
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, for example, binary space partitioning
(BSP) trees are heavily favored to minimize visibility tests. BSP trees, however, take a very long time to compute from design scene graphs, and must be recomputed if the design scene graph changes, so the levels tend to remain static, and dynamic characters aren't generally considered in the spatial partitioning scheme.
Scene graphs for dense regular objects such as heightfields and polygon meshes tend to employ quadtree
s and octree
s, 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.
was the first commercial scene graph specification, and became an ANSI standard in 1988. Disparate implementations were provided by Unix
hardware vendors. The HOOPS 3D Graphics System
appears to have been the first commercial scene graph library provided by a single software vendor. It was designed to run on disparate lower-level 2D and 3D interfaces, with the first major production version (v3.0) completed in 1991. Shortly thereafter, Silicon Graphics
released IRIS Inventor 1.0 (1992), which was a scene graph built on top of the IRIS GL 3D API. It was followed up with Open Inventor
in 1994, a portable scene graph built on top of OpenGL. More 3D scene graph libraries can be found in :Category:3D scenegraph APIs.
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.
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
commonly used by vector-based graphics editing
Vector graphics
Vector graphics is the use of geometrical primitives such as points, lines, curves, and shapes or polygon, which are all based on mathematical expressions, to represent images in computer graphics...
applications and modern computer games. Examples of such programs include Acrobat 3D, Adobe Illustrator
Adobe Illustrator
Adobe Illustrator is a vector graphics editor developed and marketed by Adobe Systems. Illustrator is similar in scope, intended market, and functionality to its competitors, CorelDraw, Xara Designer Pro and Macromedia FreeHand....
, AutoCAD
AutoCAD
AutoCAD is a software application for computer-aided design and drafting in both 2D and 3D. It is developed and sold by Autodesk, Inc. First released in December 1982, AutoCAD was one of the first CAD programs to run on personal computers, notably the IBM PC...
, CorelDRAW
CorelDRAW
CorelDRAW is a vector graphics editor developed and marketed by Corel Corporation of Ottawa, Canada. It is also the name of Corel's Graphics Suite...
, OpenSceneGraph
OpenSceneGraph
OpenSceneGraph is an open source 3D graphics application programming interface, used by application developers in fields such as visual simulation, computer games, virtual reality, scientific visualization and modeling....
, OpenSG
OpenSG
OpenSG is a scene graph system to create real-time graphics programs, e.g. for virtual reality applications. It is developed following Open Source principles, LGPL licensed, and can be used freely...
, VRML97, and X3D
X3D
X3D is the ISO standard XML-based file format for representing 3D computer graphics, the successor to the Virtual Reality Modeling Language . X3D features extensions to VRML X3D is the ISO standard XML-based file format for representing 3D computer graphics, the successor to the Virtual Reality...
.
The scene graph is a structure that arranges the logical and often (but not necessarily) spatial representation of a graphical scene.
The definition of a scene graph is fuzzy because programmers who implement scene graphs in applications — and, in particular, the games industry — take the basic principles and adapt these to suit particular applications. This means there is no consensus as to what a scene graph should be.
A scene graph is a collection of nodes in a graph
Graph (data structure)
In computer science, a graph is an abstract data structure that is meant to implement the graph and hypergraph concepts from mathematics.A graph data structure consists of a finite set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices...
or tree
Tree (data structure)
In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.Mathematically, it is an ordered directed tree, more specifically an arborescence: an acyclic connected graph where each node has zero or more children nodes and at...
structure. A node may have many children but often only a single parent, with the effect of a parent applied to all its child nodes; an operation performed on a group automatically propagates its effect to all of its members. In many programs, associating a geometrical transformation matrix (see also transformation
Transformation (mathematics)
In mathematics, a transformation could be any function mapping a set X on to another set or on to itself. However, often the set X has some additional algebraic or geometric structure and the term "transformation" refers to a function from X to itself that preserves this structure.Examples include...
and matrix) at each group level and concatenating such matrices together is an efficient and natural way to process such operations. A common feature, for instance, is the ability to group related shapes/objects into a compound object that can then be moved, transformed, selected, etc. as easily as a single object.
It also happens that in some scene graphs, a node can have a relation to any node including itself, or at least an extension that refers to another node (for instance Pixar
Pixar
Pixar Animation Studios, pronounced , is an American computer animation film studio based in Emeryville, California. The studio has earned 26 Academy Awards, seven Golden Globes, and three Grammy Awards, among many other awards and acknowledgments. Its films have made over $6.3 billion worldwide...
's PhotoRealistic RenderMan
PhotoRealistic RenderMan
PhotoRealistic RenderMan, or PRMan for short, is a proprietary photorealistic RenderMan-compliant renderer.It primarily uses the Reyes algorithm but is also fully capable of doing ray tracing and global illumination....
because of its usage of Reyes rendering
Reyes rendering
Reyes rendering is a computer software architecture used in 3D computer graphics to render photo-realistic images. It was developed in the mid-1980s by Loren Carpenter and Robert L. Cook at Lucasfilm's Computer Graphics Research Group, which is now Pixar. It was first used in 1982 to render images...
algorithm, or Adobe Systems
Adobe Systems
Adobe Systems Incorporated is an American computer software company founded in 1982 and headquartered in San Jose, California, United States...
's Acrobat 3D for advanced interactive manipulation).
Scene graphs in graphics editing tools
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 ellipseEllipse
In geometry, an ellipse is a plane curve that results from the intersection of a cone by a plane in a way that produces a closed curve. Circles are special cases of ellipses, obtained when the cutting plane is orthogonal to the cone's axis...
or Bezier path
Bézier curve
A Bézier curve is a parametric curve frequently used in computer graphics and related fields. Generalizations of Bézier curves to higher dimensions are called Bézier surfaces, of which the Bézier triangle is a special case....
. Although shapes themselves (particularly paths) can be decomposed further into nodes such as spline nodes
Spline (mathematics)
In mathematics, a spline is a sufficiently smooth piecewise-polynomial function. In interpolating problems, spline interpolation is often preferred to polynomial interpolation because it yields similar results, even when using low-degree polynomials, while avoiding Runge's phenomenon for higher...
, it is practical to think of the scene graph as composed of shapes rather than going to a lower level of representation.
Another useful and user-driven node concept is the layer. A layer acts like a transparent sheet upon which any number of shapes and shape groups can be placed. The document then becomes a set of layers, any of which can be conveniently made invisible, dimmed, 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 nodes of a scene graph. If differences are needed, a common type declaration in C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
would be to make a generic node 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.
Scene graphs in games and 3D applications
Scene graphs are useful for modern games using 3D graphics and increasingly large worlds or levels. In such applications, nodes in a scene graph (generally) represent entities or objects in the scene.For instance, a game might define a logical relationship between a knight and a horse so that the knight is considered an extension to the horse. The scene graph would have a 'horse' node with a 'knight' node attached to it.
As well as describing the logical relationship, the scene graph may also describe the spatial relationship of the various entities: the knight moves through 3D space as the horse moves.
In these large applications, memory requirements are major considerations when designing a scene graph. For this reason, many large scene graph systems use instancing to reduce memory costs and increase speed. In our example above, each knight is a separate scene node, but the graphical representation of the knight (made up of a 3D mesh, textures, materials and shaders) is instanced. This means that only a single copy of the data is kept, which is then referenced by any 'knight' nodes in the scene graph. This allows a reduced memory budget and increased speed, since when a new knight node is created, the appearance data does not need to be duplicated.
Scene graph implementation
The simplest form of scene graph uses an array or linked listLinked list
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
, 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
Point location
The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems , motion planning, and computer aided design ....
(e.g., in a GUI
Gui
Gui or guee is a generic term to refer to grilled dishes in Korean cuisine. These most commonly have meat or fish as their primary ingredient, but may in some cases also comprise grilled vegetables or other vegetarian ingredients. The term derives from the verb, "gupda" in Korean, which literally...
-based applications
Application software
Application software, also known as an application or an "app", is computer software designed to help the user to perform specific tasks. Examples include enterprise software, accounting software, office suites, graphics software and media players. Many application programs deal principally with...
) are also done via linear searches. For small scene graphs, this tends to suffice.
Larger scene graphs cause linear operations to become noticeably slow and thus more complex underlying data structures are used, the most popular and common form being a tree. In these scene graphs, the composite design pattern
Composite pattern
In software engineering, the composite pattern is a partitioning design pattern. The composite pattern describes that a group of objects are to be treated in the same way as a single instance of an object. The intent of a composite is to "compose" objects into tree structures to represent...
is often employed to create the hierarchical representation of group nodes and leaf nodes.
Group nodes — Can have any number of child nodes attached to it. Group nodes include transformations and switch nodes.
Leaf nodes — Are nodes that are actually rendered
Rendering (computer graphics)
Rendering is the process of generating an image from a model , by means of computer programs. A scene file contains objects in a strictly defined language or data structure; it would contain geometry, viewpoint, texture, lighting, and shading information as a description of the virtual scene...
or see the effect of an operation. These include objects, sprites, sounds, lights and anything that could be considered 'rendered' in some abstract sense.
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 anglesEuler angles
The Euler angles are three angles introduced by Leonhard Euler to describe the orientation of a rigid body. To describe such an orientation in 3-dimensional Euclidean space three parameters are required...
. After which a leaf node sends the object off for rendering to the renderer. Some implementations might render the object directly, which provokes the underlying rendering API, such as DirectX
DirectX
Microsoft DirectX is a collection of application programming interfaces for handling tasks related to multimedia, especially game programming and video, on Microsoft platforms. Originally, the names of these APIs all began with Direct, such as Direct3D, DirectDraw, DirectMusic, DirectPlay,...
or OpenGL
OpenGL
OpenGL is a standard specification defining a cross-language, cross-platform API for writing applications that produce 2D and 3D computer graphics. The interface consists of over 250 different function calls which can be used to draw complex three-dimensional scenes from simple primitives. 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++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
, 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
Visitor pattern
In object-oriented programming and software engineering, the visitor design pattern is a way of separating an algorithm from an object structure on which it operates. A practical result of this separation is the ability to add new operations to existing object structures without modifying those...
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
Run-time type information
In programming, RTTI refers to a C++ system that makes information about an object's data type available at runtime. Run-time type information can apply to simple data types, such as integers and characters, or to generic objects...
). 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 callbacks or functor
Function object
A function object, also called a functor, functional, or functionoid, is a computer programming construct allowing an object to be invoked or called as though it were an ordinary function, usually with the same syntax.-Description:...
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
TraversalsTree traversal
In computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited...
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.
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
Painter's algorithm
The painter's algorithm, also known as a priority fill, is one of the simplest solutions to the visibility problem in 3D computer graphics...
. 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, because they are occluded by nearer objects.
Scene graphs and bounding volume hierarchies (BVHs)
Bounding Volume HierarchiesBounding volume hierarchy
A bounding volume hierarchy is a tree structure on a set of geometric objects. All geometric objects are wrapped in bounding volumes that form the leaf nodes of the tree. These nodes are then grouped as small sets and enclosed within larger bounding volumes...
(BVHs) are useful for numerous tasks — including efficient culling and speeding up collision detection between objects. A BVH is a spatial structure, but doesn't have to partition the geometry (see spatial partitioning below).
A BVH is a tree of bounding volume
Bounding volume
In computer graphics and computational geometry, a bounding volume for a set of objects is a closed volume that completely contains the union of the objects in the set. Bounding volumes are used to improve the efficiency of geometrical operations by using simple volumes to contain more complex...
s (often spheres, axis-aligned bounding boxes or oriented bounding boxes). At the bottom of the hierarchy, the size of the volume is just large enough to encompass a single object tightly (or possibly even some smaller fraction of an object in high resolution BVHs). As one ascends the hierarchy, each node has its own volume that tightly encompasses all the volumes beneath it. At the root of the tree is a volume that encompasses all the volumes in the tree (the whole scene).
BVHs are useful for speeding up collision detection between objects. If an object's bounding volume does not intersect a volume higher in the tree, it cannot intersect any object below that node (so they are all rejected very quickly).
Obviously, there are some similarities between BVHs and scene graphs. A scene graph can easily be adapted to include/become a BVH — if each node has a volume associated or there is a purpose-built 'bound node' added in at convenient location in the hierarchy. This may not be the typical view of a scene graph, but there are benefits to including a BVH in a scene graph.
Scene graphs and spatial partitioning
An effective way of combining spatial partitioningSpace partitioning
In mathematics, space partitioning is the process of dividing a space into two or more disjoint subsets . In other words, space partitioning divides a space into non-overlapping regions...
and scene graphs is by creating a scene leaf node that contains the spatial partitioning data. This data is usually static and generally contains non-moving level data in some partitioned form. Some systems may have the systems and their rendering separately. This is fine and there are no real advantages to either method. In particular, it is bad to have the scene graph contained within the spatial partitioning system, as the scene graph is better thought of as the grander system to the spatial partitioning.
When it is useful to combine them
In short: Spatial partitioning will/should considerably speed up the processing and rendering time of the scene graph.Very large drawings, or scene graphs that are generated solely at runtime (as happens in ray tracing rendering
Scanline rendering
Scanline rendering is an algorithm for visible surface determination, in 3D computer graphics,that works on a row-by-row basis rather than a polygon-by-polygon or pixel-by-pixel basis...
programs), require defining of group nodes in a more automated fashion. A raytracer, for example, will take a scene description of a 3D
Dimension
In physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...
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 testing 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 in it, it is useful to use a bounding box (or in this case, a bounding rectangle scheme) to quickly determine which scene graph elements are visible and thus actually need to be drawn.
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, for example, binary space partitioning
Binary space partitioning
In computer science, binary space partitioning is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of the scene by means of a tree data structure known as a BSP tree.Originally, this approach was proposed in 3D computer...
(BSP) trees are heavily favored to minimize visibility tests. BSP trees, however, take a very long time to compute from design scene graphs, and must be recomputed if the design scene graph changes, so the levels tend to remain static, and dynamic characters aren't generally considered in the spatial partitioning scheme.
Scene graphs for dense regular objects such as heightfields and polygon meshes tend to employ quadtree
Quadtree
A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. This...
s and octree
Octree
An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees. The name is formed from oct + tree,...
s, 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.
PHIGS
PHIGSPHIGS
PHIGS is an API standard for rendering 3D computer graphics, at one time considered to be the 3D graphics standard for the 1990s. Instead a combination of features and power led to the rise of OpenGL, which became the most popular professional 3D API of the 1990s...
was the first commercial scene graph specification, and became an ANSI standard in 1988. Disparate implementations were provided by Unix
Unix
Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
hardware vendors. The HOOPS 3D Graphics System
HOOPS 3D Graphics System
The HOOPS 3D Graphics System is a 3D Graphics API, part of The HOOPS 3D Application Framework. The HOOPS 3D Application Framework has three main elements the first of which is the core HOOPS 3D Graphics System itself, a 3D scene-graph API. The second is a rendering pipeline which can drive a...
appears to have been the first commercial scene graph library provided by a single software vendor. It was designed to run on disparate lower-level 2D and 3D interfaces, with the first major production version (v3.0) completed in 1991. Shortly thereafter, Silicon Graphics
Silicon Graphics
Silicon Graphics, Inc. was a manufacturer of high-performance computing solutions, including computer hardware and software, founded in 1981 by Jim Clark...
released IRIS Inventor 1.0 (1992), which was a scene graph built on top of the IRIS GL 3D API. It was followed up with Open Inventor
Open Inventor
Open Inventor, originally IRIS Inventor, is a C++ object oriented retained mode 3D graphics API designed by SGI to provide a higher layer of programming for OpenGL. Its main goals are better programmer convenience and efficiency.-Early history:...
in 1994, a portable scene graph built on top of OpenGL. More 3D scene graph libraries can be found in :Category:3D scenegraph APIs.
X3D
X3DX3D
X3D is the ISO standard XML-based file format for representing 3D computer graphics, the successor to the Virtual Reality Modeling Language . X3D features extensions to VRML X3D is the ISO standard XML-based file format for representing 3D computer graphics, the successor to the Virtual Reality...
is a royalty-free open-standards file format and run-time architecture to represent and communicate 3D scenes and objects using XML
XML
Extensible Markup Language is a set of rules for encoding documents in machine-readable form. It is defined in the XML 1.0 Specification produced by the W3C, and several other related specifications, all gratis open standards....
. 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.
See also
- Graph (data structure)Graph (data structure)In computer science, a graph is an abstract data structure that is meant to implement the graph and hypergraph concepts from mathematics.A graph data structure consists of a finite set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices...
- Graph theoryGraph theoryIn mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
- Space partitioningSpace partitioningIn mathematics, space partitioning is the process of dividing a space into two or more disjoint subsets . In other words, space partitioning divides a space into non-overlapping regions...
- Tree (data structure)Tree (data structure)In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.Mathematically, it is an ordered directed tree, more specifically an arborescence: an acyclic connected graph where each node has zero or more children nodes and at...
Books
- Leler, Wm and Merry, Jim (1996) 3D with HOOPS, Addison-Wesley
- Wernecke, Josie (1994) The Inventor Mentor: Programming Object-Oriented 3D Graphics with Open Inventor, Addison-Wesley, ISBN 0-201-62495-8 (Release 2)
Web sites and articles
- Bar-Zeev, Avi. "Scenegraphs: Past, Present, and Future"
- Carey, Rikk and Bell, Gavin (1997). "The Annotated VRML 97 Reference Manual"
- Helman, Jim; Rohlf, John (1994). "IRIS Performer: A High Performance Multiprocessing Toolkit for Real-Time 3D Graphics"
- Java3D: Aviatrix3D, LG3D * jReality
- OpenSG
- OpenSceneGraph
- PEXTimes http://www.jch.com/jch/vrml/PEXTimes.txt
- Strauss, Paul (1993). "IRIS Inventor, a 3D Graphics Toolkit"
- Visualization Library
- X3dX3DX3D is the ISO standard XML-based file format for representing 3D computer graphics, the successor to the Virtual Reality Modeling Language . X3D features extensions to VRML X3D is the ISO standard XML-based file format for representing 3D computer graphics, the successor to the Virtual Reality...