EXHIBIT 1003
`
`EXHIBIT 1003
`
`

`

`SECOND EDITION
`
`1 Computer Graphics
`
`
`
`/
`
`CHRIS
`
`32b-0772
`
`2m #36“:
`
`
`
`
`
`
`PRINCIPLES AND PRACTICE
`
`Intel Exhibit 1003 Page 1
`
`

`

`SECOND EDITION
`
`PRINCIPLES AND PRACTICE
`
`James D. Foley
`The George Washington University
`
`Andries van Dam
`Brown University
`
`Steven K. Feiner
`Columbia University
`
`John F. Hughes
`Brown University
`
`Computer Graphics
`
`Sydney ¢ Singapore 9 Tokyo 0 Madrid ’ San Juan
`
`YAY
`
`ADDISONJNESLEY PUBLISHING COMPANY
`Reading, Massachusetts ¢ Mcnlo Park, California * New York
`Den Mills, Ontario 0 Wokingham, England ' Amsterdam 0 Bonn
`
`Intel Exhibit 1003 Page 2
`
`

`

` 34D
`Object Hierarchy and Simple PHIGS (SPHIGSJ
`
`7.13 OPTIMIZING DISPLAY OF HIERARCHICAL MODELS
`
`7.13.1
`
`Elision
`
`We can model a building as a parts hierarchy by saying that it consists of hours, the linen,-
`consist of oiliccs. and so on: there are no primitives in the hierarchy‘s nodes until we get In
`the level of bricks. planks, and concrete slabs that consist ol‘ polyhedra. Although this
`representation might be useful for construction purposes.
`it is not as useful for chaplay,
`when: we sometimes wish to see a cruder. simplilicd picture that eliminates confusing and
`unneeded details (and that is faster to reader). The term etr‘st‘tm refers to the decision by a
`display lravcrser to refrain from descending into a substructure.
`
`In Section 7.l2.l, we showed how a display traverser can avoid executing a
`Pruning.
`subordinate structure by checking its NPC extent against
`the vicwport,
`to dcterminc
`whether the substructure lies wholly outside (Le. . is fully clipped by) the view volume. This
`type of elision. a typical feature ol‘ optimized display traverscrs. is called priming.
`Culling.
`In addition, a traverscr can examine tlte size of the sulinrdinate‘s NPC extent,
`and can choose to clide the substructure if that substructure’s extent is so small that, after
`transformation and projection,
`the image of the object would be compressed into a few
`pixels. This type of clision is called calling; on systems that support it.
`the application
`typically can specify a minimum extent size, below which a substructure is culled.
`When a substructure is pruned.
`it
`is not drawn at all; however, that is not the best
`approach for culling. The object is being culled‘P-not because it is invisible from the current
`point of view, but because its image is too tiny for its details to be discernible. Ratherthan
`not draw it at all, most
`implementations draw it as an abstract
`form,
`typically a
`parallelipiped representing its WC extent, or simply a rectangle (the 2D projection of its
`NPC extent).
`
`Lerol-ol—detail clision. Printing and calling are optimization techniques, preventing
`traversal that is unnecessary (pruning) or that would produce an unusable image (culling).
`Elision can also be used to give the user control over the amount of detail presented in a
`view of the CSS. For example, a user examining our building model could specify a low
`level ol‘ detail in order to view the building as simply a set of parallelepipeds representing
`the individual floors. or could increase the level of detail so as to see in addition the “flll5
`that form otlicc boundaries.
`.
`'l'ltc MIDAS microprocessor architecture simulator [GURW8 I] was one of the earlicSl
`systems in which alternate representations of subohjects were traversed automatically by the
`display processor. depending on the size of the projection of the subobject on the screen-
`This logical—zoom l‘acility made successively more detail appear as the user dynamicalli'
`zoomed in on the processor block in the CPU architecture block diagram. Also, at
`increased zoom factors. one could see digits representing address, data, and control 113135
`moving I'rom source to destination over system buses during the simulation Ol
`ll“:
`instruction cycle.
`_
`lilision in MIDAS was implemented using a eonditional—csecution facility of the BUGS
`vector-graphics system [VAND74]: The hierarchical display list
`included a condiliflnz'l
`substructure execution element that tested the screen extent of the substructure. A sinulflr
`
`
`
`
`
`Intel Exhibit 1003 Page 3
`
`-z
`
`
`1:me:cmn'.x._\_‘x'-_:l-‘Wi‘i'
`
`
`
`'xinn-h:
`m:
`
`

`

`7,14
`
`Limitations of Hierarchal Modeling in PHIGS
`
`341
`
`feature described in the 1988 specification of l’lllGS+ in the form of a conditional-
`execution clement. allowing pruning attd calling to be pcrt'ormed explicitly by elements
`within the CSS.
`
`
`
`
`
`
`
`
`..
`
`
`'3
`
`I-
`:'
`
`
`.
`
`
`I
`
`
`
`
`
`
`
`
`.
`
`7.13.2 Structure Referral
`Certain implementations of PHIGS and l’i-iIGS-i- allow a nonstandard form of structure
`.
`.
`.
`.
`.
`cxecuttott, called referral.
`that bypasses the expenstve state savtng and restoring of
`the
`t. Whereas we could argue that a better. transparent approach
`ExecuteStructurc mechanisn
`utentation of the iixectiteStrueture operation
`to increasing efficiency is to optimize the imple
`itseit' (so that the operation saves only as much state as required at any given time), it
`is
`simpler to add a ReferStrueturc operation and to let the programmer use it for those cases
`where an invoked citiid structure does ttot have any attribute—setting elements.
`A second use of ReferStructure is to allow a child to inliucrtee its parents‘ attributes.
`This is useful when a group of objects do not have a common parent, but do need to
`"inherit" the same group of attributes,
`including potentially an arbitrary number of
`modeling transformations.
`In this also, we can create a structure A that consisLs of
`transformation and appearance attribttte settings. anti then have each of the object structures
`refer to structure A. By editing structure A later. we indirectly affect all structures referring
`to A. if only appearance attributes need to be afl'ectcd. Pl [168 attribute bundles provide an
`alternative, standard mechanism for changing the appearance of diverse structures.
`
`7.14 LIMITATIONS 0F HiERAHCijJCAL MODELING 1N PHIGS
`Although this chapter has emphasized geometric modeling hierarchy,
`it is important to
`realize that hierarchy is only one ot‘ many forms of data representation. in this section, we
`discuss the limitations of hierarchy in general and in PHIGS in particular; in the next
`section, we present some alternatives to structure hierarchy.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`-
`'!
`=
`.-
`
`
`
`
`
`
`
`
`
`7.14.1 Limitations of Simple Hierarchy
`some applications have no real structure for their data
`As mentioned in Section 1.7.2,
`(cg. data for scatter plots), or have at most a (partial) ordering in their data (e.g.. a
`function represented algebraically). Many other applications are tnore naturally expressed
`its networks—that is, as general (directed) graphs (which may have hierarchial subnets).
`Among these are circuit and electrical-wiring diagrams. transportation anti ctmnnunica-
`lions networks,
`and citenticai-plattt—pipiug diagrams. Another example of simple
`hierarchy’s insufficiency for certain types of models is Rubik's cube, a collection of
`Components in which the network and any hierarchy (say of layers, rows, anti columns] is
`fundamentally altered after any transformation.
`hy does not suiiice. For example, the pelt
`For other types of models, a single hierarc
`’ to. both the horizontal anti
`holder on an (.r, y) plotter is moved by, and therefore "belungs’
`vertical arms. In short, whether the application model exhibits pure hierarchy, pure network
`Without hierarchy. hierarchy in a network with cross-links. or multiple hierarchies. SPHIGS
`can he used to display it, bttt we may not want. or be able, to use structure hierarchy in its
`full generality.
`
`
`
`
`_
`
`
`Intel Exhibit 1003 Page 4
`
`

`

`Parametric Bicubic Surfaces
`
`521
`
`44
`
`Fig. 11.42 Sixteen control points for a Bézier bieebic patch.
`
`Entries marked with a dash can have any value. if four patches joined at a common corner
`and along the edges emanating from that corner are to have GI continuity,
`then the
`relationships are more coinplcs; see Exercise 11.25.
`
`1 1 .3.2 Bézier Surfaces
`
`The Bézier hieubic formulation can be derived in exactly the same way as the Hermite
`cubic. The results are
`1!;
`
`
`
`.t'(.s', I)
`
`S - M” - Ge, - M11;
`
`-
`
`'1”,
`
`3‘1"" I) ‘ 5 ' Mn ' Gs, ' 1" ii
`
`' Tr.
`
`“1.86)
`
`3“" r)
`
`5 ‘ Mn ' Git.
`
`' Mira ' H",
`
`l 1.42.
`The Béeier geometry matrix G consists of IO control points, as shown in Fig.
`Bézicr surfaces are attractive in interactive design for the saute reason as Bézier curves are:
`Some of the control points interpolate the surface. giving convenient precise cott-
`trol. who 'as tangent vectors also can be controlled explicitly. When Béziet‘ surfaces are
`“59d as an internal representation.
`their convex-hull property and easy subdivision are
`attractive.
`
`CrI and G“ continuity across patch edges is created by making the four common control
`Points equal. Ci continuity occurs when the two sets of four control points on either side of
`the Edge are collinear with the points on the edge. In Fig. H.513, the tollowing sets of
`Control points are collinear and define {our liiie segments whose lengths all have the same
`111110 k: (Plii- p”. [115)! (1):“ P“. P35). (1),?" PM, [135); and (I’m. 1”“. Pg}.
`in
`An allerrlative way to maintain interpalch continuity, described in more detail
`EFAUX'J”); BlEZI70i, requires that, at each corner of an edge across which continuity is
`tiesired. the corner control points and the control points immediately adjacent. to the corner
`be Coplanar.
`
`Intel Exhibit 1003 Page 5
`
`

`

` Representing Curves and Surfaces
`
` 11.3.3 B-Spline Surfaces
`
` B-splinc patches are represented as
`
`- Gm, - Mm'r - T1",
`
`
`
`
`you n = s - MRS - Gm! - Mini" - TT.
`:(s, r) : S - Mm - Gm; ‘ MMT - T11
`
`
`tics.
`
`C’2 conlinuity across boundaries is automatic with B~splincs; no spcciul arrungcmcnls of
`control points arc nccdcd cxccpt lo avoid duplicate control poims. which crcutc discontinui-
`
`'3."
`
`.r(s, r) = S ' Mm.
`
` 522
` Fig. 11.43 Two Bézier patches joined along the edge P”. Pm, PM, and P“.
`
`
`
`(11.87)
`
`Bicubic nonuniform and rational B-splinc surfuccs and other rational surfaces an:
`similarly unalogouu lo lhcir cubic counterparts. All
`thc lcchniqucs for subdivision and
`display curry ovcr (lircctly t0 the hicuhic case.
`
`11.3.4 Normals to Surfaces
`
`[or performing
`[(1).
`to :1 hicuhic surface. nccilcd for shading (Chaplcr
`Thc normal
`inlcrl‘crcncc dclcclion in robotics.
`for calculating nll‘scis
`for numcrically controlled
`machining, and for doing olhcr calculations. is easy to lind. From Eq. (I 1.75), the .s' lamgcfll
`vector of the surfucc le, r) is
`
`3
`.
`'
`..
`gguni = Ej—rLS-flvf-(i-111’“qu :fiiSl‘M-G-fi-f' -TT
`
`= |3.~‘-’
`
`25
`
`1
`
`0|
`
`- M - G - M“ - "1"".
`
`“1.88)
`
`Intel Exhibit 1003 Page 6
`
`

`

` Algorithms for Visible-line Determination
`
`/l\
`
`Room 1 Room 2
`
`Floom 3
`
`665
`
`
`
`
`
`
`
`
`Building
`
`A
`
`Fioort Floor2 Floor3 Floors
`
`restrict the number of object comparisons
`Fig. 15.18 Hierarchy can be used to building and floor 1 does it need to be tested
`needed. Only if a projector intersects the
`for intersection with rooms 1 through 3.
`
`. subdivision may stop when there are lea-er than
`fulfilled for each partition. For example
`artilion ['thMéiZl. The qoadlree, octree, and
`some maximum number of objects in a p
`nlarly attractive for this purpose.
`ESP-tree data structures of Section [2,6 are partic
`
`15.2.6 Hierarchy
`
`hierarchies can be useful for relating the structure and motion ol‘
`As WC saw in Chapter 7.
`different objects. A nested hierarchical model, in which each child is considered part of its
`parent, can also be used to restrict
`the number of object comparisons needed by a
`visible—surface algorithm {CLARK}; RUBISO; WE(illS4]. An object on one level of the
`hierarchy can serve as an extent for its children if they are entirely contained within it, as
`shown in Fig. lilS. In this case.
`it'ii‘t'o objects in the hierarchy fail to intersect. the
`lower-level objects of one do not need to be tested for intersection with those of the other.
`Similarly. onlyr if a projector is found to penetrate an object in the hierarchy must
`it be
`ainst the object‘s children. This use of hierarchy is an important instance of object
`tested ag
`construction of hierarchies is discussed in Section
`coherence. A way to automate the
`1.5.10.2.
`
`15.3 ALGORITHMS FOR VlSlBLE-LINE DETERMINATION
`general techniques, we introduce some visible—line
`Now that we have discussed a number of
`miques are used.
`\‘e begin with
`and visiblersurlhcc algorithms to see how these tecl
`visible-line algorithms. The algorithms presented here all operate in object precision and
`produce as output a list of visible line segments suitable for vector display. The
`Visible-surface algorithms discussed later can also he used for visible-line determination by
`rendering each surface as a backgrounil—colored interior surrounded by a border of the
`desired line color: most visible—surface algorithms produce an image-precision array of
`pls‘els, however. rather than an object-precision list of edges.
`
`15.3.1 Roberta's Algorithm
`It requires that
`was developed by Roberts [ROBEM].
`The earliest visible—line algorithm
`First, back—lace calling is used to
`each edge be part of the face of a convex polyhedron.
`lg polygons. Next. each
`remove all edges shared by a pair of a polyhedron‘s hack-tacit
`remaining edge is compared with each polyhedron that might obscure it. Many polyhedra
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`F.||‘_'_'L14MIWM
`
`
`Intel Exhibit 1003 Page 7
`
`

`

`
`
`16.13
`
`Radiosity Methods
`
`799
`
`
`
`
`
`xiii-.5:"i3":"..
`
`.:_|'._-.5,-4.;
`
`s
`
`We cart approximate Fr}: _J for any patchj by summing the values of of; associated with
`each cell p in Al's hcmieuhe projections. (Note that the values of Ali, for all the hetnicube's
`cells stun to 1.) Assuming that the distance between the patches is large relative to the size
`of the patches, these values for I},_J- may be used as the values of [4,),- in Eq. “6.62) to
`compute the patch radiosities. Color Plate Ill.2|(a-b) was made with the hemicube
`algorithm. Because much of the computation performed using tlte hemicube involves
`computing item bullets, it can take advantage of existing z—butl'cr hardware. On the other
`hand, hecause it uses image-precision operations. the hemicube is prone to aliasing.
`_
`Nisltita and Nakarnae [NISHBfia] have adopted a dill‘erent approach to computing form
`factors in occluded environments by incorporating their shadow algorithm for area light
`sources (Section 16.8) into a radiosity algorithm that was used to make Color Plate
`lll.22{a—b). Color Plate Ill.22(e) [NISH86] adds to this a model of sky light, approximated
`by a large hemispherical source ofditl‘use light. The hemisphere is divided into bands that
`are transversely unifomt and longitudinally nonuniform. As with other luminous surfaces,
`the etl'ects of occluding objects are modeled.
`
`
`
`16.13.13 Substructuring
`
`the better the results, at the expense of increased
`The finer the patch parametrization,
`computation time for a" form factors. To prevent this square—law increase in the number of
`form factors, Cohen, Greenberg,
`lmmel, and Brock [COl-ll386] adaptively subdivide
`patches into subpatches at places in the patch mesh at which a high radiosity gradient is
`found. The suhpatches created by this .vubs'trmrturing process are not
`treated like
`full-[lodged patches. Whenever a patch 1' is subdivided into subpatchcs, the form factors P; _J-
`front each suhpatch s to each patch j are computed using the hemicube technique, but form
`factors from the patches to the subpatchcs are not computed. After a patch has been broken
`into subpatches, however,
`the previously calculated values of each form factor from the
`patch to other patches are replaced by the more accurate area—weighted average of the form
`factors from its at subpatches:
`
`r;q,=— E 15“,th
`At l-:.w::n
`
`(16.7[)
`
`After patch radiosities are calculated as described before, the radiosity ofeach subpatch s of
`patch i can be computed as
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a, = 5, +p, 2 app}.
`lij‘Et n
`The algorithm iterates, adaptively subdividing suhpatches at places of high radiosity
`gradient, until the tlilferences reach an acceptable level. The linal subpatch radiosities are
`then used to determine the vertex radiosities. Color Plate |ll.2l(b), made using a
`ltomtdaptive version of the algorithm in which subdivision is specified by the user, shows
`“1:11 the same image takes substantially less time to compute when patches are divided into
`Oltc level ol'subpatches. than when an equivalent number of patches are used. The adaptive
`”'CfSion ol'the algorithm is initialized with a “first guess" subdivision specified by the user.
`Color Plate lIl.2[(c) was created by adaptively subdividing the subpatches of Color Plate
`
`Ill-2‘07). Note the improved shadow resolution about the table's legs.
`
`
`(16.72}
`
`
`
` "'I.'t"."(:'-"='.T.-TWFT"'_"""."-‘.'"'E.-,-.
`
`
`
`
`
`Intel Exhibit 1003 Page 8
`
`