VALEO EXHIBIT 1031
`Valeo v. Magna
`IPR2015-____
`(cid:57)(cid:36)(cid:47)(cid:40)(cid:50)(cid:3)(cid:40)(cid:59)(cid:17)(cid:3)(cid:20)(cid:19)(cid:22)(cid:20)(cid:66)(cid:19)(cid:19)(cid:20)
`
`

`

`
`
`Computer Graphics July 1984mVolume 18, Number3
`
`
`
`Compositing Digital Images
`Thomas Porter
`
`Tom Duff 1’
`
`Computer Graphics Project
`Lucasfilm Ltd.
`
`ABSTRACT
`
`1. Introduction
`
`Most computer graphics pictures have been computed all
`at once, so that the rendering program takes care of all
`computations relating to the overlap of objects. There are
`several applications. however, where elements must be
`rendered separately, relying on compositing techniques for
`the anti-aliased accumulation of the full image. This paper
`presents the case for four-channel pictures, demonstrating
`that a matte component can be computed similarly to the
`color channels. The paper discusses guidelines for the
`generation of elements and the arithmetic for their arbi-
`trary compositing.
`
`1.3.3 [Com-
`CR Categories and Subject Descriptors:
`puter Graphics]: Picture/Image Generations ~
`Display algorithms;
`1.3.4
`[Computer Graphics]:
`Graphics Utilities — Software support; 1.4.1 [Image
`Processing]: Digitization — Sampling.
`
`General Terms: Algorithms
`
`compositing, matte
`Additional Key Words and Phrases:
`channel, matte algebra, visible surface algorithms,
`graphics systems
`
`fAuthor’s current address: AT&T Bell Laboratories, Murray Hill, NJ 07974, Room 20465
`
`Permission to copy without fee all or part of this material is granted
`provided that the copies are not made or distributed for direct
`commercial advantage, the ACM copyright notice and the title of the
`publication and its date appear, and notice is given that copying is by
`permission of the Association for Computing Machinery. To copy
`otherwise, or to republish, requires a fee and/or specific permission.
`
`©1984 ACM 0-8979]-138-5/84/007/0253
`
`$00.75
`
`Increasingly, we find that a complex three dimensional
`scene cannot be fully rendered by a single program. The
`wealth of literature on rendering polygons and curved
`surfaces, handling the special cases of fractals and spheres
`and quadrics and triangles, implementing refinements for
`texture mapping and bump mapping, noting speed-ups on
`the basis of coherence or depth complexity in the scene,
`suggests that multiple programs are necessary.
`
`reliance on a single program for rendering an
`In fact,
`entire scene is a poor strategy for minimizing the cost of
`small modeling errors. Experience has taught us to break
`down large bodies of source code into separate modules in
`order to save compilation time. An error in one routine
`forces only the recompilation of its module and the rela-
`tively quick reloading of the entire program. Similarly,
`small errors in coloration or design in one object should
`not force the ”recompilation” of an entire image.
`
`into elements which can be
`Separating the image
`independently rendered saves enormous time. Each ele-
`ment has an associated matte, coverage information
`which designates the shape of the element. The compo-
`siting of those elements makes use of the mattes to accu-
`mulate the final image.
`
`The compositing methodology must not induce aliasing in
`the image; soft edges of the elements must be honored in
`computing the final image. Features should be provided
`to exploit
`the full associativity of the compositing pro-
`cess; this affords flexibility, for example, for the accumu—
`lation of several foreground elements into an aggregate
`foreground which can be examined over different back-
`grounds. The compositor should provide facilities for
`arbitrary dissolves and fades of elements during an
`animated sequence.
`
`rendering algorithms have
`Several highly successful
`worked by reducing their environments to pieces that can
`be combined in a 2 1/2 dimensional manner, and then
`overlaying them either front-to—back or back-to-front [3].
`Whitted and Weimar's graphics test-bed [6] and Crow’s
`image generation environment
`[2] are both designed to
`deal with heterogenously rendered elements. Whitted
`
`253
`
`(cid:57)(cid:36)(cid:47)(cid:40)(cid:50)(cid:3)(cid:40)(cid:59)(cid:17)(cid:3)(cid:20)(cid:19)(cid:22)(cid:20)(cid:66)(cid:19)(cid:19)(cid:21)
`VALEO EX. 1031_002
`
`

`

`.SIGGRAPH’84a
`
`
`
`and Weimar’s system reduces all objects to horizontal
`spans which are composited using a Warnock—like algo-
`rithm.
`In Crow’s system a supervisory process decides
`the order in which to combine images created by indepen-
`dent special—purpose rendering processes. The imaging
`system of Warnock and Wyatt
`[5]
`incorporates 1-bit
`mattes. The Hanna-Barbera cartoon animation system
`[4] incorporates soft-edge mattes, representing the opacity
`information in a less convenient manner than that pro-
`posed here. The present paper presents guidelines for
`rendering elements and introduces the algebra for compo-
`siting.
`
`2. The Alpha Channel
`A separate component
`is needed to retain the matte
`information,
`the extent of coverage of an element at a
`pixel.
`In a full color rendering of an element, the RGB
`components retain only the color.
`In order to place the
`element over an arbitrary background, a mixing factor is
`required at every pixel to control the linear interpolation
`of foreground and background colors.
`In general, there is
`no way to encode this component as part of the color
`information. For anti—aliasing purposes, this mixing fac-
`tor needs to be of comparable resolution to the color
`channels. Let us call this an alpha channel, and let us
`treat an alpha of 0 to indicate no coverage, 1 to mean full
`coverage, with fractions corresponding to partial cover-
`age.
`
`In an environment where the compositing of elements is
`required, we see the need for an alpha channel as an
`integral part of all pictures. Because mattes are naturally
`computed along with the picture, a separate alpha com-
`ponent
`in the frame buffer
`is appropriate. Off-line
`storage of alpha information along with color works con-
`veniently into run-length encoding schemes because the
`alpha information tends to abide by the same runs.
`
`What is the meaning of the quadruple (r,g,b,a) at a pixel?
`How do we express that a pixel is half covered by a full
`red object? One obvious suggestion is to assign (l,0,0,.5)
`to that pixel: the .5 indicates the coverage and the (1,0,0)
`is the color. There are a few reasons to dismiss this pro-
`posal, the most severe being that all compositing opera-
`tions will involve multiplying the l in the red channel by
`the .5 in the alpha channel to compute the red contribu-
`tion of this object at this pixel. The desire to avoid this
`multiplication points up a better solution, storing the
`pre-multipIied value in the color component,
`so that
`(.5,0,0,.5) will indicate a full red object half covering a
`pixel.
`
`is a
`the pixel
`indicates that
`The quadruple (r,g,b,a)
`covered by the color (r/a, g/a, b/a). A quadruple where
`the alpha component is less than a color component indi-
`cates a color outside the [0,1] interval, which is somewhat
`unusual. We will see later that luminescent objects can be
`usefully represented in this way. For the representation
`of normal objects, an alpha of 0 at a pixel generally
`forces the color components to be 0. Thus the RGB
`channels. record the true colors where alpha is l, linearly
`
`254
`
`darkened colors for fractional alphas along edges, and
`black where alpha is 0. Silhouette edges of RGBA ele-
`ments thus exhibit their anti—aliased nature when viewed
`on an RGB monitor.
`
`to distinguish between two key pixel
`
`important
`is
`It
`representations:
`black = (0,0,0,l);
`clear = (0,0,0,0).
`The former pixel is an opaque black; the latter pixel is
`transparent.
`
`3. RGBA Pictures
`
`If we survey the variety of elements which contribute to a
`complex animation, we find many complete background
`images which have an alpha of 1 everywhere. Among
`foreground elements, we find that the color components
`roll off in step with the alpha channel, leaving large areas
`of transparency. Mattes, colorless stencils used for con-
`trolling the compositing of other elements, have 0 in their
`RGB components. Off-line storage of RGBA pictures
`should therefore provide the natural data compression for
`handling the RGB pixels of backgrounds, RGBA pixels of
`foregrounds, and A pixels of mattes.
`
`to computing with these
`There are some objections
`RGBA pictures. Storage of the color components pre
`multiplied by the alpha would seem to unduly quantize
`the color resolution, especially as alpha approaches 0.
`However, because any compositing of the picture will
`require that multiplication anyway, storage of the pro-
`duct forces only a very minor loss of precision in this
`regard. Color extraction, to compute in a different color
`space for example, becomes more difficult. We must
`recover
`(r/a, g/a, b/a),
`and once again,
`as alpha
`approaches 0,
`the precision falls ofl sharply. For our
`applications, this has yet to affect us.
`
`4. The Algebra of Compositing
`let us examine
`Given this standard of RGBA pictures,
`how compositing works. We shall do this by enumerating
`the complete set of binary compositing operations. For
`each of these, we shall present a formula for computing
`the contribution of each of two input pictures to the out-
`put composite at each pixel. We shall pay particular
`attention to the output pixels,
`to see that they remain
`pre—multiplied by their alpha.
`
`4. 1 . Assumptions
`
`When blending pictures together, we do not have infor-
`mation about overlap of coverage information within a
`pixel; all we have is an alpha value. When we consider
`the mixing of two pictures at a pixel, we must make some
`assumption about the interplay of the two alpha values
`In order to examine that interplay,
`let us first consider
`the overlap of two semi-transparent elements like haze,
`then consider the overlap of two opaque, hard-edged ele-
`ments.
`
`(cid:57)(cid:36)(cid:47)(cid:40)(cid:50)(cid:3)(cid:40)(cid:59)(cid:17)(cid:3)(cid:20)(cid:19)(cid:22)(cid:20)(cid:66)(cid:19)(cid:19)(cid:22)
`VALEO EX. 1031_003
`
`

`

`Computer GraphicsM
`July 1984
`Volume 18, Number 3
`
`semi-
`the opaqueness of
`(IE represent
`and
`(14
`If
`transparent objects which fully cover the pixel, the com-
`putation is well known. Each object
`lets (l—a) of the
`background through,
`so that
`the background shows
`through only (l—aA)(l~aB) of the pixel.
`01A(1—OB) of the
`background is blocked by object A and passed by object
`B;
`(l—aA)a3 of
`the background is passed by A and
`blocked by B. This leaves 01,103 of the pixel which we
`can consider to be blocked by both.
`
`If (1A and 03 represent subpixel areas covered by opaque
`geometric objects, the overlap of objects within the pixel
`is quite arbitrary. We know that object A divides the
`pixel into two subpixel areas of ratio aAzl—aA. We know
`that object B divides the pixel into two subpixel areas of
`ratio agzl—aB. Lacking further information, we make the
`following assumption:
`there is nothing special about the
`shape of the pixel; we expect that object B will divide each
`of the subpixel areas inside and outside of object A into
`the same ratio agzl—aB. The result of the assumption is
`the same arithmetic as with semi-transparent objects and
`is summarized in the following table:
`
`
`
`The assumption is quite good for most mattes, though it
`can be improved if we know that the coverage seldom
`overlaps (adjacent segments of a continuous line) or
`always overlaps (repeated application of a picture). For
`ease in presentation throughout this paper,
`let us make
`this
`assumption and consider
`the
`alpha values
`as
`representing subpixel coverage of opaque objects.
`
`4.2. Compositing Operators
`
`Consider two pictures-A and B. They divide each pixel
`into the 4 subpixel areas
`
`EI-lm__'-*
`
`listed in this table along with the choices in each area for
`contributing to the composite. In the last area, for exam-
`ple, because both input pictures exist there, either could
`survive to the composite. Alternatively,
`the composite
`could be clear in that area.
`
`be
`can
`compositing operation
`A particular binary
`identified as a quadruple indicating the input picture
`which contributes to the composite in each of the four
`subpixel areas 0, A, B, AB of the table above. With
`three choices where the pictures intersect, two where only
`one picture exists and one outside the two pictures, there
`are 3X2X2Xl=12 distinct compositing operations listed
`
`in the table below. Note that pictures A and B are
`diagrammed as covering the pixel with triangular wedges
`whose overlap conforms to the assumption above.
`
`(D’A’B’B)
`
`I
`
`A in B
`
`(0,0,0,A)
`
`
`
`B atop A w.
`
`(O’A,B’0)
`
`Useful operators include A over B, A in B, and A held
`out by B. A over B is the placement of foreground A in
`front of background B. A in B refers only to that part of
`A inside picture B. A held out by B, normally shor-
`tened to A out B, refers only to that part of A outside
`picture B. For completeness, we include the less useful
`operators A atop B and A xor B. A atop B is the union
`of A in B and Bout A. Thus, paper atop table includes
`paper where it is on top of table, and table otherwise; area
`beyond the edge of
`the table is out of
`the picture.
`A xor B is the union of A out B and B out A.
`
`255
`
`(cid:57)(cid:36)(cid:47)(cid:40)(cid:50)(cid:3)(cid:40)(cid:59)(cid:17)(cid:3)(cid:20)(cid:19)(cid:22)(cid:20)(cid:66)(cid:19)(cid:19)(cid:23)
`VALEO EX. 1031_004
`
`

`

` //// .SIGGRAPH’84
`
`4.3. Compositing Arithmetic
`
`4.4. Unary operators
`
`For each of the compositing operations, we would like to
`compute the contribution of each input picture at each
`pixel. This is quite easily solved by recognizing that each
`input picture survives in the composite pixel only within
`its own matte. For each input picture, we are looking for
`that fraction of its own matte which prevails in the out-
`put. By definition then, the alpha value of the composite,
`the total area of the pixel covered, can be computed by
`adding 01A times its fraction FA to 013 times its fraction
`FB-
`
`The color of the composite can be computed on a com-
`ponent basis by adding the color of the picture A times
`its fraction to the color of picture B times its fraction.
`To see this, let cA, CB, and c0 be some color component
`of pictures A, B and the composite, and let CA, CB, and
`00 be the true color component before pre—multiplication
`by alpha. Then we have
`
`60 = 0000
`
`Now 00 can be computed by averaging contributions
`made by CA and 03, so
`
`6 _ a aAFACA+aBFBCB
`O
`O
`OAFA‘l'aBFB
`
`but the denominator is just 010, so
`
`Co = aAFAoA—l'aBFBCB
`CA
`CE
`= a F — a F —-
`A AaA'l' B 803
`
`= CAFA‘l‘cBFB
`
`(1)
`
`Because each of the input colors is pre—multiplied by its
`alpha,
`and we are adding contributions
`from non-
`overlapping areas,
`the sum will be
`effectively pre
`multiplied by the alpha value of the composite just com—
`puted. The pleasant result that the color channels are
`handled with the same computation as alpha can be
`traced back to our decision to store pre—multiplied RGBA
`quadruples. Thus the problem is reduced to finding a.
`table of fractions FA and FB which indicate the extent of
`contribution of A and B, plugging these values into equa-
`tion 1 for both the color and the alpha components.
`
`the fractions are quickly
`By our assumptions above,
`determined by examining the pixel diagram included in
`the table of operations. Those fractions are listed in the
`FA and FB columns of the table. For example,
`in the
`A over B case, picture A survives everywhere while pic-
`ture B survives only outside picture A, so the correspond-
`ing fractions are 1 and (1—0:A). Substituting into equa-
`tion 1, we find
`
`60 = cAXl+c3X(l—aA).
`
`This is almost the well used linear interpolation of fore-
`ground F with background B
`
`B’ = FXa+BX(l~a),
`
`except that our foreground is pre—multiplied by alpha.
`
`256
`
`To assist us in dissolving and in balancing color bright-
`ness of elements contributing to a composite, it is useful
`to introduce a darken factor 9*) and a dissolve factor 6:
`darken(A,¢)E(¢rA,¢gA,¢bA,aA)
`‘ dissolve(A,6).=_(6rA,6gA,6bA,6aA) .
`Normally, 03¢,6_<_1 although none of the theory requires
`it.
`
`As ¢ varies from 1 to 0, the element will change from
`normal to complete blackness.
`If (it)! the element will
`be brightened. As 6 goes from 1 to 0 the element will
`gradually fade from view.
`
`information
`color
`add
`objects, which
`Luminescent
`without obscuring the background, can be handled with
`the introduction of a opaqueness factor a), OSwS l:
`Opaque(Avw)E(rAugAabAawaA) '
`As w varies from 1 to 0, the element will change from
`normal coverage over the background to no obscuration.
`This scaling of the alpha channel alone will cause pixel
`quadruples where a is less than a color component, indi-
`cating a representation of a color outside of the normal
`range. This possibility forces us to clip the output compo-
`site to the [0,1] range.
`
`An w of 0 will produce quadruples (r,g,b,0) which do have
`meaning. The color channels, pre-multiplied by the origi-
`nal alpha, can be plugged into equation 1 as always. The
`alpha channel of 0 indicates that this pixel will obscure
`nothing.
`In terms of our methodology for examining sub-
`pixel areas, we should understand that using the opaque
`operator corresponds to shrinking the matte coverage
`with regard to the color coverage.
`
`4.5. The PLUS operator
`We find it useful to include one further binary composit-
`ing operator plus. The expression A plus B holds no
`notion of precedence in any area covered by both pic-
`tures; the components are simply added. This allows us
`to dissolve from one picture to another by specifying
`
`dissolve(A,a) plus dissolve(B,l—a).
`
`allows
`In terms of the binary operators above, plus
`both pictures to survive in the subpixel area AB. The
`operator table above should be appended:
`
`
`
`(cid:57)(cid:36)(cid:47)(cid:40)(cid:50)(cid:3)(cid:40)(cid:59)(cid:17)(cid:3)(cid:20)(cid:19)(cid:22)(cid:20)(cid:66)(cid:19)(cid:19)(cid:24)
`VALEO EX. 1031_005
`
`

`

`
`
`Computer Graphics July 1984MVolume 18, Number 3
`
`
`
`5. Examples
`The operations on one and two pictures are presented as
`a basis for handling compositing expressions involving
`several pictures. A normal case involving three pictures
`is the compositing of a foreground picture A over a back-
`ground picture B, with regard to an independent matte
`C. The expression for this compositing operation is
`
`(A in C’) over B.
`
`Using equation 1 twice, we find that the composite in this
`case is computed at each pixel by
`
`CO = cAag+cB(l—aAaC).
`
`Point Reyes [1]. This still frame was assembled from
`many elements according to the following rules:
`
`Foreground = FrgdGrass over Rock over Fence
`over Shadow over BkgdGrass;
`
`GlossyRoad 2 Puddle over (PostReflection atop
`(PlantReflection atop Road”;
`Hillside = Plant over GlossyRoad over Hill;
`
`Background = Rainbow plus Darkbow over
`Mountains over 5km
`PLReyes = Foreground over Hillside over Background.
`
`As an example of a complex compositing expression, let
`us consider a subwindow of Rob Cook‘s picture Road to
`
`Figure 1 shows three intermediate composites and the
`final picture.
`
`Foreground = FrgdGrass over Rock over Fence
`over Shadow over BkgdG'rass;
`
`
`
`
`
`Hillside = Plant over GlossyRoad over Hill;
`
`Background = Rainbow plus Darkbow over
`Mountains over Sky,
`
`PLReyes = Foreground over Hillside over Background.
`
`Figure 1
`
`257
`
`(cid:57)(cid:36)(cid:47)(cid:40)(cid:50)(cid:3)(cid:40)(cid:59)(cid:17)(cid:3)(cid:20)(cid:19)(cid:22)(cid:20)(cid:66)(cid:19)(cid:19)(cid:25)
`VALEO EX. 1031_006
`
`

`

` //// .SIGGRAPH’84
`
`W
`Eat-ms
`
`P13 [1 m.
`
`
`
` FFiro
`
`
`BMW out Planet
`
`(,umpnmto
`
`Figure 2
`
`258
`
`(cid:57)(cid:36)(cid:47)(cid:40)(cid:50)(cid:3)(cid:40)(cid:59)(cid:17)(cid:3)(cid:20)(cid:19)(cid:22)(cid:20)(cid:66)(cid:19)(cid:19)(cid:26)
`VALEO EX. 1031_007
`
`

`

`
`
`Computer Graphics July 1984WVolume 18, Number3
`
`
`
`A further example demonstrates the problem of corre-
`lated mattes.
`In Figure 2, we have a star field back-
`ground, a planet element,
`fiery particles behind the
`planet, and fiery particles in front of the planet. We wish
`to add the luminous fires, obscure the planet, darkened
`for proper balance, with the aggregate fire matte, and
`place that over the star field. An expression for this com-
`positing is
`
`(FFire plus (BFire out Planet))
`over darken(Planet,.8) over Stars .
`
`We must remember that our basic assumption about the
`division of subpixel areas by geometric objects breaks
`down in the face of input pictures with correlated mattes.
`When one picture appears twice in a compositing expres-
`sion, we must take care with our computations of FA and
`F8- Those listed in the table are correct only for uncorre-
`lated pictures.
`
`To solve the problem of correlated mattes, we must
`extend our methodology to handle 11 pictures: we must
`examine all 2" subareas of the pixel, deciding which of
`the pictures survives in each area, and adding up all con-
`tributions. Multiple instances of a single picture or pic-
`tures with correlated mattes are resolved by aligning their
`pixel coverage. Example 2 can be computed by building
`a table of survivors (shown below)
`to accumulate the
`extent to which each input picture survives in the compo-
`site.
`
`FFire
`
`Stars
`Planet
`Planet
`BFire
`BFire
`Plan et
`Planet
`FF ire
`FFire
`FFire
`FFire
`FFire,BFire
`FFire,BFire
`FFire
`
`6. Conclusion
`
`We have pointed out the need for matte channels in syn-
`thetic pictures, suggesting that
`frame buffer hardware
`should offer this facility. We have seen the convenience
`of the RGBA scheme for integrating the matte channel. A
`language of operators has been presented for conveying a
`full range of compositing expressions. We have discussed
`a methodology for deciding compositing questions at the
`subpixel level, deriving a simple equation for handling all
`composites of two pictures. The methodology is extended
`to multiple pictures, and the language is embellished to
`handle darkening, attenuation, and opaqueness.
`
`There are several problems to be resolved in related
`areas, which are open for
`future research. We are
`interested in methods for breaking arbitrary three dimen-
`sional scenes into elements separated in depth. Such ele—
`ments are equivalent to clusters, which have been a sub-
`ject of discussion since the earliest attempts at hidden
`surface elimination. We are interested in applying the
`compositing notions to Z-bufler algorithms, where depth
`information is retained at each pixel.
`
`7. References
`
`1.
`
`2.
`
`Cook, R. Road to Point Reyes. Computer Graphics
`Vol 17, N0. 3 (1983), Title Page Picture.
`Crow, F. C. A More Flexible Image Generation
`Environment. Computer Graphics Vol. 16, No. 3
`(1982), pp. 9-18.
`3. Newell, M. G., Newell, R. G., and Sancha, T. L.. A
`Solution to the Hidden Surface Problem, pp. 443-
`448. Proceedings of the 1972 ACM National Confer-
`ence.
`
`4. Wallace, Bruce. Merging and Transformation of
`Raster
`Images for Cartoon Animation. Computer
`Graphics Vol. 15, No. 3 (1981), pp. 253-262.
`5. Warnock,
`John, and Wyatt, Douglas. A Device
`Independent Graphics Imaging Model for Use with
`Raster Devices. Computer Graphics Vol. 16, No. 3
`(1982), pp. 313319.
`6. Whitted, Turner, and Weimer, David. A Software
`Test-Bed for the Development of 3D Raster Graph-
`ics Systems. Computer Graphics Vol. 15, No. 3
`(1981), pp. 271-277.
`
`8. Acknowledgments
`The use of mattes to control the compositing of pictures
`is not new. The graphics group at the New York Insti-
`tute of Technology has been using this for years. NYIT
`color maps were designed to encode both color and matte
`information; that idea was extended in the Ampex AVA
`system for storing mattes with pictures. Credit should be
`given to Ed Catmull, Alvy Ray Smith, and Ikonas Graph-
`ics Systems for the existence of an alpha channel as an
`integral part of a frame buffer, which has paved the way
`for the developments presented in this paper.
`
`The graphics group at Lucasfilm should be credited with
`providing a fine test bed for working out
`these ideas.
`Furthermore, certain ideas incorporated as part of this
`work have their origins as idle comments within this
`group. Thanks are also given to Rodney Stock for com-
`ments on an early draft which forced the authors to clar-
`ify the major assumptions.
`
`259
`
`(cid:57)(cid:36)(cid:47)(cid:40)(cid:50)(cid:3)(cid:40)(cid:59)(cid:17)(cid:3)(cid:20)(cid:19)(cid:22)(cid:20)(cid:66)(cid:19)(cid:19)(cid:27)
`VALEO EX. 1031_008
`
`