EXHIBIT 1011
`
`EXHIBIT 101 1
`
`LEGAL27990979.1
`LEGAL27990979.1
`
`
`
`EXHIBIT 101 1
`
`LEGAL27990979.1
`LEGAL27990979.1
`
`
`
`A SUBDIVISION ALGORITHM FOR COMPUTER
`
`DISPLAY OF CURVED SURFACES
`
`by
`
`Edwin Earl Catmuli
`
`A dissertation submitted to the facuity of the
`University at Utah in Partial Fulfillment of the requirements
`for the degree of
`’
`
`Doorm- of Philomphy
`
`Department of Camputor Science
`
`University of Utah
`
`December 1974
`
`Intel Exhibit 1011 Page 1
`
`
`
`UNIVERSITY OF UTAH GRADUATE SCHOOL
`
`SUPERVISORY COMMITTEE APPROVAL
`
`of a dissertation submitted by
`
`Edwin Earl Catmull
`
`I have read this dissertation and have 10
`
`N
`
`WW/ifl W " m4
`
`’3‘“
`
`
`d i:
`satisfa cry quality for _a___
`
`
`obert B. Step nson
`Chzlimun, Supervisory Commillre
`
`I have read this dissertation and have found it to bc of satisfactory quality for a
`doaoml degree.
`.26 < P1“- 1924 “flan Adan Gog.
`Steven A. Coons
`Member, Supervisory Con-3:533:
`
`I haw mud this diswnminn and haw: I’ound it to be of mlisfactory quality for a
`doctor-.1] degree.
`
`9:.-
`JL- gym/«(K _
`Dale
`David C. Evans
`thber, Super-vixen] Committee
`
`I have read this dissvrmtion and
`doctoral
`(1: rec.
`12..
`.41.,2}._
`Data
`
`
`
`
`
`
`quality for a
`
`c found it to
`4
`.. -flwtfl;
`Ivan E. Sutherland
`Member, Supervisory Committce
`
`Intel Exhibit 1011 Page 2
`
`
`
`UNIVERSITY OF UTAH GRADUATE SCHOOL
`
`FINAL READING APPROVAL
`
`12; the Graduate Council of the University of Utah:
`
`I haw mad the disk‘rtation ofWW in it:
`final form and hzwc found that (l) in format, citations, and bibliographic style are
`cansistent and ucccpmble; (2) its illustrative matcn‘als including figxm-s, tabla, and
`charts an: in place; and (3) the final manuscript is mtislactory to (he Supavisory
`Conunittoe and is ready {or submission to the Graduate School.
`
`
`
`Approved for the Major Dcpartmcm
`
`/
`
`f. fli-LKV/
`
`111
`Anthony C.
`Ch airman [Dun
`
`Approved for the Graduate Council
`
`fl
`
`
`
`Sterling . Mdiurrin
`Dw.
`l the Gndumc School
`
`
`um
`
`Intel Exhibit 1011 Page 3
`
`
`
`ACKNOWLEDGMENTS
`
`l express my appreciation to Steve Coons who gave me considerable help in
`
`writing this thesis.
`
`i am indebted to fellow students and co—workers who aided With ideas and criticism.
`
`Ephraim Cohen stimutated a better mathematical
`
`form.
`
`Lance Williams suggested
`
`numerous ideas including "mapping" and helped correct my English. Martin Nowell was
`
`always willing to discuss new ideas; Robert McDermott provided critical
`
`reading.
`
`Frank Crow stimulated ideas about frame boilers and shadows.
`
`My thanks to lvan Sutherland who stimulated me by telling me that i needed to find
`
`a faster way of subdividing.
`
`I
`
`am grateful
`
`to Rich Riesenfeld who help stimulate a good atmosphere of
`
`interaction at the University of Utah. My thanks also to the members of my committee,
`
`Robert Stephenson, Dave Evans,
`
`lvan Sutherland, and Steve Coons who insisted that
`
`this thesis be somewhat readable- ‘
`
`Thanks to Mike Milochik tor photographic aid and in making prints of the pictures.
`
`I give special thanks to my patient wife who will be glad to see me when this is all
`
`over.
`
`Intel Exhibit 1011 Page 4
`
`
`
`TABLE OF CONTENTS
`
`Abstract
`
`.
`
`,
`
`Chapter 1
`
`Introduction
`
`Chapter 2
`
`A General Aigorithm for Dispaying Curve-d Patches
`
`Chapter 3
`
`Subdividing a Cubic Curva
`
`.
`
`Chapter 4
`
`Extension of Cubic Subdivision to Surfaces
`
`Chapter 5
`
`The Hidden Surface Problem
`
`Chapter 5
`
`intensity
`
`Chapter 7
`
`Sampling, Rastering, and Aliasing
`
`Chapter 8
`
`Conclusion
`
`Appendix A The Bicubic Equation
`
`vi
`
`1
`
`4
`
`13
`
`22
`
`31
`
`34
`
`40
`
`50
`
`53
`
`Appendix B Relationship of Canadian Factors to Beam Canttoi Points
`
`62
`
`Appendix C Approximating tha Bicubic Normai Equation
`
`Appendix D Pictures
`
`References
`
`Vita
`
`'
`
`64
`
`69
`
`76
`
`77
`
`intel Exhibit 1011 Page 5
`
`
`
`ABSTRACT
`
`This thesis presents a method for producing computer shaded pictures of curved
`
`surfaces. Three-dimensional curved patches are used, as contrastad with conventional
`
`methods using polygons. The method subdivides a patch into successivety‘ smaller
`
`Rubpatches until a subpatch is as small as a raster-element, at which time it can he
`
`displayed.
`in general this method could be very time consuming because of the great
`number of subdivisions that must take place; however, there is at least one very usetui
`
`ciao: of patches -- the bicubic patch -- that can be subdivided very quickty. Pictures
`
`produced with the ntethod accurately portray the shading and siihouette of curved
`
`surfaces.
`
`in addition, photoaraphs can be “mapped” onto patches thus providing a
`
`means for putting texture on computer-generated pictures.
`
`Intel Exhibit 1011 Page 6
`
`
`
`CHAPTER ONE
`
`lNTRODUCT'C‘N
`
`A method for creating shaded pictures of curved surfaces is; presented in this
`
`thesis.
`
`A motivation for
`
`the method is
`
`that we wish to produce nigh quality
`
`computer-generated images of surfaces and curved solid objects on a raster-scan
`
`output device. We would not oniy like the images to accurately represent the surfaces
`
`we choose but in addition we wciuld like control ever shading and texture. There has
`
`already been significant
`
`research directed toward these ends, especially on the
`
`hidden-surface [1,2] and shading [3,4] aspects of the problem. Ail such methods must
`
`must address the questions of how to mode! objects and then how to render them.
`
`Poiygons, and sometimes quadric patches, are used to model objects in current
`
`shaded—picture methods . There are some diificullies with using these simple pieces to
`
`model or approximate free-form curved surfaces. Approximation with polygons gives
`
`a faceted effect and : siihoueite made up of straight~line segments. Quadric patches
`
`[5,6], white smooth in appearance, are not suitable for modelling, arbitrary forms, since
`
`they don't provide enough degrees of freedom to satisfy slope continuity between
`
`patches.
`
`There are two significant methods used for reducing or eliminating 9M undesirable
`
`visual effects that occur when polygons are used to approximate curved surfaces. The
`
`first method tor getting rid of the faceted effect is that of Henri Gouraud [3}. With
`
`Intel Exhibit 1011 Page 7
`
`
`
`this method a scalar light intensity value is associated with each vertex of a polygon.
`
`Gouraud r’wes linear interpolation at
`
`the intensity value between vertices and then
`
`subsequently across scan-lines.
`
`If adjoining polygons have the same intensities at the
`
`common vertices then this method yields continuous shading across the surface;
`
`however. the first derivative of the shading is discontinuous. Gouraud‘s method has
`
`been implemented by different groups matting shaded-pictures.
`
`it
`
`is a simple and
`
`successful method but has a few shortcomings: the discorwtinuity oi the derivative is
`
`noticable (the “Mach band effect”), it is difficult to do highlights, the shading is aflected
`
`by the orientation of the polygon in the picture, and the silhouette is still made up of
`
`straight-line segments.
`
`The
`
`second method develooed to improve the appearance of
`
`the polygon
`
`approximation is that of Phong [4]. Since current mr.thds of generating intensities for
`
`polygon surfaces include calculating a surface normal
`
`the verticelei’hong decided to
`
`interpolate the entire surface normal vector between vertices and edges instead of the
`
`scalar intensity values that Gouraud used. This yields a normal at every display point
`
`which can be used to calculate the intensity. Although this normal may not be the
`
`mathematically correct One,
`
`it
`
`is close enough to .se for
`
`intensity and highlight
`
`calculations. As Phong has noted, although there is sin: a discontinuity in the first
`
`derivative of the shading, the discontinuity is. s..1atler than for Gouraud’s method and
`
`hence less noticeable. Phong‘s method has been used to make same visually attractive
`
`photographs, but the problem of straight—line segments at the silhouette still remains.
`
`Curved surface segments or “patches” can be mod in:tead of polygons to model
`
`tree-form curved surfaces.
`
`If
`
`such patches can [.3 joined together with slope
`
`Intel Exhibit 1011 Page 8
`
`
`
`continuity across the boundaries then a picture of a surface can be made to appear
`
`"smooth“ both in shading and at the silhouette. For patches to be useful in modelling a
`
`curved surface, techniques must be found for describing and manipulating the patches
`
`and for connecting them together with siope continuity across boundaries. One such
`
`patch is the bicubic patch, which is widely used (see Appendix A). Most of the ideas in
`
`this thesis will be applied to the bicubic patch, but this is not
`
`intended to imply a
`
`limitation on generality.
`
`Generating pictures of curved patches requires techniques for
`
`l) establishing a correspondence between points on the surface and the elements of
`
`the display raster,
`
`2) removing hidden or. more generally, the "not seen“ parts at patches, and
`
`3) calculating light intensities to be displayed on the raster.
`
`Chapter two will deal with the first item: it will present a technique for establishing the
`
`correspondence between points on the surface and the raster elements, Chapters
`
`three and tour will describe a specific method for quickly making the correspondence
`
`when bicubic patches are used. Chapter five ‘
`
`ill deal with item two: it will discuss the
`
`”hidden-surface” problem for patches.
`
`item three -~ calculating light intensities -- will
`
`be discussed in chapters six and sewn.
`
`Intel Exhibit 1011 Page 9
`
`
`
`CHAPTER TWO
`
`A GENERAL ALGORITHM FOR DISPLAYING CURVED PATCHES
`
`An algOrithm for establishing a correspondence between points on a patch and
`
`raster elements is described in this chapter.
`
`It applies to patches and surtace sections
`
`in general, hence the algorithm presented will not be specific at the outset. Later on,
`
`when a specific kind of patch is used, more detail will be given. Before presenting
`
`that algorithm, however, some terms must be defined.
`
`DEFINITIONS
`
`A “rastahscan device" or ”raster—display" is the device that we will consider for
`
`final output of an image. The rectangular array of "dots” that
`
`is produced .on a
`
`raster-display
`
`is
`
`called
`
`ths
`
`"raster.”
`
`Each
`
`dot will
`
`usually be
`
`called
`
`a
`
`"raster-element.“ The raster element covers a very small area of the raster; however.
`
`it should not be thought of as a point. A row of raster-elements is a ”scan-line."
`
`Scan-lines are usually produced in sequential order, termed ”scan~|ine*order.“ Each
`
`raster—element has a brightness that
`
`is determined by the intensity value for that
`
`raster-element. The prece‘ss of taking the intensity values and putting the dots on the
`
`raster with thecorresponding intensities is called "displaying."
`
`_
`
`Intel Exhibit 1011 Page 10
`
`
`
`_‘J'l
`
`A ”frame-butler“ is a memory large enough to store all of
`
`the intensity values
`
`prior to displaying. An intensity value in the frame-butter can be addressed in a way
`
`that corresponds to the position where the value will be displayed on the raster.
`
`Locations In the trams-butler will also be called ”raster-elements“ since there is a
`
`strong one-to—one
`
`correspondence between those lecations
`
`and the geometric
`
`locatiOns of the raster—elements and because the distinction between the two is not
`
`important here.
`
`For our purposes,
`
`the frame-butter is made with random-access
`
`memory so that values can be written into it
`
`in any order, as opposed to scam-line
`
`order Only. The size of the frams‘butter is determined by the resolution at
`the
`raster-display and the number of I'bits" used to store intensity values. For exempts, if
`
`the raster has 512 scan-lines and 512 raster-elements per line and each element has 8
`
`bits for
`
`the intensity value,
`
`then the frame-butter requires a storage capacity of
`
`512x512x8 bits.
`
`For the most part we will
`
`ignore the raster~dicplay and address
`
`ourselves to the issue of putting the right intensity values in the raster-elements of
`
`the frame-buffer.
`
`The terms relating the original description of an object to its image will now be
`
`defined.
`
`“Object-space“ is the three-dimensional space in which objects will ordinarily
`
`be described.
`
`in order to generate realistic pictures of objects we make a perspective
`
`transformation [1,7,8] of the object from object—space to ”image-space."
`
`image-space
`
`Is also three-dimensional but the objects have undergone a perspective distortion so
`
`that an orthogonal projection oi
`
`the object onto the x-y plane would result
`
`in the
`
`expected perspective image. We want
`
`the lmage~space to be threevdimensional
`
`in
`
`order
`
`to preserve depth information which Will
`
`inter be used to solve the
`
`Intel Exhibit 1011 Page 11
`
`
`
`y
`
`
`
`!
`
`Three-dimensional
`object l
`E 9
`
`Z
`
`Perspective
`transformation
`
`eye
`
`7 \ Projected image
`Orthoacnal projecflon
`
`Object—seam
`
`./
`
`Three~dimen550na1
`image-space abject
`
`
`
`
`
`€-~ Raster~element
`squares
`
`Sample—points
`
`fl
`
`3335 or
`raster-element:
`
`_
`
`mm
`elements
`
`M «
`
`values
`
`K Raster-
`
`Raster-disglax
`
`Figure 2-].
`
`Intel Exhibit 1011 Page 12
`
`Intensity
`values
`
`_I
`
`{r
`
`Frame-buffer
`
`
`
`hidden-surface problem.
`
`The orthogona' projection of
`
`the image—space object onto
`
`the x—y plane is called the "projected image.” That part of the x~y plane which will be
`
`associated with the raster is called the ”screen."
`
`We must define the relationship between the imageospace and the raster in order
`
`to transfer information from the projected image to the raster. Recall that the screen
`
`is the portion of the x-y plane of the image-space that corresponds to the raster. The
`
`area of the screen is divided into email squares called "raster~eiement squares." There
`
`is. of course, a onewto—one correspondence between raster-element square: and raster
`
`elements. The center of each raster-element square will be called a “sample-point.“
`
`A diagram depicting the relationships of the above terms is shown in figure 2-1.
`
`THE SUBDlVlSlON ALGORITHM
`
`The algorithm for establishing the correspondence between a patch and the
`
`raster-elements will
`
`now be presented.
`
`The
`
`algorithm, hereaiier
`
`called .the
`
`"subdivision algorithm.” works for either patches or segments of patches, called
`
`"subpatches." Figure 2-2 illustrates a portion of the screen where the dots represent
`
`the sample-points.
`
`(The outlines of the raster~alement squares are not shown.) The
`
`curved lines represent
`
`the edges of
`
`a projected patch.
`
`Even though only the
`
`projection is shown, we assume that enough information about the patch is maintained
`
`so that the light intensity for any location on the patch can be calculated.
`
`A statement at the algorithm is:
`
`it the patch («ubpatchi is small enough so that its projection covers only
`
`Intel Exhibit 1011 Page 13
`
`
`
`one sample-point,
`
`then compute the intensity oi the patch and write it
`
`into the corresponding element of the frame-butter; otherwise, subdivide
`
`the patch into smaller subpatches; and repeat
`
`the process tor each
`
`subpatch.
`
`Figure 2-3 shows
`
`a patch subdivided into four subpatcnes where most of
`
`the
`
`subpatches still cover more than one sample-point.
`
`in figure 2~4 the subpatches that
`
`are too large are again subdivided. Subdivision continues until no subpatch cavers
`
`more than one sample-point.
`
`Readers
`
`familiar with other computer—gamete:
`
`seeded-picture efforts will
`
`recoanize a similarity between the method presented here and Warnock’s hidden
`
`surface algorithm [9]. Warnock solve"-I
`
`the hidden surface problem for polygons by
`
`recursively subdividing the screen space into successively smaller sections until all
`
`questions about
`the ordering of polygons left
`in a section were easy to answer.
`Warnock’s algorithm differs from the One presented here in that the former subdivides
`
`the screen, while the latter subdivides the surface being rendered.
`
`The patch subdivisiOn algorithm as stated is very simple but some questions
`
`remain: How is
`
`the subdivision process terminated? What
`
`if
`
`a patch covers no
`
`sample-points? What
`
`if part of
`
`the patch intersects the edge of
`
`the screen or is
`
`behind the eye? How many times must a patch be subdivided? Finally, what kinds of
`
`problems does the discrete sampling introduce? Each of these issues will be discussed
`
`in turn.
`
`Intel Exhibit 1011 Page 14
`
`
`
`. o
`
`<— \ 3'5ng t31prc‘xjechm'1
`image of patch
`.
`
`g
`
`,
`
`O
`
`n
`
`a
`
`I
`
`Sample vpoinf
`
`I»
`
`9
`
`o
`
`Patch divided into
`four sub-patches
`
`are samptwpoint
`
`Patch subdivided
`so ihat‘no sub-patch
`cavers more than
`
`Intel Exhibit 1011 Page 15
`
`
`
`to.
`
`TERMINATION
`
`The decision as to whether or not a subpatch should be subdivided is based on
`
`termination conditions.
`
`Two termination canditions will be discussed -- size and
`
`clipping.
`
`For
`
`the purpose of
`
`this discussiori we note that
`
`the terms ”patch” and
`
`"subpatch" can be used interchangeably, hence we will usuatly use the word "patch.”
`
`As specified in the algoflthm, subdivision termtnates when a patch covers only one
`
`sample-point. Since the edges of a patch are curved. the test as to whether or not a
`
`Approximating
`polygon
`
`.
`
`Q
`
`.
`
`.
`
`‘
`
`Sample-
`point
`
`\.
`
`\ Patch
`
`,.
`
`c
`
`
`
`i
`
`5
`
`Figure 2-5
`
`patch covers only one sample-point may be time consuming. However, for the purpose
`
`of this test. a patch can be approximated by a polygon termed by connecting the font
`
`corners oi the patch wlth straight line sogmants. The size of that polygon can then be
`
`checked to determine whether or not
`
`it covers at most one sampte-point.
`
`This
`
`approximation shook! usually be adequate for patches that are approaching the size of
`
`Intel Exhibit 1011 Page 16
`
`
`
`11
`
`the raster-eiements.
`
`It may not be adequate if the patch is very curved (see figure
`
`2-5).
`
`it
`
`this case can be detected because of special characteristics of the patch
`
`geometry, men the patch can be subdivided again.
`
`If
`
`it cannot be detected then a
`
`local error may occur.
`
`CLIPPING
`
`A second termination condition might be a check to see if
`the patch is on the
`screen.
`It part :5 the projection of a patch in imaoe-soace onto the x-v plane tied off
`
`the screen or the patch is behind the eye then that part of the projection should not
`
`be displayed. The process of eliminating the portion of the projection that should not
`
`be on the screen is called clipping[7.81 A clipping termination condition requires that
`
`there be some method for determining ii a patch is totally on or totally off the screen.
`
`it the patch is totally on the screen then subdivision may praceed for that patch with
`
`no further need of clipping checks tor the subpatches generated from that patch.
`
`if
`
`the patch is toteiiy of! the screen then that patch may be discarded.
`
`if it cannot be
`
`determined that the patch is totally on or totaity off the screen then that patch should
`
`be subdivided and the clipping check shouid be made {or each new patch resulting from
`
`the subdivision.
`
`NUMBER OF SUBDlVlSIONS
`
`The number of times a patch nust be subdivided to get down to the size of a
`
`raster-element is proportional to the area of the patch on the screen. Consider the
`
`best case: a square two-by~two raster~elements needs Only one subdivision, or 4°; 3
`
`Intel Exhibit 1011 Page 17
`
`
`
`12
`
`square 2’ by 2‘ needs 4'44” subdivisions; a square 2" by 2" needs 2.1;!“ subdivisions.
`
`This is a geometric series equivalent
`
`to (4"-1)/3 which is approximateiy 4'73. The
`
`area of the square is 2’" or 4". Therefore, the ratio of number of subdivisions to area
`
`is about 3/3. This analysis is most accurate for nearly square patches. For curved
`
`patches and skewed orientations the ratio may be somewhat larger.
`
`THE SAMPLlNG PROBLEM
`
`There are some problems encountered when using sample points. The most
`
`obvious is the “staircase-effect“ or "jaggies" seen on the silhouettes of objects.
`
`In
`
`addition, a patch might be so small that it doesn’t cover any sample-point, causing it to
`
`disappear. The tatter problem can be solved by assigning a patch to the nearest
`
`sample-point h it deesn't sou.- any sample~point. The problems of sampling are
`
`inherent with the use of a raster display. Chapter seven will discuss the problems
`
`' further as well as a means to alleviate them.
`
`APPLlCATlON
`
`The subdivision algorithm presented above was first. applied to bicubic patches.
`
`Bicubic patches are convenient on several counts: they are widely used, they can be
`
`compactly specified in several different ways (see Appendix A), they can be easily
`
`joined with first derivative continuity at the boundaries and they can be subdivided '
`
`very easily. The next two chapters will pesent a method for test subdivision of such
`
`patches.
`
`it should be emphasized at this point however that the subdivision algorithm
`
`is by no means limited to bicubic patches but can be applied to other kinds of surfaces.
`
`Intel Exhibit 1011 Page 18
`
`
`
`CHAPTER THREE
`
`SUBDlVlDlNG A CUBIC CURVE
`
`A method tor quickly subdividing a cubic curve is presented in this chapter; the
`
`extension to patches is developed in the next chapter. The method uses a new kind of
`
`ditterence equation for obtaining the midpoint of a curve segment.
`
`The resulting
`
`ability to quickly subdivide a curve makes the application at the subdivision algorithm
`
`practical.
`
`SUEDi‘v’iDlNG THE CUBlC CURVE
`
`Subdivision is easy because, as we shall see. the midpoint of a cubic curve is the
`
`avorago of its two endpoints minus a correction term. One result of this is that the
`
`cubic can be subdivided with oniy three acids. A similar method can be used to find
`
`the derivative at the midpoint.
`
`Consider the cubic:
`
`Kt) '" at” 4- 5? 4» ct + d.
`
`The problem is to find Kt) when Hub) and mom are aiready known. Note first that:
`
`Intel Exhibit 1011 Page 19
`
`
`
`mm) - alixh)’ + bttzh)’ + cttth) + d
`
`- att’ : Sht’ 4» Sh’t : h’) 4- b(t’ 1 2th + h') + c“ t h) +cl.
`
`14.
`
`If the points f(t+h) and ftt-h) are added them
`
`mm) + ftt-h) - 2alt’ 4» Sh’t) + tht’ + h’) 4- at + 2d
`
`- 2m) + 2h’t3at + b);
`
`therefore :(iwum) + ftt-h)]/2 — h’tSat + b).
`
`The midpoint
`
`then is the average of
`
`the two endpoints minus the correction term,
`
`h’(3at+b). The correction'term is a linear tunction of t and h.
`
`It h-l/2", then since h
`
`is a power at two it can be calculated on a computer with a simple binary shift.
`
`The correctiOn farm at
`
`t can similarly be found from the correction terms at Ni
`
`and t—h.
`
`lt gtt) ~ h’lSat <- b) then attth) - h’tSattth) + b). Again by adding:
`
`gum) + gttvh) . 2h’(3at) + th’ .. tht)
`
`and so
`
`<3~1>
`
`gm - (gum) + gtt-h)]/2.
`
`Let hn - 1/2" where n can be considered a level of subdivision. Then hm. - mm and
`
`Wm,
`
`u- h’ala and since g0) - hil3at + b) than
`
`(3‘2)
`
`Enos“) " 811(1)]4.
`
`and (34'; can be rewritten as
`
`Intel Exhibit 1011 Page 20
`
`
`
`15
`
`(3-9)
`
`8n“) "' {Snfi‘bn} 1’ Bn(t’hn)]/2
`
`Therefore:
`
`(3—4)
`
`“H - “((+11) fut-11).”? ’ [8n(t+h) + Bun—hull
`
`Equation (3—4) is the subdividing difference equation for a cubic and equations (3-2)
`
`and (843) are used to get the right correction term as h" is made smaller by powers of
`
`two.
`
`EquatiOns 3-2, 3-3, and 3-4 can be express-ed diagrammatically as as shown in
`
`figure 3-5. At each and point there are two values -- the values at the function and
`
`the correction term, Those values can be put into two registers. The contents of the
`
`registers for the midpoint can be found by the indicated combination of the registers at
`
`the endpoints.
`
`in order to subdivide one of the new halves it is necessary to update
`
`'the correction term at the end points since in“ will be half as big and the correctiou
`
`terms are functions of h".
`
`in terms of the diagram in figure 34, the subdivisiori
`
`process cascades downward. The correction terms are functions of
`
`the level of
`
`subdivision. The initial values in the registers can be found by solving f(t) and gem.
`
`Since n-O then h’-1 and f(0)-d. him-b, ftl)-a+b+c+d, and goal-wave
`
`it may be useful sometimes to compute the derivative. The derivative can be
`
`found as a simpie function of the endpoints and a correction term that is dependent
`
`only upon the depth of subdivision.
`
`instead of adding t(t+h) and i(t~h), subtract them:
`
`Intel Exhibit 1011 Page 21
`
`
`
`16
`
`o .
`
`1
`
`t
`
`
`
`
`f(O)_ we)
`
`em 8am
`
`
`1(0) 8:140)
`-—
`
`“(1)? .
`{(1
`((1/2) 8n.:(1/2)
`m W ”— '— f seval n+1
`Figure 34
`-
`
`KHh) - {(t-h) - 28(3111' + h”) + meh) + 26h
`
`- Zhaat’ + 2ah’ + 3h2bt + th
`
`Note that the derivative iszlf’fl) - Gai’ * 2b! + 6
`
`therefore {(t+h) - {(t-h) - 2111““) + 2ah’ so
`
`(3—5) V“) - [f(t+h) — f(t«h)]/2h - ah’
`
`Note that ah’ is a function only of the level of subdivision.
`
`Intel Exhibit 1011 Page 22
`
`
`
`17
`
`A MATRIX REPRESENTATION
`
`The subdivision method can be put in matrix form and hence related to the matrix
`
`methods for generating bicubic patches presented in Appendix A. The matrix form of
`
`a simple cubic is:
`
`fttl-[t’ t’ t
`
`1]
`
`QOU‘M
`
`The correctian terms and function values for the simple cubic can also be put in matrix
`
`form. Let that matrix be called the correctian matrix C and it contents be:
`
`tit-11)
`
`Cu gnfi’h)
`“HM
`Snug”
`
`Recall that the correciian factor is gntti-h’fiiahb}. At the zerath level of subdivision
`
`h’-1/2"‘-1.
`
`So t(0)-d,
`
`“(m-b.
`
`t(1)-a+b+c+d,
`
`and g¢(l)-3a+b.
`
`If we- put
`
`thesa
`
`values that fit in C than
`
`
`
`We can get the values in C by using the matrix:
`
`Intel Exhibit 1011 Page 23
`
`
`
`18.
`
`Ob-‘OH
`
`0 0 l O
`
`p.-...o
`
`0
`Sta-0
`
`l 3
`
`no relation is
`
`(3-5)
`
`G - SA
`
`The object at subdivision is to find the C matrix for each half of a segment. to!
`
`those two matrices be CL and CR for C left and C right. There are matrices L and R
`
`such that CL - LC and CR - RC. The Operation on the values of C have already been
`
`defined. They require that:
`
`1
`
`‘ O
`
`i... 0 1/4
`
`0
`
`0
`
`O
`
`08"
`
`1/2—1/8 1/2-1/
`0
`'1/8 0 my
`
`1/2 -1/8 1/2-1/8
`R . c
`1/8 0
`1/8
`0
`o
`1 ~ 0.
`O
`0
`0
`llqj
`
`'
`
`As an example. the second quarter 0‘ of a segment can be lound by C‘ - RLC. Note
`
`that ail entries in the L and R matrices are powers of two. The bicubic subdivision
`
`method is merely a fast way at doing a matrix multiply taking advantage of the values
`
`in L and R.
`
`Intel Exhibit 1011 Page 24
`
`
`
`19,
`
`SUBDIVISION APPLIED T0 POLYNOMIALS
`
`The cubdlvisian notion can be exlended to polynomials in general. A polynomial of
`
`degree n can be written as:
`
`Kl) - 27..a.t'
`
`therefore
`
`{(txh) - Zimaxtth)‘
`
`The binomial expansion lor (till? is
`
`(lth) - 2.3,(l)!"'(eh)‘
`
`Again, as In the cubic case, add mm) and m-h). Consider just one term (lth)'
`
`(M1)I + (t—h)‘ n 22.5“)!“91‘
`
`(I: ever.)
`
`Since a. are 0le coefficients,
`
`flhh) + m-h) - Zfioafiyldlll'fi‘
`
`(k even)
`
`but Z’Iwafi' - f0)
`
`Intel Exhibit 1011 Page 25
`
`
`
`20.
`
`so we can take the first element out of the series:
`
`f(l+h) + ill-h) - 2M) + 2‘Z;.a.2,.‘,.‘)l”h‘
`
`(is even)
`
`and finally
`
`Kt) - [f(t+h) 4»
`
`f(t~.‘u)]/2 - flamzh’JSWh‘
`
`(k even)
`
`The correction term is a polyrsamiit of degree n~2. One can apply the same
`
`method to the correction term to reduce it
`
`to a function of the endpoints and their
`
`separation. h.
`
`TAYLOR SERIES
`
`A further extension of the subdivisian concept applies to Taylor series. This last
`
`discussion should paint the was; to finding, appropriate solutions for functicns other
`
`than simple polynOmials. Recall that the Taylor series is:
`
`flx) - f(a) + (x-a)f’(e) + (x~a)'t”(a)/2! + .
`
`.
`
`.
`
`+ (x-a)”t""/n! + Rn
`
`and if Rn-oo as n-ooc than
`
`fix) - Zl‘"’(aXx-ai"/nl
`
`3‘
`
`Intel Exhibit 1011 Page 26
`
`
`
`21.
`
`Let a .. (Kin)
`
`then
`
`ftx) - Etth)"f""(x:h)/n!
`
`Again h. can he of
`
`the term 1/2‘.
`
`If for same is the truncated series is a good
`
`approximation to {(x)
`
`in the intervai of h” then the function car. be found in any
`
`subintervai of h, This differs (mm the poiynomiai case in ’hat
`
`information for 'a
`
`segment can be thought of as being at one and rather that at both ends.
`
`Intel Exhibit 1011 Page 27
`
`
`
`CHAPTER FOUR
`
`EXTENSION OF CUBIC SUBDIVISION TO SURFACES
`
`The method of subdividing cubic curves can be extended to bicubic surfaces. With
`
`a cubic curve there is a value and a correction term at each end; with a bicubic patch
`
`there it a value 2'“! three correction terms at each corner. Subdivision of the patch
`
`into four pieces means finding the midpoint of each of the sides and the midpoint of the
`
`patch.
`
`There may be several components to the vector that describes a three dimensional
`
`patch. The surface has three purely geometric components Xtuw), Y(u.v), and Z(u,v).
`
`There may be additional component: for other information such as shading and color.
`
`Each cemponent 9:. treated the same so we need only consider one component of the
`
`patch here.
`
`Since we are considering only one camponent of the surface let that component be:
`
`[3'
`itu.v)-[U’U’” 11a.
`c,
`dl
`
`a,
`b:
`c,
`d:
`
`a)
`b:
`c,
`d:
`
`3‘
`b.
`c.
`d,
`
`v3
`v:
`V
`1
`
`it we multiply the u matrix by the coetticient matrix this equation becomes
`
`Intel Exhibit 1011 Page 28
`
`
`
`F(u,v) qr, F. F,
`
`V,
`in] V’V
`1
`
`where
`
`.
`
`F, - afiu’ + b.u’ + c.u *- d.
`
`F, n aéu’ + bzu’ + call + d.
`
`F, - a,u' + b.u’ + c,u + d.
`
`F. - a‘u’ 4- b.u’ 4- c.u + it.
`
`Since each F“ is a cubic we observe that there is a correction term for each Ftr Cail
`
`this correction term G...
`
`The final value of the compenent is
`
`f(u,v) - v’-F, + VLF, + wF, + F...
`
`Consider v‘.l-'.:
`
`v’-F. - ta,v')u’ + (b,v’lu’ + (c,v°)u + (d.v').
`
`80 v‘ can be considered as a coefficient
`
`in the u equation.
`
`!n that case v’-G, is a
`
`correction term for v'-F,. Similarly, V’-G= is the correction term for V747,. etc.
`
`if we
`
`sum the Fa and 8.,
`
`t u VJ-F, + v'-F, +' wF, + 7.-
`
`g - v’-G, + va, + v-G, + G,
`
`Now 3 is th- correctlon term for t along constant v. This reduction to two numbers
`
`when v is constant is exactly as expected since the curve along constant v is simple
`
`cubic.
`
`Therr"-‘-.-e. for any v, the function and its correction terms alang u can be
`
`found.
`
`Intel Exhibit 1011 Page 29
`
`
`
`24_
`
`Next suppose v changes white u is constant.
`
`In this case FH and G" are constants
`
`and can be thought of as just coatiicients in the above equations. Let the correction
`
`term for f be c; and the correction term for g be (:3. Since g is a correction term for t,
`
`than c; is a correction term tor cg.
`
`These four numbers can be arranged in a square as shown in figure 4-1. This
`
`rei'econtctiun wm‘ be called a “register-square.“
`
`Ifl
`
`Figure 4-1
`
`in the register-square,
`
`t
`
`is the vatue “of
`
`the function at u,v, and g. Cr, and C; are
`
`correction terms.
`
`it we move in the v direction then cg corrects f and c; corrects g.
`
`It'
`
`We move in the u direction, a corrects t and c; corrects cg.
`
`Inserting u, v, and the
`
`coefficients yields:
`
`v’(u'a, + u'b| + uc. 4- oi.)
`+v’tu35, + u’b, 4» uc, + d,)
`+ v(u‘a, + u’b, 4- uc, + d.)
`* (U13. 4. u’b. 4' UC. 4" d!)
`
`h’[v°(3a.u + b.)
`+v’(33,u + b,)
`+v(3a,u + b.)
`4' “33‘“ + bl)]
`
`-
`
`t
`
`+ (am + b,)]
`
`k’[3v(u‘a, + u’b, + uc. + d.)
`+(u’a, + u’b. + m. + dd]
`
`h'k'wvmfiiu t bi)
`
`Intel Exhibit 1011 Page 30
`
`
`
`I?!
`
`where h’ Md K’ apply to the u and v directions respectively and have the same
`
`meaning as h in chapter three. A: in the cubic polynomial case they can be calculated
`
`an a computer with a shilt.
`
`A register-square makes it easy to think about an algorithm for subdividing a
`
`patch. A register~square can be associated with each corner of a patch (See figure
`
`4‘2).
`
`lll
`
`l,l
`
`Register-
`square
`
`M u —>
`
`ill
`
`Figure 4-3
`
`The subdivision algorithm can be applied to the register squares either vertically
`
`or horizontally depending on whether u or v is constant. Figure 11-3 shows a notation
`
`for horizontal subdivision. The top two values oi the left and right register-squares
`
`are used to create the top two values of the middle square using the same nuhdlvision
`
`eigorlthm presented in chapter three. The same applies to the bottom two values of
`
`each square. Vertical subdivision works in a similar manner. The notation of figure
`
`4-3 can be used for the entire patch as shown in figure 4-4. The center square can
`
`be derived from two of the newly Created edge squares. There are now four squares
`
`for each quarter of the patch so subdivision can again take place for each quarter.
`
`Intel Exhibit 1011 Page 31
`
`
`
`Combine
`
`25,
`
`
`
`Combme \ New register—square
`
`Figure 4-3
`
`Corner square
`
`New CeMef square
`L New side,- square
`EE E
`
`3W
`
`1W. .@ CL?
`
`W—flfiewilw
`
`Figure 4-4
`
`Intel Exhibit 1011 Page 32
`
`
`
`27.
`
`it
`
`is important to note that the concept of level of subdivision stilt
`
`'pplies. This
`
`means that the carrcction terms must be adjusted each subdivision. One could think of
`
`each square as extending in two directions. When two squares are combined to create
`
`a new one then its correctiOn terms in that direction are divided by four as required
`
`by the subdivision algorithm. The extension in the other direction is the same for the
`
`new square as for the two end ones and is unaffected by subdivision. This depth
`
`correction will be called "reduction.’
`
`A full patch subdivisiOn can be clarified with figure 4-5. The letters in the four
`
`small boxes represent the initial vaiue; in the register-squares. The next nine boxes
`
`depict the subsequent values in each register-square aft
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
