We
`
`LIBRARY OF CONGRESS
`
`Office of Business Enterprises
`Duplication Services Section
`
`THIS IS TO CERTIFYthat the collections of the Library of Congress contain a
`publication entitled COMPUTER GRAPHICS- PROCEEDINGS,call number T 385.S517a
`1993, and that the following pages — cover page,title page, copyright, table of contents pages,
`and pages 109 through 116, on which contain the followingarticle, “RealityEngine Graphics,”
`- are a true representation from that work.
`
`THIS IS TO CERTIFY FURTHER,that workis marked with a Library of Congress
`stampthat bears the date June 30, 1994.
`
`IN WITNESS WHEREOF,the seal of the Library of Congressis affixed hereto on
`September 22, 2017.
`
`
`
`Deirdre Scott
`Business Enterprises Officer
`Office of Business Enterprises
`Library of Congress
`
`101 Independence Avenue, Si! Washington, DC20540-4917 ‘I'cl 202.707.5650 www.loc.gov; duplicationservices@loc.gov
`MEDIATEK, Ex. 1004, Page 1
`
`MEDIATEK, Ex. 1004, Page 1
`
`

`

`A publication of AGM SIGGRAPH
`
`Sponsored by the Assaciation for
`Gomputing Machinery's Special
`lnierest' Group on Gompuler
`Graphics
`
`Annual Conference Series
`
`1993
`
`SIGGRAPH 93
`Conference Proceedings
`1=6 Augus! 1993
`Papers:Chain James T. Kajiya
`EMOV MB Lela ine).
`
`MEDIATEK, Ex. 1004, Page 2
`
`MEDIATEK, Ex. 1004, Page 2
`
`

`

`
`Annual Conference Series
`1993
`
`SIGGRAPH 93
`Conference Proceedings
`August 1-6, 1993
`Papers Chair James T. Kajiya
`Panels Chair Donna Cox
`
`
`i
`;
`|
`i
`
`A publication of ACM SIGGRAPH
`Production Editor Steve Cunningham
`
`Interest Group on Computer Graphics PROCEEDINGS
`
`Sponsored by the Association for
`Computing Machinery’s Special
`
`MEDIATEK, Ex. 1004, Page 3
`
`MEDIATEK, Ex. 1004, Page 3
`
`

`

`SIGGRAPH99,Anaheim, California!1-6August1993
`
`The Association for Computing Machinery, Inc.
`1515 Broadway, 17th Floor
`New York, NY 10036
`
`Copyright © 1993 by the Association for Computing Machinery, Inc. Copying without
`fee is permitted provided (hat the copies are not made ordistributed 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 (hat the per-copyfee is paid through the Copyright Clearance Center,
`27 Congress Street, Salem, MA 01970, For permission to republish write to Director of __—.
`Publications, Association for Computing Machinery. To copy otherwise, or republish,
`f 3e5
`-S SVla
`requires a fee and/or specific permission,
`(993
`
`Sample Citation Information:
`...Proceedings of SIGGRAPH93 (Anaheim,California, August !-6, 1993). In Computer
`Graphics Proceedings, Annual Conference Series, 1993, ACM SIGGRAPH, New York,
`1993, pp. xx-yy.
`
`Orders from nonmembers ofACM placed
`within the United Statesshould be directed
`to:
`
`Addison-Wesley Publishing Company
`Order Department
`Jacob Way
`Reading, MA 01867
`Tel: 1-800-447-2226
`
`Addison-Wesley witl pay postage and
`handling on orders accompanied by check.
`Credit card orders may be placed by mail or
`by calling the Addison-Wesley Order
`Departmentat the number above. Pollow-
`up inquiries should be directed to the
`Customer Service Department at the same
`number. Please include the Addison-Wesley
`ISBN slumber with your order:
`A-W Softcover ISBN 0-201-58889-7
`A-W CD-ROM ISBN 0-201-56997-3
`
`Orderstrom nonmembers ofACM placed
`from outside the United States should be
`addressed as noted below.
`
`Europe/Middle East:
`Addison-Wesley Publishing Group
`Concertgebouwplein 25
`1071 LM Amsterdam
`The Netherlands
`Tel: +31 20 6717296
`Fax: _31 20 6645334
`
`Germany/Austria/Switzerland:
`Addison-Wesley Verlag Deutschland
`GmbH
`Wachsbleiche 7-12
`W-5300 Bonn |
`Germany
`Tel: +49 228 98 5150
`Fax: +49 228 98 515 99
`
`
`
`ORDERING INFORMATION
`
`United Kingdom/Africa:
`Addison-Wesley Publishers Ltd,
`Finchampstead Road
`Wokingham, Berkshire RG] 1 2NZ
`United Kingdom
`Tel: +44 734 794000
`Fax: +44 734 794035
`
`Asia:
`Addison-Wesley Singapore Pte. Ltd.
`15 Beach Road
`#05-02/09/10 Beach Centre
`Singapore 0718
`Tel: +65 339 7503
`Fax: +65 339 9709
`
`Japan:
`Addison-Wesley Publishers Japan Ltd.
`Nichibo Building
`1-2-2 Sarugakucho
`Chiyoda-ku, Tokyo 101
`Japan
`Tel: +81 33 2914581
`Fax: +81 33 2914592
`
`Australia/New Zealand:
`Addison-Wesley Publishers Pty. Ltd.
`6 Byfield Street
`North Ryde, N.S.W. 2113
`Australia
`Tel: +61 2 878 5411
`Fax: +61 2 878 5830
`
`Latin America:
`Addison Wesley Iberoamericana S.A.
`Boulevard de las Cataratas #3
`Colonia Jardines del Pedregal
`Delegacion Alvaro Obregon
`01900 Mexica D.F.
`Tel: +52 5 660 2695
`Fax: +52 5 660 4930
`
`Canada:
`Addison-Wesley Publishing (Canada) Ltd.
`26 Prince Andrew Place
`Don Mills, Ontario M3C 2T8 Canada
`Tel: 416-447-5101
`Fax: 416-443-0948
`
`Orders from ACM Members:
`
`A limited aumber of copies are available at
`the ACM member discount. Send order with
`payment in U.S. dollars to:
`
`ACM Order Department
`P.O. Box 64145
`Baltimore, MD 21264
`
`OR,for informatio on accepted European
`currencies and exchange rates, contact:
`
`ACM European Service Center
`Avenue Marcel Thiry 204
`1200 Brussells
`Belgium
`Tel: +32 2 774 9602
`Fax: +32 2 774 9690
`Email: acm_europe@acm.org
`
`ACMwill pay postage and handling on
`orders accompanied by check.
`
`Credit card orders only: 1-800-342-6626
`Credit card orders may also be placed by
`mail.
`
`Customerservice, or credit card orders from
`Alaska, Maryland, and outside the U.S.:
`+1 410 528 426]
`
`Single-copy orders placed by fax:
`+1 410 528 8596
`
`Blectronic mai] inquities may bedirected to
`acmpubs @acm org,
`Please include your ACM member
`number and the ACMorder number with
`your order.
`ACM Order Number: 428930
`
`ACMISBN:
`
`0-89791-601-8
`
`ISSN: 1069-529
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a
`
`
`
`
`
`
`
`
`
`
`
`
`MEDIATEK, Ex. 1004, Page 4
`
`MEDIATEK, Ex. 1004, Page 4
`
`

`

`
`
`COMPUTER GRAPHICS Proceedings, Annual Conference Series, 1993
`
`Contents
`
`Papers Sessions, Tuesday, 3 August 1993
`
`8:30-10:00
`
`1:30-3:15
`
`SIGGRAPH93 Keynote Address
`{993 ACM SIGGRAPH Computer Graphics Achievement Award .......:.csuseern cece: |
`eaeen |S
`1993 Coons Award.... eee
`
`Surfaces
`Chair: David F. Rogers
`2D Shape Blending: An Intrinsic Solution to the Vertex Path Problem .........-s+00-
`Thomas W. Sederberg, Peisheng Gao, Guojin Wang, Hong Mu
`
`edenentiesnen rennet 15
`
`Mesh Optimization viccsccceccssescscesersecssaeressscerseetseneusnsserasasnearerereereteeenemnantnayatestre
`Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, Werner Stuetzle
`Interactive Texture Mapping onc ccccscsseecseereserecaseiinectrennnsarscensnseraneereteseenentany es
`Jéréme Maillot, Hussein Yahia, Anne Verroust
`Efficient, Fair Interpolation using Catnwull-Clark Surfaces ....seecsececserenineneneseeseententennens
`Mark Halstead, Michael Kass, Tony DeRose
`
`seceasnasuraneesers 19
`
`ee 27
`
`35
`
`3:30-5:00
`
`Hardware
`Chair: Ed Catmull
`
`Implementing Rotation Matrix Constraints in Analog VLSI.....sssscecesserccenreesies
`David B. Kirk, Alan H., Barr
`Correcting for Short-Range Spatial Non-Linearities of CRT-based Output Devices «1.0.5... 53
`R. Victor Klassen, Krishna Bharat
`
`ee 45
`
`Attocalibration for Virtual Environments Tracking Hardware o.com
`Stefan Gottschalk, John F. Hughes
`
`2ee. 65
`
`
`
`MEDIATEK, Ex. 1004, Page 5
`
`MEDIATEK, Ex. 1004, Page 5
`
`

`

`
`
`SIGGRAPH93, Anaheim, Callfornia; 1-6 August 1993
`
`Papers Sessions, Wednesday, 4 August 1993
`
`8:30-10:00
`
`Interaction
`Chair: Jock Mackinlay
`Pad: An Alternative Approachto the Computer Interface ...sessessssssserernersesneeserssnsesnresesnsssateneeneey OD
`Ken Perlin, David Fox
`Toolglass and Magic Lenses: The See-Through Interface ......cccsrrcesereretetseeerereseunecinnenensnerenenees 73
`Eric A. Bier, Maureen C. Stone, Ken Pier, William Buxton, Tony DeRose
`
`AnInteractive 3D Toolkit for Constructing 3D Widgets ......s.scsssscisecrereeseenenerenasenenenareneeenenes 81
`Robert C. Zeleznik, Kenneth P. Herndon, Daniel C, Robbins, Nate Huang,
`Tom Meyer, Noah Parker, John F. Hughes
`
`1:30-3:15
`
`Rendering Architectures
`Chair: Forest Baskett
`
`EXACT: Algorithm and Hardware Architecture for an Improved A-BUffer«cosets 85
`Andreas Schilling, Wolfgang Straper
`Graphics Rendering Architecture for a High Performance Desktop Workstation.......:.se001 93
`Chandlee B. Harrell, Farhad Fouladi
`
`Leo: A System for Cost Effective 3D Shaded Graphics .......ccecccssscsesesssentseanseneeaeretenceeie 101
`Michael F. Deering, Scott R. Nelson
`RealityEngine Graphics woes cceeseseseeesseescesescenstessonseeecesteesnsecnensessrmesnenssnmensieesnesbaneant es 109
`Kurt Akeley
`
`3:30-5:00
`
`Virtual Reality
`Chair: Andries van Dam
`
`VIEW — An Exploratory Molecular Visualization System with User-Definable
`Interaction SEQuences ....cuscesesseeeesrteesseeeterecssessenertsneeeeseeeeeeeeneeeetaseneaeene cad eagennsceenentsUistenesnange ress M17
`Lawrence D. Bergman, Jane S. Richardson, David C. Richardson, Frederick P. Brooks Jr.
`The Nanomanipulator: A Virtual-Reality Interface for a Scanning Tunnelling Microscope...... 127
`Russell M, Taylor I, Warren Robinett, Vernon L. Chi, Frederick P. Brooks Jr.,
`William V. Wright, R. Stanley Williams, Eric J. Snyder
`
`Surround-Screen Projection-Based Virtual Reality: The Design and Implementation
`Of the CAVE vicccceectssseceeessctscreeeerensegessessseensneeaaarsscscsvssaseeseecsugessaseaaeaseeaiasasassseessnasaeneantaerbanegaeised 135
`Carolina Cruz-Neira, Daniel J. Sandin, Thomas A. DeFanti
`
`MEDIATEK, Ex. 1004, Page 6
`
`MEDIATEK, Ex. 1004, Page 6
`
`

`

`COMPUTER GRAPHICS Proceedings, Annual Conference Series, 1993
`
`Papers Sessions, Thursday, 5 August 1993
`
`8:30-10:00
`
`Global Illumination
`Chair: Francois Sillion
`
`Painting with Light .ccccccsscersersseesecenenreegeseeserensresserassanascsserdonessurnsenanteeresneacaseceanneegnen eaas 143
`Chris Schoeneman, Julie Dorsey, Brian Smits, James Arvo, Donald Greenberg
`Radioptimization — Goal-based Rendering... cencepeesST Sree 147
`John K. Kawai, James S. Painter, Michael F. Cohen
`A Hierarchical Illumination Algorithm for Surfaces with Glossy Reflection wuss159
`Larry Aupperle, Pat Hanrahan
`On the Form Factor between Two PolyZons vcccecccesesresreeceretecesestenneersereeetaversessenenensasnescenses 163
`Peter Schréder, Pat Hanrahan
`
`10:15-12:00
`
`Light and Color
`Chair: Ken Torrance
`
`Reflection from Layered Surfaces due to Subsurface Scattering -...ccsccecererctereseis teense 165
`Pat Hanrahan, Wolfgang Krueger
`Display of the Earth Taking into Account Atmospheric Scattering ......-cssseseseeeeseeeneesensnereety 175
`Tomoyuki Nishita, Takao Sirai, Katsunti Tadamura, Ethachiro Nakamae
`Smooth Transitions between Bump Rendering Algorithms...... cesses renner escrsennersnesens 183
`Barry G. Becker, Nelson L. Max
`Linear Color Representations for Full Spectral Rendering... cece seaenseesenrsessesesieesiees 191
`Mark S. Peercy
`
`1:30-3:15
`
`Numerical Methods for Radibsity
`Chair: Paul Heckbert
`
`Combining Hierarchical Radiosity and Discontinuity Meshing .........cscssssreresesesrserssssrsertsnens 199
`Dani Lischinski, Filippo Tampieri, Donald P. Greenberg
`Radiosity Algorithms Using Higher Order Finite Blements...........:sseseereeeseeneecsniesssnesenivess 209
`Roy Troutman, Nelson L. Max
`Galerkin Radiosity; A Higher Order Solution Method for Global Mlumination .......cece 213
`Harold R. Zatz
`Wavelet Radiosity ...ccccccsesceseetcsecrsenessssrescseseyteseinsnsersnensrsensneerteceriansssenensenermeseneraseasensenes 221
`Steven J. Gortler, Peter Schroder, Michael F. Cohen, Pat Hanrahan
`
`3:30-5:00
`
`Visibility
`Chair: Frank Crow
`
`Hierarchical Z-Butfer Visibility 0... ccs cnet cceetseceeseeeneesecseeserin erence tenn aterateevereeenenesnees 231
`Ned Greene, Michael Kass, Gayin Miller
`Global Visibility Algorithms for Tlumination Computations ......ce:seeceecessnueseeressrenteanesrennecens 239
`Seth Teller, Pat Hanrahan
`Adaptive Display Algorithmfor Interactive Frame Rates During Visualization of
`Complex Virtual Environments... cccscuecseeseesesssancenesenerercsuneesecesenesqaserensteestaecnsarenenanesanensiany 247
`Thomas A. Funkhouser, Carlo H, Séquin
`
`
`
`MEDIATEK, Ex. 1004, Page 7
`
`MEDIATEK, Ex. 1004, Page 7
`
`

`

`
`
`SIGGRAPH 93, Anaheim, Callfornia} 1-6 August 1993
`
`lS
`
`PaperSessions, Friday, 6 August 1993
`
`8:30—10:00
`
`Visualization
`Chair: Mike Keeler
`
`Discrete Groups and Visualization of Three-Dimensional Manifolds ....,.....---csereesecsesssesereseene’ 255
`Charlie Gunn
`
`Imaging Vector Fields Using Line Integral Convolution v..sssecsssisesssreeeceeseceneneseanereeresenees 263
`Brian Cabral, Leith (Casey) Leedom
`
`Frequency Domain Volume Rendering ......cccccccestesceescsseetennsnserseesncassesssssenerceneserigenentenenen 271
`Takashi Totsuka, Marc Levoy
`
`10:15-12:00
`
`Processing Synthetic hnages
`Chair: Don Mitchell
`
`View Interpolation for Image Synthesis ......cccccccssescssssvessscssssuesrscsssseeasnessernscaeseescsressessstisssansanste 219
`Shenchang Eric Chen, Lance Williams
`Spatial Anti-aliasing for Animation Sequences with Spatio-temporalFiltering ..........ssescses 289
`Mikio Shinya
`Motion Compensated Compression of Computer Animation Frames v...cscsescsesesssstcsetseeceseeees 297
`Brian K. Guenter, Hee Cheol Yun, Russell M. Mersereau
`
`Space Diffusion: An Improved Parallel Halftoning Technique Using Space-filling Curves....... 305
`Yuefeng Zhang, Robert E. Webber
`
`1:30-3:15
`
`Techniques for Animation
`Chair: Andrew Glassner
`
`3:30-5:00
`
`An Implicit Formulation for Precise Contact Modeling between Flexible Solids.......-......:0++ 313
`Marie-Paule Gascuel
`
`Interval Method for Multi-Point Collisions between Time-Dependent Curved Surfaces............ 321
`John M. Snyder, Adam R. Woodbury, Kurt Fleischer, Bena Currin, Alan H. Barr
`
`Sensor-Actuator Networks siaescsssaiserssvceruensorteronenannmenececeenevececsnersnarpeucrareeescrennvseneepenerenenegnennanenny 335
`Michiel van de Panne, Eugene Fiume
`
`Spacetime Constraints Revisited ........cccscsssesersesecsesesseessnsenssvsvsesececsesesususeavarpesesenseasseesasaeetucnscosens 343
`J, Thomas Ngo, Joe Marks
`
`Natural Phenomena
`Chair: Darwyn Peachey
`Animation of Plant Development...c.ccccccscsssssscsseesessnsserssnesserersteseesonteteaseeseeneneetnssenensnenesstcasesnwane 351
`Przemyslaw Prusinkiewicz, Mark S. Hammel, Eric Mjolsness
`
`Modeling Soil: Realtime Dynamic Models for Soil Slippage and Manipulation...........00-000 361
`Xin Li, J. Michael Moshell
`
`Turbulent Wind Fields for Gaseous Phenomena ......ccccsccseteessssstsiecesasteensesseensinseenssrsassees 369
`Jos Stam, Eugene Fiume
`
`
`
`MEDIATEK, Ex. 1004, Page 8
`
`MEDIATEK, Ex. 1004, Page 8
`
`

`

`
`
`COMPUTER GRAPHICSProceedings, Annual Conference Series, 1993
`
`Panel Sessions, Tuesday, 3 August 1993
`1:30-3:15
`Real Virtuality: Stereo Lithography — Rapid Prototyping in 3D 0... seein 377
`Chair: Jack Bresenham
`Panelists: Paul Jacobs, Lewis Sadler, Peter Stucki
`Visual Thinkers in an Age of Computer Visualization: Problems and Possibilities............ 379
`Chair: Kenneth R. O'Connell
`Panelists: Vincent Argiro, John Andrew Berton Jr., Craig Hickman, Thomas G. West
`
`3:30-5:00
`
`8:30-10:00
`
`Panel Sessions, Wednesday, 4 August 1993
`8:30-10:00
`Updating Computer Animation: An Interdisciplinary Approach..............sseeerecenn 381
`Chair: Jane Veeder
`Panelists: Charlie Gunn, Scott Liedtka, William Moritz, Tina Price
`Facilitating Learning with Computer Graphics and Multimedia .........-+.:0:sseeneenneenen 383
`Chair: G. Scott Owen
`Panelists: Robert V. Blystone, Valerie A. Miller, Barbara Mones-Hattal, Jacki Morie
`Visualizing Environmental Data Sets .......c..ccssstseeeinienesssenaneenenenesesienseeesonnener neta 385
`Chair: Theresa Marie Rhyne
`Panelists: Kevin J. Hussey, Jim McLeod, Brian Orland, Mike Stephens, Lloyd A. Treinish
`Howto Lie and Confuse with Visualization ...........:.cssccscssseeenssssnsesrsscutertsemsssesersnceanteree, 387
`Chair: Nahum D, Gershon
`Panelists: James M. Coggins, Paul R. Edhotm, Al Globus, Vilayanur S. Ramachandran
`The Applications of Evolutionary and Biological Processes to
`Computer Art and Amimation oo... ern nesses iceserencnenenrancenrneriteanenean eens sree ee nents 389
`Chair: George Joblove
`
`1:30-3:15
`
`3:30-5:00
`
`3:30-5:00
`
`Panelists: William Latham, Karl Sims, Stephen Todd, Michael Tolson
`
`MEDIATEK, Ex. 1004, Page 9
`
`MEDIATEK, Ex. 1004, Page 9
`
`

`

`SIGGRAPH 93, Anaheim, California; 1-6 August 1993
`
`Panel Sessions, Thursday, 5 August 1993
`8:30-10:00
`Urban Tech-Gap: How Museum/University Liaisons Propose to Create
`a Learning Ladderfor Visual Literacy ..........cccccccscccssecessenssseseessssseseereseeseeteetssteeneeesceecenneeee 391
`Chair: Richard Navin
`Panelists: Lynn Holder, Edward Wagner, Robert Carlson, Michael McGetrick
`Virtual Reality and Computer Graphics Programming............0...0.cscceeeceeessteeetestenterteee 392
`Chair: Bob C. Liang
`Panelists: William Bricken, Peter Cornwell, Bryan Lewis, Ken Pimental, Michael J. Zyda
`
`8:30-10:00
`
`10:15-12:00
`
`Ubiquitous Computing and Augmented Reality 0.0.0... ceceeseceeeeeeteeerenenpineneerreneasseeseeanen 393
`Chair: Rich Gold
`Panelists: Bill Buxton, Steve Feiner, Chris Schmandt, Mark Weiser, Pierre Wellner
`
`1:30-3:15
`
`1:30-3:15
`
`3:30-5:00
`
`Merging 3D Graphics and Lnaging —Applications and Issues ...........:.ceccceensteeieeeeneecens 395
`Chair: Willian R. Pickering
`Panelists: Paul Douglas, Kevin Hussey, Michael Natkin
`
`Nan-o-sex and Virtual Seduction... cescessesesecseseeeesesssesanesesessensonscanecaepeetssnnesssaperene 396
`Co-Chairs: Joan I, Staveley, David Steiling
`Panelists: Paul Brown, Michael Heim, Jill Hunt, Chitra Shriram
`
`Critical Art/Interactive Art/Virtual Art: Rethinking Computer ALrt uo... ceteris 398
`Chair; Timothy Druckrey
`Panelists: Regina Cornwell, Kit Galloway, Sherrie Rabinowitz, Simon Penny, Richard Wright
`
`Panel Sessions, Friday, 6 August 1993
`8:30-10:00
`Digital Musion: Theme Park Visualization - Part OMe .........2:..:::ccseseeteeeeceeseeeenete tere taeenee vi 400
`Chair; Clark Dodsworth
`Panelists: Kevin Biles, Richard Edlund, Michael Harris, Phil Hettema, Mario Kamberg,
`Brenda Laurel, Sherry McKenna, Allen Yamashita
`
`10:15-12:00
`
`1:30-3:15
`
`1:30-3:15
`
`3:30-5:00
`
`Digital [Musion: Theme Park Visualization - Part Two
`Continuationofpanel described above.
`
`Man VS. Mouse .......ccccccscsesescssssesscssesvscsscecsseevsrsceeessersecessvesseeepaccaseauedeceeseeddsesesseeeennssenaecneseneeen 401
`Chair: Jonathan Luskin
`Panelists: Terri Hansford, Robert E. Markison, Joan Stigliani
`
`Multimedia and Interactivity im the Antipodes .0........ cc eee cesteseneseeeesesearersssnensentscnenaenes 401
`Chair: Lyane Roberts-Goodwin
`Panelists: Chris Caines, Paula Dawson, Adam Lucas, Cameron McDonald-Stuart
`
`The Integrative Use of Computer Graphics in a Medical University ..........:.:-:eeeece 403
`Chair: Dave Warner
`Panelists: A. Douglas Will, Jodi Reed
`
`Cumulative Index of SIGGRAPHProceedings, 1984-1993 wicccscseseeeteesrenensneeentssenerpenerene 405
`Stephen Spencer
`
`Conference COMIMiltee .occcceceeccceseeccseneseseeeneseetseessaeaeereseeneenesDeeseseee eee sneeeeeerseeeeshendsaneaesearessane 419
`EXDIDICOTS s.cceesseue sone one oisilvbieneeiecaveven illetbisna Vee nihdaa heidi anetavsinannicbasaabakeaneovenie mana EMH MER CaeeNRORENENENE 423
`PUGHOR THON iss ccccassa siseseseueinsmsied davarnsaneravesbemnsnveansiennmaaicxcaionn nitenvnnacnErENeMneReReeENneNtENE 425
`Cover Image Credits ...c.csccccsccscccssessesesteesseescscsneaneacssesassnessseascansnesssecessneastessteananenstsqsaneneeneayencaneess 427
`
`MEDIATEK,Ex. 1004, Page 10
`
`MEDIATEK, Ex. 1004, Page 10
`
`

`

`
`
`COMPUTER GRAPHICS Proceedings, Annual Conference Series, 1993
`
`RealityEngine Graphics
`
`Kurt Akeley
`Silicon Graphics Computer Systems*
`
`Abstract
`
`The RealityEngine™ graphics system is (he first of a new genera-
`tion of systems designed primarily lo rendertexture mapped, an-
`lialiased polygons. This paper describes the architecture of the
`Realitylingine graphics system,then justifies someofthe decisions
`madeduringits design. The implementation is near-massively par-
`allel, employing 353 independent processorsin its fullest configura-
`tion, resulting in a measuredfill rate of over 240 millionantialiased,
`texture mappedpixels per sccond. Rendering performance exceeds
`1 million antialiased, texture mappedtriangles per second. In ad-
`dition to supporting the functions required of a general purpose,
`high-end graphics workstation, the system enables realtime, “out-
`the-window” image generation and interactive image processing.
`
`~~
`
`CR Categories and Subject Descriptors: 13.1 [Computer
`Graphics]: Hardware Architecture; 1.3.7 [Computer Graphics]:
`Three-Dimensional Graphics and Realism- colon shading, shad-
`owing, and texture
`
`1
`
`Introduction
`
`This paperdescribes and to a large extent justifies the architecture
`chosenfor the RealityIingine graphics system. ‘Ihe designers (hink
`of this system as our first implementation of a third-generation
`-graphics system.
`‘Yo us a generation is characterized not by the
`scope of capabilities of an architecture, but rather by the capabili-
`ties for which the archilecture was primarily designed — the target
`capabilities with maximized performance. Because we designed
`ourfirst machinein the early eighties, our notionoffirst generation
`corresponds to this period. Floating point hardware was just be-
`coming availableat reasonableprices, framebuffer memory wasstill
`quite expensive, and application-specific integrated circuits (ASICs)
`were nol readily available. The resulting machincs had workable
`transformation capabililics, but very limited framebuffer process-
`ing capabilities. In particular, smooth shading and depth buffering,
`which require substantial framebuffer hardware and memory, were
`nol available. Thus the target capabilities of first-generation ma-
`chines were the transformation and rendering offlat-shaded points,
`lines, and polygons. Theseprimitives were notlighted, and hidden
`surface elimination, if required, was accomplished by algorithms
`implemented by the application. Examples of such systems are the
`
`*2011.N. Shoreline Blyd., Mountain View, CA 94043 USA, kutt@sgi.com
`
`Permission lo copy without fee all or part of this material is granted
`Provided that the copics are not made ar distributed for direct
`commercial advantage, ihe ACM copyright notice andthe title of the
`publication andits date appear, andnotice is given (hat copyingis by
`bermissionofthe Association for Computing Machinery. To copy
`atherwise,or to republish, requires a fee and/or specific permission.
`
`Silicon Graphics Iris 3000 (1985) and the Apollo DN570 (1985).
`‘Toward the end ofthefirst-generation period advances in technology
`allowed lighting, smooth shading, and depthbuffering to be imple-
`mented, but only with an order of magnitudeless performance than
`was available to renderflat-shaded lines and polygons. Thus the
`target capability of these machines remained first-gencration. The
`Silicon Graphics 4DG (1986)is an example of such an architecture.
`
`Becausefirst-generation machines could not efficiently climinate
`hiddensurfaces, and could not efficiently shade surfaces even if the
`application was able to eliminate them, they were more effective
`at rendering wireframe images thanal rendering solids. Begin-
`ning in 1988 a second-generalion of graphics systems, primarily
`workstations rather than terminals, became available.
`‘These ma-
`chines took advantage of reduced memory costs and the increased
`availabilily of ASICs to implementdeep framebuffers wilh multiple
`rendering processors. These framebuffers had the numeric ability
`to interpolate colors and depths with little or no performanceloss,
`and the memory capacity and bandwidth to support depthbuffering
`with minimal performance loss. They were therefore able lo render
`solids and full-frame scenesefficiently, as well as wireframe images.
`The Silicon Graphics GT (1988)[11] and the Apollo DN590 (1988)
`are carly examples of second-generation machines, Later second-
`generation machines, such as the Silicon Graphics VGX[12] the
`Hewlctt Packard VRX, and the Apollo DN10000{4] include texture
`mapping and antialiasing of points and lines, but not of polygons.
`Their performancesare substantially reduced, however, when tex-
`ture mapping is enabled, and the texture size (of the VGX) and
`filtering capabilities (of the VRX and the IYN10000)are limited,
`
`The RealityEngine systemis ourfirst third-generation design. Jts
`target capability is the rendering oflighted, smooth shaded, depth
`buffered, texture mapped, antialiased triangles, The initial target
`performance was 1/2 million such triangles per second, assuming
`the triangles are in short strips, and 10 percentintersectthe viewing
`frustum boundaries, Textures were to be well filtered (8-sample lin-
`car interpolation within and between two mipmap[13] levels) and
`large enough (1024 x 1024) to be usable as truce images, rather
`than simply as repeated textures. Antialiasing wasto result in high-
`quality images of solids, and was to work in conjunction with depth
`buffering, meaning that no application sorting was to be required.
`Pixels were to be filled at a rate sufficient to support 30IIz ren-
`dering of full-screen images. Vinally, the performance on second-
`generation primitives (lighted, smooth shaded,depth buffered) was
`to be no Jowerthan that of the VGX, which renders roughly 800,000
`such meshtriangles per second. All of these goals were achieved.
`
`The remainderof(his paperis in four parts: a description ofthe
`architecture, some specifics of features supported by the archilec-
`ture, alternatives considered during the design of the architecture,
`and finally some appendixes that describe performance andimple-
`mentation details.
`
`© 1993
`
`ACM-0-89791-60 1-8/93/008/0109
`
`$01.50
`
`109
`
`
`MEDIATEK, Ex. 1004, Page 11
`
`MEDIATEK, Ex. 1004, Page 11
`
`

`

`SIGGRAPH93, Anaheim,California, 1-6 August 1993
`
`
`
`
`
`
`
`
`
`System Bus —~
`Command
`Processor
`
`Geometry
`Engines
`Trlangte Bue —>~
`Fragment __.
`Generators
`
`Imago __.__
`Engines
`
`Denne niie
`| geometry jy
`jan.
`an board
`=a
`
`i]
`a)
`
`
`
`
`or ee ee
`_. raater memory bonrd at
`
`
`
`Figure 1. Board-level block diagram ofan intermediate configu-
`xation with 8 Gecanetry Engines on the geomeny board, 2 raster
`memory boards, and a display generator board.
`
`
`
`
`
`
`
`2 Architecture
`
`The RealityEngine system is a 3, 4, or 6 board graphics accelerator
`that is installed in a MIPS RISC workstation. The graphics system
`and one or more MIPS processors are connected by a single system
`bus. Figure | is a board-ievel block diagram of the RealityEngine
`graphics accelerator, The geometry board comprises an input FIFO,
`the Command Processor, and 6, 8, or 12 Geometry Engines. Each
`raster memory board comprises 5 Fragment Generators (each with
`its own complete copyof the texture memory), 80 Image Engines,
`and enough framebuffer memory to allocate 256 bits per pixel to a
`1280 x 1024 framebuffer. The display generator board supports all
`video functions, including video timing, genlock, color mapping,
`and digital-to-analog conversion. Systems can be configured with
`1, 2, or 4 raster memory boards,resulting in 5, 10, or 20 Fragment
`Generators and 80, 160, or 320 ImageJingines.
`To get an inilial notion of how the system works, let's follow
`a single triangle as it is rendered. The position, color, normal,
`and texture coordinate commands that describe the vertexes of the
`triangle in object coordinates are queued by the input FIFO, then
`interpreted by the Command Processor. The Command Processor
`directs all of this data to one of the Geometry Engines, where the
`coordinates and normalsare transformedto eye coordinates, lighted,
`transformedto clip coordinates, clipped, and projected to window
`coordinates. The associated texture coordinates are transformed
`by a third matrix and associated with the window coordinates and
`colors. Then window coordinate slope information regarding the
`red, green, blue, alpha, depth, and texture coordinates js computed.
`The projected triangle, ready for rasterization,is then output from
`the Geometry Engine and broadcast on the ‘Triangle Bus to the5,
`10, or 20 Fragment Generators.
`(We distinguish between pixels
`generated by rasterization and pixels in the framebuffer, referring to
`the former as fragments.) Each Fragment Generatoris responsible
`for the rasterization of 1/5, 1/10, or 1/20 ofthe pixels in the frame-
`
`110
`
`buffer, with the pixel assignments finely interleaved to insure that
`even small triangles are partially rasterized by each of the Fragment
`Generators. Each Fragment Generator computes the intersection of
`the set of pixels that ace fully or partially covered by the triangle and
`ihe set of pixels in the framebuffer thatit is responsible for, gener-
`ating a fragmentfor each ofthese pixels. Color, depth, and texture
`coordinates are assigned to each fragment based onthe initial and
`slope values computed by the Geometry Engine. A subsample mask
`is assigned to the fragment based on the portion of each pixel that
`is covered by the triangle. The local copy of the texture memory is
`indexed by the texture coordinates, and the 8 resulting samples are
`reduced by linear interpolation to a single color value, which then
`modulates the fragment’s color.
`The resulting fragments, each comprising a pixel coordinate, a
`calor, a depth, and a coverage mask, are then distributed to the
`Image Engines, Like the Fragment Generators, the Image Engines
`are each assigned a fixed subset of the pixels in the framebuffer.
`These subsets are themselves subsets of the Fragment Generator
`allocations, so that each Fragment Generator communicates only
`with the 16 Image Engines assigned to it, Each Image Engine
`manages its own dynamic RAM that implements its subset of the
`framebuffer. When a fragmentis received by an Image Engine,
`its depth and color sample data are merged with the data already
`stored al that pixel, and a new aggregate pixel coloris immediately
`computed. Thus the image is complete as soon as the last primitive
`has been rendered; there is no need fora final framebufler operation
`to resolve the multiple color samples al each pixel location to a
`single displayable color.
`Before describing each ofthe rendering operations in more detail,
`we make the following observations. First, after it is separated by
`the Command Processor, the stream ofrendering commands merges
`only at the Triangle Bus. Second, triangles of sufficient size (a
`function of the numberof raster memory boards) are processed by
`almost all the processors in the system, avoiding only 5, 7, or 1]
`Geometry Engines. Finally, small to moderate FIFO memoriesare
`included at the input and output of each Geometry Engine, at the
`input of each Fragment Generator, and at the input of each Image
`Engine. These memories smooth the flow of rendering commands,
`helpingto insure that the processors are utilized efficiently.
`
`2.1 Command Processor
`
`That the CommandProcessoris required atall is primarily a func-
`tion of the OpenGL™ [8)(7] graphics language. OpenGLis modal,
`meaning that much ofthe state that controls rendering js included
`in the command stream only when it changes, rather than with
`each graphics primitive. The Command Processor distinguishes
`between (wo classes af this modal state. OpenGL commands that
`are expected infrequently, such as matrix manipulations and light-
`ing model changes, are broadcastto all the Geometry Engines.
`OpenGL commands that are expected frequently, such as vertex
`colors, normals, and texture coordinates, are shadowed by the Com-
`mand Processor, and the current values are bundled with each ren-
`dering commandthat is passed to an individual Geometry Engine.
`The CommandProcessor also breaks long connected sequences of
`line segments or triangles into smaller groups, each group passing
`to a single Geometry Engine. The size of these groups is a trade-
`off between the increased vertex processing efficiency of larger
`groups (due to shared vertexes within a group) and the improved
`{oad balancingthat resul(s from smaller groups. Finally, because
`the Command Processor mustinterpret each graphics command,it
`is also able to detect invalid command sequences and protect the
`
`MEDIATEK, Ex. 1004, Page 12
`
`MEDIATEK, Ex. 1004, Page 12
`
`

`

`COMPUTER GRAPHICS Proceedings, Annual Conference Series, 1993
`
`2.3 Triangle Bus
`
`The Triangle Bus acts as a crossbar, connecting the output of each
`Geometry Engine to the inputs of all the Fragment Generators,
`Because all Geometry Engine output convergesat this bus, it is a
`potential bottleneck. To avoid performanceloss, the Triangle Bus
`was designed with bandwidth to handle over one million shaded,
`depth buffered, texture mapped,antialiased triangles per second,
`more than twice the numberof primitives per second that were
`anticipated from an 8 Geometry Engine system. This performance
`cushion allows the later-conceived 12 Geometry Engine system lo
`render at full performance, in spite of the greater than expected
`performanceofthe individual engines.
`In addition to broadcasting the rasterization data for triangles to
`the Fragm