United States Patent
`Rich
`
`[19]
`
`[54] IMAGE GENERATION SYSTEM, METHODS
`AND COMPUTER PROGRAM PRODUCTS
`USING DISTRIBUTED PROCESSING
`
`[75] Inventor: Henry H. Rich, Raleigh, NC.
`
`[73] Assignee: Integrated Device Technology, Inc.,
`Santa Clara, Calif.
`
`[21] Appl. No.: 661,200
`[22]
`Filed:
`Jun. 10, 1996
`
`[51] Int. Cl.6 .................................................... .. G06F 15/80
`[52] US. Cl. ......................... .. 345/505; 345/514; 345/520
`[58] Field of Search ................................... .. 395/501, 505,
`395/506, 519—521, 507—509, 280, 306,
`309; 345/501, 505—509, 519, 521
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4/1986 Sims etal. ............................ .. 340/729
`4,586,038
`5/1986 Fuchs .......... ..
`340/723
`4,590,465
`9/1987 MerZ et al.
`364/521
`4,692,880
`2/1988 Bunker et al.
`340/728
`4,727,365
`4,783,649 11/1988 Fuchs et al. .... ..
`340/747
`4,827,445
`5/1989 Fuchs .............. ..
`364/900
`4,905,164
`2/1990 Chandler et al. .
`364/518
`4,965,745 10/1990 Economy et al.
`364/518
`5,388,206
`2/1995 Poulton et al.
`395/163
`5,396,346
`3/1995 Nakayama et al.
`358/448
`5,455,600 10/1995 Friedman et al.
`345/153
`5,481,669
`1/1996 Poulton et al. ....................... .. 395/164
`
`FOREIGN PATENT DOCUMENTS
`
`WO 92/09947 6/1992 WIPO .
`
`OTHER PUBLICATIONS
`
`Computer Graphics, 26, Jul. 2, 1992, “Pixel How: High—
`Speed Rendering Using Image Composition” Steven Mol
`mar et al.
`
`US005808690A
`[11] Patent Number:
`[45] Date 0f Patent:
`
`5,808,690
`Sep. 15, 1998
`
`Williams, Lance, Pyramidal Parametrics, Computer Graph
`ics, vol. 17, No. 3, pp. 1—11 (Jul. 1983).
`
`Fuchs et al., Fast Spheres, ShadoWs, Textures, Transparen
`cies, and Image Enhancements in Pixel—Planes, Association
`for Computing Machinery ’s SIGGRAPH ’85, pp. 111—120.
`
`Primary Examiner—Kee M. Tung
`Attorney, Agent, or Firm—Myers Bigel Sibley & Sajovec,
`PA.
`
`[57]
`
`ABSTRACT
`
`An image generation system having a processing element
`array comprised of a plurality of processing elements inter
`connected so that processing elements may communicate
`With other processing elements in the processing element
`array. A linear expression evaluator provides coef?cients of
`linear expressions Which de?ne object primitives to the
`processing element array and a processing element array
`controller provides instruction and control data. A central
`control unit controls the How of data to and from the
`processing element array and controls the presentation of
`linear expression coef?cients to the linear expression evalu
`ator. Methods, apparatus and program products include
`assigning home pixel addresses corresponding to pixels of
`the screen regions to the plurality of processing elements. A
`database of geometric primitives is traversed and each
`primitive is assigned processing elements. The processing
`elements generate and store linear coef?cients Geometric
`primitives Which touch each screen region are provided to
`the processing elements Which determine Whether the home
`pixels of the processing element are Within the geometric
`primitive and calculate the subpixel coverage of the home
`pixels. Contributions are scattered throughout the processing
`elements for processing and returned to the home pixels to
`determine a ?nal pixel value.
`
`26 Claims, 29 Drawing Sheets
`
`20\
`
`235..‘
`30\
`
`_________________ LL, 1 s2\ :
`
`: a2
`
`ALu
`T
`as
`EvALuAToR ;
`r
`T MEMORY
`l
`3_4
`
`I
`Am
`:-- -.
`as
`.
`I
`—
`;
`I MEMORY
`I
`I
`3_4
`
`1
`
`1
`1
`T
`1
`2
`
`3%
`
`A
`
`CENTRAL CONTROL
`UNIT
`
`A
`
`l
`
`4%]
`
`]
`
`_ PROCESSING ELEMENT
`ARRAY CONTOL
`
`42\ ‘y
`PCI
`INTERFACE
`
`y
`44\
`VIDEO MEMoRY
`INTERFACE
`
`46\
`
`VIDEO FUNCTIONS
`
`HOST
`PRooEssoR
`
`FRAME BUFFER/
`VIDEO MEMORY
`
`ANALOG VIDEO
`
`MEDIATEK, Ex. 1005, Page 1
`
`

`

`U.S. Patent
`
`Sep. 15,1998
`
`Sheet 1 0f 29
`
`5,808,690
`
`HOST PROCESSOR
`
`IMAGE GENERATION
`SYSTEM
`
`VIDEO MEMORY
`
`DISPLAY DEVICE
`
`FIG. 1
`
`LINEAR
`3_6 EXPRESSION
`EVALUATOR
`
`CENTRAL CONTROL
`UNIT
`
`PROCESSING ELEMENT
`ARRAY CONTOL
`
`PCI
`INTERFACE
`
`VIDEO MEMORY
`INTERFACE
`
`VIDEO FUNCTIONS
`
`HOST
`PROCESSOR
`
`FRAME BUFFER/
`VIDEO MEMORY
`
`ANALOG VIDEO
`
`FIG. 2
`
`MEDIATEK, Ex. 1005, Page 2
`
`

`

`U.S. Patent
`
`Sep. 15, 1998
`
`Sheet 2 0f 29
`
`5,808,690
`
`HOST UPDATES THE
`DATABASE OF PRIMITIVES
`
`DATABASE IS TRAVERSED
`AND PRIMITIVES ARE
`ASSIGNED TO
`PROCESSING ELEMENTS
`
`52\
`
`I
`
`PROCESSING ELEMENTS
`OPTIONALLY TRANSFORM
`FROM 3D MODEL TO 2D
`SCREEN AND DETERMINE
`LIGHTING; GENERATE LINEAR
`COEFFICIENTS FOR PRIMITIVES
`
`53\
`
`I
`
`PROCESSING ELEMENTS
`WRITE LIST OF
`TRANSFORMED PRIMITIVES
`TO MEMORY
`
`54\
`
`I
`
`FOR EACH SCREEN REGION,
`A LIST OF PRIMITIVES WHICH
`TOUCH THAT REGION
`IS GENERATED AND
`WRITTEN TO MEMORY
`
`EACH REGION’S PRIMITIVES ARE
`PROVIDED TO THE PROCESSING
`ELEMENTS WHICH CALCULATE
`WHETHER THE HOME PIXELS OF
`THE PROCESSING ELEMENT ARE
`INSIDE THE PRIMITIVE AND MAY
`CALCULATE VISIBILITY
`INFORMATION
`
`6%
`
`I
`
`PROCESSING ELEMENTS
`DISCARD CONTRIBUTIONS
`WHICH ARE OBSCURED BY
`NEARER PRIMITIVES
`
`6%
`
`I
`
`PRIMITIVE CONTRIBUTIONS
`ARE SCATTERED THROUGH
`PROCESSING ELEMENT ARRAY
`SO THAT EACH PROCESSING
`ELEMENT HANDLES ONLY
`ONE CONTRIBUTION
`
`6%
`
`I
`
`WHEN EACH PROCESSING
`ELEMENT IN THE PROCESSING
`ELEMENT ARRAY HAS BEEN
`ASSIGNED A CONTRIBUTION
`THEN SHADING lTEXTURING
`IS PERFORMED
`
`FIG. 3
`
`FIG. 4
`
`MEDIATEK, Ex. 1005, Page 3
`
`

`

`waled °S11
`
`8661 'SI *daS
`
`6Z JO £ lamIS
`
`NO
`
`400 -
`
`PROVIDE TO THE
`PROCESSING ELEMENTS
`A PRIMITIVE
`
`FIGURE 4A
`
`FIG. 4A-1
`FIG. 4A-2
`FIG. 4A-3
`
`NO
`
`404 -
`
`YES
`
`PROCESSING ELEMENTS
`PROCESS EDGE
`INFORMATION FOR
`PRIMITIVE
`
`FIG. 4A-1
`
`426 )
`
`NEXT PRIMITIVE
`
`@
`
`MEDIATEK, Ex. 1005, Page 4
`
`

`

`U.S. Patent
`
`Sep. 15,1998
`
`Sheet 4 0f 29
`
`5,808,690
`
`wZOFDmEPZQQ
`
`cum
`:owmO
`
`N.
`
`F m;
`
`mmFEom
`
`We?
`mm;
`
`omv
`
`MEDIATEK, Ex. 1005, Page 5
`
`

`

`U.S. Patent
`
`Sep. 15,1998
`
`Sheet 5 0f 29
`
`5,808,690
`
`Oz
`
`Kw;
`
`EMIQEOQ
`
`N.
`
`MEDIATEK, Ex. 1005, Page 6
`
`

`

`U.S. Patent
`
`Sep. 15,1998
`
`Sheet 6 0f 29
`
`5,808,690
`
`75\
`
`‘7
`CONTRIBUTIONS ARE
`COMBINED FOR THE HOME
`PIXELS TO GIVE THE TO GIVE
`THE FINAL RG__B PIXEL VALUE
`
`I
`
`76
`\
`SCREEN REGION IS WRITTEN
`To FRAME BUFFER
`
`70\
`FOR EACH CONTRIBUTION, EACH
`PROCESSING ELEMENT
`OPTIONALLY CALCULATES
`LIGHTING, FOG AND
`SMOOTH SHADING
`
`I
`71 \
`TEXTURE UV VALUES ARE
`OPTIONALLY PERSPECTIVE
`CORRECTED AND CONVERTED
`TO M ADDRESS
`
`7%
`
`I
`
`TEXTURE TEXELS ARE LOOKED
`UP AND COMBINED WITH
`LIGHTING AND FOG TO PROVIDE
`FINAL CONTRIBUTION VALUES
`
`73\
`
`I
`
`TRANSPARENCIES ARE
`DETERMINED FOR TRANSPARENT
`TEXTURES TO MODIFY COVERAGE
`AND CONTRIBUTION COVERAGE
`IS USED TO MODIFY
`CONTRIBUTION VALUES
`
`74 \
`
`I
`
`CONTRIBUTIONS ARE RETURNED
`TO ORIGINAL PROCESSING
`ELEMENTS FOR THE HOME PIXELS
`
`FIG. 5
`
`MEDIATEK, Ex. 1005, Page 7
`
`

`

`wawa •sn
`
`8661 'SI *daS
`
`6Z JO L 13311S
`
`0
`0
`K
`0 0
`z a)
`m -I
`z
`CO
`
`SORTER
`204
`
`DJ
`M
`o
`C
`m
`U)
`- I
`C)
`o
`-a
`o z
`m z ---i
`
`U)
`
`_1
`
`MEMORY REQUEST
`CONTROLLER
`212
`
`4
`
`FIGURE 6
`FIG. 6-1
`FIG. 6-2
`
`FIG. 6-1
`
`PROCESSING ELEMENT ARRAY
`400
`
`z
`
`0 I= 0 D cc 1-
`
`40 -., Cl)
`
`o 0 a m
`
`0
`0
`CI
`=I
`0
`z
`
`MICRO - SEQUENCER
`200
`
`t
`
`MICRO
`CONTROL
`AREA
`236
`
`_1
`
`MICROCODE
`CACHE
`202
`
`L
`
`MANAGEMENT
`CPU
`208
`
`mCPU COMMAND BUS
`
`21
`<
`a
`In
`0
`CO
`C
`U)
`
`1-z w
`z
`O o_
`
`36 0 o
`
`38 -.
`
`4
`
`co
`co
`.i 03
`-1228
`9
`
`GLOBAL BUS
`CONTROLLER
`218
`
`•
`
`C
`> co c
`
`cn
`
`-1240
`
`1VCI C3C100N3
`
`a m
`o 0 a
`m C
`C >
`
`DECODER
`220
`
`LEE
`FRONT
`END
`142
`
`1
`
`LEE
`FRONT
`END
`140
`
`226
`
`ii,
`
`MEDIATEK, Ex. 1005, Page 8
`
`

`

`U.S. Patent
`
`Sep. 15,1998
`
`Sheet 8 0f 29
`
`5,808,690
`
`Omn=>
`
`mOwmwoOmm
`
`@
`
`TOHiNOO
`
`DATA
`
`mlw .QE
`
`A?
`
`@
`
`>
`
`M0515;
`
`Q
`
`DATA
`
`ADDRESS b
`
`405.200 \ wmmmonz
`
`x2: mam wwm
`
`A
`
`4. ...................... -92..
`..........
`
`DATA
`
`ADDRESS
`
`wO_m OP
`
`MEDIATEK, Ex. 1005, Page 9
`
`

`

`U.S. Patent
`
`Sep. 15,1998
`
`Sheet 9 0f 29
`
`5,808,690
`
`FIG. 8
`
`MEDIATEK, Ex. 1005, Page 10
`
`

`

`U.S. Patent
`
`Sep. 15,1998
`
`Sheet 10 0f 29
`
`5,808,690
`
`m mmzwE
`
`r;
`
`k
`
`fem
`
`a 5
`
`a 5m
`
`Q :0
`
`a Wm?
`
`02
`
`MEDIATEK, Ex. 1005, Page 11
`
`

`

`U.S. Patent
`
`Sep. 15,1998
`
`Sheet 11 0f 29
`
`5,808,690
`
`NIm
`.GE
`
`@ Q
`
`MEDIATEK, Ex. 1005, Page 12
`
`

`

`U.S. Patent
`
`Sep. 15,1998
`
`Sheet 12 0f 29
`
`5,808,690
`
`A
`
`%
`
`A
`
`//w:
`
`‘Ill
`
`Kai
`
`Wow?
`
`K E:
`
`mm?
`
`2 mEDOE
`
`1: .GE
`
`NA: .QE
`
`mm;
`wmOE
`
`956.5
`
`m.
`
`Q Fm:
`
`W z;
`
`mzmow z_
`
`m
`
`Kw:
`
`@ @@
`
`MEDIATEK, Ex. 1005, Page 13
`
`

`

`U.S. Patent
`
`Sep. 15,1998
`
`Sheet 13 0f 29
`
`5,808,690
`
`NIOTQE
`
`Oz
`
`wmwwmmomz
`
`Km:
`
`m:
`
`MEDIATEK, Ex. 1005, Page 14
`
`

`

`U.S. Patent
`
`Sep. 15,1998
`
`Sheet 14 0f 29
`
`5,808,690
`
`300 w
`ENCODE HIGHEST LEVEL OF
`DETAIL M USING WAVELET BASIS
`FUNCTION TO GENERATE AI FOR
`EACH BASIS FUNCTION
`302 N
`I
`DIVIDE Al BY 5H WHICH IS
`A SMALLER ODD INTEGER
`304 \
`I
`
`I
`
`QUANTIIZE SCALED AMPLITUDES
`TO INTEGER VALUE
`TO GENERATE \_/FI
`
`Y
`305 \
`OPTIONALLY ENTROPY
`ENCODE QUANTIZED DATA
`
`306 \
`
`STORE ENCODED MP
`I
`308 \
`NO.
`COMPUTE AMPLITUDES FOR
`NEXT COARSER LEVEL OF DETAIL
`303 N
`I
`OPTIONALLY ENTROPY
`ENCODE QUANTIZED DATA
`309 N
`I
`STORE ENCODED MP
`
`310
`
`ALL
`LEVELS OF
`DETAIL DEFINED
`
`FIG.11A
`
`MEDIATEK, Ex. 1005, Page 15
`
`

`

`U.
`S. Patent
`
`Sep. 15, 1998
`
`Sheet 15 0f 29
`
`5,808,690
`
`314 \
`
`RETRIEVE STORED COEFFICIENTS
`FOR DESIRED LEVEL OF DETAIL
`
`315\
`
`I
`
`OPTIONALLY, ENTROPY
`DECODE RETRIEVED DATA
`
`316\
`
`I
`
`CALCULATE FINE LEVEL OF DETAIL
`BY SUMMING FOR ALL BASIS
`FUNCTIONS yFvgFvgl
`
`318\
`
`I
`
`CALCULATE NEXT COARSER LEVEL
`OF DETAIL BY SUMMING FOR BASIS
`FUNCTIONS OF NEXT LEVEL OF
`DETAIL ROUND (l/FI'KFI /ECI )*§'I
`
`FIG. 115
`
`I
`_ L _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ l
`
`1 MBIT MEMORY
`(1024 x 128 BYTES)
`100MHZ
`
`28\
`
`I
`
`CONTROL
`
`MINIMUM DETECTOR l
`
`HOST I / F
`
`41 \
`ODING
`H BUFFERS AND ENTFIOPY DEC
`
`I?/IBUS ASIC CELL
`
`MEDIATEK, Ex. 1005, Page 16
`
`

`

`waled °S'Il
`
`6Z JO 91 13311S
`
`'00
`0
`00
`
`0
`
`32-
`
`,
`
`
`
`1
`
`:
`
`LEE
`36
`
`
`\
`
`35 1 43...
`1
`32 ALUs
`(200MHZ)
`
`r
`-
`1
`1
`1
`
`1 i I _ _L
`
`32 ALUs
`
`32 ALUs
`
`BUS
`
`i
`1
`1
`1
`I _L
`1 _, _
`ISOLATION,--- 49
`
`
`
`BUS
`
`ISOLATION
`ISOLATION
`
`ISOLATION
`
`BUS
`
`37
`
`1
`I _.
`
`32 X 128 BYTES
`
`32 X 128 BYTES
`
`32 X 128 BYTES
`
`FIG.13
`
`MEDIATEK, Ex. 1005, Page 17
`
`

`

`U.S. Patent
`
`Sep. 15,1998
`
`Sheet 17 0f 29
`
`5,808,690
`
`0006 mm x mm 00m
`0050 mm x mm 0:0
`w3< mm
`.
`
`205302
`205102
`
`$06 mm X mm 03m
`0050 mm x mm 03m
`23 mm
`.
`
`205302 .
`205102
`
`205302
`205302
`
`-
`
`mica
`mm x mm 03m
`$50 mm x N0 030 w3< mm
`_
`205202 -
`205309
`-
`-
`
`n ............ -
`Mm.»
`- XE .................. - $8.0m
`- -Mmm
`................. -
`
`v _. .O _u_
`
`{mm (00 K8 [mm
`{mm [a
`
`MEDIATEK, Ex. 1005, Page 18
`
`

`

`U.S. Patent
`
`Sep. 15,1998
`
`Sheet 18 0f 29
`
`5,808,690
`
`/
`momma
`/
`
`any \\
`
`m8
`Sm \\
`/
`6mm
`mam \
`
`mom
`
`/
`
`Ia
`
`MEDIATEK, Ex. 1005, Page 19
`
`

`

`U.S. Patent
`
`Sep. 15,1998
`
`Sheet 19 0f 29
`
`5,808,690
`
`512 PIXELS
`16 REGIONS
`
`640 PIXELS
`20 REGIONS
`
`FIG.16A
`
`I
`
`SUB - REGION SUB - REGION
`2’
`1
`
`32 PIXELS
`
`SUB - REGION SUB - REGION
`2
`3
`
`32 PIXELS —>
`
`FIG.16B
`
`MEDIATEK, Ex. 1005, Page 20
`
`

`

`U.S. Patent
`
`Sep. 15, 1998
`
`Sheet 20 of 29
`
`5,808,690
`
`0
`
`64
`
`32
`
`96
`
`1
`
`33
`
`2
`
`34
`
`3
`
`35
`
`4
`
`36
`
`5
`
`37
`
`6
`
`38
`
`7
`
`39
`
`65
`
`97
`
`66
`
`98
`
`67
`
`99
`
`68 100 69 101 70 102 71 103
`
`128 160 129 161 130 162 131 163 132 164 133 165 134 166 135 167
`
`192 224 193 225 194 226 195 227 196 228 197 229 198 230 199 231
`
`8
`
`40
`
`9
`
`41
`
`10
`
`42
`
`11
`
`43
`
`12
`
`44
`
`13
`
`45
`
`14
`
`46
`
`15
`
`47
`
`72 104 73 105 74 106 75 107 76 108 77 109 78 110 79
`
`111
`
`136 168 137 169 138 170 139 171 140 172 141 173 142 174 143 175
`
`200 232 201 233 202 234 203 235 204 236 205 237 206 238 207 239
`
`16
`
`48
`
`17
`
`49
`
`18
`
`50
`
`19
`
`51
`
`20
`
`52
`
`21
`
`53
`
`22
`
`54
`
`23
`
`55
`
`80 112 81 113 82 114 83 115 84 116 85 117 86 118 87
`
`119
`
`144 176 145 177 146 178 147 179 148 180 149 181 150 182 151 183
`
`208 240 209 241 210 242 211 243 212 244 213 245 214 246 215 247
`
`24
`
`56
`
`25
`
`57
`
`26
`
`58
`
`27
`
`59
`
`28
`
`60
`
`29
`
`61
`
`30
`
`62
`
`31
`
`63
`
`88 120 89 121 90 122 91 123 92 124 93 125 94 126 95 127
`
`152 184 153 185 154 186 155 187 156 188 157 189 158 190 159 191
`
`216 248 217 249 218 250 219 251 220 252 221 253 222 254 223 255
`
`FIG.16C
`
`MEDIATEK, Ex. 1005, Page 21
`
`

`

`waled °S11
`
`etc"'
`lz
`
`Ui
`
`I-1
`V0
`V0
`00
`
`6Z JO 1Z lamIS
`
`CA
`'GA
`0
`00
`1:11
`itZ
`0
`
`140 )
`
`1421
`
`144 )
`
`30 )
`
`FROM
`GBC
`
`RAW LEE
`10.-
`COEFFICIENTS
`
`LEE IMPUT
`MACHINE
`
`FORMATTED LEE
`COEFFICIENTS
`
`GLOBAL LEE 0.
`BUSSES
`
`LEE
`PANEL
`ADDERS
`
`LEE 1 BUS 0
`146)
`
`LEE 2 BUS
`148)
`
`PROCESSING
`ELEMENT
`ARRAY
`
`GLOBAL BUS
`
`FROM
`mCPU
`
`mCPU COMMAND BUS
`
`IMMEDIATE DATA
`
`FROM
`MICRO-
`SEQUENCER
`
`CONTROL
`
`LEE
`
`FRONT FRONT
`END
`
`FIG.17
`
`MEDIATEK, Ex. 1005, Page 22
`
`

`

`waled °S11
`
`6Z JO ZZ lamIS
`
`3201
`
`3221
`
`SUPPLY LEE FRONT END WITH
`A,B,C COEFFICIENTS AND
`REGION BASE ADDRESS
`
`ASSIGN EACH PROCESSING
`ELEMENT A PIXEL ADDRESS
`
`FIGURE 18
`FIG. 18-1
`FIG. 18-2
`
`28 )
`
`STORE X AND Y OFFSETS
`IN S REGISTER
`
`301
`
`V
`LEE FRONT END TIME
`MULTIPLEXES ON THE 4 PANEL
`BUSES WITH 16A THROUGH 2A BY 2
`
`321
`
`M REGISTER IS LOADED WITH
`PANEL BUS VALUE SELECTED
`FROM MULTIPLEXED VALUES ON
`PANEL BUSES
`
`FIG.18-1
`
`MEDIATEK, Ex. 1005, Page 23
`
`

`

`Juaied 'S11
`
`6Z JO £Z looqS
`
`338 )
`
`LEE1 BUS = AXr+BYr+C+16A+8B+
`[0,13,213,3B ]
`LEE2 BUS= AX r +BYr,+C+16A+24B+
`[0',8,26,3B ]
`
`334
`EVEN
`
`340 )
`
`336 )
`
`ODD
`
`LEE1 BUS = AXr +BYr+C+A+16A+8B+
`[.0",B,26,313 ]
`LEE2 BUS= AXr +BYr +C+A+16A+24B+
`[.0,B,213,3B ]
`
`PROCESSING ELEMENT SELECTS
`EITHER LEE1 OR LEE2 AS A
`OPERAND AND B OPERAND FROM
`M REGISTER AND SUMS A AND
`AND EITHER B OR COMPLIEMENT OF B
`
`3421
`
`LEE 1 BUS IS SET TO 8B AND
`LEE2 BUS IS SET TO 4B
`RESULT TO R REGISTER
`
`44 )
`
`V
`PROCESSING ELEMENT SELECTS
`A OPERAND FROM LEE1 OR LEE2
`AND B FROM R REGISTER AND
`SUMS EITHER A OR COMPLEMENT
`OF AAND B
`
`FIG.18-2
`
`MEDIATEK, Ex. 1005, Page 24
`
`

`

`waled °S11
`
`etc"'
`
`Ui
`I-1
`V0
`V0
`00
`
`6Z JO 17Z lamIS
`
`CA
`'00
`0
`00
`1:11
`itZ
`0
`
`258 )
`
`PE BUS
`
`34)
`
`262)
`
`PE MEMORY
`0-127
`
`DAISY
`CHAIN
`
`_
`
`(MSB)
`
`254 )
`
`M REGISTER
`
`-1-
`
`•
`
`LEEI
`
`
`
`LEE2
`
`146
`
`FIGURE 19
`FIG. 19-1
`FIG. 19-2
`
`256 A SCRATCHPAD
`
`0-7
`
`A
`
`B
`264
`
`266-)
`
`260 1
`V
`o 6© @0
`
`/w•i
`B
`CARRY
`OPERAND
`• IN
`®
`0
`
` V I
`• / \ /
`COMPARATOR
`A
`OUTPUT
`OPERAND
`0 ©
`
`®
`
`FIG.19-1
`
`MEDIATEK, Ex. 1005, Page 25
`
`

`

`waled °S11
`
`6Z JO SZ lamIS
`
`8 0
`
`®
`
`268_270
`
`272
`
`CARRY A
`OUT
`
`• U
`
`Cl C2
`
`274 )
`\ 1
`N
`
`1 ( 276
`WRITE
`ENABLE
`
`/
`
`r 278
`ENABLE
`HOLD
`
`/
`\
`2501 1
`R REGISTER
`
`1
`
`252
`S REGISTER
`
`FIG.19-2
`
`MEDIATEK, Ex. 1005, Page 26
`
`

`

`Pined °S'il.
`
`6Z JO 9Z lamIS
`
`(A
`'GO
`0
`00
`IT
`0
`
`FIGURE 20
`FIG. 20-1
`FIG. 20-2
`
`35
`
`35 -1
`
`PE MEMORY
`
`SUBPANEL 3
`96-127
`SUBPALEL 2
`64-95
`SUBPANEL 1
`32-63
`SUBPANEL 0
`0-31
`
`294)
`R
`REGISTER
`
`V
`
`A
`
`S
`REGISTER
`V
`
`M REGISTER
`
`• • •
`
`288
`
`PE MEMORY
`SUBPANEL 3
`96-127
`SUBPALEL 2
`64-95
`SUBPANEL 1
`32-63
`SUBPANEL 0
`0-31
`
`S
`REGISTER
`
`M REGISTER
`A
`
`294)
`R
`REGISTER
`
`294) A
`BUS REGISTER
`
`X REGISTER
`L 290
`
`294) A
`BUS REGISTER
`
`X REGISTER
`I v L 290
`
`294-
`I
`BUS REGISTER
`t
`
`PANEL BUS 0
`-.-- 280
`
`X REGISTER
`L 290
`
`294)
`1
`BUS REGISTER
`
`X REGISTER
`-1
`X290
`V
`
`PANEL BUS 1
`L-282 ©
`
`®
`FIG.20-1
`
`MEDIATEK, Ex. 1005, Page 27
`
`

`

`Poled *S11
`
`6Z JO LZ lamIS
`
`294
`BUS REGISTER
`
`1----'
`
`X REGISTER
`290
`
`PANEL BUS 2
`- 284
`
`X REGISTER
`-7/ -290
`
`294)
`I
`BUS REGISTER
`f----
`
`1r
`X REGISTER
`.-- 290
`
`V
`
`
`
`294) 1
`BUS REGISTER
`292-)
`
`WRITE ENABLE
`
`X REGISTER
`v L290
`
`294) 1
`BUS REGISTER
`292)
`
`WRITE ENABLE
`
`PANEL BUS 3
`
`286
`
`FIG. 20-2
`
`MEDIATEK, Ex. 1005, Page 28
`
`

`

`Poled *S11
`
`6Z JO 8Z lamIS
`
`2801
`
`2821
`
`2841
`
`2861
`
`228)
`
`PANEL 0
`
`8
`riMI
`
`PANEL BUS 0
`IMIM010•11,
`
`k
`
`280
`
`
`
`• • •
`
`8 PANEL BUS 0
`
`PANEL 7
`
`8
`
`PANEL BUS 1
`
`282
`
`8 PANEL BUS 1
`
`
`
`• • •
`
`
`
`8 PANEL BUS 2
`
`284
`
`II
`
`• •
`
`8 PANEL BUS 2
`
`8 PANEL BUS 3
`
`,
`
`296
`
`31 24 23 16 15
`8
`PBX REGISTER
`
`286)
`
`3
`8 PANEL BUS
`• • rfi.....im..
`
`•
`
`296
`
`8
`15
`16
`31 24 23
`PBX REGISTER
`
`32
`/
`
`228)
`FIG. 21
`
`MEDIATEK, Ex. 1005, Page 29
`
`

`

`U.S. Patent
`
`Sep. 15, 1998
`
`Sheet 29 of 29
`
`5,808,690
`
`372-
`
`370
`
`/
`
`z
`
`Ae
`
`,
`,
`
`/
`
`/
`
`,
`
`/
`
`374 .__
`
`FIG. 22A
`
`I I
`/
`
`r
`
`/
`
`/1 /
`
`7//
`/
`
`/
`
`/
`/
`
`4
`
`/
`
`/
`
`7
`
`FIG. 22B
`
`,
`
`MEDIATEK, Ex. 1005, Page 30
`
`

`

`5,808,690
`
`1
`IMAGE GENERATION SYSTEM, METHODS
`AND COMPUTER PROGRAM PRODUCTS
`USING DISTRIBUTED PROCESSING
`
`RELATED APPLICATIONS
`
`This application is related to and claims priority from U.S.
`patent application Ser. No. 08/582,085 entitled "Method and
`Apparatus for Texturing Computer Graphic Images" filed
`Jan. 2, 1996 which has been converted to Provisional
`Application Ser. No.60/032,799.
`
`5
`
`10
`
`FIELD OF THE INVENTION
`
`The present invention relates to data processing systems
`and more particularly to methods, apparatus and program is
`products for image generation systems.
`
`BACKGROUND
`
`35
`
`Computer graphics systems are widely used in personal
`computer interfaces, desk top publishing, computer aided 20
`design applications, scientific simulations, military and
`industrial process control and communications networks,
`and in various education, training and entertainment fields.
`The breadth of utility of computer graphics systems in so
`many diverse areas is based upon the singular effectiveness 25
`of communicating large volumes of information by means of
`visual images and the ease, and often the enjoyment, with
`which humans accept visually presented data. The ability of
`the computer industry to consistently provide increasingly
`efficient and economically produced graphics hardware is, 30
`however, dependent to large degree upon the
`costs of electronic components and the development of
`improved system architectures and methods for graphics
`image generation.
`Many conventional interactive computer graphics sys-
`tems employ an applications object model library, an appli-
`cations program to access, create and process the library of
`object models, and an image generation system to convert
`the object models to screen images which may be displayed 40
`on a display device such as a computer monitor. To increase
`usefulness with current display technologies, it is beneficial
`for an image generation system to be capable of producing
`a two dimensional frame or screen defined in screen coor-
`dinates from a selected group of objects defined in model 45
`space. However, such a conversion from an object model to
`a format suitable for display as a screen is a computationally
`intense task which can require high levels of a computing
`systems resources. Thus, the techniques employed to create
`the contents of a frame (i.e. a complete screen image) and 50
`the computer hardware used to generate the data required to
`describe a frame in many cases determine the effectiveness
`of a computer graphics system. This relationship is espe-
`cially true in the area of high performance and intensively
`user interactive computer graphics systems.
`In a conventional object model oriented graphics system,
`the object models, or more simply objects, are digitally
`formatted geometric descriptions of two or three dimen-
`sional objects. An object's description typically consists of
`a set of geometric primitives. A primitive can be a point, line 60
`or polygon defined by one or a set of vertices defined in
`model space coordinates. The geometric primitives combine
`to create an object model.
`In an interactive graphics system, the applications pro-
`gram responds to user input by selecting objects from the 65
`applications model library. In fact, certain graphics systems
`allow the applications program to wholly create new object
`
`55
`
`2
`models. The application program informs the graphics sys-
`tem as to which models are to be displayed and how they are
`to be displayed, along with the geometric description of each
`object on a frame by frame or screen by screen basis.
`To create a screen image the application program defines
`the description of the image in terms of the object models in
`the image. Modeling transformation and the viewing opera-
`tion (i.e. converting from a 3D model to a two dimensional
`view of that model) are next sequentially performed, fol-
`lowed by rasterization. Modeling transformation and the
`viewing operation are referred to as front-end or geometry
`processing. Rasterization, or back-end processing, includes
`the steps of visible surface determination, scan conversion
`and shading/illumination.
`Early raster display architectures provided a system con-
`sisting of a system communications bus, a central processing
`unit (CPU), system memory, a frame buffer, a video con-
`troller and a video monitor. The frame buffer could consist
`of a dedicated memory device or devices, or it may have
`resided anywhere within the system memory. The CPU,
`system memory and video controller were all three con-
`nected to the system communications bus, through which
`data, control and status signals were transmitted. In such a
`system the CPU was required to carry out all of the functions
`in generating a screen image. This system was not efficient
`because a general purpose CPU was not well suited to the
`highly iterative tasks of generating a screen image.
`An alternate architecture further included a separate dis-
`play processor and display processor memory through which
`the video controller was connected to the system commu-
`nications bus. The display processor performed many of the
`calculations required to generate frame data, and, therefore,
`reduced the computational load placed on the system CPU
`by the applications program. The Texas Instruments
`TMS34020 peripheral display processor is an example of a
`device intended for use as a display processor. However,
`simply segregating the display functions from the CPU in
`certain instances may not effectively support graphic intense
`applications such as full motion video and multimedia
`entertainment applications.
`The application of multi-processing methodologies, to
`include pipelining and parallelized computing, has also been
`attempted to increase the speed with which the large vol-
`umes of computation required in graphics image computa-
`tions could be performed. The inclusion of pipeline and
`parallel processors are fundamental to the performance of
`many high performance graphics systems such as the Pixel-
`Planes and Pixel Flow systems described in U.S. Pat. Nos.
`5,388,206 and 5,481,669, to cite examples. These systems
`include a plurality of logic enhanced memory elements.
`Each logic enhanced memory element possesses a dedicated
`arithmetic logic unit (ALU) and a small strip of digital
`memory. The Pixel-Planes design further includes a linear
`expression tree, which evaluates linear expressions devised
`in the form of f(x,y)=Ax+By+C in parallel for every pixel of
`the screen or region of the screen. Each processing element
`is dedicated to calculating values for a single pixel. There is
`only limited capacity for direct interprocessing element
`communication and the processing elements are, therefore,
`constrained in the types of functions that they may perform.
`Because parallel processing has such advantages in image
`generation, it is desirable to utilize a processing element
`array such as that used in Pixel-Planes and Pixel-Flow.
`However, despite the advances in image generation systems,
`additional work is necessary to reduce the amount of hard-
`ware required to provide high speed image generation and to
`off-load as much processing function from the CPU as is
`possible.
`
`MEDIATEK, Ex. 1005, Page 31
`
`

`

`3
`SUMMARY OF THE INVENTION
`
`5,808,690
`
`5
`
`1 5
`
`4
`munications buses for selectively communicating informa-
`tion on one panel communications bus to the other panel
`communication buses of the plurality of panel communica-
`tion buses.
`In a further embodiment of the present invention, the
`image generation system also includes a global communi-
`cations bus for communicating information to all of the
`processing elements in the processing element array. The
`panel communications buses are operably associated with
`10 the global communication bus such that information com-
`municated on all of the panel communication buses may be
`combined to be communicated on the global communica-
`tions bus. Likewise, information communicated on the glo-
`bal communications bus may be divided and provided to
`each of the plurality of panel communications buses.
`Also provided is an image generation system for gener-
`ating a screen image comprised of a plurality of screen
`regions where each screen region has a plurality of pixels.
`The image generation system utilizes a plurality of parallel
`processing elements and includes assigning home pixel
`20 addresses corresponding to pixels of the screen regions to
`the plurality of processing elements. A database of geomet-
`ric primitives is traversed and each primitive is assigned to
`a respective specified subset of processing elements of the
`plurality of processing elements for each of the geometric
`25 primitives. The processing elements optionally transform
`the assigned geometric primitives to screen coordinates. The
`processing elements may also generate linear coefficients for
`the assigned primitives and store the linear coefficients
`associated with the assigned geometric primitives. The geo-
`30 metric primitives which touch each of the screen regions are
`determined based on the stored linear coefficients. The
`plurality of processing elements are provided with the
`geometric primitives which touch a screen region. The
`processing elements determine whether the home pixels of
`the processing element are within the geometric primitive
`provided to the processing element such that the geometric
`primitive will specify a contribution for a home pixel of the
`processing element and optionally calculate the subpixel
`coverage of the home pixels for geometric primitives which
`specify a contribution for a home pixel of the processing
`40 element. Contributions which are obscured by nearer primi-
`tives are discarded and the remaining contribution values
`may then be scattered throughout the plurality of processing
`elements such that each processing element is assigned one
`contribution value. Remaining contributions are evaluated to
`45 determine the contributions assigned to each processing
`element. The contribution values are then returned to the
`processing element assigned to the home pixel correspond-
`ing to the contribution and combined to provide a final pixel
`value.
`Optionally, the processing elements may also determine
`lighting for their assigned geometric primitive. The process-
`ing elements may also determine at least one of the contri-
`bution characteristics selected from the group consisting of
`lighting, fog and smooth shading. The texture value for each
`55 contribution may also be determined. Texture values for
`each contribution may then be combined with any deter-
`mined contribution characteristics. Additionally, it may be
`determined if transparencies modify the contribution cover-
`age.
`As will be appreciated by those of skill in this art, the
`above described aspects of the present invention may also be
`provided as apparatus, data processing system or computer
`readable program means.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram of a processing system utilizing
`an image generation system of the present inventions;
`
`In view of the above, it is an object of the present
`invention to provide methods, apparatus and computer pro-
`gram products to efficiently generate computer graphics
`images. It is a further object of the present invention to allow
`for more efficient use of processing resources.
`It is a further object of the present invention to reduce the
`computational bottlenecks which can arise in distributed
`processing systems.
`An additional object of the present invention is to allow
`for flexibility in use of an array of processing elements.
`These and other objects of the present invention are
`achieved by providing an image generation system having a
`processing element array comprised of a plurality of pro-
`cessing elements. The processing elements are intercon-
`nected such that processing elements in the processing
`element array may communicate with other processing
`elements in the processing element array. The image gen-
`eration system also includes a linear expression evaluator for
`providing coefficients of linear expressions which define
`object primitives to the processing element array and a
`processing element array controller operably associated with
`the processing element array for providing instruction and
`control data to processing elements of the processing ele-
`ment array. A central control unit is operably associated with
`the processing element array, the linear expression evaluator
`and the processing element array control unit control the
`flow of data to and from the processing element array. The
`central control unit also controls the presentation of linear
`expression coefficients to the linear expression evaluator.
`The image generation system may also include a host
`interface adapter operably associated with the central control
`unit for communicating with a host processor. A video
`memory interface operably associated with the central con-
`trol unit may also be included in the image generation
`system of the present invention. The video memory interface
`provides access to a frame buffer memory by the image
`generation system. Video generation means operably asso-
`ciated with the central control unit and the video memory
`interface for generating an analog video signal correspond-
`ing to information provided by the central control unit and
`the video memory interface may also be included.
`Preferably, an image generation system according to the
`present invention is formed as a single integrated device or
`chip.
`In a specific embodiment of the present invention, the
`image generation system includes a processing element
`array comprised of a plurality of processing elements,
`wherein the processing elements are interconnected such
`that processing elements in said processing element array
`may communicate with other processing elements in the
`processing element array. The processing element array is
`divided into a plurality of panels with each of the processing
`elements in a panel being connected to one of a plurality of
`panel communications buses which are common to process-
`ing elements of a panel.
`The processing elements of the specific embodiment of
`the present invention may include an arithmetic logic unit
`and memory operably associated with the arithmetic logic
`unit. A panel bus interface for communicating with other
`processing elements in the processing element array over the
`common panel communications bus is also provided.
`The specific embodiment of the image generation system 65
`further includes panel communications bus interconnection
`means operably associated with the plurality of panel com-
`
`35
`
`50
`
`60
`
`MEDIATEK, Ex. 1005, Page 32
`
`

`

`5,808,690
`
`5
`FIG. 2 is a block diagram of an image generation system
`of the image generation system of FIG. 1;
`FIG. 3 is a flow chart of geometry processing aspects of
`the image generation system of FIG. 1;
`FIG. 4 is a flow chart of rasterization aspects of the image
`generation system of FIG. 1;
`FIG. 4A is a flow chart of an alternative embodiment of
`the present image generation system utilizing non-
`dispersion;
`FIG. 5 is a flow chart of texturing and composition aspects
`of the image generation system of FIG. 1;
`FIG. 6 is a block diagram of one embodiment of the image
`generation system of FIG. 1;
`FIG. 7 is a three dimensional view of a robot arm;
`FIG. 8 is a tree diagram describing the relationship
`between the model objects of FIG. 7;
`FIG. 9 is a flow chart describing aspects of the image
`generation system of FIG. 1 relating to conversion from
`model to screen coordinates;
`FIG. 10 is a flow chart showing texturing aspects of the
`present invention;
`FIG. 11A is a flowchart of a wavelet encoding process;
`FIG. 11B is a flowchart of a wavelet decoding process;
`FIG. 12 is a block diagram of a circuit in accordance with
`the preferred embodiment of texturing aspects of the image
`generation system of FIG. 1;
`FIG. 13 is a block diagram illustrating panel organization
`and panel interconnections with respective circuit elements
`and components in accordance with the image generation
`system of FIG. 1;
`FIG. 14 is a block diagram illustrating panel and subpanel
`organization accordi