The Render Graph: A Data Structure to Aid in the Interactive Display of Scene Graph Data

ii Interactive display of three-dimensional geometry has become increasingly popular over the past decade. This geometry is usually organized into a directed graph structure called a scene graph, with display of that geometry implemented by walking that graph. This is insufficient to properly display a wide variety of scenes, especially if there are transparent elements within the scene that require display in a specific order. In addition, to provide for the fastest display of scene-graph geometry, render state changes should be minimized, and reconciling the requirements for display of transparent geometry with the minimization of state changes can be difficult. This thesis presents a data structure built from the scene graph which is structured to make the rearrangement of the scene-graph data for correct and fast display simple. The render graph is designed to reorganize the scene-graph data in order to minimize the number of render state changes, take advantage of spatial and temporal coherency within the stream of graphics instructions, and also to provide for the correct display of elements with camera-space order dependencies (such as transparent elements). As a side effect it also provides an abstraction layer that simplifies porting the display system to new graphics hardware interfaces (e.g. OpenGL, Direct3D). ii