Jim Durbin, Rich Gossweiler, Randy Pausch
University of Virginia, School of Engineering
Department of Computer Science
[durbin | rich | pausch]@Virginia.edu, (804) 982-2289
Table of Contents
Amortizing 3D Graphics Optimization Across Multiple Frames
Cover Page
Submission Category: Conference Paper
Title: Amortizing 3D Graphics Optimization Across Multiple Frames
Contributors:
Jim Durbin (804) 982-2292 durbin@virginia.edu
Rich Gossweiler (804) 982-2289 rich@Virginia.edu
Randy Pausch (804) 982-2211 pausch@Virginia.edu
University of Virginia, School of Engineering
Department of Computer Science
Charlottesville, VA 22903
Contribution: Description of optimization mechanism
Primary Contact: Rich Gossweiler (rich@virginia.edu)
Keywords: three-dimensional graphics, interactive graphics, real-time, optimization, rendering, virtual environments
100 word abstract:
This paper describes a mechanism for improving rendering rates dynamically during runtime in an interactive three-dimensional graphics application. Well-known techniques such as transforming hierarchical geometry into a flat list and removing redundant graphics primitives are often performed off-line on static databases, or continuously every rendering frame. In addition, these optimizations are usually performed over the whole database. We observe that much of the database remains static for a fixed period of time, while other portions are modified continuously (e.g. the camera position), or are repeatedly modified during some finite interval (e.g. during user interaction). We have implemented a runtime optimization mechanism which is sensitive to repeated, local database changes. This mechanism employs timing strategies which optimize only when the cost of optimization will be amortized over a sufficient number of frames. Using this optimization scheme, we observe a rendering speedup of roughly 2.5 in existing applications. We discuss our initial implementation of this mechanism, the improved timing measurements, the issues and assumptions we made, and future improvements.
Amortizing 3D Graphics Optimization Across Multiple Frames
However, for the rendering engine, a hierarchical data structure is not optimal. To keep the highly pipelined architecture of modern graphics hardware from stalling, we would prefer to make few, if any calculations while traversing the graphics database. To that end, a flat list of graphics primitives is preferable, because it requires no combination of transformations (e.g. matrix multiplications). Flat lists also offer the opportunity to perform compiler-like peephole optimizations (e.g. removing redundancies), and is efficient for pipelining graphics.
The use of optimization techniques to improve rendering speeds is well-established, in both research (e.g. the Berkeley and UNC Walkthrough projects [7][1][2]) and commercial systems (e.g. SGI Performer [11]). These two systems exemplify both ends on the spectrum of when to optimize. The Berkeley Walkthrough assumes that the database is static, and can perform aggressive off-line optimization to restructure the database for improved runtime performance. Performer, on the other hand, supports very dynamic environments and cannot make assumptions about the static nature of the database. Performer employs global database optimization for every frame. Since optimization takes time, Performer users prefer to execute these mechanisms on an auxiliary CPU to minimize impact on the rendering CPU. Both techniques apply optimization globally over the database.
In this paper, we present optimizations that occurs after higher-level techniques such as culling objects which are not in view, or using multiple representations of objects stored at various levels of detail [12].
We have observed that in many applications some portions of the database remain unchanged during the entire run, and other portions change repeatedly, but during brief intervals (e.g. when the user is directly manipulating the object), and still other portions change continuously (e.g. the camera location).
This paper describes a mechanism for improving rendering rates dynamically during runtime in an interactive three-dimensional graphics application. Well-known techniques such as transforming hierarchical geometry into a flat list and removing redundant graphics primitives are often performed off-line on static databases, or continuously every rendering frame. In addition, these optimizations are usually performed over the whole database. We observe that much of the database remains static for a fixed period of time, while other portions are modified continuously (e.g. the camera position), or are repeatedly modified during some finite interval (e.g. during user interaction). We have implemented a runtime optimization mechanism which is sensitive to repeated, local database changes. This mechanism employs timing strategies which optimize only when the cost of optimization will be amortized over a sufficient number of frames. Using this optimization scheme, we observe a rendering speedup of roughly 2.5 in existing applications. We discuss our initial implementation of this mechanism, the improved timing measurements, the issues and assumptions we made, and future improvements.
three-dimensional graphics, interactive graphics, real-time, optimization, rendering, virtual reality
In 1976 Clarke suggested that a hierarchical data structure would have several characteristics which are useful for manipulating and rendering graphics objects [4]. One powerful advantage of a tree structure for the application programmer is that matrices at each node in the tree can represent individual coordinate systems. When the programmer manipulates a graphics object, its children will inherit the changes implicitly [13].
This paper is currently submitted to ACM UIST `95.
Since we have constructed a rendering system which is application independent [8], we, like Performer, cannot make assumptions that a given portion of the database will remain static. We must analyze the database during runtime. Instead of attempting to transform the entire database during each frame, our mechanism records the frequency with which portions of the database change, and uses this information to predict how frequently the object will be changed in the near future. The mechanism determines or predicts the cost of performing an optimization and uses a simple utility function to determine the value of optimizing those portions of the database. The algorithm collects data about the average frequency for which each object gets altered. If the object does not get altered frequently, then the cost to optimize the object may be worth the savings recouped over later frames. However, if the object is constantly changing, then there is less incentive to perform the optimization, as the benefits will be fleeting. Our approach is a hybrid, as shown in Figure 1:
Figure 1: When to optimize
We implemented our optimization mechanism as part of the Alice graphics system [10]. Alice supports a variety of applications ranging from immersed virtual environments, to rapid exploration of three-dimensional interfaces, to a teaching tool for graphics classes. The rendering subsystem [8] is based on a hierarchical data structure. All graphical objects in the rendering sub-system are represented as nodes in the tree. Nodes contain transformation matrices and may also contain geometry consisting of polygons, polylines or polypoints.
When rendering from this data structure, there are two basic forms of inefficiency:
1) matrix multiplications to combine the implicitly chained transformations (in order to render a leaf node, we must first apply all the transformations from the root node to that leaf).
2) redundant calls to set state in the graphics pipeline; for example, in most objects, a large number of polygons are the same color. Repeatedly calling the graphics setColor() subroutine (the OpenGL glColor3f() call) [9] disrupts the pipeline. In addition, even using a local if statement in the inner rendering loop also disrupts the hardware pipeline [5], degrading rendering performance. This is partially because the if statement to compare with, for example, the current normal vector, needs to compare three floating point values. The most efficient mechanism is to produce the list of graphics calls which will be streamlined into the graphics pipeline, and to remove the redundant calls. This is exactly what Performer does on an extra CPU for each frame.
Our technique involves several optimization phases and a separate mechanism for analyzing the benefit of performing the optimizations. The phases are:
- streamlining each individual node in the tree by creating an array of graphics calls without any intervening computations. This is done for each node in the tree, so that if the node is altered, only that particular node's streamlined array needs to be re-constructed
- peephole optimization to the streamlined list, removing redundancies
- flattening the hierarchical tree structure -- coalescing nodes so that each subtree node has a single cache list representing all of its children at one transformed level. We call this list the streamlined array.
- peephole optimization of the flattened list for the entire subtree
Since invoking these optimization mechanisms requires time, we need a guideline to determine if it is worth performing these operations. The algorithm must evaluate the time needed to perform the optimizations, how long the object has remained unaltered and how much of a predicted improvement will be achieved.
Converting Each Node into a Rendering List
Each node in the tree may be thought of as a container holding a set of properties describing the object or sub-object at that level. For example, in a hierarchical model of a bunny, the bunny's foot may be a child of the bunny's leg. As a node, the foot contains geometry, color information and inherits the transformation matrix from its parent (the leg). When traversing the foot's node, the rendering engine may have to perform several conditional statements to determine how to draw the foot. The color may be inherited from the parent (the leg), set for all of the polygons, be specified for each individual polygon, or specified for each individual vertex of each polygon. Evaluating these conditional statements every frame disrupts the pipeline. If the graphics calls are the same from frame to frame, these calls can be cached into an array. Then the rendering engine can iterate through the array rather than making repeated conditional evaluations. While it is surprising that seemingly minor conditional tests have a strong impact on rendering performance, this is due to the highly pipelined nature of high-end graphics hardware. To quote the authors of SGI Performer:
"The data structures used to represent geometry and the code which transfers that data to the graphics hardware very often make or break an immediate-mode graphics application." [11]
Peephole Optimization
When rendering an object, there are many polygons which are the same color. Instead of resetting the color for every vertex or for every polygon, the color call can be factored out and made only once.
This redundancy factoring can occur for many of the properties which characterize the object (e.g. the color, the vertex normal vectors, and the textures). For the initial implementation, our optimization removes redundant color and normal information. This operation is performed during the construction of the streamlined array.
Early peephole compilers used a similar method to track the source of a register's value and remove redundant load commands [6]. More sophisticated peephole optimizers perform increasingly complex pattern matching and even rearrange code in an attempt to minimize the number of instructions and register manipulations; we hope to use a number of these techniques to further optimize rendering.
Flattening the Tree
Since the optimization mechanism is traversing the hierarchical structure and creating cache arrays for each node, the cost to accumulate the transformation matrices is trivial. This allows the optimization mechanism to effectively flatten subtrees into a single node with a longer cache array.
Figure 2: Tree flattening
Note that the original hierarchy is not discarded, since alterations to the nodes in the tree require that the cache be invalidated and the original hierarchy be available.
Flattening the hierarchy into a rendering list is an explicit function call in Performer, and therefore makes it the responsibility of the application programmer to perform this operation. Our optimization mechanism engages automatically when optimization is cost-effective.
The important distinction of our mechanism is how it determines when optimization should be done, and to which portions of the database. Performer does optimization globally to the entire hierarchy every frame. Our approach is to perform a utility measurement, comparing the cost/benefit of flattening subtrees and factoring out redundant calls. We measure how long an object remains unaltered, how long it takes to optimize, and the value of performing the optimizations.
Wall-clock Time v. Frame Time
Because we are interested in how many times an object is modified versus how many times it is rendered, it is more appropriate to use rendering frame counts rather than wall-clock time. For example, if we used wall-clock time, and the system pauses momentarily (perhaps due to other users on the machine) a single frame could take arbitrarily long to render. The ratio of how frequently the object is modified to how frequently it is rendered is what is important.
While frame-counting is necessary to determine when to optimize, wall-clock time is necessary to compute the effectiveness of the optimizations. We measure the rendering times of objects in both their unoptimized and optimized states.
Important Information for the Algorithm
AUT -- Average Unaltered Time: the ratio of the number of frames where an object is not altered to the total number of frames (This is a running total average, but other options are discussed later).
TTRU -- Time to Render Unoptimized: the amount of time to render an object without any optimizations.
TTRO -- Time To Render Optimized: the amount of time to render an object once it has been optimized.
OT -- Optimization Time: the time it takes to perform the optimization on the object.
Computing Variables
Since there already is a penalty for loading an object from the disk we expend slightly more time to obtain timing information. We load the object and render it several times without performing a swapbuffer() call. During this time we gather the TTRU, the TTRO and the OT. We also create the streamlined array for each node. The performance cost of gathering this information is not observable, as it is dominated by the time to read the object from the disk.
Dynamically Created Objects
During the execution of the program, subtrees may be reparented, effectively creating new objects, and the timing variables cease to be representative. In this case, we use a simple, coarse predictive function based on the number of polygons in a subtree.
Based on timings taken on a large number of subtrees on an SGI Reality Engine2 [3], we find for an N polygon subtree, the representative times are:
EstimatedTTRU = (0.0000127 * N) seconds
EstimatedTTRO = (0.0000038 * N) seconds
EstimatedOT = (0.0000879 * N) seconds
The Utility Function
For each node, we store the TTRU, TTRO, and OT. The utility function computes the amount of savings we will obtain over the average unaltered time (AUT) and adds the cost of performing the optimization. The total is compared to the cost of rendering unoptimized over the same AUT:
if (TTRO*AUT + OT < TTRU*AUT) then optimize...
This simple algorithm does not prevent arbitrarily bad hitches. For example, if the object has not changed for a very long time, but the optimization time (OT) is five seconds, the algorithm would perform the optimization, and the system would stall for five seconds. This problem can be solved by placing a hard upper limit on the allowable OT.
Since our system supports a dynamic tree, we must invalidate the caches when an object's characteristics change (e.g. color, translucency, texture), when the object's matrix undergoes a transformation, and when reparenting occurs. The caches are marked dirty and the rendering engine traverses the unoptimized hierarchy instead. Since each node maintains its own streamlined array, any unaltered node keeps its streamlined array:
Figure 3: invalidating the optimizations
The effectiveness of this optimization mechanism depends on how frequently an application alters an object. If the object is altered continuously, then no optimizations are performed. If an object is never altered, then it is optimized once and remains in the optimized state for the duration of the application.
To establish that these optimizations produce a worthwhile savings, we measured the time to render a variety of objects when they are optimized and when they are unoptimized. The results are shown in Table 1. The graphical objects in the table represent several contrived and actual objects to explore variations on tree configurations and redundancy removal. Note that these speedups are greater than 2.5; actual day-to-day use achieves roughly a 2.5 speedup because of constant cost operations per frame such as clearing and swapping the frame buffer, which dilutes the speedup somewhat.
Note to the reviewers: the enclosed video tape shows the amusement park simulation rendering at 12 frames per second without optimizations and 29 frames per second with the optimizations engaged.
As future work we would like to gather statistics about how frequently objects are optimized and how long they remain optimized.
The graphics database is accessed by both the application program and the rendering engine, but the usage patterns and frequency of access dictate very different internal representations. Transforming a subtree into a render-optimized list steals rendering time which may be recouped over future frames. The question of utility becomes, "Is it worth the time to optimize now, to speed up the application for the future?" By observing that some parts of the tree are active for discrete periods of time, we have implemented a runtime optimization mechanism which optimizes only local portions when the utility of optimization appears worthwhile. The results are dependent on usage patterns, but initial timing experiments indicate that this mechanism is useful for improving runtime efficiency. Our initial measurements indicate a factor of 2.5 increase in rendering speeds when the optimization mechanism is employed.
We have two high level observations based on this implementation. The first is that preliminary results of employing this mechanism look promising. Alice was recently used in a graphics class project where ten students built an amusement park (each student built individual rides). This was a fair test, involving an application written by a ten person team, unaware of the underlying optimization techniques. The optimization mechanism improves the rendering by a factor of 2.5.
Our second observation is that trees are typically constructed with very little depth -- on the order of five levels or less.
The following is a brief list of issues we intend to consider as we continue this work.
The rendering engine, by computing the bounding volumes of subtrees, knows which objects in the tree are located near each other after the matrix transformations. This may not be identical to the way the user has constructed the parent-child relationships of the tree.
For portions of the database which do not change over long periods of time, the rendering engine could flatten the application tree and then reconstruct a different tree based on spatial locality. This would allow for more efficient high-level culling.
We currently compute all variables for the optimizations at runtime. There may be some benefit in storing the timing data across runs. This information might be useful when determining the utility of flattening and may serve as a second-order statistic about the nature of the object (e.g. the "lamp" object is used by many applications as static decoration).
We currently compute the Average Unaltered Time (AUT) over the entire run. An alternate approach is to weight the timings, so that over time the more recent alterations influence the average more than alterations having occurred a long time ago. The general problem is similar to the page replacement problem in operating systems.
It might be prudent in some cases to allow the application to explicitly express good moments to perform optimizations. For example, if the application knows that the user has paused or gone into another mode, then that might be a good time to optimize.
For example, if we flatten a bunny object which has children nodes of head, body and arms, and then we rotate the head, the entire head tree will be unflattened. If, instead, we progressively flatten each subtree into larger and larger lists, we can unflatten only the portions which have been altered, rather than the whole subtree.
Using this optimization mechanism does not preclude off-line optimization. For example, with a static database such as the Berkeley Walkthrough, off-line optimization can provide a great deal of effective visibility culling. During runtime a given "cell of visibility" may still have a large number of objects. Our mechanism may then be effective for improving the cell.
- 1.
- John M. Airey, John H. Rholf and Frederick Brooks Jr., Towards Image Realism with Interactive Update Rates in Complex Virtual Building Environments, ACM SIGGRAPH Special Issue on 1990 Symposium on Interactive 3D Graphics, 24 (2), 1990, pp. 41-50.
- 2.
- Frederick Brooks Jr, Walkthrough - A Dynamic Graphics System for Simulating Virtual Buildings, Proceedings of the 1986 Workshop on Interactive 3D Graphics.
- 3.
- Kurt Akeley, Reality Engine Graphics, ACM Annual Proceedings of SIGGRAPH `93 (Anaheim California), August 1-6, 1993, Addison-Wesley, pp. 109-116.
- 4.
- James H. Clarke, Hierarchical Geometric Models for Visible Surface Algorithms, Communications of the ACM, 19(10), October 1976, pp. 547-554.
- 5.
- Sharon Clay, member of SGI Perfomer Group. Personal conversation, April 25, 1995.
- 6.
- Jack W. Davidson and Christopher W. Fraser, Register Allocation and Exhaustive Peephole Optimization, Software -- Practice and Experience, 14(9), John Wiley & Sons, September 1984, pp. 857-865.
- 7.
- Thomas A. Funkhouser, Carlo Séquin and Seth J. Teller, Management of Large Amounts of Data in Interactive Building Walkthroughs, 1992 Symposium on Interactive 3D Graphics, ACM SIGGRAPH, Cambridge Mass. April 1992, pp. 11-20.
- 8.
- Rich Gossweiler, Chris Long, Shuichi Koga, Randy Pausch, DIVER: A Distributed Virtual Environment Research Platform, IEEE Symposium on Research Frontiers in Virtual Reality, October 25-26, 1993, San Jose, CA, pp. 10-15.
- 9.
- Jackie Neider, Tom Davis and Mason Woo, Open GL Programming Guide, Addison-Wesley, Reading, Mass, 1993.
- 10.
- Randy Pausch, Tommy Burnette, A.C. Capehart, Matthew Conway, Dennis Cosgrove, Rob DeLine, Jim Durbin, Rich Gossweiler, Shuichi Koga, Jeff White, Alice: A Rapid Prototyping System for 3D Graphics, IEEE Computer Graphics and Applications, 15(3), May 1995, pp. 8-11.
http://www.cs.virginia.edu/~alice/
- 11.
- John Rohlf and James Helman, IRIS Performer: A High Performance Multiprocessing Toolkit for Real-Time 3D Graphics, ACM Annual Proceedings of SIGGRAPH `94, (Orlando Florida), July 24-29, 1994, Addison-Wesley, pp. 381-393.
- 12.
- Bruce Schachter (Ed.), Computer Image Generation, John Wiley and Sons, New York, NY, 1983.
- 13.
- Andries van Dam, et al. PHIGS+ Functional Description 3.0, Computer Graphics, 22 (3), July, 1988, pp. 124-218.
