PRINCIPLES AND PRACTICE
`
`THIRD EDITION
`
`OMPUTER GRAPHICS
`
`IPR2018-00788
`
`JOHN F. HUGHES - ANDRIES VAN DAM > MORGAN MCGUIRE
`
`DAVID F. SKLAR - JAMES D. FOLEY - STEVEN K. FEINER * KURT AKELEY
`
`3SHAPE EXHIBIT 2005
`Exocad v. 3Shape
`
`

`

`
`
`EERaHRDRETRORaBOSOAIRarUEDASRABORGOthses
`CSStitsASTaaBoaEegAEeeecao
`
`
`
`
`%
`
`Computer Graphics
`
`Principles and Practice
`
`Third Edition
`3
`
`JOHN F. HUGHES
`
`ANDRIES VAN DAM
`
`MORGAN MCGUIRE
`DAVID FE SKLAR
`JAMESD. FOLEY
`STEVENK. FEINER
`
`KURT AKELEY
`
`vvAddison-Wesley
`
`
`
`Upper Saddle River, NJ « Boston « Indianapolis « San Francisco
`New York * Toronto * Montreal * London « Munich « Paris * Madrid
`Capetown * Sydney * Tokyo * Singapore * Mexico City
`
`teknehadearstaanraeget
`
`aietiaacesto
`
`
`

`

`
`
`Manyofthe designations used by manufacturers andsellers to distinguish their products are claimed
`as trademarks. Where those designations appearin this book, and the publisher was aware of a
`trademark claim, the designations have been printed with initial capital letters or in all capitals.
`
`The authors and publisher have taken care in the preparation of this book, but make no expressed or
`implied warranty of any kind and assumeno responsibility for errors or omissions. No liability is
`assumed for incidental or consequential damages in connection with or arising out of the use of the
`information or programs containedherein.
`
`The publisher offers excellent discounts on this book when ordered in quantity for bulk purchases or
`special sales, which may includeelectronic versions and/or custom covers and contentparticular to
`yourbusiness, training goals, marketing focus, and branding interests. For more information, please
`contact:
`
`
`
`U.S. Corporate and GovernmentSales
`governmentsales @pearsoned.com
`
`For sales outside the United States, please contact:
`
`International Sales
`intlcs @pearson.com
`
`Visit us on the Web: informit.com/aw
`
`Library of Congress Cataloging-in-Publication Data
`Hughes, John F., 1955—
`Computer graphics: principles and practice / John F. Hughes, Andries van Dam, Morgan McGuire,
`David F. Sklar, James D. Foley, Steven K. Feiner, Kurt Akeley.—Third edition.
`pages cm
`Revised ed. of: Computer graphics / James D. Foley... [et al.].—-2nd ed. ~ Reading, Mass. :
`Addison-Wesley, 1995.
`Includes bibliographical references and index.
`ISBN 978-0-321-39952-6 (hardcover : alk. paper)—ISBN 0-321-39952-8 (hardcover: alk. paper)
`1. Computer graphics. I. Title.
`T385.C5735 2014
`006.6—de23
`
`2012045569
`
`Copyright © 2014 Pearson Education,Inc.
`
`All rights reserved. Printed in the United States of America. This publication is protected by
`copyright, and permission must be obtained from the publisherprior to any prohibited reproduction,
`storage in a retrieval system, or transmission in any form or by any means,electronic, mechanical,
`photocopying, recording, or likewise. For information regarding permissions, request forms and the
`appropriate contacts within the Pearson Education Global Rights & Permissions,Department, please
`visit www.pearsoned.com/permissions/.
`
`ISBN-13: 978-0-321-39952-6
`ISBN-10:
`0-321-39952-8
`2
`17
`
`
`
`
`
`

`

` “ieee
`
`
`C
`
`Contents at a Glance
`
`CONTCNES 0. eee cece e etc cesettseseseecesecstecsesessssessestevssteesstetsasctatensasess
`ix
`PHEPACE .oecccccccesecceencecescecetsesesiessssssessecsecsecstssevsevaseivsseuserseaneateas XXKV
`About the Authors ..c.eccccccccccccccscccsccscsesscesevsecesevesusecateuasscsecstscsseeses xlv
`
`
`:
`:
`
`‘
`E
`'
`|
`|
`
`
`
`]
`Introduction... cccccecccccceecssecsecesensecssesasecseeseceaseuss
`VL
`35
`Introduction to 2D Graphics Using WPF............0..00..00c000.
`2
`61
`3 An Ancient Renderer Made Moderm...............0....cccccccccccceees
`81
`4 A2D Graphics Test Bed.....cccccccsccccssscsssessssssssesssssessssseee
`5 An Introduction to Human Visual Perception....................... 101
`6
`Introduction to Fixed-Function 3D Graphics and
`Hierarchical Modeling .........0.00..0.cccccccecccceccsccsseeseececeseeeeaes 117
`7 Essential Mathematics and the Geometry of2-Space and
`BSPACE oocecvessssesevessssssssvsssvsssssissssissesisssssesssstssesesasessssesee 149
`A Simple Wayto Describe Shape in 2D and 3D.................... 187
`Functions onCSce 201
`10 Transformations in Two Dimensions.......0..........0..00ccccccccc0ccs. 221
`11 Transformations in Three Dimensions...........Vacseseeeaaeeeeeeanenes 263
`12 A 2D and 3D Transformation Library for Graphics............. 287
`13 Camera Specifications and Transformations.................0.0..... 299
`14 Standard Approximations and Representations.................... 321
`“15 Ray Casting and Rasterization ..0..0000000..0.occcccccccccceccecceseeeee 387
`16.Survey of Real-Time 3D Graphics Platforms......................... 451
`17
`Image Representation and Manipulation.....................000000.. 481
`18
`Images and Signal Processing ...........0..0...cceccccccecccccseceesceseee 495
`19 Enlarging and Shrinking Images .0.0000000.0 00. ecoccccceccceccecceees 533
`
`-
`|
`vy
`|
`|
`|
`|
`|
`|
`
`vii
`
`
`
`

`

`viii
`
`Contents at a Glance
`
`20 Textures and Texture Mapping....................: cece teers 547
`21 Interaction Techniques ..............cccccccceccseeseceseeeeseeeeeseteeneenees 567
`22 Splines and Subdivision Curves.............cccc:ccceeereteee, 595
`23 Splines and Subdivision Surfaces..................::::c eee 607
`24
`Implicit Representations of Shape ................... cece 615
`25 MESHES... ec ee ccccccc cee cecee cece ce eeeennneeeeeeeeeeeenneeu eee eentbenaaeaneeeese 635
`
`26 Light... cee cere cee cereeeneceneeseteessseeeseeseesneeesneeenten 669
`27. Materials and Scattering... cece eee ccccceeeesnsaeneeneees 7\1
`
`QB COLO cece cee ceeenee eee ee eee n enn e eee e eee en HEISE SF eee tebe ana taeeee® 745
`
`
`
`29 Light Transport .........000 000 cccceerseeceeeereeeesneeeeteeenneeenes 783
`30 Probability and Monte Carlo Integration......................06 801
`31 Computing Solutions to the Rendering Equation:
`Theoretical Approaches................... 00ers eeeecereneateees 825
`32 Rendering in Practice 0.0.0.0... cece teen eeeereteeeeeees 881
`33 Sader... ec ecccccccccee cece cece eet e cece cece eee eee e Eee EEE EE EEE EEE EE EEE 927
`
`34 Expressive Rendering ............0..00ccccceccccssceseceneeetteenseerereenaes 945
`35 Mtn. ..:......cccccceececcceeceeeeeeeetaneeeeenerensenseeeeeeeeseseneeeeneeeeess 963
`36 Visibility Determination.........seaseaeeeeaeeeeeseneeeaesevstsaeeenesaes 1023
`37 Spatial Data Structures............ vacceeeeeceeeeneauecececeeeesvsenaceeeeeers 1065
`38 Modern Graphics HarGware..............cccccccccccccccecereeteeeeeeseseees 1103
`
`List ofPrinciples .....cccccccccececccseseetseeeeteveeeeeeseneeeteeseseeenecseeeseeteaes 1145
`Bibliography cosecccssvccssssvvscssssvsssvessssssesssssessssssessesssessesssisesessiceessssees 1149
`TNO. cece cc cece cccaccuccuveceneecceceueceeceseeeeesaea seen eneeeeseeeee eee eeeeeneneeeeeeeeeeeas 1183
`
`
`
`
`
`

`

`
`
`Chapter1
`
`Introduction
`
`This chapter introduces computer graphics quite broadly and from several per-
`spectives: its applications, the various fields that are involved in the study of
`graphics, someof the tools that make the images produced by graphics so effec-
`tive, some numbers to help you understandthe scales at which computergraphics
`works, and the elementary ideas required to write your first graphics program.
`We'll discuss many of these topics in more detail elsewhere in the book.
`
`1.1 An Introduction to Computer Graphics
`Computer graphics is the science and art of communicating visually via a com-
`puter’s display andits interaction devices. The visual aspect of the communica-
`tion is usually in the computer-to-humandirection, with the human-to-computer
`direction being mediated by devices like the mouse, keyboard, joystick, game
`controller, or touch-sensitive overlay. However, even this is beginning to change:
`Visual data is starting to flow back to the computer, with new interfaces being
`based on computervision algorithms applied to video or depth-camerainput. But
`for the computer-to-user direction, the ultimate consumers of the communica-
`tions are human, and thus the ways that humans perceive imagery arecritical in
`the design of graphics! programs—features that humansiignore need not be pre-
`sented (nor computed!). Computer graphicsis a cross-disciplinary field in which
`physics, mathematics, humanperception, human-computerinteraction, engineer-
`ing, graphic design, andart all play important roles. We use physics to model
`light and to perform simulations for animation. We use mathematics to describe
`shape. Human perceptualabilities determine our allocation of resources—we
`don’t want to spend time rendering things that will not be noticed. We use engi-
`neering in optimizing the allocation of bandwidth, memory, and processortime.
`Graphic design and art combine with human-computer interaction to make the
`computer-to-human direction of communication most effective. In this chapter,
`
`
`1. Throughout this book, when weuse the term “graphics” we mean “computer graphics.”
`
`1
`
`

`

`
`UL
`
`we discuss someapplication areas, how conventional graphics systems work, and
`how eachofthese disciplines influences work in computer graphics.
`A narrow definition of computer graphics would state thatit refers to taking a
`modelof the objects in a scene (a geomettic description of the things in the scene
`and a description of how theyreflect light) and a modelof the light emitted into the
`scene (a mathematical description of the sources of light energy, the directions of
`radiation, the distribution of light wavelengths, etc.), and then producing a repre-
`sentation of a particular view of the scene(thelight arriving at some imaginary eye
`or camera in the scene). In this view, one might say that graphicsis just glorified
`multiplication: One multiplies the incominglight by the reflectivities of objects in
`the scene to compute the light leaving those objects’ surfaces and repeats the pro-
`cess (treating the surfaces as new light sources and recursively invoking the light-
`transport operation), determiningall light that eventually reaches the camera. (In
`practice, this approach is unworkable,butthe idea remains.) In contrast, computer
`vision amounts tofactoring—given a view of a scene, the computer vision system
`is charged with determining the illumination and/or the scene’s contents (which
`a graphics system could then “multiply” together to reproduce the same image).
`In truth, of course, the vision system cannotsolve the problem as stated and typ-
`ically works with assumptions aboutthe scene, or the lighting, or both, and may
`also have multiple views of the scene from different cameras, or multiple views
`from a single camerabutat differenttimes.
`
`n the field of computer graphics, the word “model”can refer to a geometric
`model or a mathematical model. A geometric model is a model of something
`weplan to have appear in a picture: We make a modelofa car, or a house, or
`an armadillo. The geometric model is enhanced with various otherattributes
`that describe the coloror texture or reflectance of the materials involved in the
`model. Starting from nothing and creating such a modelis called modeling,
`and the geometric-plus-other-information description thatis the result is called
`a model.
`A mathematical modelis a model of a physical or computational process.
`For instance, in Chapter 27 we describe various models of how light reflects
`from glossy surfaces. We also have models of how objects move and models of
`things like the image-acquisition process that happensinadigital camera. Such
`models may be faithful (i.c., may provide a predictive and correct mathemat-
`ical model of the phenomenon)ornot; they may be physically based, derived
`from first principles, or perhaps empirical or phenomenological, derived from
`observations or even intuition.
`
`— I
`
`In actual fact, graphics is far richer than the generalized multiplication pro-
`cess of rendering a view,just as vision is richer than factorization. Much ofthe
`“ current research in graphicsis in methodsfor creating geometric models, methods
`for representing surface reflectance (and subsurface reflectance, and reflectances
`of participating media such as fog and smoke,etc.), the animation of scenes by
`physical laws and by approximations of those laws, the control of animation,
`interaction with virtual objects, the invention of nonphotorealistic representa-
`tions, and, in recent years, an increasing integration of techniques from computer
`vision. As a result, the fields of computer graphics and computervision are grow-
`ing increasingly closer to each other. For ‘example, consider Raskar’s work on a
`
`
`
`
`
`2
`
`Introduction
`
`

`

`
`
` ae
`
`TEBLRRTPRURaoSRreerrieennane
`
`aeroertiestaictmeccaiitnaeassr
`
`1.1. An Introduction to Computer Graphics
`
`3
`
`
`
`Figure 1.1: A nonphotorealistic camera can create an artistic rendering of a scene by
`applying computer vision techniques to multiple flash-photo images and then rerender-
`ing the scene using computer graphics techniques. Atleft is the original scene; at rightis
`the new rendering of the scene. (Courtesy ofRamesh Raskar; ©2004 ACM, Inc. Included
`here by permission.)
`
`nonphotorealistic camera: The camera takes multiple photos of a single scene,
`illuminated by differently placed flash units. From these various images, one can
`use computer vision techniques to determine contours and estimate some basic
`shape properties for objects in the scene. These, in turn, can be used to create a
`nonphotorealistic rendering of the scene, as shown in Figure 1.1.
`In this book, we emphasizerealistic image capture and rendering becausethis
`is where the field of computer graphics has hadthe greatest successes, represent-
`ing a beautiful application of relatively new computer science to the simulation
`ofrelatively old physics models. But there’s more to graphics than realistic image
`capture and rendering. Animationandinteraction, for instance, are equally impor-
`tant, and we discuss these disciplines throughout many chapters in this book as
`well as address them explicitly in their own chapters. Why has success in the
`nonsimulation areas been so comparatively hard to achieve? Perhaps because
`these areas are more qualitative in nature and lack existing mathematical mod-
`els like those provided by physics.
`This bookis notfilled with recipes for implementing lots of ideas in computer
`graphics; instead, it provides a higher-level view ofthe subject, with the goal of
`teaching you ideas thatwill remain relevant long after particular implementations
`are no longer important. Webelieve that by synthesizing decades of research, we
`can elucidate principles that will help you in your study and use of computer
`graphics. You’ll.generally need to write your own implementations or find them
`elsewhere.
`Thisis not, by any means, because we disparage such information or the books
`that provide it. We admire such work andlearn from it. And we admire those who
`can synthesize it into a coherent and well-presented whole. With this in mind,
`“we strongly recommendthat as you read this book, you keep a copy of Akenine-
`Maller, Haines, and Hoffman’s book on real-time rendering [AMHH08] next to
`you. An alternative, but less good, approachis to take anyparticular topic that
`interests you and search the Internet for information aboutit. The mathematician
`Abelclaimed that he managed to succeed in mathematics because he made a prac-
`tice of reading the works of the masters rather than their students, and we advise
`that you follow his lead. The aforementionedreal-time rendering book is written
`by masters of the subject, while a random web page may be written by anyone.
`
`
`
`

`

`Introduction
`
`
`
`Webelieve that it’s far better, if you want to grab something from the Internet, to
`grab the original paper on the subject.
`Having promised principles, we offer two right away, courtesy of Michael
`Littman:
`
` 4
`
`Vv THE KNOW YOUR PROBLEM PRINCIPLE:
`
`Know whatproblem youare solv-
`
`ing.
`
`Y THE APPROXIMATE THE SOLUTION PRINCIPLE: Approximate the solution,
`not the problem.
`
`Both are good guides for research in general, but for graphics in particular,
`where there are so many widely used approximations that it’s sometimes easy
`to forget what the approximation is approximating, working with the unapproxi-
`mated entity may lead to a far clearer path to a solution to your problem.
`
`1.1.1. The World of Computer Graphics
`
`The academic side of computer graphics is dominated by SIGGRAPH,the Asso-
`ciation for Computing Machinery’s Special Interest Group on Computer Graph-
`ics and Interactive Techniques; the annual SIGGRAPHconference is the premier
`venue for the presentation of new results in computer graphics, as well as a large
`commercial trade show and several colocated conferences in related areas. The
`SIGGRAPH proceedings, published by the ACM,are the most important refer-
`ence works that a practitioner in the field can have. In recent years these have
`been published as an issue of the ACM Transactions on Graphics.
`Computer graphics is also an industry, of course, and it has had an enor-
`mous impact in the areas of film,television, advertising, and games.It has also
`changed the way welookat information in medicine, architecture, industrial pro-
`cess control, network operations, and our day-to-day lives as we see weather maps
`and other information visualizations. Perhaps most significantly, the graphical
`user interfaces (GUIs) on our telephones, computers, automobile dashboards, and
`many homeelectronics devicesare all enabled by computer graphics.
`
`
`
`aearteeettt’
`
`Se
`
`1.1.2 Current and Future Application Areas -
`Computer graphics has rapidly shifted from a novelty to an everyday phenomenon.
`Even throwawaydevices,like the handhelddigital gamesthat parents give to chil-
`dren to keep them occupied on airplane trips, have graphical displays and inter-
`faces. This corresponds to two phenomena: First visual perception is powerful,
`and visual communication is incredibly rapid, so designers of devicesof all kinds
`want to use it, and second, the cost to manufacture computer-based devices is
`decreasing rapidly. (Roy Smith [Smi], discussing in the 1980s various claimsthat
`a GPS unit was so complex that it could never cost less than $1000, said, “Any-
`thing madeof silicon will somedaycostfive dollars.” It’s a good rule of thumb.)
`As graphics has become more prevalent, user expectations have risen. Video
`games display many millions of polygons per second, and special effects in
`films are now so good that
`they’re no longer readily distinguishable from
`
`
`
` ae
`
`

`

`
`
`
`
`
`
`Figure 17.1: An actor, photogra-
`phed in front of a green screen,
`is to be composited into a scene.
`(Jackson
` Lee/Splash
` News/
`Corbis)
`
`. F
`
`igure 17.2: The actor, compos-
`ited atop an outdoor scene. The
`detail shows how the horse’s tail
`obscures part of the background,
`while some background shows
`through.
`(Jackson Lee/Splash
`News/Corbis)
`
`17.4
`
`Image Compositing
`
`485
`
`For programs that manipulate images, the choice of image format is almost
`’ alwaysirrelevant: You almostcertainly want to represent an image as an array of
`double-precision floating-point numbers (or one such array per channel, or per-
`haps a single three-index array where the third index selects the channel). The
`reason to favor floating-point representations is that we often perform operations
`in which adjacent pixel values are averaged; averaging integer or fixed-point val-
`ues, especially whenit’s done repeatedly, may result in unacceptable accumulated
`roundoff errors.
`There are two exceptionsto the “use floating point” rule.
`
`e
`
`e
`
`If the data associated to each pixel is of a type for which averaging makes
`no sense (e.g., an object identifier telling which object is visible at that
`pixel—aso-called object ID channel), then it is better to store the value in
`a form for which arithmetic operations are undefined (such as enumerated
`types), as a preventive measure against silly programmingerrors.
`If the pixel data will be used in a search procedure, then a fixed-point
`representation may make more sense. If, for example, one is going to
`look through the imageforall pixels whose neighborhoods “look like” the
`neighborhoodofa given pixel, integer equality tests may make more sense
`than floating-point equality tests, which must almost always be imple-
`mented as “‘near-equality”tests (i.e., “Is the difference less than some small
`value €?’’).
`
`17.4
`
`Image Compositing
`
`Movie directors often want to film a scene in which actors are in some type of
`interesting situation (e.g., a remote country, a spaceship, an exploding building,
`etc.). In many cases,it’s not practical to have the actors actually be in these situ-
`ations (e.g., for insurance reasonsit’s impossible to arrange for top-paid actors to
`‘stand inside exploding buildings). Hollywood uses a technique called blue screen-
`ing (see Figure 17.1) to address this. With this technique, the actors are recorded in
`a featureless room in which the back wallis of some knowncolor(originally blue,
`now often green; we'll use green in our description). From the resultant digital
`images, any pixel that’s all green is determinedto be part of the background;pix-
`els that have no greenare “actor” pixels and those that are a mix of green and some
`other color are “part actor, part background”pixels. Then the interesting situation
`(e.g., the exploding building) is also recorded. Finally, the image of the actors is
`composited atop the imagesof the interesting situation: Every ‘green pixel in the
`actor imageis replaced bythe color of the situation-image pixel;every nongreen
`pixel remains. And the partially green pixels are replaced by a combination of a
`color extracted from the actor image and the situation image (see Figure 17.2).
`The resultant composite appears toshow the actor in front of the exploding
`building.
`-
`There are some limitations to this approach: The lighting on the actors does
`"Mot come from the lighting in the situation (or it must be carefully choreographed
`to approximateit), and things like shadowspresentreal difficulties. Furthermore,
`‘at the part actor, part backgroundpixels, we have to estimate thecolor that’s to be
`associated to the actors, and the fraction of coverage. Theresultis a foreground
`image and a mask, whosepixel values indicate what fraction of the pixel is cov-
`ered by foreground content: A pixel containing an actor has maskvalue 1; a pixel
`
`
`
`

`

`
`
`
`
`486
`
`Image Representation and Manipulation
`
`_
`
`showing the background has mask value 0, and a pixel at the edge (e.g., in the
`actor’s hair) has some intermediate value.
`In computer graphics, we often perform similar operations: We generate a
`rendering of some scene, and we wantto place other objects (which we also ren-
`der) into the scene after the fact. Porter and Duff [PD84] gave the first published
`description of the details of these operations, but they credit the ideas to prior
`work at the New York Institute of Technology. Fortunately, in computer graphics,
`as we renderthese foreground objects we can usually compute the mask value at
`the same time, rather than having to estimateit; after all, we know the exact geom-
`etry of our object and the virtual camera. The mask value in computer graphics
`is typically denoted bythe letter a so that pixels are represented by a 4-tuple
`(R, G,B, a). Images with pixels of this form are referred to as RGBA images and
`as RGBa images.
`Porter and Duff [PD84] describe a wide collection of image composition oper-
`ations; we'll follow their developmentafterfirst concentrating on the single oper-
`ation described above: If U and V are images, the image “U over V” corresponds
`to “actor over (i.e., in front of) situation.”
`
`17.4.1. The Meaning of a Pixel During Image
`Compositing
`The value a: represents the opacity ofa single pixel of the image. If we regard the
`image as being composed oftiny squares, then @ = 0.75 for some square tells us
`that the square is three-quarters covered by some object(i.e., 3/4 opaque) but 1/4
`uncovered(i.e., 1/4 transparent). Thus, if our rendering is of an object consisting
`of a single pure-red triangle whoseinterior covers three-quarters of some pixel,
`the q-value for that pixel would be 0.75, while the R value would indicate the
`intensity of the red light from the object, and G and B would be zero.
`With a single number, a, we cannotindicate anything more than the opacity;
`we cannot, for instance, indicate whetherit is the left or the right half of the pixel
`that is most covered, or whetherit’s covered in a striped or polka-dotpattern. We
`therefore make the assumption that the coverage is uniformly distributed across
`the pixel: If you picked a point at random in the pixel, the probability that it is
`opaquerather than transparent is a. We makethe further assumption that there is
`no correlation between these probabilities in the two images;that is, ifay = 0.5
`and ay = 0.75,then the probability that a random. point is opaque in both images
`is 0.5 - 0.75 = 0.375,and the probability that it is transparent in both is 0.125.
`Thered, green, and blue values represent the intensity of light that would arise
`from the pixelif it were fully opaque,thatis, if a = 1.
`,
`s
`
`17.4.2 Computing Uover V
`Because compositing is performedone pixel at a time, we can illustrateour com-
`»» putation with a single pixel. Figure 17.3 shows an example in which ay = 0.4
`and ay = 0.3. Thefraction of the image covered by both is 0.4 -0.3 = 0.12,
`while the fraction covered by V butnotUis 0.6 - 0.3 = 0.18.
`To compute U over V, we mustassign both an a-value and a colorto the resul-
`tant pixel. The coverage, a, will be 0.4 + 0.18, representing that all the opaque
`parts of U persist in the composite, as do the parts of V not obscured by U.In
`more generality, we have
`
`
`
`

`

`
`
`
`
`17.4
`
`Image Compositing
`
`487
`
`
`
`(b)
`
`(@)
`
`(a)
`
`Figure 17.3: (a) A pixel from an image U, 40% covered. Properly speaking, the covered
`area should be shown scattered randomly about the pixel square. (b) A pixel from the
`image V, 30% covered. (c) The two pixels, drawn in a single square; the overlap area is
`12% ofthe pixel. (d) The compositing resultfor U over V:All ofthe opaque part of U shows
`(covering 40% of the pixel), and the nonhidden opaque part of V shows (covering 18% of
`the pixel).
`
`-
`
`a=ay+(1—ay)ay = ay + ay — ayay.
`
`(17.1)
`
`
`
`
`
`
`Whataboutthe color of the resultantpixel(i.e., the intensity of red, green, and
`blue light)? Well, the light contributed by the U portionof the pixel(i.e., the frac-
`tion ay containing opaquebits from U)is ay - (Ru, Gy, By), where the subscript
`
`indicates that these are the RGB values from the U pixel. Thelight contributed by
`
`the V part of the pixel is (1 ~ ay)ay - (Ry, Gy, By). Thus, the total lightis
`
`
`
`
`
`: 4.3 Simplifying Compositing
`orter and Duff [PD84] observe that in these equations, the color of U always
`
`ppears multiplied by ay, and similarly for V. Thus,if instead of storing the val-
`
`ues (R, G, B, x) at each pixel, we stored (aR, aG, aB, a), the computations would
`
`mplify. Denoting these by (r, g,b, a) (so that r denotes Ra, for instance), the
`mpositing equations become
`
`
`Where the fraction has disappeared because the new (r,g,b) values must include
`the premultiplied a-value.
`.- The form of these two equations is identical: The data for U are multiplied
`
`by 1, and the data for V are multiplied by (1 — ay). Calling theseFy and Fy,the
`“over” compositing rule becomes
`
`(7,8,b,a) = Fy - (ry, gu, bu, av) + Fy - (rv, gv, by, ay).
`
`(17.4)
`
`
`
`ay - (Ru, Gy, By) + (1 — ay)ay - (Ry, Gy, By),
`
`(17.2)
`
`while the total opacity is a = ay + (1 — ay)ay. If the pixel weretotally opaque,
`the resultant light would be brighter by a factor of a; to avoid this brightness
`change, we mustdivide by a, so the RGB valuesforthe pixel are
`
`ay: (Ru, Gy, By) + (1 — ay)ay - (Ry, Gy, By)
`
`‘ay + (1 _ ay)ay
`
`.
`
`(17.3)
`
`. These compositing equationstell us how to associate an opacity or coverage
`value and a colorto each pixel of the U over V composite.
`
`
`
`a=1-ay+ (1 — ay) - ay and
`(7, g,b) =1- (ru, gu, bu) + (1 — ay) . (rv, gv, by),
`
`
`
`

`

`488
`
`Image Representation and Manipulation
`
`17.4.4 Other Compositing Operations
`
`Porter and Duff define other compositing operations as well; almost all have the
`same form as Equation 17.4, with the values Fy and Fy varying. One can think of
`each pointof the pixel as being in the opaquepart of neither U nor V, the opaque
`part ofjust U,ofjust V, or of both. For each, we can think of taking the color from
`U, from V, or from neither, but to use the color of V on a point where only U is
`opaque seemsnonsensical, and similarly for the points that are transparentin both.
`Writing a quadruple to describe the chosen color, we have choiceslike (0,U,V,U)
`representing U over V and (0, U, V, 0) representing U xor V (i.e., show the part of
`the image that’s in either U or V but not both). Figure 17.4, following Porter and
`Duff, lists the possible operations, the associated quadruples, and the multipliers
`F,4 and Fp associated to each. Thetable in the figure omits symmetric operations
`(i.e., we show U overV, but not V over U).
`Finally, there are other compositing operationsthat do not follow the blending-
`by-Fsrule. One of these is the darken operation, which makes the opaquepart of
`an image darker without changing the coverage:
`
`darken(U,s) = (sry, sgu,sby, au).
`
`(17.5)
`
`Closely related is the dissolve operation, in which the pixel retainsits color, but
`the coverage is gradually reduced:
`
`dissolve(U, s) = (sry, sgu, Sby, sau).
`
`(17.6)
`
`
`
`U
`
`
`
`
`
` (0, U,0,U)
`
`2?
`as
`
`
`
`jvev|ono[RI |
`
`
`
`
`
`
`
`
`
`
`Figure 17.4: Compositing operations, and the multipliers for each, to be used with colors
`premultiplied by a (following Porter and Duff).
`
`oO
`
`

`

`
`
`17.4
`
`Image Compositing
`
`489
`
`
`
`Inline Exercise 17.2: Explain why, in the dissolve operation, we had to multi-
`ply the “rgb”values by s, even though we were merely altering the opacity of
`the pixel.
`
`.
`
`Thedissolve operation can be used to create a transition from one image to
`~. another:
`
`(17.7)
`blend(U,V,s) = dissolve(U,(1 — s)) + dissolve(V, s),
`: where component-by-component addition is indicated by the + sign, and the
`parameter s varies from 0 (a pure-U result) to 1 (a pure-V result).
`
`
`
`
`Inline Exercise 17.3: Explain why, if ay and ay are both between zero
`and one, the resultant a-value will be as well so that the resultant pixel is
`meaningful.
`
`Image operations like these, and their generalizations, are the foundation of
`_image editing programslike Adobe Photoshop [Wik].
`
`
`
`
`
`
`
`
`
`17.4.4.1 Problems with Premultiplied Alpha
`‘Suppose you wrote a compositing program that converted ordinary RGBA images
`
`into premultiplied-a images internally, performed compositing operations, and
`then wrote out the images after conversion back to unpremultiplied-a: images.
`What would happenif someone used your program to operate on an RGBA image
`
`in which the a-values were already premultiplied? In places where a = 0,it
`would makeverylittle difference; the same goes for a = 1. But in partially opaque
`
`places,
`the opacity would be reduced. That would make background objects
`
`show through to the foreground more clearly. In practice,
`this happens fairly
`
`frequently; it’s a tribute to our visual system’s tolerance that it does not tend to
`confound us.
`
`
`17.4.5 Physical Units and Compositing
`We've spoken about blending light “intensity” using a-values. This has really
`
`een a proxy for the idea of blending radiance values (discussed in Chapter 26),
`hich are the values that represent the measurement of light in terms of energy.
`
`If, instead, our pixels’ red values are simply numbers between 0 and 255 that
`€present
`a range from “no red at all” to “as much red as we can represent,”
`
`then combining them with linear operations is meaningless. Worsestill, if they
`
`do not correspond to radiance, but to some powerofradiance(e.g., its square
`
`Toot), then linear combinations definitely produce the wrong results. Nonetheless,
`age composition using pixel values directly, whatever they might mean, was
`
`‘done for many years, onceagain,it’s a testamentto the visual system’s adaptivity
`that we foundthe results so convincing. When people began to compositereal-
`World imagery and computer-generated imagery together, however, some prob-
`
`‘ems became apparent; the industry standard is now to do compositing “in linear
`Space,” that is, representing color values by something that’s a scalar multiple of
`
`@physically meaningful and linearly combinable unit [Rob].
`
`r
`
`
`
`
`
`
`
`
`

`

`490
`
`image Representation and Manipulation
`
`i
`
`As indicated by the description of the PPM imageformat, pixel values in stan-
`dard formats are often nonlinearly related to physical values; we'll encounterthis
`again when we discuss gamma correction in Sectio