TEXAS INSTRUMENTS EX. 1011 - 1/229
`
`

`
`Computer Science Publishing Program
`
`Advisory Board
`Christopher Brown, University of Rochester
`Eugene Fiume, University of Toronto
`Brad Myers, Carnegie Mellon University
`Daniel Siewiorek, Carnegie Mellon University
`
`TEXAS INSTRUMENTS EX. 1011 - 2/229
`
`

`
`Multiprocessor Methods
`for Computer Graphics
`Rendering
`
`TEXAS INSTRUMENTS EX. 1011 - 3/229
`
`

`
`Multipr~cessor Methods
`for Computer Graphics
`Rendering
`
`Scott Whitman
`
`Lawrence Livermore National Laboratory
`Livermore, California
`
`Jones and Bartlett Publishers
`Boston
`London
`
`-
`
`I
`
`TEXAS INSTRUMENTS EX. 1011 - 4/229
`
`

`
`Editorial, Sales, and Customer Service Offices
`Jones and Bartlett Publishers
`20 Park Plaza
`Boston, MA 02116
`
`Jones and Bartlett Publishers International
`P.O. Box 1498
`London W6 7RS
`England
`
`Copyright© 1992 by Jones and Bartlett Publishers, Inc.
`
`All rights reseJVed. No part of the material protected by this copyright notice may be
`reproduced or utilized in any form, electronic or mechanical, including photocopying,
`recording, or by any information storage and retrieval system, without written permission
`from the copyright owner.
`
`About the cover: The tree dataset was generated using Eric Haines' SPD database and
`rendered at a resolution of 640 by 484 pixels. The tree contains approximately 850,000
`polygons and was rendered on %processors of a BBN TC2000 in 8.8 seconds (including
`specular highlights and stochastic sampling for anti-aliasing).
`
`Library of Congress Cataloging-in-Publication Data
`
`· Whitman, Scott.
`Multiprocessor methods for computer graphics rendering/ Scott Whitman.
`p.
`em.
`Includes bibliographical references and index.
`ISBN 0-86720-229-7
`I. Computer graphics. 2. Microprocessors.
`T385.W54
`1992
`006.6'6--{jc20
`
`I. Title.
`
`92-3810
`ClP
`
`ISBN
`
`0-86720-229-7
`
`Printed in the United States of America
`
`96 95 94 93 92
`
`10 9 8 7 6 5 4 3 2
`
`TEXAS INSTRUMENTS EX. 1011 - 5/229
`
`

`
`To Carol,
`
`who was not there to share the past,
`but with whom I shall enjoy the future
`
`TEXAS INSTRUMENTS EX. 1011 - 6/229
`
`

`
`Table of Contents
`
`Preface ................................................................................................. ix
`1 Introduction ....................................................................................... 1
`1.1. Problem Description ................................................................... 2
`1.2. Overview of Accelerated Rendering Techniques ....................... 6
`1.3. Research Context .................................................................... 11
`1.4. Document Overview ................................................................ 14
`2 Overview of Parallel Methods for Image Generation ................... 17
`2.1. Criteria for Evaluation of Parallel Graphics
`Display Algorithms .................................................................. 17
`2.2. Taxonomy of Parallel Graphics Decompositions. ................... 23
`2.3. Conclusions .............................................................................. 48
`3 Issues in Parallel Algorithm Development ................................... 49
`3.1. Architectural Choices .............................................................. 50
`3.2. Comparison of MIMD Methodologies ..................................... 60
`3.3. The BBN Programming Environment ................................... 62
`3.4. Summary ................................................................................. 64
`4 Overview of Base Level Implementation. ...................................... 67
`4.1. Design of the Basis Algorithm ................................................ 68
`4.2. Testing Procedures .................................................................. 77
`4.3. Performance Analysis. ............................................................. 79
`4.4. Summary ................................................................................. 91
`5 Comparison of Task Partitioning Schemes ................................... 93
`5.1. Data Non-Adaptive Partitioning Scheme .............................. 95
`5.2. Data Adaptive Partitioning Scheme ...................................... 119
`5.3. Task Adaptive Partitioning Scheme ...................................... 126
`5.4. Conclusions ............................................................................. 134
`6 Characterization of Other Parameters on Performance. ............. 139
`6.1. Shared Memory Storage and Referencing. ............................ 140
`6.2. Machine Parameters .............................................................. 157
`6.3. Scene Characteristics ............................................................. 171
`6.4. Conclusions ............................................................................. 177
`7 Conclusion ...................................................................................... 181
`7.1. Summary ................................................................................ 182
`7.2. Future Work ........................................................................... 186
`References ......................................................................................... 188
`
`TEXAS INSTRUMENTS EX. 1011 - 7/229
`
`

`
`viii
`
`Contents
`
`Appendix ........................................................................................... 199
`A Information on Test Scenes ......... ; ............................................ 199
`B. Data for Various Algorithms .................................................... 199
`C. Supplementary Graphs ............................................................ 204
`Index .................................................................................................. 214
`
`TEXAS INSTRUMENTS EX. 1011 - 8/229
`
`

`
`Preface
`
`Parallel computing and computer graphics are currently two of the
`hottest topics in computer science. It is only natural that a merging
`of these two fields has now occurred in hardware architectures as well
`as software algorithms. This text explores a number of methods
`which can be used on current generation commercial multiprocessors
`to perform computer image synthesis. The emphasis here is on image
`space rendering methods since these types of algorithms will likely
`get the most use in the day to day work environment.
`The subject matter of computer image synthesis is over 20 years
`old, dating back to Warnock's and Watkins' rendering algorithms,
`along with Gouraud's lighting model. Since then, many refinements
`have been developed which use advanced hardware and software
`techniques to hasten the rendering computation. The availability and
`price/performance ratio of commercial multiprocessors makes them
`attractive for development of general purpose computer graphics al(cid:173)
`gorithms. When parallel computer architectures became commer(cid:173)
`cially available in the mid-1980s, the sequential programs that had
`been previously developed for computer graphics rendering were in
`need of a re-evaluation for a parallel context. In addition, it was
`questioned whether new and completely different rendering programs
`would be required for use on these computers. In this book, we exam(cid:173)
`ine previous and current solutions to the computer image generation
`problem presented by a variety of researchers. Several of these
`solutions, along with a number of newly developed algorithms by the
`author, are analyzed according to their performance on a scalable
`multiprocessor.
`The problem of quickly generating three-dimensional synthetic
`imagery has remained challenging for computer graphics researchers
`due to the large amount of data which is processed and the complexity
`of the calculations involved. For instance, in a multiprocessor, one
`needs to minimize the communication of data between processors so
`that the majority of the execution time is spent on computations. The
`large datasets inherent in computer graphics scenery do not lend
`themselves to ease of partitioning among processors. Tradeoffs
`between synchronization, load balancing, and communication must be
`made during algorithm development and refinement in order to
`effectively utilize the resources available in the system. These issues
`are discussed in detail in this text with regard to the parallel
`algorithms which were implemented on the BBN Butterfly family of
`
`TEXAS INSTRUMENTS EX. 1011 - 9/229
`
`

`
`x
`
`Preface
`
`computers. Although the algorithms were developed for these
`machines, they could be modified with minimal effort to work on any
`general purpose multiprocessor. Unfortunately, the time to modify
`and test the code on a variety of machines would be prohibitive,
`especially to the degree used in the latter part of this book. It is
`hoped that the insights presented here along with the various issues
`raised, and will be informative as both a guide for implementation
`and a reference to methods of attacking this problem.
`In the first chapter of this book, an overview of computer graphics
`rendering is provided, and the issues that are of importance to the
`fields of computer graphics and parallel processing are noted. The
`second chapter provides a historical reference to previous efforts in
`this field. Each of these is categorized into a taxonomy to indicate
`what algorithmic methods each work has utilized. Most of this
`research involved simulations of parallel environments whereas this
`book provides an analysis of actual implementations on general
`purpose commercially available multiprocessors. The third chapter
`analyzes the various multiprocessor architectures with regard to
`graphics rendering algorithms.
`In chapter 4, the basis parallel
`algorithm is presented, along with the procedures used for testing and
`performance analysis. Chapter 5 includes descriptions and analyses
`of each of the work decomposition methods which were implemented.
`The analysis is a scrutiny of a given program's parallel performance
`which provides information to the reader on exactly why each
`algorithm performed the way it did. There were two main choices for
`storing the graphics data in main memory, and these are analyzed in
`chapter 6. The first is a shared memory paradigm while the second,
`although using shared memory, takes advantage of local memory on
`each processor to reduce latency. The results for all of the algorithms
`are compared on a variety of imagery to convince the reader that the
`results presented are representative of real world expected
`performance.
`Acknowledgments. This book was originally a doctoral
`dissertation written and researched while I was at The Ohio State
`University. My dissertation committee of Richard Parent, P.
`Sadayappan, and D. Jayasimha helped to guide me through the
`difficult phases of my research. I am indebted to my committee for
`the countless hours of useful discussions and comments that they
`provided me on my dissertation. Others who helped to make my stay
`at Ohio State that much more rewarding include Scott Dyer, Doug
`Roble, Manas Mandai, as well as my other colleagues in the Computer
`and Information Science Department, the Advanced Computing
`Center for Arts and . Design, and the Ohio Supercomputer Center.
`
`TEXAS INSTRUMENTS EX. 1011 - 10/229
`
`

`
`Preface
`
`xi
`
`This research was conducted over a period of several years and
`utilized literally thousands of hours of computer time. The author
`would like to acknowledge the institutions and staff at BBN Advanced
`Computers, Inc., Argonne National Laboratory, and Lawrence
`Livermore National Laboratory for allowing their machines to be used
`for benchmarking and testing purposes. Individuals deserving special
`recognition for their assistance include: Ed Forbes, John Price, Linda
`Woods, and Eugene Brooks.
`
`Scott R. Whitman
`
`TEXAS INSTRUMENTS EX. 1011 - 11/229
`
`

`
`1
`
`Introduction
`
`High quality computer graphics imagery is used in a wide variety of
`fields in society today. Most people are familiar with the
`entertainment uses of computer graphics which span the artistic
`realm and include two-dimensional imagery using paintbox systems,
`three-dimensional surreal scenes for aesthetic prints, and 2D and 3D
`animation sequences for use in the video and film industry. There are
`many major motion pictures which rely on computer graphics
`rendering to achieve cost effective special effects. The quality of this
`imagery has risen to such a high level that the public is accustomed to
`seeing on a regular basis computer generated commercials of
`photorealistic caliber. In addition, applications such as CAD/CAM,
`finite element modeling, flight simulation, and molecular modeling
`use computer graphics to aid in the visualization of scientific and
`industrial data. The demand for higher quality images from these
`applications has grown as computer time has become less expensive.
`Even though faster computers are now available in reference to the
`past, the time to generate a typical image has not really decreased
`due to the more elaborate imagery required. Deering [Deer88] noted
`that "an increase in graphics performance is more likely to cause
`users to display more complex objects, rather than the same objects
`faster." A computer graphics display algorithm must be able to
`
`1
`
`TEXAS INSTRUMENTS EX. 1011 - 12/229
`
`

`
`2
`
`Introduction
`
`handle this highly complex imagery in an efficient manner. One
`solution to this problem involves utilizing parallel computer
`architectures to render the graphics image. If an efficient software
`algorithm is employed on this type of machine, performance will
`increase with the number of processors added to the system.
`This book examines techniques which utilize parallel processing
`to accelerate the computations necessary for rendering three(cid:173)
`dimensional computer graphics scenes. The most promising
`algorithms are developed and quantitatively compared under a
`variety of circumstances to ascertain which has the highest
`performance.
`The basic problem in computer image synthesis of 3D scenes is
`outlined in the first section of this chapter. Here, the components of a
`computer graphics display algorithm are described. The terms
`hidden surface removal and rendering are defined in the context of a
`computer graphics display program. The second section presents a
`brief overview of the research which has been done in the area of
`developing parallel computer graphics rendering techniques. This
`research can be broadly grouped into two categories: hardware and
`software based solutions. The hardware based solutions typically
`involve designing custom VLSI chips to transform and display data in
`near real-time. Real-time is a term used to describe calculations
`which can proceed within the update rate for a single frame on a CRT
`monitor, typically 30 frames per second. Software solutions use high
`performance advanced computer architectures to achieve fast
`computer graphics renderings. The goals of each of these methods are
`described in some detail in this section. The third section outlines the
`area of research which this book covers. In this section, the context of
`this work in both the parallel processing and computer graphics
`communities is stated. Finally, the fourth section provides an
`overview of the rest ofthe text.
`
`1.1. Problem Description
`Computer graphics imagery can serve many purposes, but the basic
`computer program used to generate these images is the same, regard(cid:173)
`less of the intended application. The input data consists of a set of
`objects which are described both geometrically and topologically, us(cid:173)
`ing a polygonal format. Various scene parameters are also input to
`describe the lights, shading, color, and other information regarding
`how the objects should appear in the computer synthesized scene. All
`data is input as x, y, z floating point variables. The input datasets
`are assumed to contain closed planar polygons. The output of a
`
`TEXAS INSTRUMENTS EX. 1011 - 13/229
`
`

`
`Problem Description
`
`3
`
`graphics display algorithm is a rendering of a three-dimensional
`scene, taking into account realistic lighting and object attributes.
`This output is an image in the form of picture elements (pixels) which
`may be displayed immediately on a frame buffer color monitor or
`stored on hard disk for later display. A frame buffer is a dynamic
`memory collection of pixels containing red, green, and blue
`components. Each pixel component is usually 8 bits deep allowing for
`a choice of 2563 or approximately 16 million colors.
`In general, a computer graphics display algorithm which gener(cid:173)
`ates images of three-dimensional data consists of the following
`phases:
`
`1. Read-in polygonal data from disk.
`2. Transform data from object space to eye space.
`3. Clip and perform perspective projection of the data.
`4. Remove hidden surfaces so only displayable surfaces are seen.
`5. Render surface data using an illumination model.
`6. Calculate special visual effects such as anti-aliasing or
`texture mapping.
`7. Write pixel data to the frame buffer for display or to a file for
`storage.
`
`The overall algorithm is shown in detail in figure 1.1. The top
`diagram indicates the world space three-dimensional view of a sphere
`dataset composed of quadrilateral polygons. The sphere is initially
`described in its own 3D coordinate system (object space). The scene
`as a whole consists of a collection of objects in 3D space relative to
`each other. In addition, an eye point and light sources are present in
`the scene (world space or eye space). In order for the graphics
`program to display the scene on a two-dimensional screen, each object
`must be transformed to screen space and (if necessary) clipped to the
`borders of the screen. The middle diagram is the same sphere after
`3D to 2D transformations, clipping, and perspective operations have
`been applied. The bulk of the work in the program occurs in the
`rendering phase. This amounts to taking into account the position of
`the eye and each light source in relation to the objects in the scene,
`and then accurately displaying the objects according to their surface
`geometry. Incorporated here are such operations as hidden surface
`removal, illumination modeling, anti-aliasing, and other visual
`effects.
`
`TEXAS INSTRUMENTS EX. 1011 - 14/229
`
`

`
`4
`
`Introduction
`
`y\_
`'V '
`
`Figure Ll: Graphics rendering pipeline
`
`TEXAS INSTRUMENTS EX. 1011 - 15/229
`
`

`
`Problem Description
`
`5
`
`These operations are elaborated upon in the sub-sections that
`follow. This process is shown in the bottom diagram as the final
`rendered and shaded image which takes into account the location of
`the light source, object, and eye position.
`The problem domain of this book focuses primarily on the tiling
`portion of a graphics display algorithm (steps 4, 5, and 6). Methods to
`speed up both the front end (reading in, transforming of data) as well
`as the back end (writing out pixels) of the program are also
`investigated. The assumption here is that the nature of the input and
`output is unique to each application, while tiling is the same for the
`majority of applications. Because the tiling operations constitute the
`bulk of the computation in this type of program, it is worthwhile to
`concentrate one's efforts on this section of a graphics rendering
`algorithm. Steps 4, 5, and 6 are described in more detail next.
`
`1.1.1. Hidden Surface Removal
`Hidden surface removal consists of determining which surface
`element in the synthetic 3D scene is closest to the observer for each
`pixel on a CRT screen. There are a variety of techniques for solving
`this problem, and most take advantage of some form of coherence in
`the image in order to reduce the amount of computation.
`In
`Sutherland, Sproull, and Schumacker's landmark paper [Suth74],
`graphical coherence is defined as "the extent to which the
`environment or the picture of it is locally constant." For instance,
`scan line coherence refers to the fact that successive lines of pixels do
`not differ greatly in the data displayed, so that incremental
`calculations can be used to achieve faster processing. Sutherland et
`al. point out that "all ofthe [display] algorithms capitalize on various
`forms of coherence to reduce to manageable proportions the work of
`sorting." The exploitation of image coherence in a parallel setting
`poses a challenging problem. The use of coherence reduces the
`amount of computation in a sequential machine by using results from
`previously computed parameters when generating new values. The
`independent parallel generation of these parameter values in the
`image implies redundant recomputation and the loss of coherence.
`The tradeoff between parallelism and coherence is an important issue
`that is studied here.
`
`1.1 .2. Rendering and Special Effects
`Rendering is a method for displaying polygonal or bicubic patch
`surfaces on a frame buffer monitor so that the overall surface geome-
`
`TEXAS INSTRUMENTS EX. 1011 - 16/229
`
`

`
`6
`
`Introduction
`
`try is approximated and lighting in the scene is taken into account.
`Rendering techniques include illumination models such as Gouraud
`[Gour71] and Phong [Phon75] shading, which are used to simulate
`smooth surfaces. Using Lambert's law and approximations to the
`normal vector of the surface at each pixel, the data can be displayed
`accurately on the screen. Computer graphics special effects add
`realism to a computer generated scene. Some of these include:
`calculating refractions of transparent objects, modeling of wrinkled
`surfaces (bump mapping), applying texture to a surface (texture
`mapping), and accounting for shadows in a scene.
`Anti-aliasing is another added visual effect which removes the
`jagged or staircase edges which appear at surface boundaries due to
`discrete sampling of the analog dataset. Both rendering and special
`effects are closely tied because the addition of visual features
`normally occurs during the rendering process. Current display
`methods incorporate advanced rendering and visual effects as an
`integral part of the algorithm. The complexity of these computations
`in most cases overrides those necessary for hidden surface removal.
`Any techniques used to speed up the image generation process must
`concentrate heavily on the rendering and visual effects stages.
`In the next section, the background on a number of hardware and
`software graphics techniques is given.
`
`1.2. Overview of Accelerated Rendering
`Techniques
`Although significant work has been done in the past regarding the
`sequential computer graphics image generation problem, it is
`necessary to re-investigate this problem to see what changes or
`alternate approaches are necessary for parallel implementation.
`Work in this area has centered around both hardware based graphics
`workstations and software solutions for parallel machines.
`Numerous companies have developed graphics superworkstations
`which incorporate special purpose chips along with multiple
`processors to achieve a high performance visual computing system.
`Initial developments in this area involved the use of special purpose
`graphics terminals which manipulated wire-frame images in real(cid:173)
`time. Wire-frame imagery only shows the outline of the dataset
`surfaces and makes use of phases 1 through 4 given in the beginning
`of this section. Using today's technology, more sophisticated
`machines can generate smoothed surface representations in near real(cid:173)
`time to aid in visualizing data. The term "real-time" generally refers
`
`TEXAS INSTRUMENTS EX. 1011 - 17/229
`
`

`
`Overview of Accelerated Rendering Techniques
`
`7
`
`to an update rate of at least 10 frames per second (fps). Standard
`video update rate is 30 fps while film is 24 fps.
`Commercial machines of this type include the Apollo DNlOOOOVS
`[Kirk90], the Silicon Graphics 4D VGX [Haeb90], the Stellar Graphics
`Supercomputer GSlOOO [Apga88], and the Ardent Titan [Died88]. All
`of these machines support parallelism with typically up to 4
`processors, while the Stellar and Ardent architectures employ parallel
`processing at both the MIMD (multiple instruction, multiple data
`path) and SIMD (single instruction, multiple data path) levels.
`MIMD refers to the fact that each processor is executing a set of
`instructions asynchronously from other processors. SIMD refers to a
`central processor controlling execution or to a vector pipeline
`architecture.
`In addition, fast rendering engine processors are
`coupled with the frame buffer in these machines to achieve high speed
`generation of images. The Silicon Graphics and Apollo machines
`support anti-aliasing and texture mapping. The Apollo DNlOOOOVS
`uses quadratic interpolation to help alleviate Mach bands, although
`this technique is not quite as good as true Phong shading. Mach
`bands (see [Roge85]) can occur when the smooth surface interpolation
`in the illumination model is not an accurate representation of the
`actual surface. The Silicon Graphics 4D VGX has what is called an
`"accumulation buffer." This buffer allows such features as motion
`blur, soft shadows, depth of field, and anti-aliasing to be performed on
`a polygonal database. Motion blur smooths out the motion of fast
`moving objects in a scene. Soft shadows provide a smoothing effect to
`the shadow that simulates a penumbra rather than the typical quick
`cutoff that is apparent in conventional shadow algorithms. Depth of
`field simulates the way a camera lens focuses. Other hardware
`approaches including new chip designs from Schlumberger [Deer88]
`and IBM [Ghar88] promise high graphics performance for the future.
`An example of using a hardware architecture to solve the
`radiosity problem is given by Baum and Winget [Baum90]. Radiosity
`is a very computationally expensive technique for visualizing 3D
`scenes. It is essentially an n2 problem which involves calculating the
`diffuse inter-reflection of all surfaces against one another so that the
`light reflectance of the entire scene is taken into account. In their
`algorithm, Baum and Winget use the hardware capability of the
`Silicon Graphics IRIS workstation to perform real-time radiosity.
`Their algorithm exploits the hardware by using the Z-buffer
`rendering feature of the IRIS to calculate the form factors in parallel.
`The Z-buffer is a contiguous memory which holds the Z coordinate
`value of the closest surface to the viewer for each pixel on the screen.
`Additional work by Garlick et al. [Garl90] using the IRIS workstation
`
`TEXAS INSTRUMENTS EX. 1011 - 18/229
`
`

`
`8
`
`Introduction
`
`allows one to manipulate very large databases in real-time. This
`algorithm works by using parallel processing to perform clipping
`operations necessary to observe the dataset. Although both of these
`implementations are useful, they do not deal directly with the
`problem of image generation.
`Two architectures which are primarily intended for fast image
`processing as well as 3D rendering are Pixel Planes and the AT&T
`Pixel Machine. These machines are designed to offload the graphics
`calculations from a host computer; they are not intended for use as
`workstations.
`Fuchs et al. [Fuch85] introduced their hardware approach to
`solving the visualization problem in 1985. Fuchs' team designed Pixel
`Planes, a parallel architecture containing a processor at every pixel,
`and a binary tree of adders optimized to solve the equation F(x,y) =Ax
`+ By + C at each pixel. This machine also has hardware support for
`calculating anti-aliasing, shadows, and texturing.
`The AT&T Pixel Machine [Potm89) contains a high performance
`network of processors with a fine-grained interleaved frame buffer.
`That is, the frame buffer memory is scattered throughout the
`processors. This alleviates contention while providing sufficient
`throughput. It is typically used as a graphics engine which offioads
`complex rendering calculations from a host computer. With a full
`configuration of 64 rendering processors, 820 MFLOPS peak
`performance is attainable. Since this machine is a general purpose
`graphics machine, software algorithms can be used to take advantage
`of its characteristics. Although the Pixel Machine can be
`programmed to handle a number of different graphics display
`methods, its versatility is limited as a general purpose computer
`primarily because of the small amount of memory available at each
`processor (only 64kbytes).
`The solutions described above involve integrating a special
`purpose graphics rendering engine into a high performance
`workstation or using a hardware assisted graphics accelerator. The
`first approach yields a near real-time update of polygonal based
`scenes, which is useful to designers and engineers. The second
`approach offioads the host for external graphics processing. Even
`within this realm, the designs suffer limitations. For instance, if anti(cid:173)
`aliasing and other features are used, performance degrades
`dramatically. Quantitative measures of the degradation which occurs
`when applying anti-aliasing to polygonal models in these machines
`are not available. True Phong shading is not present in the hardware
`of any of these machines. Most of the hardware methods employ a Z(cid:173)
`buffer type of hidden surface removal algorithm but the data must be
`
`TEXAS INSTRUMENTS EX. 1011 - 19/229
`
`

`
`Overview of Accelerated Rendering Techniques
`
`9
`
`stored in the memory of the machine prior to loading into the graphics
`pipeline. AZ-buffer [Catm74] is analogous to the frame buffer except
`that the z coordinate for a polygon at the given pixel is stored in
`memory. This is a simple technique used for hidden surface removal.
`Extremely large datasets are not able to fit into the physical memory
`of the machine and consequently performance suffers as a result of
`disk access. As a result of these limitations, a hardware approach is
`only adequate for interactive use with a small to medium size dataset
`(typically 10,000 polygons or less). To achieve reasonable
`performance on large,datasets, a parallel software approach to solving
`the rendering problem is warranted.
`The use of a general purpose multiprocessor computer is more
`cost effective than the specially designed architectures, since this type
`of machine can be used for non-graphics applications as well. The
`software method may not have the capability for real-time
`calculations, but this is not needed in many applications. In addition,
`a graphics workstation is not capable of the high performance general
`computing required by applications which demand supercomputer
`cycles. By integrating the graphics rendering with the application
`and using the same computer for both simultaneously, it is
`unnecessary to send the data to a separate machine for graphics
`rendering. Taking this a step further, we expect that future
`generation multiprocessors may in fact offer the capability to achieve
`real-time computer graphics rendering. Following is a description of
`how this might be used.
`For real-time interaction with a complex illumination model, the
`user is generally limited to a small number of polygons on even the
`most advanced graphics workstations. With the recent interest in
`scientific visualization, scientists would like to be able to see their
`scientific data using real-time interaction, while adjusting their
`simulation simultaneously. The simulation portion of the code is
`usually run on a supercomputer class architecture machine. Example
`applications which require this level of computer power include:
`molecular dynamics simulations, 3D finite element simulations, and
`global climate modeling. Massively parallel architectures hold great
`promise for being able to support applications of this type.
`In
`addition, the capability to support real-time interaction of a dense
`database containing perhaps a million elements is beyond the scope of
`even the most powerful graphics workstations. Consequently, it is
`natural to incorporate the graphics rendering operations along with
`the simulation program in the same computer so that the coupled
`system can output the graphics image in real-time. This desired
`interactive environment has come to be known as simulation steering.
`
`TEXAS INSTRUMENTS EX. 1011 - 20/229
`
`

`
`10
`
`Introduction
`
`It is expected that massively parallel architectures will provide the
`capability to accomplish steering before the end of the 1990s
`[Upso89]. This book gives insight into how graphics rendering
`programs will be developed for massively parallel architectures to
`incorporate this desired feature in the near future. Already, some
`researchers a