J
`
`'
`
`V
`
`‘
`
`,
`
`-
`
`<
`
`V
`
`_
`
`‘
`
`.
`
`‘
`
`V
`
`‘
`
`V
`
`‘
`
`-
`
`r
`
`—
`
`‘
`
`'
`
`
`
`“
`
`A
`
`'
`
`,
`
`‘
`
`.
`
`'
`
`: ; D <
`
`.
`
`.
`
`.
`
`I { S
`
`
`
`
`
`
`
`
`
`V _Symp'osium—Chair
`_
`Michaelzyda, »
`, Program Co-jCha’irs ’
`’Pa't Hanrahan
`Jim Winget
`‘
`
`,
`
`V
`
`V
`
`V
`‘
`
`.'
`
`A
`
`;
`
`' [ r
`
`o
`
`
`
`Sponsored by_ the Association for"
`Computihg Machinery‘s Special‘
`Interest Group or; Computer:
`
`Graphics
`7, V
`V
`
`7
`
`Apublication'ofACMSIGGRAPH
`
`‘
`
`L
`
`'
`
`
`
`/A’
`
`TEXAS INSTRUMENTS EX. 1010 - 1/17
`
`

`
`Prgceedings
`1995 Symposium on
`Interactive 3D Graphics
`
`’§,};l:,§@~, e:’;3A
`
`Monterey, California
`April 9 -12, 1995
`
`Symposium Chair
`
`Michael Zyda, Naval Postgraduate School
`
`Program Co-Chairs
`
`Pat Hanrahan, Stanford University
`Jim Winget, Silicon Graphics, Inc.
`
`Program Committee
`
`Frank Crow, Apple Computer
`Andy van Dam, Brown University
`Michael Deering, Sun Microsystems
`Steven Feiner, Columbia University
`Henry Fuchs, UNC - Chapel Hill
`Thomas Funkhouser, Bell Labs
`Fred Kitson, Hewlett-Packard
`Randy Pausch, University of Virginia
`Paul Strauss, Silicon Graphics, Inc.
`Andy Witkin, Camegie—Mellon University
`David Zeltzer, Massachusetts Institute of Technology
`
`Financial support provided by the following organizations:
`
`Office of Naval Research, Advanced Research Projects Agency
`US. Army Research Laboratory
`Apple Computer
`AT&T B ell Laboratories
`Cyberware
`Hewlett-Packard
`
`Microsoft Corporation
`Silicon Graphics, Inc.
`Sun Microsystems
`
`Production Editor
`
`Stephen Spencer, The Ohio State University
`
`00t.(;
`/l>2fYtc
`
`liar
`
`Sponsored by the Association for Computing Machinery's Special Interest Group on Computer Graphics
`
`TEXAS INSTRUMENTS EX. 1010 - 2/17
`
`TEXAS INSTRUMENTS EX. 1010 - 2/17
`
`

`
`The Association for Computing Machinery, Inc.
`1515 Broadway, 17th Floor
`New York, NY 10036
`
`Copyright © 1995 by the Association for Computing Machinery, Inc. Copying without fee is permit-
`ted provided that the copies are not made or distributed for direct commercial advantage and credit to
`the source is given. Abstracting with credit is permitted. For other copying of articles that carry a code
`at the bottom of the first page, copying is permitted provided that the per-copy fee is paid through the
`Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 01923. For permission to republish
`write to Director of Publications, Association for Computing Machinery. To copy otherwise, or re-
`publish, requires a fee and/or specific permission.
`
`Orders from ACM Members:
`
`A limited number of copies are available at
`the ACM member discount. Send order with
`payment in US. dollars to:
`
`ACM Order Department
`P.O. Box 12114
`Church Street Station
`New York, NY 10257
`
`0
`
`OR, for information on accepted European
`currencies and exchange rates, contact:
`.
`
`ACM European Service Center
`Avenue Marcel Thiry 204
`1200 Brussels
`
`Belgium
`Tel: +32 2 774 9602
`Fax: +32 2 774 9690
`Email: acm_europe@acm . org
`
`_
`
`Credit card orders from US. and Canada:
`1-800—342-6626
`
`Credit card orders may also be placed by
`mail.
`‘
`
`Credit card orders from the New York
`metropolitan area and outside the
`U.S.:
`
`+1 212-626-0500
`
`Single-copy orders placed by fax:
`+1 212-944-1318
`
`Electronic mail inquiries may be directed to
`acmhe lp@acm. org.
`
`Please include your ACM member
`number and the ACM order number
`with your order:
`
`ACM Order Number: 429953
`ACM ISBN: 0-89791-736-7
`
`TEXAS INSTRUMENTS EX. 1010 - 3/17
`
`TEXAS INSTRUMENTS EX. 1010 - 3/17
`
`

`
`Table of Contents and Symposium Program
`
`Preface ........................................................................................................................................................... ..4
`
`Monday, April 10, 1995
`
`8:00,— 8:15
`
`Welcome
`
`8:15 — 10:15
`
`Session 1: Virtual Reality
`Chair: Henry Fuchs — University ofNorth Carolina, Chapel Hill
`
`Resolving Occlusion in Augmented Reality .................................................................................................. .. 5
`Matthias M. Wloka and Brian G. Anderson
`
`Surface Modification Tools in a Virtual Environment Interface to a Scanning Probe Microscope ............ .. 13
`M. Finch, M. Falvo, I/. L. Chi, S. Washburn, R. M. Taylor, and R. Superfine
`Color Plates ............................................................................................................................................... .. 203
`
`Combatting Rendering Latency .................................................................................................................. .. 19
`Marc Olano, Jon Cohen, Mark Mine and Gary Bishop
`Color Plates ................................................... .; .......................................................................................... .. 204
`
`Underwater Vehicle Control from a Virtual Environment Interface .......................................................... .. 25
`Stephen D. Fleischer, Stephen M. Rock and Michael I Lee
`Color Plates ............................................................................................................................................... .. 204
`
`11:00 — 12:05
`
`Session 2: Geometric Modeling
`Chair: Paul Strauss — Silicon Graphics, Inc.
`
`Interactive Design, Analysis, and Illustration of Assemblies ..................................................................... .. 27
`Elana Driskill and Elaine Cohen
`
`Hierarchical and Variational Geometric Modeling with Wavelets ............................................................ .. 35
`Steven J. Gortler and Michael F. Cohen
`Color Plates ............................................................................................................................................... .. 205
`
`Interactive Shape Metamorphosis ............................................................................................................... ..43
`David T. Chen, Andrei State and David Banks
`»
`Color Plates ............................................................................................................................................... .. 205
`
`12:05 -— 1:30
`
`Lunch
`
`1:30 — 3:10
`
`Session 3: Rendering Systems
`Chair: Michael Deering — Sun Microsystems
`
`Shadow Volume BSP Trees for Computation of Shadows in Dynamic Scenes ........................................ ..45
`Yiorgos Chrysanthou and Mel Slater
`
`Interactive Display of Large-Scale NURBS Models .................................................................................
`Subodh Kumar, Dinesh Manocha and Anselmo Lastra
`Color Plates ............................................................................................................................................... .. 206
`
`51
`
`Real-Time Programmable Shading ............................................................................................................. .. 59
`Anselmo Lastra, Steven Molnar, Marc Olano and Yulan Wang
`Color Plates ............................................................................................................................................... .. 207
`
`Interactive Full Spectral Rendering ............................................................................................................ .. 67
`Mark S. Peercy, Benjamin M. Zhu and Daniel R. Baum
`Color Plates ............................................................................................................................................... .. 207
`
`4:00 — 5:00
`
`Session 4: Benefits of Exchange Between Computer Scientists and Perceptual Scientists
`Chair: Randy Pausch — University of Virginia
`‘ Panel: Robert Eggleston — Wright-Patterson AFB, Steve Ellis — NASA Ames, Mary Kaiser — NASA
`Ames, Jack Loomis — UCSB, Dennis Profiitt — University of Virginia
`
`8:00 — 9:30
`
`Session 5: Government Programs on Virtual Environments & Real-Time Interactive 3D
`Chair: Michael Zyda, Naval Postgraduate School
`Panel: Rick Satava —ARPA, Craig Wier —ARPA, Ralph Wachter — ONR, Paul Stay — ARL
`
`v
`it "' as
`E£‘1%f%I$/) in if if
`.5; ii;
`».
`TEXAS INs'TRl“LJ“i§/I"é’i\‘?1”§Ts EX. 1010 — 4/17
`
`TEXAS INSTRUMENTS EX. 1010 - 4/17
`
`

`
` 8:30 — 10:10
`
`Tuesday, April 11, 1995
`
`Session 6: Parallel and Distributed Algorithms
`Chair: Frank Crow —« Apple Computer
`
`Interactive Volume Visualization on a Heterogeneous Message-Passing Multicomputer ..... .. ................. .. 69
`A. State, J. McAllister, U. Neumann, H. Chen, T. J. Cullip, D. T. Chen and H. Fuchs
`Color Plates ............................................................................................................................................... .. 208
`
`The Sort-First Rendering Architecture for High-Performance Graphics ................................................... .. 75
`Carl Mueller
`Color Plates ............................................................................................................................................... .. 209
`
`RING: A Client-Server System for Multi-User Virtual Environments ...................................................... .. 85
`Thomas A. Funkhoiiser
`Color Plates ............................................................................................................................................... .. 209
`
`NPSNET: A Multi-Player 3D Virtual Environment over the Internet ....................................................... .. 93
`M. R. Macedonia, D. P. Brutzman, M. J. Zyda, D. R. Pratt, P. T. Barham, J. Falby and J. Locke
`Color Plates ............................................................................................................................................... .. 210
`
`11:00-12:10
`
`Session 7: Virtual Environments
`Chair: Thomas Funkhouser — AT&T Bell Laboratories
`
`Visual Navigation of Large Environments Using Textured Clusters ......................................................... .. 95
`Paulo W. C. Maciel and Peter Shirley
`Color Plates ............................................................................................................................................... .. 211
`
`Guided Navigation of Virtual Environments ............................................................................................ .. 103
`Tinsley A. Galyean
`Color Plates ............................................................................................................................................... .. 210
`
`Portals and Mirrors: Simple, Fast Evaluation of Potentially Visible Sets ............................................... .. 105
`David Luebke and Chris Georges
`Color Plates ............................................................................................................................................... .. 212
`
`Interactive Playing with Large Synthetic Environments .......................................................................... .. 107
`Bruce F. Naylor
`Color Plates ............................................................................................................................................... .. 212
`Lunch
`
`Session 8: Input and Output Techniques
`Chair: Randy Pausch — University of Virginia
`Of Mice and Monkeys: A Specialized Input Device for Virtual Body Animation .................
`Chris Esposito, W. Bradford Paley and JueyChong Ong
`Color Plates ............................................................................................................................................... .. 213
`
`................. 109
`
`A Virtual Space Teleconferencing System that Supports Intuitive Interaction
`for Creative and Cooperative Work .......................................................................................................... .. 115
`M. Yoshida, Y. Tijerino, S. Abe and F. Kishino
`
`Haptic Rendering: Programming Touch Interaction With Virtual Objects ............................................. ..123
`K. Salisbury, D. Brock, T. Massie, N. Swamp and C. Zilles
`
`12:10— 1:30
`
`1:30—2:50
`
`4:00 — 5:00
`
`Session 9: Invited Speaker
`
`TEXAS INSTRUMENTS EX. 1010 - 5/17
`
`
`TEXAS INSTRUMENTS EX. 1010 - 5/17
`
`

`
`Wednesday, April 12, 1995
`
`8; 30 — 10:10
`
`Session 10: Interactive Manipulation
`Chair: David Zeltzer — MIT Research Laboratory ofElectronics
`
`Object Associations: A Simple and Practical Approach to Virtual 3D Manipulation ............................. .. 131
`Richard W. Bukowski and Carlo H. Sequin
`Color Plates ............................................................................................................................................... .. 214
`
`CamDroid: A System for Implementing Intelligent Camera Control ...................................................... .. 139
`Steven M. Drucker and David Zeltzer
`
`3D Painting on Scanned Surfaces ............................................................................................................... 145
`Maneesh Agrawala, Andrew C. Beers and Marc Levoy
`Color Plates .......................................................................................................................... .. ................... .. 215
`
`Volume Sculpting ...................................................................................................................................... .. 151
`Sidney W. Wang and Arie E. Kaufman
`Color Plates ............................................................................................................................................... .. 214
`
`11:00 — 12:10
`‘
`
`Session 11: Applications
`Chair: Steven Feiner — Columbia University
`The Tecate Data Space Exploration Utility ............................................................................................ .. 157
`Peter Kochevar and Len Wanger
`
`An Environment for Real-time Urban Simulation .................................................................................... .. 165
`William Jepson, Robin Liggett and Scott Friedman
`Color Plates ............................................................................................................................................... .. 216
`
`Mathenautics: Using Virtual Reality to Visit 3-D Manifolds ................................................................... .. 167
`R. Hudson, C. Gunn, G. K. Francis, D. J. Sandin and T. A. DeFanti
`
`Tracking A Turbulent Spot in an Immersive Environment ...................................................................... .. 171
`David C. Banks and Michael Kelley
`Color Plates ............................................................................................................................................... .. 216
`Lunch
`
`Session 12: Physical and Behavioral Simulation
`Chair: Fred Kitson — Hewlett-Packard Labs
`
`12:10 — 1:30
`
`1:30 — 2:45
`
`
`
`Behavioral Control for Real—Time Simulated Human Agents ................................................................. .. 173
`John P. Granieri, Welton Becket, Barry D. Reich, Jonathan Crabtree and Norman I. Badler
`
`lmpu1se—based Simulation of Rigid Bodies .............................................................................................. .. 181
`Brian Mirtich and John Canny
`.
`Color Plates ............................................................................................................................................... .. 217
`
`I-COLLIDE: An Interactive and Exact Collision Detection System for Large—Scale Environments ..... .. 189
`J. D. Cohen, M. C. Lin, D. Manocha and M. K. Ponamgi
`A
`Color Plates ............................................................................................................................................... .. 218
`
`3:30 -— 4:30
`
`Keynote Address: Interactive 3D Graphics: Challenges and Opportunities
`Henry Fuchs — University ofNorth Carolina, Chapel Hill
`Chair: Andy van Dam — Brown University
`
`Closing Remarks
`Conference Chairs: Pat Hanrahan, Jim Winget and Michael Zyda
`
`Author Index .............................................................................................................................................. .. 197
`Cover Image Credits .................................................................................................................................. .. 199
`Color Plate Section .................................................................................................................................... .. 203
`
`£13
`
`[15
`
`123
`
`TEXAS INSTRUMENTS EX. 1010 - 6/17
`
`
`TEXAS INSTRUMENTS EX. 1010 - 6/17
`
`

`
`The Sort-First Rendering Architecture for High-Performance Graphics Carl Mueller Department of Computer Science University of North Carolina at Chapel Hill Abstract Interactive graphics applications have long been challenging graphics system designers by demanding machines that can provide ever increasing polygon rendering performance. Another trend in interactive graphics is the growing use of display devices with pixel counts well beyond what is usually considered “high resolution.” If we examine the architectural space of high-performance rendering systems, we discover only one architectural class that promises to deliver high polygon performance wirh very-high-resolution displays and do so in an efficient manner. It is known as “sort-first.” We investigate the sort-first architecture, starting with a comparison to its architectural class mates (sort-middle and sort-last). We find that sort-first has an inherent ability to take advantage of the frame-to-frame coherence found in interactive applications. We examine this ability through simulation with a set of test applications and show how it reduces sort-first’s communication needs and therefore its parallel overhead. We also explore the issue of load-balancing with sort-first and introduce a new adaptive algorithm to solve this problem. Additional simulations demonstrate the effectiveness of this algorithm. Finally, we touch on a variety of issues that must be resolved in order to fulfill sort-first’s ultimate promise: millions of polygons for zillions of pixels. 1. Introduction The demands for better interactivity and realism in applications such as vehicle simulation, architectural walkthrough. computer-aided design, and scientific visualization have continually been driving forces for increasing the graphics performance available from high-end graphics systems. Interactivity implies that the images are drawn in real-time in rapid response to user input. This immediately brings out two requirements from the graphics system: it must be able to draw images at approximately 30 frames per second (real-time), and it must have low latency (rapid response). Realism implies that the images are rendered from detailed UNC Sitterson Hall CB 3175; Chapel Hill, NC 27599-3175 phone: (919) 962-1878; email: mueller@cs.unc.edu Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association of Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 1995 Symposium on Interactive 3D Graphics, Monterey CA USA 0 1995 ACM O-89791 -736-7/95/0004...$3.50 scene descriptions, meaning that the scenes consist of many thousands of graphics primitives. Realism also requires a display system that can show the scenes with a level of detail matching what the eye can see. Providing such detail for a reasonable field of view requires millions of pixels. There are a variety of display devices on the path toward offering better realism. The proposed HDTV standard aims at nearly two million pixels. CAVE-type immersive displays [5] cover 4 walls of a room with a total of 5 million pixels, a number much smaller than what is desirable. Even head- mounted displays (HMDs), which would seem to require many fewer pixels, already are reaching one million pixels per eye [ 121 and are expected to go much further. In fact, Kaiser Electro- Optics is working on an ARPA-sponsored project to create an immersive HMD system with 4.6 million pixels per eye [7]. The number of applications which will want to take advantage of such high-resolution display devices will only increase as such devices become more popular. Yet so far, the only way to generate interactive images for these devices requires massive duplication of graphics hardware. Without an efficient solution, use of such devices will be limited to those parties with large acquisition budgets. 2. Parallel Graphics Systems The task of a graphics computer can be described fairly simply. Given a mathematical model of all the objects in a particular environment, it must compute the visual contribution of each object for each pixel in a given viewing plane. This is a type of sorting problem, a fact recognized by Sutherland, Sproull, and Schumacher in 1974 [ 181. For interactive graphics, the task is performed in two major stages: transformation and rasterization. The former converts the model coordinates of each object primitive into screen coordinates, while the later converts the resulting geometry information for each primitive into a set of shaded pixels. The graphics performance demanded by the aforementioned applications requires parallel processing at both the transformation and rasterization stages of the graphics pipeline. The former is needed to cope with the large number of primitives, while the latter is needed for the large number of display pixels. The choices for how to partition and recombine the parallelized work at the different pipeline stages lead to a taxonomy of different architectures: sort-first, sort-middle, and sort-last [l3, 151. We now briefly examine each of sort-first, sort-middle, and sort-last. In the following descriptions, we consider a framework of an application host computer working with a 75
`
`TEXAS INSTRUMENTS EX. 1010 - 7/17
`
`

`
`graphics computer subsystem. The latter consists of many parallel processors working to produce the desired images in real time. Initially, the display database is partitioned and distributed among all the processors. 2.1 Sort-first In sort-first (figure I), each processor is assigned a portion of the screen to render. First, the processors examine their primitives and classify them according to their positions on the screen. This is an initial transformation step to decide to which processors the primitives actually belong, typically based upon which regions a primitive’s bounding box overlaps. During classification, the processors redistribute the primitives such that they all receive all of the primitives that fall in their respective portions of the screen. The results of this redistribution form the initial distribution for the next frame. Following classification, each processor performs the remaining transformation and rasterization steps for all of its resulting primitives. Finished pixels are sent to one or more frame buffers to be displayed. 2.2 Sort:-middle In sort-middle (figure 2), there is a set of transformation processors and a set of rasterization processors. Physically. the two sets may use the same hardware, but they remain logically separate sets. Each rasterization processor is assigned a portion of the screen. To produce an image, each transformation processor completely transforms its portion of the primitives. The resulting primitive information is again classified by screen location and sent to the correct set of rasterization processors. After rasterization, finished pixels go to the frame buffer(s). In contrast to sort-first, the original distribution of primitives is maintained on the transformation processors. For each frame, all of the transformed primitives must be routed to the correct set of rasterization processors. 2.3 Sort-last For sort-last (figure 3), each processor has a complete rendering pipeline and produces an incomplete full-area image by transforming and rasterizing its fraction of the primitives. These partial images are composited together, typically by depth sorting each pixel, in order to yield a complete image for the frame buffer. The composition step requires that pixel information (at least color and depth values) from each processor be sent across a network and sorted along the way to the frame buffer. qraphics,Databa; qraphics,Database Classification Geometric transformation Rasterization i i i * v t Display Display Figure 1. Sort-First Pipeline Figure 2. Sort-Middle Pipeline Naturally, each architecture has a set of advantages and disadvantage:;. We outline these briefly here; for a more complete comparison, refer to [15]. 2.4 Comparison Sort-last is a very promising architecture and is discussed in detail in [13] and [14]. It offers excellent scalability in terms of the number of primitives it can handle. However, its pixel budget is limited by the bandwidth available at the composition stage. Using a specialized composition network can help to overcome this problem. Anti-aliasing is a major problem for sort-last: regardless ad the solution chosen, the composition task is non-trivial. IJsing super-sampling multiplies the amount of pixel bandwidth required, since each sample must be composited. A-buffer approaches introduce new complications to the composition process, since the number of fragments per pixel may vary and become arbitrarily large. Finally, since visibility is not decided until after the composition stage, sort-last places limitations on the kinds of rendering algorithms which may be used. The choice of algorithms available for rendering transparent polygons becomes limited, for example, and visibility-based culling algorithms are less useful on sort-last. Because of the way it builds upon traditional graphics pipelines, sort middle is a fairly natural architecture which has resulted in many implementations. Some examples are [I II, [3], [6], [9], [I I], and [21]. However, sort-middle’s requirement that any transformation processor be able to talk to any rasterization processor means that its scalability is limited. increasing the number of processors geometrically increases the demands on the communications network between them. In addition, sort-middle faces load-balancing problems when the on-screen distribution of primitives is uneven. This will result in rasterization processors becoming unevenly loaded, and this in turn may degrade system performance unless careful attention is given to this problem. A variety of solutions have been used to address this issue (refer to the references above). Sort-first is a promising architecture that has until now received little attention. It is the only architecture which inherently takes advantage of frame-to-frame coherence. In an interactive application, the viewpoint changes very little from frame to frame, and thus the on-screen distribution of primitives does not change appreciably. Since primitives in a sort-first system are only transferred when they cross frorn one processor’s screen region to another’s, only a fraction of them will have to be communicated each frame. Also, any @ $l $-I . . . Rasterization G G G . . . R R R Sorting of pixel data . . . Display Geometric transformation Rasterization Composition Figure 3. Sort-Last Pipeline 76
`
`TEXAS INSTRUMENTS EX. 1010 - 8/17
`
`

`
`communication that does occur is typically fairly local; usually only “neighboring” processors will need to talk with each other. These facts suggest that it has good scalability in terms of the number of primitives it can handle. In sort-first, once a processor has the correct set of primitives to render, only that processor is responsible for computing the final image for its portion of the screen. This allows great flexibility in terms of the rendering algorithms which may be used. All the speed-ups which have been developed over time for serial renderers may be applied here. Since only finished pixels need to be sent to the frame-buffer, sort-first can easily handle very-high-resolution displays. This is the bottleneck for sort-last. Sort-middle also sends only finished pixels to the frame-buffer, but increasing the display resolution requires increasing either the size or number of rasterization processors, either of which causes problems. Thus sort-first is the only architecture of the three that is ready to handle large databases and large displays. However, sort-first is not without its share of problems. Load- balancing is perhaps one of the biggest concerns: because the on-screen distribution of primitives may be highly variable, some thought must go into how the processors are assigned screen regions. Also, managing a set of migrating primitives is a complex task. These and other problems are the focus of this research. 3. Coherence Study Because sort-first utilizes the coherence of on-screen primitive movement, we performed experiments to analyze this factor and determine what kind of savings might be achieved with actual applications. We wanted to know what fraction of primitives would need to be sent from processor to processor in a sort-first implementation. This testing was done using a simulation with several simplifying assumptions. The testing involved two phases. The first was to make recordings from actual applications running on UNC’s Pixel- Planes 5 graphics system. The resulting recordings contain a series of viewpoint information for each frame rendered while the application was run. The second phase was to take this information and the graphics database archive files and feed them to the simulation program. This program is based upon a framework written by David Ellsworth for his study of sort- middle systems [9]. Code was added to implement a sort-first partitioning and to calculate the resulting primitive traffic. Various applications were used for the different test cases. “PLB” spins its database on the screen’s vertical axis (named after a graphics performance benchmark from [ 161). “Vixen” is a HMD-based visualization program that allows one to fly through an arbitrary display database. Finally, “Xfront” is similar except that it is joystick-controlled. The setup for these tests is as follows: The database is simply a list of polygons (no structure). The aspect ratio of the screen is square. The screen is subdivided into equal-size square regions with one region assigned to each processor. The primitives are initially randomly distributed (the first frame’s data is ignored for this reason). Primitives are redistributed according to the regions their bounding boxes cover. If a primitive falls into multiple regions, the processor at the upper-left region is deemed to be “in charge” of it. Off-screen primitives remain at the processor where they were last on-screen. In these tests, the screen resolution is irrelevant; only the number of regions (and thus processors) matter. Several configurations of regions were tested: 4x4, 8x8, and 16x16. The simulation program outputs a series of values per frame representing the percentage of primitives that had to be communicated in that frame. From these figures, we calculate the arithmetic mean, the high value, the standard deviation, and the 95th percentile value. For PLB, the database is a scanned model of a human head (see plate 1). The model is placed in the center of the screen and spun at 4.5 degrees per iteration around a vertical axis through its center (as in [ 161). PLB 59,592 polygons, 80 frames regions: Lw ai!3 16x16 mean 4.06 % 8.80 % 18.07 % high 5.19 10.30 20.80 std-dev 0.54 0.70 1.05 95-% 5.07 9.92 20.06 For Vixen, the test case is a HMD walk-through of a Sitterson Hall’s lobby (plate 2). The path starts on the mezzanine, goes down the stairs, and then turns around to look back at the starting point. LQW 16,267 polygons, 218 frames regions: 4x4 8x8 JA.Lui mean 2.13 % 4.95 % 11.41 % high 21.17 45.17 87.44 std-dev 3.38 7.28 15.05 95-% 8.67 20.67 44.60 For Xfront, the model is a terrain database of a section of the Sierra Nevada mountains (plate 3). The model undergoes a series of zooms, rotations, and translations, with an abrupt reset between each sequence. m 162,690 polygons, 234 frames regions: 4x4 8x8 li!dA mean 3.17 % 6.08 % 11.51 % high 98.07 102.26 107.38 std-dev 7.68 9.53 11.76 95-% 5.04 10.36 20.53 Looking at the results, we can see that increasing the number of regions increases the percentage of primitives that are communicated. This is fairly obvious, since increasing the number of region borders will increase the chance of a primitive crossing them. The high values are somewhat interesting. For Sierra, the large values resulted from the abrupt transitions in this sequence. These exceeded 100% for two of the cases since primitives which fall into multiple regions may need to be sent more than once. The percentiles perhaps are of greatest interest. They show that for moderately interactive applications (PLB, Xfront), 95% of the rendered frames require reshuffling of only about 20% of t