`

`Computer Graphics
`
`PRJ CIPLES AND PRACflCE
`SLC0:'\0 EDITIO:'IJ in C
`
`Foley • vun Dam • Fcmcr • Hughes
`
`James 0. •'oley (Ph.D., University of Mochogan) is lhe
`founding dorector of the interdiscoplinary GraphiC>. Visual·
`tl31oon & Uubo~t) Centu at Georgoa ln~ttlute of Technol·
`01)). and Profe;sor of Computer Scoenc:e and of Electrical
`Engoneenna. Coauthor "'ilh And~ •an Dam of Funda·
`mrntols of lmtructllt Computtr Graphu:s, Foley os 3
`member of ACM. ACM SIGGRAPII. ACM SIGCIII. the
`Hu~an Factors Society. IEEE, and the IEEE Computer
`Soeocty. l ie recently ser.cd as Editor-in-Chief of ACM
`Transllt 110m"" Graphics. and l~ on 1he editoriul boards of
`Compllltro arul Grapllrcs. User Modtlm~ uml U.vu-Adapt(cid:173)
`td lnrtrat rum. and Prtstna. Hi, re<ean:h onteresl\ in(cid:173)
`clude model-~ u<er interface de•ctopmeD!tools. user
`in1erface \Oil" are. onformation vt>uahl<luoo, mulumedia.
`and human f.oCtoo of the user interface. Foley os a Fello"
`of the IEEE. and a member of Pho Beta Kappa. Tau Beta
`Pill. Ela Kappa u. and Sogma Xi. AI GeO'lJW Tech. he
`has received College of Computing gradua1e s1uden1
`award, n• Mo>t Likely 10 Make Studenls Wnnl to Grow
`Up to Be Prote,.or<. Most lnspirmional F:ocully Member.
`the campu~ lnterdoo;ciplinlll) Aclovilte< A"ard. and the
`Sogma Xi Su;tained Re.'oea1Ch A"ard.
`
`Andries \'lin Dam (Ph.D .• UDJ•et\11) of Penns}hanoa)
`was the liN ch.urman of the Computer Scoence Depart(cid:173)
`menial Bro"'n Unove..,uy. Current!) Thomas J. Wa1son.
`Jr. Unovef\11) Profcs.or of Technology nnd Educu1ion Jnd
`Profe.-or of Computer Science m Bro,.n. he is also Dircc(cid:173)
`lor of !he NSf'/ ARPA Science nnd Technology Cemcr for
`Computer Grnphic~ and Sciemilic Vi>unli7nlion. Hi~ re(cid:173)
`search lnlere~l\ onclude compu1er ~rnphic•. hypcnnedja
`S)Stems. and \\OrkMalJons. He is pas! Chaim1an of the
`Compuung RC\Cmh Msocia1ion. Choef ScocnlJ" at Elee(cid:173)
`tronoc Bon~ Technologoes. Chairman of ObJCCI Po.,.er'•
`T<ehnocal Ad' t\Ory Board. and • member of Mocrosofl's
`Technocal Advowry Board. A Fellow of both the IEEE
`Com puler Society and or ACM. he " aL1o cofounder of
`ACM SIGORAPH. Coauthor of the wodely u;cd book
`Fmodammttfls of ltuutu•ltrt Ctmtpru~r Grttpluc.< witlt
`James Foley, and of Objtct-Oritmtd Program111111g ;,
`P{Jjt a/ A Graplucu/ Approach, "-ith D. Brook>hore Con(cid:173)
`ner and Da>od ~oguodula. he has. on addouon. publt;hed
`over eighl) papeo. In 1990 van Dam recel\ed the NCGA
`Academoc A"Jrd. on 1991. the SIGGRAPH Stc•cn A.
`Coons A\I.Jrd. and on 1993 the AC\1 Karl V. Knrl>trom
`Ou1St3ndong Educa1or A""ard.
`
`. tc,en K. Feiner (Ph.D .. Bro"n Un.-ersuy) is Associa1e
`Profe.>sor of Computer ScJence at Columbo• Unt\er<tt).
`-.he,.., he directs the Computer Graplucs and u..,r lmcr·
`faces Lab. Hos currem research roeuses oo 3D user tnlcr·
`face>. virtual worlds. augmented real it). knowledge-oo.>ed
`desogn of gmphics and mullimediu. animmion, visualiza.
`tion. and hypermedia. Dr. Feiner is on !he edjtotial board<
`of ACM Trwtsacrio11s on GrliJllrics. /1!££ Tramaaio11s
`"" I /srwli:ation and Compllltr Grapl11rs. and £/tcrromc
`Publtshi"R· and is on the C\ecutove board of the IEEE
`T~><:hmcal Committee on Computer GraphiCs. He is a 111<'111·
`ber of ACM SIGGRAPH and 1he IEEE Computer Soeiety.
`In 1991 he received an ONR Young lnvestJgator Award. Dr
`Fetner's work has been published on over lifly papers and
`pre>entL-d in numerous talk>, tutorial>. and panels.
`
`John •~ Hughes (Ph.D .. Univers11y of California. Berkeley)
`is nn Assistunl Professor of Computer Science nl Brown
`Univc110ily. where he codirec" !he computer gruphics group
`"'•th Andries van Dam. Ht> research onlerests are in appli·
`cauon; or mathematics to computer gntphJcs. scienulic
`vosuJh.za!Jon. mathematical sh3pe descnpooo. malhemato(cid:173)
`cal fundamentals of con1pu1er gruplucs. and low-dirnen(cid:173)
`;oooal !apology and geomett) He o< a member of the AMS.
`IEEE. and ACM SIGGRAPH. Hos recent papers ha.e
`appeared in Complller Graplucs. and in Visualization Con·
`fcrence Proceedings. He al~o ho~ n long-standing in1ere~1 in
`!he u;e of COmpulcr graphics in mathematics educalion.
`
`RELATED TITLES
`
`The Pa5Cal·l>nguage •ersoon of Conrpmu Graphr~s· Pnn·
`rrpln and Pramu. Stcond Edtlton remruns available.
`ISBN 0·201-12 110-7
`
`lmroduwon w Computer Grcrplllt'S is an abbreviated vcr·
`MOn of' Foley, va.n D:om, Feiner. and Hugtocs thai focuse~ on
`tO(liCS e<sem ial for beginner. ttllhc field and provides e•(cid:173)
`pandcd explanations for reader> with '""' 1ccbnical bad(cid:173)
`ground. also with example, on C. Added to the orig~nal list
`of auth(m. Richard Pholltp. "a; pnncopall) responsoble for
`thos adapcatioo. ISBN 0-201·60921-S
`
`For on formation aboUI other Addison· Wesle) bools. you
`may acce>> our electronic cn1nlog through the World Wide
`Web nl http: I /WoMN .aw. com/ or through gopher
`aw.can
`
`TEXAS INSTRUMENTS EX. 1009 - 2/1253
`
`

`

`THE
`SYSTEMS
`PROGRAMMING
`SERIES
`
`Computer
`Graphics:
`Principles and
`Practice
`SECOND EDITION in C
`
`Foley • \lan Dam • Feiner • l-Iughes
`
`,
`
`TEXAS INSTRUMENTS EX. 1009 - 3/1253
`
`

`

`Plan I: "Vanna-I Game-n ' itiirur'lflfiv {IF Nod Greer-1N?” Cumpurar Gtaphlcs Lab J
`
`'Luinc Ilm Bumf |:Jn..r J Emit-.1. T Kw. anflJ Emma-r
`Flut- l.
`iPluduwd .11 Enlmch and 13'“ Curporntmn CDPVHUHI . 1989
`Calmch I
`
`
`
`
`TEXAS INSTRUMENTS EX. 1009 - 4/1253
`
`TEXAS INSTRUMENTS EX. 1009 - 4/1253
`
`

`

`HI“ I "Bland State,‘ by F. K. Mulgrlw. {Cnpvrifiht fl" 1m K. Mumrlva and
`E. Mandelbrot.)
`
`Pin-LI
`
`Hill III ”Luna Jr..' by J. LII-Ifllr. W. Emu. E. Ulth'f. Ind 5. Llffler. {Copyright If 15“
`
`TEXAS INSTRUMENTS EX. 1009 - 5/1253
`
`TEXAS INSTRUMENTS EX. 1009 - 5/1253
`
`

`

`SECOND EDITION IN C
`
`Computer Graphics
`
`PRINCIPLES AND PRACTICE
`
`TEXAS INSTRUMENTS EX. 1009 - 6/1253
`
`

`

`SECOND EDITION IN C
`
`Computer Graphics
`
`PRINCIPLES AND PRACTICE
`
`James D. Foley
`Georgia Institute of Technology
`
`Andries van Dam
`Brown University
`
`Steven K. Feiner
`Columbia University
`
`John F. Hughes
`Brown University
`
`..,..,
`
`ADDISON-WESLEY PUBLISHING COMPANY
`Reading, Massachusetts • Menlo Park, California • New York
`Don MiUs, Ontario • Wokingharn, England • Amsterdam • Bonn
`Sydney • Singapore • Tok)Q • Madrid • San Juan • Milan • Paris
`
`TEXAS INSTRUMENTS EX. 1009 - 7/1253
`
`

`

`Sponsoring Editor: Peter S. Gordon
`Production Supervisor: Bette J. Aaronson
`Production Supervisor for the C edition: Juliet Silveri
`Copy Editor: Lyn Dupre
`Text Designer: Herb Caswell
`Technical Art Consultant: Joseph K. Vetere
`Illustrators: C&C Associates
`Cover Designer: Marshall Henrichs
`Manufacturing Manager: Roy Logan
`
`This book is in the Addison-Wesley Systems Programming Series
`Consulting editors: IBM Editorial Board
`
`Library of Congress Cataloging-in-Publication Data
`
`Computer graphics: principles and practice I James D. Foley . . . [ et
`a!.]. -
`2nd ed. in C.
`p.
`em.
`Includes bibliographical references and index.
`ISBN 0-201-84840-6
`1. Computer graphics.
`T385.C5735 1996
`006.6'6-dc20
`
`I. Foley, James D. , 1942-
`
`Reprinted with corrections, July 1997.
`
`95-13631
`CIP
`
`Cover: " Dutch Interior," after Vermeer, by J. Wallace, M. Cohen, and D. Greenberg, Cornell University
`(Copyright © 1987 Cornell University , Program of Computer Graphics .)
`
`Many qf the designations used by manufacturers and sellers to distinguish their products are claimed as
`trademarks. Where those designations appear in this book, and Addison-Wesley was aware of a trademark
`claim, the designations have been printed in initial caps or all caps.
`
`The programs and applications presented in this book have been included for their instructional value. They are
`not guaranteed for any particular purpose. The publisher and the author do not offer any warranties or
`representations, nor do they accept any liabilities with respect to the programs or applications.
`
`Reprinted with corrections November 1992, November 1993, and July 1995.
`
`Copyright© 1996, 1990 by Addison-Wesley Publishing Company , Inc.
`
`All rights reserved . No part of this publication may be reproduced, stored in a retrieval system, or transmitted,
`in any form or by any means , electronic, mechanical, photocopying, recording, or otherwise, without the prior
`written permission of the publisher. Printed in the United States of America.
`
`6 7 8 9 10-DOC-99 98 97
`
`TEXAS INSTRUMENTS EX. 1009 - 8/1253
`
`

`

`To Marylou , Heather, Jenn, my parents, and my teachers
`Jim
`
`To Debbie, my father, my mother in memoriam, and
`my children Elisa, Lori, and Katrin
`
`To Jenni, my parents, and my teachers
`
`To my family, my teacher Rob Kirby, and
`my father in memoriam
`
`And to all of our students.
`
`Andy
`
`Steve
`
`John
`
`TEXAS INSTRUMENTS EX. 1009 - 9/1253
`
`

`

`THE SYSTEMS PROGRAMMING SERIES
`
`Communications Architecture for Distributed Systems
`
`R.J. Cypser
`
`An IntrOduction to Database Systems, Volume I,
`Fifth Edition
`
`C.J. Date
`
`An Introduction to Database Systems, Volume U
`
`C.J. Date
`
`Computer Graphics: Principles and Practice,
`Second Edition
`
`Structured Programming: Theory and Practice
`
`Conceptual Structures: lnformation ProCessing in
`Mind and Machines
`
`James D. Foley
`Andries van Dam
`Steven K. Feiner
`John F. Hughes
`
`Richard C. Linger
`Harlan D. Mills
`Bernard l. Wiu
`
`John F. Sowa
`
`IBM EDITORIAL BOARD
`
`Chairman:
`
`Gene F. Hotfnagle
`
`TEXAS INSTRUMENTS EX. 1009 - 10/1253
`
`

`

`Foreword
`
`The field of systems programming primarily grew out of the efforts of many programmers
`and managers whose creative energy went into producing practical, utilitarian systems
`programs needed by the rapidly growing computer industry. Programming was practiced as
`an art where each programmer invented his own solutions to problems with little guidance
`beyond that provided by his immediate associates. In 1968, the late Ascher Opler, then at
`IBM, recognized that it was necessary to bring programming knowledge together in a form
`that would be accessible to all systems programmers. Surveying the state of the art, he
`decided that enough useful material existed to justify a significant codification effort. On his
`recommendation, IBM decided to sponsor The Systems Programming Series as a long term
`project to collect, organize, and publish those principles and techniques that would have
`lasting value throughout the industry. Since 1968 eighteen titles have been published in the
`Series, of which six are currently in print.
`The Series consists of an open-ended collection of text-reference books. The contents
`of each book represent the individual author's view of the subject area and do not
`necessarily reflect the views of the lBM Corporation. Each is organized for course use but is
`detailed enough for reference.
`Representative topic areas already published, or that are contemplated to be covered by
`the Series, include: database systems, communication systems, graphics systems, expert
`systems, and programming process management. Other topic areas will be included as the
`systems programming discipline evolves and develops.
`
`The Editorial Board
`
`ix
`
`TEXAS INSTRUMENTS EX. 1009 - 11/1253
`
`

`

`Preface
`
`Interactive graphics is a field whose Lime has come. Until recently it was an esoteric
`specialty involving expensive display hardware, substantial computer resources, and
`idiosyncratic software. In the last few years, however, it has benefited from the steady
`and sometimes even spectacular reduction in the hardware price/performance ratio
`(e.g., personal computers for home or office with their standard graphics terminals),
`and from the development of high-level, device-independent graphics packages that
`help make graphics programming rational and straightforward. Interactive graphics is
`now finally ready to fulfill its promise to provide us with pictorial communication and
`thus to become a major facilitator of man/machine interaction. (From preface,
`Fundamemals of Interactive Computer Graphics, James Poley and Andries van Dam,
`1982)
`
`This assertion that computer graphics had finally arrived was made before the revolution in
`computer culture sparked by Apple's Macintosh and the ffiM PC and its clones. Now even
`preschool children are comfortable with interactive-graphics techniques, such as the
`desktop metaphor for window manipulation and menu and icon selection with a mouse.
`Graphics-based user interfaces have made productive users of neophytes, and the desk
`without its graphics computer is increasingly rare.
`At the same time that interactive graphics has become common in user interfaces and
`visualization of data and objects, the rendering of 30 objects has become dramatically
`more realistic, as evidenced by the ubiquitous computer-generated commercials and movie
`special effects. Techniques that were experimental in the early eighties are now standard
`practice, and more remarkable " photorealistic" effects are around the comer. The simpler
`kinds of pseudorealism, which took hours of computer time per image in the early eighties,
`now are done routinely at animation rates (ten or more frames/second) on personal
`computers. Thus "real-time" vector displays in 1981 showed moving wire-frame objecL~
`made of tens of thousands of vectors without hidden-edge removal; in 1990 real-time raster
`displays can show not only the same kinds of line drawings but also moving objects
`composed of as many as one hundred thousand triangles rendered with Gouraud or Phong
`shading and specular highlights and with full hidden-surface removal. The highest(cid:173)
`performance systems provide real-time texture mapping, antialiasing, atmospheric attenua(cid:173)
`tion for fog and haze, and other advanced effects.
`Graphics software standards have also advanced significantly since our first edition.
`The SIGG RAPH Core '79 package, on which the first edition's SGP package was based,
`has all but disappeared, along with direct-view storage tube and refresh vector displays. The
`much more powerful PHlGS package, supporting storage and editing o( structure hierarchy,
`h,ts become an official ANSI and ISO standard, and it is widely available for real-time
`
`xi
`
`TEXAS INSTRUMENTS EX. 1009 - 12/1253
`
`

`

`xii
`
`Preface
`
`geometric graphics in scientific and engineering applications, along with PHIGS+, which
`suppons lighting, shading, curves, and surfaces. Official graphics standards complement
`lower-level. more efficient de facto standards, such as Apple's QuickDraw, X Window
`System's Xlib 20 integer raster graphics package, and Silicon Graphics' GL 30 library.
`Also widely available are implementations of Pixar's RenderMan interface for photorealis(cid:173)
`tic rendering and PostScript interpreters for hardcopy page and screen image description.
`Better graphics software has been used to make dramatic improvements in the .. look and
`feel ' 'of user interfaces. and we may expect increasing use of 3D effects, both for aesthetic
`reasons and for providing new metaphors for organizing and presenting, and navigating
`through information.
`Perhaps the most important new movement in graphics is the increasing concern for
`madding objects, not just for creating their pictures. Furthermore, interest is growing in
`describing the time-varying geometry and behavior of 30 objects. Thus graphics is
`increasingly concerned with simulation, animation, and a " back to physics" movement in
`both modeling and rendering in order to create objects that look and behave as realistically
`as possible.
`As the tools and capabilities available become more and more sophisticated and
`complex, we need to be able to apply them effectively. Rendering is no longer the
`bottleneck. Therefore researchers are beginning to apply anificial-intelligence techniques to
`assist in the design of object models, in motion planning, and in the la~ut of effective 20
`and 30 graphical presentations.
`Today the frontiers of gr.tphics are moving very rapidly, and a text that sets out to be a
`standard reference work must periodically be updated and expanded. This book is almost a
`total rewrite of the Fundamentals of Interactive Computer Graphics, and although this
`second edition contains nearly double the original 623 pages, "''e remain painfully aware of
`how much material we have been forced to omit.
`Major differences from the first edition include the following:
`
`• The vector-graphics orientation is replaced by a raster orientation.
`• The simple 20 floating-point graphics package (SGP) is replaced by two packages(cid:173)
`SRGP and SPHIGS-
`that reflect the two major schools of interactive graphics
`programming. SRGP combines features of the QuickDraw and Xlib 20 integer raster
`graphics packages. SPHIGS, based on PHIGS, provides the fundamental features of a 30
`floating-point package with hierarchical display lists. We explain how to do applications
`programming in each of these packages and show how to implement the basic clipping,
`scan-conversion, viewing, and display list traversal algorithms that underlie these
`systems.
`• User-interface issues are discussed at considerable length, both for 20 desktop metapbors
`and for 30 interaction devices.
`• Coverage of modeling is expanded to include NURB (nonuniform rational 8-spline)
`curves and surfaces, a chapter on solid modeling, and a chapter on advanced modeling
`techniques, such as physically based modeling, procedural models, fractals, L-grammar
`systems. and particle systems.
`• Increased coverage of rendering inc.ludes a detailed treatment of antialiasing and greatly
`
`TEXAS INSTRUMENTS EX. 1009 - 13/1253
`
`

`

`Preface
`
`xiii
`
`expanded chapters on visible-surface determination, illumination, and shading, including
`physically based il.lumination modcls, ray tracing, and radiosity.
`• Material is added on advanced raster graphics architectures and algorithms, including
`clipping and scan-conversion of complex primitives and simple image-processing
`operations, such as compositing.
`• A brief introduction to animation is added.
`
`This text can be used by those without prior background in graphics and only some
`background in Pascal programming, basic data structures and algorithms, computer
`architecture, and simple linear algebra. An appendix reviews the necessary mathematical
`foundations. The book covers enough material for a full-year course, but is partitioned into
`groups to make selective coverage possible. The reader, therefore, can progress through a
`carefully designed sequence of units, starting with simple, generally applicable fundamen(cid:173)
`tals and ending with more complex and specialized subjects.
`
`Basic Group. Chapter I provides a historical perspective and some fundamental issues in
`hardware, software, and applications. Chapters 2 and 3 describe, respectively, the use and
`the implementation of SRGP, a simple 20 integer grdphics package. Chapter 4 introduces
`graphics hardware, including some hints about how to use hardware in implementing the
`operations described in the preceding chapters. The next t~ chapters, 5 and 6 , introduce
`the ideas of transformations in the plane and 3·space, representations by matrices. the use
`of homogeneous coordinates to unify linear and affine transformations, and the description
`of 30 views, including the transformations from arbitrary view volumes to canonical view
`volumes. Finally, Chapter 7 introduces SPHIGS, a 30 floating-point hierarchical graphics
`package that is a simplified version of the PHIGS standard, and describes its use in some
`basic modeling operations. Chapter 7 also discusses the advantages and disadvantages of the
`hierarchy avai.lable in PHIGS and th.e structure of applications that use this graphics
`package.
`
`U ser Interface Group. Chapters 8-10 describe the current technology of interaction
`devices and then address the higher-level issues in user-interface design. Various popular
`user-interface paradigms are described and critiqued. In the final chapter user-interface
`software, such as window managers, interaction technique-libraries, and user-interface
`management systems, is addressed.
`
`Model Definition Group. The first ~ modeling chapters, ll and 12, describe the
`current technologies used in geometric modeling: the representation of curves and surfaces
`by parametric functions , especially cubic splines, and the representation of solids by
`various techniques, including boundary representations and CSG models. Chapter 13
`introduces the human color-vision system, various color-description systems, and conver(cid:173)
`sion from one to another. This chapter also briefly addresses rules for the effective use of
`color.
`
`Image Synthesis Group. Chapter 14, the first in a four-chapter sequence, describes
`the quest for realism from the earliest vector drawings to state-of-the-art shaded graphics.
`The artifacts caused by aliasing are of crucial concern in raster graphics, and this
`chapter discusses their causes and cures in considerable detail by introducing the Fourier
`
`TEXAS INSTRUMENTS EX. 1009 - 14/1253
`
`

`

`xiv
`
`Preface
`
`transfonn and convolution. Chapter I 5 describes a variety of strategies for visible-surface
`detennination in enough detail to allow the reader to implement some of the most im(cid:173)
`portant ones. Tllumination and shading algorithms are covered in detail in Chapter 16.
`The early part of this chapter discusses algorithms most commonly found in current
`hardware, while the remainder treats texture, shadows, transparency. reftections, physical(cid:173)
`ly based illumination models, ray tracing, and radiosity merhods. The last chapter in
`this group, Chapter l 7, describes both image manipulations, such as scaling, shearing,
`and rotating pixmaps, and image storage techniques, including various image-compres(cid:173)
`sion schemes.
`Advanced Techniques Group. The last four chapters give an overview of the current
`stare of tbe art (a moving target, of course). Chapter 18 describes advanced graphics
`hardware used in high-end commercial and research machines; this chapter was contributed
`by Steven Molnar and Henry Fuchs, authorities on high-perfonnance graphics architec(cid:173)
`tures. Chapter 19 describes the complex raster algorithms used for such tasks as
`scan-converting arbitary conics, generating antialiased text, and implementing page(cid:173)
`description languages, such as PostScript. The final two chapters survey some of the most
`important techniques in the fields of high-leYCI modeling and computer animation.
`
`The firs! two groups cover only elementary material and thus can be used for a basic
`course at the undergraduate leYCI. A follow-on course can then use the more advanced
`chapters. Alternatively, instructors can assemble customized courses by picking chapters
`out of the various groups.
`For example, a course designed to introduce students to primarily 20 graphics would
`include Chapters I and 2 , simple scan conversion and clipping from Chapter 3, a
`rechoology overview with emphasis on raster architectures and interaction devices from
`Chapter 4, homogeneous mathematics from Chapter 5, and 3D viewing only from a "how
`to use it'" poinl of view from Secrions 6.1 to 6 .3. The User Inrerface Group, Chapters
`8-10. would be followed by selected introductory sections and simple algorithms from tbe
`Image Synthesis Group, Chapters 14, 15, and 16.
`A one-course general overview of graphics would include Chapters I and 2, basic
`algorirhms from Chapter 3, raster architectures and interaction devices from Chapter 4,
`Chaprer 5, and most of Chapters 6 and 7 on viewi ng and SPHJGS. The second half of the
`course would include sections on modeling from Chapters I I and 13, on image synthesis
`from Chapters 14, 15, and 16, and on advanced modeling from Chapter 20 to give breadth
`of coverage in these slightly more advanced areas.
`A course emphasizing 30 modeling and rendering would start with Chapler 3 secrions
`on scan converting, clipping of lines and polygons, and introducing anrialiasing. The
`course would then progress 10 Chapters 5 and 6 on the basic mathematics of traosfonna(cid:173)
`rions and viewing, Chapre.r 13 on color, and chen cover !he key Chapters 14, 15, and 16 in
`the Image Synrhesis Group. Coverage would be rounded off by selections in surface and
`solid modeling, Chapter 20 on advanced modeling, and Chapter 21 on animation from the
`Advanced Techniques Group.
`
`Graphics Packages. The SRGP and SPHIGS graphics packages, designed by David
`Sklar, coauthor of the two chapters on these packages, are available from the publisher for
`
`TEXAS INSTRUMENTS EX. 1009 - 15/1253
`
`

`

`Preface
`
`xv
`
`the LBM PC (ISBN 0-201-54700-7), the Macintosh (ISBN 0-201-54701-5), and UNIX
`workstations running X II , as are many of the algorithms for scan conversion, clipping, and
`viewing (see page I 17 5).
`
`Acknowledgments. Th.is book could not have been produced without the dedicated
`work and the indulgence of many friends and colleagues. We acknowledge here our debt to
`those who have contributed significantly to one or more chapters; many others have helped
`by commenting on individual chapters, and we are grateful to them as well. We regret any
`inadvertent omissions. Katrina Avery and Lyn Dupre did a superb job of editing. Additional
`valuable editing on multiple versions of multiple chapters was provided by Debbie van
`Dam, Melissa Gold, and Clare Campbell. We are especially grateful to our production
`supervisor, Bette Aaronson, our art director, Joe Vetere, and our editor, Keith Wollman,
`not only for their great help in producing the book, but also for their patience and good
`humor under admittedly adverse circumstances-if we ever made a promised deadline
`during these frantic five years, we can't remember it!
`Computer graphics has become too complex for even a team of four main authors and
`three guest authors to be expert in all areas. We relied on colleagues and students to amplify
`our knowledge, catch our mistakes and provide constructive criticism of form and content.
`We take full responsibility for any remaining sins of omission and commission. Detailed
`technical readings on one or more chapters were provided by John Airey, Kurt Akeley, Tom
`Banchoff, Brian Barsky, David Bates, Cliff Besbers, Gary Bishop, Peter Bono, Marvin
`Bunker, Bill Buxton, Edward Chang, Norman Chin, Michael F. Cohen, William Cowan,
`John Dennis , Tom Dewald, Scott Draves, Steve Drucker, Tom Duff, Richard Economy,
`David EIIS'M>rth, Nick England, Jerry Farrell, Robin Forrest, Alain Fournier, Alan Freiden,
`Christina Gibbs, Melissa Gold, Mark: Green, Cathleen Greenberg, Margaret Hagen, Griff
`Hamlin, Pat Hanrahan, John Heidema, Rob Jacob, Abid Kamran, Mike Kappel, Henry
`Kaufman, Karen Kendler, David Kurlander, David Laidlaw, Keith Lantz, Hsien-Che Lee,
`Aaron Marcus, Nelson Max, Deborah Mayhew, Barbara Meier, Gary Meyer, Jim
`Michener, Jakob Nielsen, Mark: Nodine, Randy Pausch, Ari Requicha, David Rosenthal,
`David Salesin, Hanan Samet, Jam.es Sanford, James Sargent, Robin ScbauHer, Robert
`ScheiDer, John Scbnizlein, Michael Shantzis, Ben Shneiderman, Ken Shoemake, Judith
`Schrier, John Sibert, Dave Simons, Jonathan Steinhart, Maureen Stone, Paul Strauss, Seth
`Tager, Peter Tanner, Brice Tebbs, Ben Trumbore, Yi Tso, Greg Turk, Jeff Vroom, Colin
`Ware, Gary Watkins, Chuck Weger, Kevin Weiler, Thmer Whitted, George Wolberg, and
`Larry Wolff.
`Several colleagues, including Jack Bresenham, Brian Barsky, Jerry Van Aken, Dilip
`Da Silva (who suggested the uniform midpoint treatment of Chapter 3) and Don Hatfield,
`not only read chapters closely but also provided detailed suggestions on algorithms.
`We.lcome word-processing relief was provided by Katrina Avery, Barbara Britten, Clare
`Campbell, Tina Cantor, Joyce Cavatoni, Louisa Hogan, Jenni Rodda, and Debbie van Dam.
`Drawings for Chapters 1-3 were ably created by Dan Robbins, Scott Snibbe, Tina Cantor,
`and Clare Campbell. Figure and image sequences created for this book were provided by
`Beth Cobb, David Kurlander, Allen Paeth, and George Wolberg (with assistance from Peter
`Karp). Plates D.21- 37, showing a progression of rendering techniques, were designed and
`rendered at Pixar by Thomas Williams and H.B. Siegel, under the direction of M.W.
`Mantle, using Pixar's PhotoRealistic RenderMan software. Thanks to Industrial Light &
`
`TEXAS INSTRUMENTS EX. 1009 - 16/1253
`
`

`

`xvi
`
`Preface
`
`Magic for the use of their laser scanner to create Plates 0.24-37, and to Norman Chin for
`computing vertex normals for Color Plates 0 .3~32. L. Lu and Carles CasteiJsagu~ wrote
`programs to make figures.
`Jeff Vogel implemented the algorithms of Chapter 3, and he and Atul Butte verified the
`code in Chapters 2 and 7. David Sklar wrote the Mac and XII implementations of SRGP
`and SPHJGS with help from Ron Balsys, Scott Boyajian, Atul Butte, Alex Contovounesios,
`and Scott Draves. Randy Pauscb and his students ported the packages to the PC
`environment.
`We have installed an automated electronic mail server to aiJow our readers to obtain
`machine-readable copies of many of the algorithms, suggest exercises, report errors in the
`text and in SRGP/SPHIGS, and obtain errata lists for the text and software. Send email to
`" graphtext@ cs.brown.edu" with a Subject line of "Help" to receive the current list of
`available services. (See page 1175 for information on how to order SRGP and SPHIGS.)
`
`Washington. D.C.
`Providence, R.I.
`New York. N.Y.
`Providence, R.I.
`
`J.D.F.
`A.v.D.
`S. K.F.
`J.F.H.
`
`TEXAS INSTRUMENTS EX. 1009 - 17/1253
`
`

`

`Contents
`
`CHAPTER 1
`INTRODUCTION
`
`1
`
`2
`. . . . . • . . . . . . . . . . . . . • . . .
`lmage Processing as Picture Analysis
`1.1
`3
`. . . . . . . . . . . . . . . . . . • . . .
`1.2 The Advantages of Interactive Graphics
`4
`1.3 Representative Uses of Computer Graphics
`. . . . . . . . . . . . . . . . . . . .
`6
`. . . . . . . . . . . . . . . . . . . . . . . . . . . .
`1.4 Classification of Applications
`8
`1.5 Development of Hardware and Software for Computer Graphics
`. . . . . . .
`17
`. . . . . . . . . . . . . . . . .
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • . . . . . . 2 1
`. . . . . . . . . . ... •. . • . • . . . . . . . . . . . . . . . • . . . . . . 22
`
`r 6 Conceptual Framework for Inter.!ctive Graphics
`
`1.7
`
`Summary
`Exercises
`
`CHAPTER 2
`PROGRAMMING IN THE SIMPLE RASTER
`GRAPHICS PACKAGE (SRGP)
`
`25
`. . . . . . . . . . . . . . . •. . . . . . . . . . . . . . . . . . 26
`Drawing with SRGP
`2.1
`2.2 Basic Interaction Handling
`. . . . . . . . . • . • . . . . . . . . . . . . . • . . . 40
`2.3 Raster Graphics Features
`. . . . . . . . . . . • . . . . . . • . . . . . . . . • . . . 52
`2.4
`Limitations of SRGP
`. . . . . . . . . . . . . . . . . . . . . . . . . . . • . . . . . 60
`2.5
`Summary
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
`. . . . . .. . . . . . . . . . .. .. . . . . . . .. . . .. .. .. . .. . 64
`Exercises
`
`CHAPTER 3
`BASIC RASTER GRAPHICS ALGORITHMS
`FOR DRAWING 2D PRIMITIVES
`
`67
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
`Overview
`3.1
`Scan Converting Lines
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
`3.2
`Scan Converting Circles
`.. ................ , . . . . . . . . . . . . 81
`3.3
`Scan Converting Ellipses
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
`3.4
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
`Filling Rectangles
`3.5
`Filling Polygons
`. . . . . . . . . . . . . . . . . . . . . . . . • . . . . . . . . . . . 92
`3.6
`Filling Ellipse Arcs
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
`3.7
`Pattern Filling
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
`3.8
`Thick Primitives
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
`3.9
`3.10 Line Style and Pen Style .................. • ...... . ..... 109
`3.11 Clipping in a Raster World
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
`3.12 Clipping Lines
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . • . . . . . . . Ill
`
`TEXAS INSTRUMENTS EX. 1009 - 18/1253
`
`

`

`xviil
`
`Contents
`
`3. 13 Clipping Circles and EUipses ......•.•................... 124
`3.14 Clipping Polygons
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
`3.15 Generating Characters
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
`3. 16 SRGP ..copy Pixel
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
`3.17 Anuahasmg ....... . .......... ... .................. 132
`3. 18 Summary ......................................