Introduction

One of the most interesting primers, and explanations of scene graphs I have read is provided here. Essential reading for the 3D enthusiast.

Although I have the grace and elegance of motion of lead piping, I do take the odd class in Tae Kwon Do, the Korean martial art, and I am fortunate to have studied under Master Wes Bethel. I don't say this as some sort of idle boast, but Mr. Bethel is also an extraordinary engineer and scientist. And, this will make you even more sick, he knows more about 3D graphics than most. So, it is a pleasure for me to introduce the following article from Mr. Bethel on scene graphs. I think it is essential reading for anyone with a deep interest in 3D graphics.

The following article is reproduce with the kind permission of Wes Bethel, Chief Technology Officer, R3vis Corporation. He can be contacted at wbethel@r3vis.com, or for more information, visit http://www.r3vis.com.

What Do All Graphics Applications Have in Common?

Some form of scene graph technology lies at the heart of every graphics application. Despite such a central role in so many applications, this fundamental technology is often misunderstood. In this article, we provide an overview of scene graph technology along with glimpses of how it is used today and how it could affect future applications.

What Do You Get When You Cross a Mathematician and Hollywood Producer?

The term "scene graph" is the by-product of a collision between the fields of discrete mathematics, computer graphics and cinematography. A "scene" in the computer graphics world refers to a collection of objects, their relationship to one another, and a definition of how a viewer sees the objects in the scene. In cinematography, scenes include things like cameras, lights, actors, backgrounds, and so forth.

To most people, a "graph" is something that shows information, such as the performance of the Dow Jones Industrial average over some period of time. However, we're interested in a different type of graph, one from the world of mathematics. The mathematical, or discrete graph, represents a system built from two fundamental entities: nodes and edges. A familiar example of a visual representation of a discrete graph is a family tree. The nodes of the family tree are people, and edges represent the parent-child relationship. This type of graph is a commonly used tool in discrete mathematics, which is the study of states, and transitions from one state to another.

Of all the different types of discrete graphs, the scene graph is a directed, acyclic graph, sometimes called a "tree." There are many specialized properties of this type of graph, illustrated by the directed, acyclic graph of the family tree. Acyclic means that you can't be the parent of your grandfather; there are no loops in the family tree. Directed means that the parent-child relationship is a one-way proposition. The edge between your parent and you represents a special kind of relationship that exists in just one direction.

The scene graph is also a directed, acyclic graph, or tree, consisting of nodes and edges. Elements of the scene that have some data component, such as viewable objects, light sources, camera locations and so forth are contained in the graph nodes. The edges in the scene are like the edges in the family tree, they define not only parent-child relationships, but also, and more importantly, scope of influence of scene parameters.

Scene Graph Systems Software

The scene graph itself, a collection of nodes and edges, is a powerful and flexible organization framework that is intuitive to most computer folks. The set of software tools that are used to build and interact with the scene graph is called a scene graph applications programming interface (API). The combination of the API and the scene graph structure are collectively known as scene graph systems.

From a high-level view, scene graph systems are similar to common database systems in terms of the types of services they provide. A two-stage usage pattern is commonplace, with a preliminary creation phase followed by a secondary usage phase. The graphics application first creates and loads data into the scene graph, then the system renders the contents of the scene graph into an image.

Why are Scene Graph Systems Useful?

Measurement of usefulness can be characterized in two ways, whether considering scene graph software or any other tool. First, are the features of the tool widely applicable to a broad range of problems? The second measure is the "duct tape" test: can the tool be useful in ways not anticipated by the tool's architect?

Convenience

The hallmark of scene graph systems is that they facilitate rapid applications development. All graphics applications, whether they use a scene graph system or not, must manage data. The objects to be drawn must be stored somewhere, and must be dispatched to a renderer in a more or less sequential fashion. The data storage, management and access machinery is fundamental part of scene graph systems. Use of this existing machinery is a convenience, and use of this machinery relieves applications developers of the burden of creating and maintaining this central part of a graphics application.

In addition to the data management infrastructure, additional convenience comes in the form of management of intricacies and details. A complex scene in three dimensions contains many different elements, including light sources, a camera model used to view the scene, objects in the scene, and so forth. Additional details that might escape a quick glance include clipping planes, a mechanism for clearing the color and depth buffers at the start of each frame, viewport controls. Keeping track of all this information, along with providing reasonable defaults, can be vastly simplified by a good scene graph system.

How Many Widgets?

One of the roles of graphics subsystems, such as OpenGL, and graphics hardware is to provide the means to quickly draw objects. Graphics hardware excels at drawing simple objects, such as triangles and line segments. However, graphics hardware is typically not known for its ability to draw more complicated objects, such as polyhedra or spheres. Polyhedra are collections of polygons, while spheres are implicit surfaces with no direct geometric representation. Scene graph systems can store polyhedron data, and feed individual polygons or polygon groups to the graphics hardware. Similarly, spheres can be tessellated into collections of triangles that approximate the implicit surface. Tessellations can be coarse if the viewer is far away from the sphere or if the sphere projects down to a small number of pixels. Scene graph systems can provide numerous primitives above and beyond the set directly supported by the graphics hardware.

Extensibility

Even the most thorough design will fail to deliver all features needed for all applications. When that condition arises, a good scene graph system should be extensible by the developer. Developers should be able to easily add their own "draw code" to support a specialized primitive that is not part of the scene graph system. Having access to the source code for the broader scene graph system is of enormous benefit to the developer that wishes to extend the base system with custom code. Extensions may also include access to platform-dependent features.

Meets Applications Needs

This is where the duct tape test becomes crucial, as developers stretch and bend the system in ways not anticipated by the design. We'll focus on one conceptually simple but powerful feature, multipass rendering. Multipass rendering refers to the process of having the scene graph system make multiple passes through the scene graph, rendering the same or different portions of the scene graph using different rendering parameters.

A good use for multipass rendering is for creating images of scenes that contain both transparent and opaque objects. In the first rendering pass, all the opaque objects are drawn using the usual z-buffer depth test. Then, in the second rendering pass, only transparent objects are rendered. During rasterization of transparent objects, a pixel is drawn if its z-value is less than the value of the depth buffer. Instead of writing the pixel's color into the framebuffer, the color is instead blended with the existing color in the framebuffer. The transparent objects must first be sorted in back-to-front order so that the blending is correct, since the blending operation does not commute.

Scenes consisting of arbitrary 2D and 3D components are likewise well-suited for deployment in a scene graph that supports configurable multipass rendering. A heads-up display, or instrument panel, can be inexpensively drawn as 2D objects on top of a 3D scene. Stereoscopic rendering consists of a left-eye and right-eye channel, and a stereo camera should be part of all scene graph systems.

A slightly different use of multipass rendering is to have the results of rendering used as input for some other rendering. Shadow algorithms render the scene from the position of the light, then use the depth buffer from that image as a luminance map in a subsequent rendering operation. Rendering of extremely complex 3D scenes in which only a small portion of the scene changes between frames can be accelerated by saving the depth and color buffers from a rendering that does not include the part that changes, then reusing them in later frames, drawing only the part of the scene that changes. Some scene graph systems allow applications to specify a background depth and framebuffer image to load prior to rendering, thereby providing a framework for implementing inter-frame, as well as intra-frame, multipass rendering.

Future Applications

A common theme in many of the points that have been made is that scene graph systems provide a way to leverage a number of resources. Future applications will likely be network-centric. In networked applications, a scarce resource that requires careful management is network bandwidth. Network latency and jitter must also be taken into account for some applications. One way to reduce the network bandwidth required for some graphics applications will be to adopt a position of requiring the client to do a lot of work. Specifically, a terse scene description consisting of a compact representation expands into a complete scene description on the client side, and the client contains tools that allow a user to navigate through a colorful, interesting and compelling three-dimensional scene.

As an example, the current e-commerce experience can be likened, in most cases, to a trip through the card catalogue at the local library. Access to information is good, but it is presented in list or tabular form. A more compelling and fun experience would be one that more closely matches the way people really shop: we browse and we make serendipitous discoveries. We are visual creatures. However, downloading a complete scene description of the local hardware store is beyond reasonable, not only from the perspective of network bandwidth, but also in terms my laptop's capabilities. A shopper can only see so much stuff at one time, and scene graph systems are a great framework for implementing view-dependent operations. Only those items that are close to me need to be loaded in my computer. The items on the other side of the store don't interest me at the moment, and they don't need to be transmitted to my computer. As I navigate through the store, the data that is needed for my local view can be requested and downloaded by the client on my laptop.

There are numerous scene graph systems available commercially as well as in the Open Source community. Of these, RM Scene Graph from R3vis Corporation in Novato, California. RM has been used in commercial products as well as in government research labs to tackle a wide variety of visualization and 3D graphics problems. Recently, R3vis announced the launch of OpenRM, an Open Source project based upon the commercial RM technology. It provides support for multipass rendering, including stereoscopy, a rich assortment of geometric and image-based primitives, is easily extensible, and runs on Unix and Win32 platforms.