`
`Volkswagen 1012 - Part 1 of 4
`
`
`
`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
`
`0002
`
`
`
`Multiprocessor Methods
`for Computer Graphics
`Rendeflng
`
`0003
`
`
`
`Multiprocessor Methods
`for Computer Graphics
`Rendefing
`
`Scott Whitman
`
`Lawrence Livermore National Laboratory
`Livermore, California
`
`Jones and Bartlett Publishers
`Boston
`London
`
`0004
`
`
`
`Editorial. Sales. and Ctutamtr Service Q35-:2:
`Jones and Bartlett Publishers
`20 Park Plaza
`Boston, MA 02 l 16
`
`Jones and Bartlett Publishers Intemalional
`PO. Box 1498
`London W6 ‘IRS
`England
`
`Copyright 9 1992 by Jones and Bartlett Publishers. Inc.
`
`All rights reserved. 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 infonnaticn 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 approxirnalely 350,000
`polygons and was rendered on 96 processors of a BBN TCZOOD in 8.8 seconds (including
`specular highlights and stochastic sampling for anti-aliasing).
`
`Library ofcongress Cataloging-ln~PublIcatlon Data
`
`Multiprocessor rnetl-rods fer computer graphics renderingf Scott Whitlnan.
`cm
`p.
`.
`Includes bibliogmplxical references and index.
`ISBN 0-86720-229-7
`l. Ccmpuler graphics.
`'I‘3S5.W54
`1992
`0O6.6'6--d-=20
`
`2. Microprocessors.
`
`I. Title.
`
`ISBN
`
`0-86‘3’20-229-7
`
`Printed in the United States of America
`
`9695949392
`
`1098765432
`
`0005
`
`
`
`To Carol,
`
`who was not there to share the past,
`but with whom I shall enjoy the future
`
`0006
`
`
`
`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 ofthe 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
`
`0007
`
`
`
`Contents
`
`Appendix ......................................................................................... .. 199
`A Information on Test Scenes. .......
`............................................ 199
`
`B. Data for Various Algorithms .................................................... 199
`C. Supplementary Graphs .......................................................... ..204
`Index................................................................................................"214
`
`0008
`
`
`
`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 sofiware 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 soitware
`techniques to hasten the rendering computation. The availability and
`pricelperformance ratio of commercial multiprocessors makes them
`attractive for development of general purpose computer graphics al-
`gorithms. When parallel computer architectures became commer-
`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 diiferent rendering programs
`would be required for use on these computers. In this book, we exam-
`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
`
`0009
`
`
`
`1
`
`Preface
`
`computers. Although the algorithms were developed for these
`machines, they could be modified with minimal efibrt 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 Manda], 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.
`
`0010
`
`
`
`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
`
`0011
`
`
`
`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 CADICAM,
`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
`
`0012
`
`
`
`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-
`dimensional computer graphics scenes. The roost promising
`algorithms are developed and tlllantitatively 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-
`less of the intended application. The input data consists of a set of
`objects which are described both geometrically and topologically, us-
`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
`
`0013
`
`
`
`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-
`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 threedimensional 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.
`
`0014
`
`
`
`Introduction
`
`/iii
`
`Ill
`HIIIIIIII
`\\i\|‘IIlgl/
`
`Figure 1.1: Graphics rendering pipeline
`
`0015
`
`
`
`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 appli cations. 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 :1, 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 of the [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-
`
`0016
`
`
`
`6
`
`Introduction
`
`try is approximated and lighting in the scene is taken into account.
`Rendering techniques include illumination models such as Gouraud
`[Gour'f 1] 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-
`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-
`time to aid in visualizing data. The term "real—time" generally refers
`
`0017
`
`
`
`Overview ofmmelerated 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 DN IOOOOVS
`[Kirk90], the Silicon Graphics 4D VGX [I-Iaeb90], the Stellar Graphics
`Supercomputer GS1000 [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 DN IOOOOVS
`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
`
`0018
`
`
`
`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 ofiloads
`complex rendering calculations from a host computer. With a full
`configuration of 64 rendering processors, B20 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 ofiloads the host for external graphics processing. Even
`within this realm, the designs suffer limitations. For instance, if anti-
`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-
`buffer type of hidden surface removal algorithm but the data must be
`
`0019
`
`
`
`Overview of Accelerated Rendering Techniques
`
`stored in the memory of the machine prior to loading into the graphics
`pipeline. AZ-bufiér [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.
`
`0020
`
`
`
`10
`
`Introduction
`
`It is expected that massively parallel architectures will provide the
`capability to accomplish steering before the end of the 1990s
`[Upso39]. 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 are looking into using SIMD architectures for such a
`purpose [Smal89], [Schr91]. Although these machines are likely to
`provide decent results, it is generally believed that the long term
`prospects for real-time interactive simulation steering can only be
`achieved by fixture genération high performance MIMD computers.
`There have been numerous software algorithms presented in the
`past that have been designed for many different types of advanced
`architectures. An overview of algorithms of this type is provided by
`Whitman and Parent fWl1it88]. In addition, Crow [Crow88a} provides
`insight into commercial ventures and other interesting methods used
`for designing parallel software approaches to display computer
`graphics images.
`Previous work in software algorithms for parallel graphics
`rendering has primarily concentrated on software simulations or
`simple ad—hoc solutions. Little work has been done in this area to
`fully exploit parallel processing at a high level. Some parallel
`graphics display solutions have dealt with a graphics rendering
`technique known as ray tracing [Wl1it80]. Ray tracing is a technique
`which involves sending rays from the observer through each pixel to
`int