“Adaptive display algorithm for interactive frame rates during visualization of complex virtual environments” by Funkhouser and Séquin

We describe an adaptive display algorithm for interactive frame
rates during visualization of very complex virtual environments.
The algorithm relies upon a hierarchical model representation in
which objects are described at multiple levels of detail and can
be drawn with various rendering algorithms. The idea behind the
algorithm is to adjust image quality adaptively to maintain a uniform, user-specified target frame rate. We perform a constrained
optimization to choose a level of detail and rendering algorithm for
each potentially visible object in order to generate the “best” image
possible within the target frame time. Tests show that the algorithm
generates more uniform frame rates than other previously described
detail elision algorithms with little noticeable difference in image
quality during visualization of complex models.

1. Airey, John M., Rohlf, John H., and Brooks, Jr., Frederick P. 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), 41-50.
2. Blake, Edwin H. A Metric for Computing Adaptive Detail in Animated Scenes using Object-Oriented Programming. Eurographics ’87. G. Marechal (Ed.), Elsivier Science Publishers, B.V. (North-Holland), 1987.
3. Brooks, Jr., Frederick P. Walkthrough – A Dynamic Graphics System for Simulating Virtual Buildings. Proceedings of the 1986 Workshop on Interactive 3D Graphics.
4. Clark, James H. Hierarchical Geometric Models for Visible Surface Algorithms. Communications of the ACM, 19, 10 (October 1976), 547-554.
5. Funkhouser, Thomas A., Saquin, Carlo H., and Teller, Seth J. Management of Large Amounts of Data in Interactive Building Walkthroughs. ACM SIGGRAPH Special Issue on 1992 Symposium on Interactive 3D Graphics, 11-20.
6. Garey, Michael R., and Johnson, David S. Computers and Intractibility: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979.
7. Ibaraki, T., Hasegawa, T., Teranaka, K., and Iwase J. The Multiple Choice Knapsack Problem. J. Oper. Res. Soc. Japan 21, 1978, 59-94.
8. Rossignac, Jarek, and Bowel, Paul. Multi-resolution 3D approximations for rendering complex scenes. IFIP TC 5.WG 5.10 H Conference on Geometric Modeling in Computer Graphics, Genova, Italy, 1993. Also available as IBM Research Report RC 17697, Yorktown Heights, NY 10598.
9. Schachter, Bruce J. (Ed.). Computer Image Generation. John Wiley and Sons, New York, NY, 1983.
10. Graphics Library Programming Tools and Techniques, Document #007-1489-01, Silicon Graphics, Inc., 1992.
11. Teller, Seth J., and S6quin, Carlo H. Visibility Preprocessing for Interactive Walkthroughs. Proceedings of SIGGRAPH ’91. In Computer Graphics 25, 4 (August 1991), 61-69.
12. Teller, Seth J. Visibility Computations in Densely Occluded Polyhedral Environments. Ph.D. thesis, Computer Science Division (EECS), University of California, Berkeley, 1992. Also available as UC Berkeley technical report UCB/CSD-92-708.
13. Zyda, Michael J. Course Notes, Book Number 10, Graphics Video Laboratory, Department of Computer Science, Naval Postgraduate School, Monterey, California, November 1991.