(12) United States Patent
`Greene et al.
`
`111111111111111011111111111)gl!6 1911111111111111111110111111
`US 6,646,639 B1
`Nov. 11, 2003
`
`(to) Patent No.:
`(45) Date of Patent:
`
`(54)
`
`(75)
`
`MODIFIED METHOD AND APPARATUS FOR
`IMPROVED OCCLUSION CULLING IN
`GRAPHICS SYSTEMS
`
`Inventors: Edward C. Greene, Portola Valley, CA
`(US); Douglas A. Voorhies, Menlo
`Park, CA (US); Paolo Sabella,
`Pleasanton, CA (US); John M.
`Danskin, Cranston, RI (US); James M.
`Van Dyke, Austin, TX (US)
`
`(73)
`
`Assignee: NVIDIA Corporation, Santa Clara, CA
`(US)
`
`Notice:
`* )
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21)
`
`Appl. No.: 09/885,665
`
`(22)
`
`Filed:
`
`Jun. 19, 2001
`
`Related U.S. Application Data
`
`(63)
`
`(60)
`
`Continuation-in-part of application No. 09/121,317, filed on
`Jul. 22, 1998, and a continuation-in-part of application No.
`09/585,810, filed on May 31, 2000.
`Provisional application No. 60/293,250, filed on May 23,
`2001.
`
`(51)
`(52)
`
`Int. C1.7
`U.S. Cl.
`
` GO6T 15/00
` 345/422
`
`(58) Field of Search
`
` 345/419, 420,
`345/422, 426
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,764,228 A * 6/1998 Baldwin
`5,914,721 A * 6/1999 Lim
`6,094,200 A
`7/2000 Olsen et al.
`6,172,679 B1 * 1/2001 Lim
`6,226,003 B1
`5/2001 Akeley
`6,246,415 B1
`6/2001 Grossman et al.
`
` 345/797
` 345/421
` 345/422
` 345/421
` 345/419
` 345/422
`
`* cited by examiner
`
`Primary Examiner—Phu K. Nguyen
`(74) Attorney, Agent, or Firm—Silicon Valley IP Group,
`PC; Kevin J Zilka
`
`(57)
`
`ABSTRACT
`
`A system, method and computer program product are pro-
`vided for avoiding reading z-values in a graphics pipeline.
`Initially, near z-values are stored which are each represen-
`tative of a near z-value on an object in a region. Such region
`is defined by a tile and a coverage mask therein. Thereafter,
`the stored near z-values are compared with far z-values
`computed for other objects in the region. Such comparison
`indicates whether an object is visible in the region. Based on
`the comparison, z-values previously stored for image
`samples in the region are conditionally read from memory.
`
`17 Claims, 31 Drawing Sheets
`
`1
`1
`I look-ahead 1-"" 195
`z-pyramid
`
`j00
`
`120 125
`
`130 135
`
`140
`
`150
`
`160
`
`scene
`manager
`
`geometric
`processor
`
`video
`output
`
`MEDIATEK, Ex. 1006, Page 1
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 1 of 31
`
`US 6,646,639 B1
`
`I look-ahead Y 195
`I z-pyramid
`
`1Q_Q
`
`Figure 1
`
`110
`
`115
`
`120
`
`125
`
`130 135
`
`140
`
`scene
`manager
`
`geometric
`processor
`
`110
`
`feedback connection
`
`L 150
`
`160
`
`output
`image
`
`video
`output
`
`170
`
`180
`
`208
`21
`
`210
`
`214
`222
`
`Figure 2
`
`206
`
`er.
`
`216
`1
`218
`I
`I ll I
`s IIIr 41
`
`200
`
`206
`_ ....
`
`230
`
`I
`
`1
`
`t
`
`I
`I I
`;
`II,
`;
`•—
`
`
`
`1 1 1
`
`0400000641.045040084.6
`
`• •••• ••• • • •-••
`....'
`
`Figure 3
`
`300
`
`list of
`Render Polygon List ) 41-- polygon
`records
`
`(geometric processor)
`For each polygon on list,
`(Transform & Set Up Polygon)
`
`(outputs records to culling stage)
`
`302
`
`(culling stage)
`Tile polygons into z-pyramid with
`
`304
`
`202
`
`( Tile Polygon List )
`
`
`IWO.. •••
`
`
`• • • • • • • •
`• • • •
`
`
`
`• • • • • • •
`
`
`
`• • • • • • • a
`
`• • •
`• • • • • • • •
`
`
`0.0000••••••••••••••
`
`64114.1.400160.
`
`
`
`• • • • • • • •
`
`• • •
`
`dill . •
`
`00900
`
`• • •
`
`212
`
`ese•eow
`
`alli • •
`• •
`
`• •
`OOOOOO
`
`
`
`• • •
`
`
`
`• • • •
`
`00oee
`
`
`
`• • • • •
`
`214
`
`•
`
`•
`
`•
`
`• • • 0
`
`• • •
`• • •
`• • • •
`• • • •
`
`••••••••400 0 ••••••
`
`6006.000.01680.1•000
`
`006.56840e
`
`000
`
`00410
`
`000.1•604060 ,0000 ,
`
`• • •
`• • • • • • • •
`
`• • • •
`
`
`
`• • II • • • • •
`
`• • • •
`
`202
`• del'
`
`• • a
`
`•
`
`202
`
`220
`224
`
`(outputs records to z-buffer renderer)
`
`(z-buffer renderer)
`Render visible polygons
`into z-buffer
`
`306
`
`(RETURN)
`1
`308
`
`MEDIATEK, Ex. 1006, Page 2
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 2 of 31
`
`US 6,646,639 B1
`
`Figure 4
`
`408
`
`400
`
`/
`
`\ S3
`/
`
`420 /
`/
`
`.....
`/
`/
`410
`/
`,
`/
`/
`
`/ Pnear
`/ 424
`
`416
`
`F
`
`422
`
`/
`
`/
`/
`/ 404
`/
`/
`406 ../
`/
`
`/
`
`402
`
`"..---.
`/
`/
`,
`
`/
`/
`406 ...,,,•
`/
`
`B `/
`/-..
`%/.......
`/
`/
`/ 1110- -
`
`MEDIATEK, Ex. 1006, Page 3
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 3 of 31
`
`US 6,646,639 B1
`
`Figure 5
`
`Figure 6
`
`500
`
`(Render Frames with Box Culling
`
`( Sort Boxes into Layers
`
`Organize polygons into boxes
`
`502
`
`Clear layer lists and
`near-box list
`
`600
`
`602
`
`Clear output image,
`z-pyramid, and z-buffer
`
`504
`
`Obtain viewing parameters
`
`( Sort Boxes into Layers
`
`For each box on near-box
`list, render polygon list with
`C Render Polygon List )
`
`Organize boxes in layer lists
`into batches and process
`in near-to-far order with
`
`Process Batch of Boxes
`
`505
`
`600
`
`506
`
`508
`
`Display output image
`
`510
`
`Any
`more
`boxes?
`
`Update bounds of box
`
`Box
`outside
`frustum?
`
`Box
`intersects
`near frustum
`face?
`
`Yes
`
`Add box to
`near-box list
`
`Determine layer L containing
`box's 'nearest corner
`
`614
`
`•
`
`Add box to list of layer L
`
`616
`
`MEDIATEK, Ex. 1006, Page 4
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 4 of 31
`
`US 6,646,639 B1
`
`Figure 7
`
`700
`
`(Process Batch of Boxes)
`
`For each box in batch, if
`Box Occluded by Tip)
`reports that box is occluded,
`remove box from batch
`
`.-702
`
`For each box in batch,
`For each front face,
`(Transform & Set Up Polygon)
`
`—704
`
`(outputs records to culling stage)
`
`706
`
`Any
`more boxes
`in batch?
`
`710
`
`Set v-query status bit
`for box to visible
`
`Yes
`
`Set v-query status bit
`for box to occluded
`
`714
`
`end v-query status
`bits to scene manager
`
`iS
`
`r
`
`Send lip* of z-pyramid
`to scene manager and
`reset far clipping plane
`
`716
`
`Determine
`if any front face
`is visible with
`
`(Tile Polygon List)
`
`Yes
`
`726
`
`RETURN
`
`Any
`more visible
`boxes?
`
`720
`1
`
`Render visible box's
`polygon list with
`C Render Polygon List )
`
`No
`^
`z •
`•
`\
`Any
`Yes I
`child
`)
`b.<
`• boxes? z
`
`i•
`722 • •/
`
`
`
`r
`I
`I Organize ch'Id boxes into
`I
`I batches and process with
`I
`
`(Process Batch of Boxes) i
`J
`
`
`
`7
`724
`
`MEDIATEK, Ex. 1006, Page 5
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 5 of 31
`
`US 6,646,639 B1
`
`Figure 8
`
`800
`
`list of records,
`processing mode
`
`812
`
`810
`
`802
`
`804
`
`806
`
`814
`(RETURN 54
`
`808
`
`
`RETURN)
`
`( Tile Convex Polygon )
`X
`1100
`
`Figure 9
`
`900
`
`(Transform & Set Up Polygon
`
`record
`4— for
`polygon
`
`Transform polygon
`to perspective space
`
`902
`
`Determine smallest
`enclosing NxN tile
`
`.904
`
`.906
`Compute "nearest corner
`
`r 908
`
`Compute line and
`plane equations
`
`Create record(s) and
`output to culling stage
`
`910
`
`(RETURN) 912
`
`Figure 10
`
`1000
`
`1008
`
`1006
`
`1004
`
`8
`7
`6
`
`1022
`
`1018
`
`1010
`
`1012
`
`1002
`
`MEDIATEK, Ex. 1006, Page 6
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 6 of 31
`
`US 6,646,639 B1
`
`Figure 11
`
`1100
`( Tile Convex Polygon )4
`
`processing mode,
`tiling record,
`(rendering record)
`
`It v-query mode,
`initialize status to occluded
`
`1102
`
`Initialize Tile Stack
`
`-1104
`
`1116
`
`(RETURN5
`
`Propagate Z Values
`
`Write z-array(lj
`to z-pyramid
`
`Polygon
`visible?
`
`1
`1120
`
`Yes
`
`1106
`
`1122
`
`(RETURN)
`
`Yes
`
`Pop record
`from Tile Stack
`
`Finest
`level and
`changed
`=TRUE?
`
`1118
`
`1112
`
`In
`v-query
`mode?
`
`1110
`
`1200
`
`z-array[L]
`corresponds to
`tile?
`
`1300
`1
`(Process NxN Tile )4
`
`Yes
`
`
`
`Figure 12
`
`1200
`(
`
`Read Z-Array ) .46— level ("1") and index of tile
`
`Write z-array[LJ
`to z-pyramid
`
`1208
`
`RETURN
`
`MEDIATEK, Ex. 1006, Page 7
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 7 of 31
`
`US 6,646,639 B1
`
`Figure 13
`
`1300
`
`processing mode,
`( Process NxN Tile ) 4— tiling record,
`(rendering record)
`
`If finest level and In render mode,
`set changed 2: FALSE,
`initialize zfarx values and zfar finest
`
`-1302
`
`1346
`
`( RETURN
`
`1304
`Any more
`cells within
`tile?
`
`Yes
`
`1306
`
`-----
`ilf shading, compute i 1332
`color and overwrite r
`output mage
`'
`I-----
`J
`
`Overwrite value
`in z-array(F]
`
`_1330
`
`.1328 No .•••
`•e • • 1336
`zfar (
`, nearer than •
`value in
`z-array[Fl?,'
`•
`•
`• 0
`
`14M
`
`1326
`
`Update zfer finest
`
`changed = TRUE
`
`1308
`Is plane
`of polygon
`occluded?
`
`Yes
`No
`e •
`• •
`A. 1334
`A.
`0
`o'
`.,
`•, 1324
`•
`No, Don't Know / Low-
`/ Polygon ,
`c° resolution (
`‘--
`covers
`"--I''‘
`•
`• ,z-pyrarnicfl, ' yes
`•
`,'No
`• cell/
`,
`• 0
`•
`•
`0
`•
`e
`•
`• e
`• 0
`.•
`
`1310
`
`Does
`cell overlap
`polygon?
`
`1322
`
`1312
`
`d If finest level and
`
`in render mode,
`update zfar finest
`
`It not yet output,
`send polygon to
`z-buffer renderer
`
`1344
`
`Create record and
`push onto Tile Stack
`
`Transform edge and
`plane equations
`
`Yes, Don't Know
`
`If not yet output,
`send polygon to
`z-buffer renderer
`
`1320
`
`1342
`
`,‘Yes
`• ,
`
`L
`r In , 1338
`• render mode, ,
`' and "z advance" ,
`No
`less than /
`zdelta 9 •
`• ,
`
`1314
`
`1316
`
`At
`finest
`level?
`
`Yes
`
`In
`v-query
`mode?
`
`Yes
`
`Set status
`to visible
`
`1318
`
`MEDIATEK, Ex. 1006, Page 8
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 8 of 31
`
`US 6,646,639 B1
`
`Figure 14
`
`140
`
`6
`
`222 ......,
`
`4
`
`1410
`
`dh
`or 1, 1402
`
`or
`
`Ape
`dr
`
`1400
`
`.,,,
`r
`%
`/Al, 1
`--4,r,
`1408
`
`Ad
`
`1406
`
`1
`
`Figure 15
`
`210
`i
`
`i 220
`
`\ X'
`224
`
`2
`
`4
`
`6
`
`8
`
`‘222
`
`X
`
`MEDIATEK, Ex. 1006, Page 9
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 9 of 31
`
`US 6,646,639 B1
`
`Figure 16
`
`1600
`
`(Update zfarx )
`
`cell index "I"
`
`,1602
`
`1614
`i
`
`1604
`
`Does
`z-array[L][I]
`cover current
`tile?
`
`1612
`
`(RETURN
`
`Yes
`
`1606
`/
`zfarx[L) = farthest of (zfarx[L],z-array[1-][1])
`
`1610
`
`Figure 18b
`
`1 816
`
`MEDIATEK, Ex. 1006, Page 10
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 10 of 31
`
`US 6,646,639 B1
`
`Figure 17
`
`1700
`
`zfar
`Propagate Z-Values ) r
`finest
`arrays zfarx, z-array, ancestor_flag
`
`L = finest level
`K = next-to-finest level
`
`1702
`
`1704
`
`1706
`
`RETURN)
`
`Is
`zfar finest
`nearer than
`zfarxM?
`
`Yes
`
`zfar = zfar finest
`
`1708
`
`1710
`
`Is
`ancestor_flag[K]
`FALSE?
`
`Yes
`
`1712
`
`Read z-array[K] with
`
`(Read Z-Array)
`
`1714
`
`A = index of ancestor
`cell in z-array(KJ
`
`zold = z-array[KJ[A]
`
`.-1716
`
`z-array(11[A] = zfar
`
`pyramid zfar = zfar
`
`1736
`k
`
`L = K
`K = coarser level adjacent to L
`
`1732
`
`(RETURN
`
`MEDIATEK, Ex. 1006, Page 11
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 11 of 31
`
`US 6,646,639 B1
`
`Figure 19
`
`1900
`/
`(is Box Occluded by Tip
`
`.1--- bounding box
`
`1902
`
`Nearest
`corner behind
`tar clipping
`lane?
`
`19041
`
`Determine bounding sphere
`
`1905
`
`Transform sphere center and
`compute sphere's nearest depth D
`
`1908
`
`Determine ear value of
`smallest enclosing cell
`
`1910
`
`1914
`1
`
`Report box
`potentially visible
`
`1912
`i
`
`i
`RETURNy.1916
`
`MEDIATEK, Ex. 1006, Page 12
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 12 of 31
`
`US 6,646,639 B1
`
`Figure 20
`
`2002
`processing
`mode
`
`2004
`input from
`geometric processor
`
`output to
`z-buffer renderer
`
`output to
`feedback connection
`A
`
`2006
`
`2008
`
`FIFO of
`Tiling
`Records
`
`FIFO of
`Rendering
`Records
`
`2028
`t
`
`Tile Stack
`
`— 2010
`
`2030
`—i—L
`V-Ouery
`Status
`Bits
`
`"tip" of
`z-pyramid
`
`170
`I
`
`Z-PYRAMID
`
`2020 4
`z-array[0]
`z-array[1]
`
`z-array[F]
`
`2018
`
`2032
`i
`
`2012
`
`2026
`
`2022
`------ - -1 2024
`I i
`
`r - -
`1
`--ej Tile Convex Polygon
`
`Figure 21
`
`tile
`
`far
`clipping
`plane
`2106
`
`-4 - - i>•-
`2102
`
`zfarc znear
`2114 2112
`
`near
`clipping
`plane
`2104
`
`MEDIATEK, Ex. 1006, Page 13
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 13 of 31
`
`US 6,646,639 B1
`
`Figure 22b
`
`Figure 22c
`
`R's mask
`
`• .
`
`O's mask
`
`2204
`
`2206
`
`8 . . •
`
`Figure 23
`
`2300
`
`2302
`
`near
`clipping
`plane
`
`2304
`
`tile
`
`far
`clipping
`plane
`2306
`
`Figure 24
`zfarm
`
`zfart
`
`I'
`
`2400
`
`2408
`
`l
`2408
`{
`
`tile
`
`2410
`
`2414
`
`t
`far
`clipping
`plane
`
`2406
`
`212
`1
`
`I
`_L
`
`1I
`
`t
`
`Pi
`
`I
`I
`
`t
`
`P2
`
`I
`
`I
`1
`I
`1
`J
`I
`
`t
`
`P3
`
`1
`I
`1
`1
`1
`1
`
`t
`
`P4
`
`i
`
`t
`
`P5
`
`2402
`
`t
`
`near
`clipping
`plane
`2404
`
`MEDIATEK, Ex. 1006, Page 14
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 14 of 31
`
`US 6,646,639 B1
`
`Figure 25
`
`2500
`
`(Update Mask-Zfar Pecord
`
`-0—
`
`zfart, masks zfarm
`zfarp, maskp
`
`Yes
`
`2504
`I
`zfart = zfarp
`maskt = all zeros
`
`2506
`i
`--(RETURN)
`
`2512
`1
`zfart = zfarm
`maskt = maskp
`zfarm = zfarp
`
`
`T
`RETURN )
`1
`2514
`
`Yes
`
`2524
`
`Yes
`
`2526
`I
`RETURN)
`
`MEDIATEK, Ex. 1006, Page 15
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 15 of 31
`
`US 6,646,639 B1
`
`Figure 26
`
`zfar
`
`2610
`
`2624
`zfar
`
`2620
`
`2634
`zfar
`
`2630
`
`cell
`
`far
`clipping
`plane
`2606
`
`znear
`2612
`
`t
`znear
`2622
`
`znear
`2632
`
`z-pyramid
`value
`2608
`
`offset
`z-pyramid
`value
`2640
`
`2600
`
`2602
`
`near
`clipping
`plane
`2604
`
`Figure 28
`
`noo
`( Is Plane Occluded within Cell
`
`Determine "nearest corner
`using quadrant of (nx,ny)
`
`2802
`
`Compute znear of plane
`of polygon within cell
`
`2804
`
`2806
`
`Is
`znear
`farther than
`cell's z-pyramid
`value?
`
`2808
`/
`Report plane occluded
`
`Yes
`
`2810
`I
`
`Report plane
`potentially visible
`
`2812
`¤
`/
`i (RETURN)
`
`Figure 29
`
`2900
`
`I
`( Create Look-Ahead Frame
`
`Clear look-ahead z-pyramid
`
`Create look-ahead view frustum
`
`2902
`
`,,2904
`
`600
`( Sort Boxes into Layers 1
`
`V
`For each box on look-ahead near-box
`list, tile polygon list into took-ahead
`z-pyramid with modified version of
`( Render Polygon List )
`
`,... 2906
`
`•
`Organize boxes in look-ahead layer lists
`into batches and process in near-to-far
`order with modified version of
`( Process Batch of Boxes )
`
`„. 2908
`
`'
`
`(RETURN y
`
`2910
`
`MEDIATEK, Ex. 1006, Page 16
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 16 of 31
`
`US 6,646,639 B1
`
`Figure 27
`
`( Render Frames Using Coherence
`
` 2700
`Y
`
`Organize scene polygons into boxes
`
`2702
`
`Clear hidden-box list 1 and visible-box list 1,
`and append all boxes to hidden-box list 1
`
`2704
`
`Clear output image,
`z-pyramid, and z-buffer
`
`2706
`
`For boxes on visible-box list 1,
`• off-screen boxes: mark as off-screen
`• on-screen boxes: render polygon list
`
`2708
`
`For boxes on hidden-box list 1,
`• off-screen boxes: mark as off-screen
`• 'near boxes: mark as visible and render polygon list
`• boxes occluded by lip": mark as occluded
`• other boxes: process in batches with Process Batch of Boxes
`(renders polygons in visible boxes) and mark occluded boxes
`
`--2710
`
`Display output image
`
`2712
`
`1.
`
`-2714
`
`Clear visible-box list 2
`and hidden-box list 2
`
`For boxes on visible-box list 1,
`- off-screen boxes: append to hidden-box list 2
`• "near boxes: append to visible-box list 2
`• boxes occluded by "tip": append to hidden-box list 2
`• other boxes: determine visibility with Process Batch of Boxes,
`append visible boxes to visible-box list 2,
`append occluded boxes to hidden-box list 2
`
`For boxes on hidden-box list 1,
`• off-screen and occluded boxes: append to hidden-box list 2
`• visible boxes: append to visible-box list 2
`• other boxes: determine visibility with Process Batch of Boxes,
`append visible boxes to visible-box list 2,
`append occluded boxes to hidden-box list 2
`
`2716
`
`2718
`
`Rename hidden-box list 2 to hidden-box list 1,
`rename visible-box list 2 to visible-box list 1
`
`2720
`
`Update bounds of boxes
`
`.- 2722
`
`MEDIATEK, Ex. 1006, Page 17
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 17 of 31
`
`US 6,646,639 B1
`
`3000
`
`3010
`
`3020
`
`3022
`
`3024
`
`3030
`
`3040
`
`3060
`
`culling stage
`
`z-value/stencil
`renderer
`
`video
`output
`
`A
`2 x 2
`tiles
`
`A
`
`3090
`
`3070
`
`occlusion image
`buffer
`
`z-value/stencil
`buffer
`
`3091
`
`3092
`
`3093
`
`I copy
`
`occlusion image
`buffer
`
`3080
`
`3095
`
`3094
`
`Figure 30
`
`geometric
`processor
`
`set-up
`
`rasterizer
`
`culling stage
`
`MEDIATEK, Ex. 1006, Page 18
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 18 of 31
`
`US 6,646,639 B1
`
`3101
`
`Figure 31
`
`3100
`
`3104
`
`MEDIATEK, Ex. 1006, Page 19
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 19 of 31
`
`US 6,646,639 B1
`
`3100
`
`Figure 32
`
`3258
`
`zfar0
`
`znear0
`
`3250
`
`/
`
`3252
`
`zfarl
`
`znearl
`
`3254
`
`-0-
`
`i
`
`3256
`
`Stencil Information
`
`stencil° = 8-bit value
`
`stencil_valid flag_O
`
`stencill = 8-bit value
`
`stencil_valid_flag_l
`
`MEDIATEK, Ex. 1006, Page 20
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 20 of 31
`
`US 6,646,639 B1
`
`Figure 32A
`
`znear value of polygon
`
`zfar value of polygon
`
`zfar value of region
`
`I
`.t,
`\ — —r- 1
`
`samples covered F(faj
`by polygon
`
`1
`
`1
`
`I
`
`Figure 32B
`
`mask created
`
`4P
`
`1
`
`F
`
`1------1
`
`N(near)
`
`I P
`
`indicates samples where
`polygon is potentially
`visible and the zfar value
`of these samples (where
`the znear value of the
`polygon is in front of the
`zfar value of the tile)
`
`Figure 32E
`
`mask omitted
`
`P
`
`initial state
`
`resulting state
`
`F
`
`Figure 32C
`may also partially
`cover "lower" region
`
`N
`
`Figure 32F
`
`F
`
`may also partially
`cover "lower region
`
`N
`
`I
`
`*I P
`
`1
`
`1
`
`1
`
`initial state
`
`I--NAP
`
`resulting state
`
`i I
`
`Figure 32D
`depth order doesn't matter
`
`F
`
`N
`
`F
`
`Figure 32G
`
`may also partially
`cover "lower region
`
`N
`
`1
`
`I V
`
`initial state
`
`resulting state
`
`1 17 P
`1
`
`1
`
`I
`
`MEDIATEK, Ex. 1006, Page 21
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 21 of 31
`
`US 6,646,639 B1
`
`Figure 32H
`
`P
`)
`
`N
`
`F
`
`initial state
`
`resulting state
`
`MEDIATEK, Ex. 1006, Page 22
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 22 of 31
`
`US 6,646,639 B1
`
`Figure 33
`
`(Conservative Culling with
`
`Z-Accept
`
`(culling stage)
`
`3300
`
`3302
`
`Z
`
`Storing near z-values each representative of
`a near z-value on an entity
`
`(culling stage)
`
`Marking entity with
`C Z-Accept Test1 )
`
`3304
`
`z
`
`3306
`
`(renderer)
`Conditionally reading z-values from memory
`based on marking using
`
`( Z-Accept Test2 )
`
`RETURN
`
`)
`
`MEDIATEK, Ex. 1006, Page 23
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 23 of 31
`
`US 6,646,639 B1
`
`Figure 34
`
`3400
`
`3402
`
`3405
`
`Mark current
`entity as
`ambiguous
`
`3404
`
`3406
`
`C Z-Accept Test1
`7
`Receive current entity
`
`NO
`
`Is far z-value of current
`entity in front of nearest
`stored z-value ?
`
`YES
`
`V
`
`Mark current entity as visible
`
`RETURN
`
`MEDIATEK, Ex. 1006, Page 24
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 24 of 31
`
`US 6,646,639 B1
`
`Figure 35
`
`3500
`
`3502
`
`7-Rendering entity with
`Z-Accept Test2
`
`Receive current entity to be
`rendered on a sample-by-sample
`basis
`
`3504
`
`YES
`Z-Accept Test2
`Is current sample marked as
`visible?
`
`3506
`
`3507
`
`NO
`
`7
`Read z-value from z-buffer to
`determine if current sample is visible
`
`YES
`41
`
`Write z-value to z-buffer and write
`color to image buffer
`
`3508
`
`3509
`
`YES
`
`RETURN
`
`MEDIATEK, Ex. 1006, Page 25
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 25 of 31
`
`US 6,646,639 B1
`
`Figure 35A
`
`3552
`
`3550
`
`PO
`
`P1
`
`P2
`
`FAR
`
`/
`3558
`
`3554
`
`NEAR
`
`3556
`
`MEDIATEK, Ex. 1006, Page 26
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 26 of 31
`
`US 6,646,639 B1
`
`3560
`
`PO
`
`FAR
`
`Figure 35B
`
`3560
`
`FAR
`
`Figure 35C
`
`P1
`
`IS1
`
`S2
`
`z2
`
`Z1
`
`3572 3574
`
`3570
`
`3576
`
`"Last Accepted"
`
`Was last sample that was
`not culled accepted?
`me of all
`true of all
`per
`sample samples In samples In
`region?
`tile?
`
`sample
`accepted or
`ambiguous?
`
`accepted
`
`accepted
`
`accepted
`
`accepted
`
`NEAR
`
`ambiguous
`
`ambiguous
`
`NEAR
`
`accepted
`
`accepted
`
`accepted
`
`yes
`
`yes
`
`yes
`
`yes
`
`yes
`
`yes
`
`no
`
`no
`
`yes
`
`yes
`
`yes
`
`yes
`
`yes
`
`yes
`
`yes
`
`no
`
`yes
`
`yes
`
`no
`
`yes
`
`FAR
`
`Figure 35D
`
`A
`
`z2
`
`z1
`
`NEAR
`
`Figure 35E
`
`MEDIATEK, Ex. 1006, Page 27
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 27 of 31
`
`US 6,646,639 B1
`
`Figure 36
`
`(Two-Pass Rendering with,
`Conservative Cullin
`
`(geometric processor - first pass)
`
`(culling stage - first pass)
`
`Creating an occlusion image requiring a first
`amount of storage
`
`(occlusion image buffers - first pass)
`
`Copy contents of occlusion image buffers or
`leave intact
`
`(geometric processor - second pass)
`
`Transforming objects
`
`(culling stage - second pass)
`
`Conservatively occlusion culling objects
`utilizing the occlusion image
`
`(renderer - second pass)
`
`Rendering remaining objects
`
`RETURN
`
`3600
`
`3602
`
`3604
`
`3605
`
`3606
`
`3608
`
`3610
`
`MEDIATEK, Ex. 1006, Page 28
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 28 of 31
`
`US 6,646,639 B1
`
`3690
`
`3692
`
`Figure 36A
`
`Fl Pass 1
`
`0
`0
`
`Fl Pass 2
`
`F2 Pass 1
`
`ca.
`0
`
`F2 Pass 2
`
`3691
`
`3693
`
`F3 Pass 1
`
`MEDIATEK, Ex. 1006, Page 29
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 29 of 31
`
`US 6,646,639 B1
`
`Figure 37
`
`3700
`
`C Conservative Stencil
`Culling
`
`Maintaining stencil values for regions at a
`plurality of levels
`
`3702
`.--.
`
`3704
`
`3706
`
`Determining whether the stencil value for a
`region at a coarser one of the levels is valid
`
`Conditionally enabling stencil culling based
`on the determination
`
`RETURN
`
`MEDIATEK, Ex. 1006, Page 30
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 30 of 31
`
`US 6,646,639 B1
`
`
`
`1
`
`34
`
`3750
`
`27
`18
`
`34 34
`34,34
`
`3774
`3572
`
`34
`34
`34
`34
`34
`34
`
`-34
`34
`34
`34
`
`34 34
`
`3754
`
`3760
`
`3754
`
`3758
`
`3754
`
`3756
`
`3770
`
`3762
`
`Figure 37B
`
`MEDIATEK, Ex. 1006, Page 31
`
`

`

`U.S. Patent
`
`Nov. 11, 2003
`
`Sheet 31 of 31
`
`US 6,646,639 B1
`
`3792
`
`3794
`
`COARSE
`RASTERIZER
`
`16x16
`Tiles
`
`RASTERIZER
`
`4x4
`Tiles
`lor
`
`/
`i
`
`/
`
`3790
`
`Figure 37C
`
`MEDIATEK, Ex. 1006, Page 32
`
`

`

`US 6,646,639 B1
`
`1
`MODIFIED METHOD AND APPARATUS FOR
`IMPROVED OCCLUSION CULLING IN
`GRAPHICS SYSTEMS
`
`RELATED APPLICATION(S)
`
`The present application is a continuation-in-part of parent
`applications entitled "METHOD AND APPARATUS FOR
`OCCLUSION CULLING IN GRAPHICS SYSTEMS" filed
`Jul. 22, 1998 under Ser. No. 09/121,317, and "SYSTEM,
`METHOD AND ARTICLE. OF MANUFACTURE FOR
`Z-VALUE AND STENCIL CULLING PRIOR TO REN-
`DERING IN A COMPUTER GRAPHICS PROCESSING
`PIPELINE" filed May 31, 2000 under Ser. No. 09/585,810.
`Further, the present application claims the priority date of a
`provisional application entitled "MODIFIED METHOD
`AND APPARATUS FOR IMPROVED OCCLUSION
`CULLING IN GRAPHICS SYSTEMS" filed May 23, 2001
`under Ser. No. 60/293,250.
`
`FIELD OF THE INVENTION
`
`The present invention relates to computer graphics, and
`more particularly to rendering images of three-dimensional
`scenes using z-buffering.
`
`BACKGROUND OF THE INVENTION
`
`Rendering is the process of making a perspective image of
`a scene from a stored geometric model. The rendered image
`is a two-dimensional array of pixels, suitable for display.
`The model is a description of the objects to be rendered
`in the descriptions of polygons together with other informa-
`tion related to the properties of the polygons.
`Part of the rendering process is the determination of
`occlusion, whereby the objects and portions of objects
`occluded from view by other objects in the scene are
`eliminated.
`As the performance of polygon rendering systems
`advances, the range of practical applications grows, fueling
`demand for ever more powerful systems capable of render-
`ing ever more complex scenes. There is a compelling need
`for low-cost high-performance systems capable of handling
`scenes with high depth complexity, i.e., densely occluded
`scenes (for example, a scene in which ten polygons overlap
`on the screen at each pixel, on average).
`There is presently an obstacle to achieving high perfor-
`mance in processing densely occluded scenes. In typical
`computer graphics systems, the model is stored on a host
`computer which sends scene polygons to a hardware raster-
`izer which renders them into the rasterizer's dedicated image
`memory. When rendering densely occluded scenes with such
`systems, the bandwidth of the rasterizer's image memory is
`often a performance bottleneck.
`Traffic between the rasterizer and its image memory
`increases in approximate proportion to the depth complexity
`of the scene. Consequently, frame rate decreases in approxi-
`mate proportion to depth complexity, resulting in poor
`performance for densely occluded scenes.
`A second potential bottleneck is the bandwidth of the bus
`connecting the host and the rasterizer, since the description
`of the scene may be very complex and needs to be sent on
`this bus to the rasterizer every frame. Although memory bus
`bandwidth has been increasing steadily, processor speed has
`been increasing faster than associated memory and bus
`speeds.
`Consequently, bandwidth limitations can become rela-
`tively more acute over time. In the prior art, designers of
`
`1
`5
`
`2
`0
`
`
`
`2 5
`
`35
`
`2
`hardware rasterizers have addressed the bottleneck between
`the rasterizer and bandwidth through interleaving and reduc-
`ing bandwidth requirements by using smart memory.
`Interleaving is commonly employed in high-performance
`5 graphics work stations. For example, the SGI Reality Engine
`achieves a pixel fill rate of roughly 80 megapixels per
`second using 80 banks of memory.
`An alternative approach to solving the bandwidth problem
`is called the smart memory technique. One example of this
`10 technique is the Pixel-Planes architecture. The memory
`system in this architecture takes as input a polygon defined
`by its edge equations and writes all of the pixels inside the
`polygon, so the effective bandwidth is very high for large
`polygons.
`Another smart-memory approach is "FBRAM," a
`memory-chip architecture with on-chip support for
`z-buffering and compositing. With such a chip, the read-
`modify-write cycle needed for z-buffering can be replaced
`with only writes, and as a result, the effective drawing
`bandwidth is higher than standard memory. All of these
`methods improve performance, but they involve additional
`expense, and they have other limitations. Considering cost
`first, these methods are relatively expensive which precludes
`their use in low-end PC and consumer systems that are very
`price sensitive.
`A typical low-cost three-dimensional rasterization system
`consists of a single rasterizer chip connected to a dedicated
`frame-buffer memory system, which in turn consists of a
`30 single bank of memory. Such a system cannot be highly
`interleaved because a full-screen image requires only a few
`memory chips (one 16 megabyte memory chip can store a
`1024 by 1024 by 16 bit image), and including additional
`memory chips is too expensive.
`Providing smart memory, such as FBRAM, is an option,
`but the chips usually used here are produced in much lower
`volumes than standard memory chips and are often consid-
`erably more expensive. Even when the cost of this option is
`justified, its performance can be inadequate when processing
`40 very densely occluded scenes.
`Moreover, neither interleaving nor smart memory
`addresses the root cause of inefficiency in processing
`densely occluded scenes, which is that most work is
`expended processing occluded geometry. Conventional ras-
`45 terization needs to traverse every pixel on every polygon,
`even if a polygon is entirely occluded.
`Hence, there is a need to incorporate occlusion culling
`into hardware renderers, by which is meant culling of
`occluded geometry before rasterization, so that memory
`so traffic during rasterization is devoted to processing only
`visible and nearly visible polygons. Interleaving, smart
`memory, and occlusion culling all improve performance in
`processing densely occluded scenes, and they can be used
`together or separately.
`55 While occlusion culling is new to hardware for
`z-buffering, it has been employed by software rendering
`algorithms. One important class of such techniques consists
`of hierarchical culling methods that operate in both object
`space and image space. Hierarchical object-space culling
`60 methods include the "hierarchical visibility" algorithm
`which organizes scene polygons in an octree and traverses
`octree cubes in near-to-far occlusion order, culling cubes if
`their front faces are occluded. A similar strategy for object-
`space culling that works for architectural scenes is to orga-
`65 nize a scene as rooms with "portals" (openings such as doors
`and windows), which permits any room not containing the
`viewpoint to be culled if its portals are occluded.
`
`MEDIATEK, Ex. 1006, Page 33
`
`

`

`US 6,646,639 B1
`
`3
`Both the hierarchical visibility method and the "rooms
`and portals" method require determining whether a polygon
`is visible without actually rendering it, an operation that will
`be referred to as a visibility query or v-query. For example,
`whether an octree cube is visible can be established by
`performing v-query on its front faces.
`The efficiency of these object-space culling methods
`depends on the speed of v-query, so there is a need to
`provide fast hardware support.
`Hierarchical image-space culling methods include hierar-
`chical z-buffering and hierarchical polygon tiling with cov-
`erage masks, both of which are loosely based on Wamock's
`recursive subdivision algorithm.
`With hierarchical z-buffering, z-buffer depth samples are
`maintained in a z-pyramid having NxN decimation from
`level to level (see N. Greene, M. Kass, and G. Miller,
`"Hierarchical Z-Buffer Visibility," Proceedings of SIG-
`GRAPH '93, July 1993). The finest level of the z-pyramid
`is an ordinary z-buffer. At the other levels of the pyramid,
`each z-value is the farthest z in the corresponding NxN
`region at the adjacent finer level. To maintain the z-pyramid,
`whenever a z-value in the finest level is changed, that value
`is propagated through the coarser levels of the pyramid.
`Since each entry in the pyramid represents the farthest
`visible z within a square region of the screen, a polygon is
`occluded within a pyramid cell if its nearest point within the
`cell is behind the corresponding z-pyramid value. Thus,
`often a polygon can be shown to be occluded by mapping it
`to the smallest enclosing z-pyramid cell and making a single
`depth comparison.
`When this test fails to cull a polygon, visibility can be
`established definitively by subdividing the enclosing image
`cell into an NxN grid of subcells and by comparing polygon
`depth to z-pyramid depth within the subcells.
`Recursive subdivision continues in subcells where the
`polygon is potentially visible, ultimately finding the visible
`image samples on a polygon or proving that the polygon is
`occluded. Since this culling procedure only traverses image
`cells where a polygon is potentially visible, it can greatly
`reduce computation and z-buffer memory traffic, compared
`to conventional rasterization, which needs to traverse every
`image sample on a polygon, even if the polygon is entirely
`occluded.
`Hierarchical z-buffering accelerates v-query as well as
`culling of occluded polygons.
`Another algorithm that performs image-space culling
`with hierarchical depth comparisons is described by Latham
`in U.S. Pat. No. 5,509,110, "Method for tree-structured
`hierarchical occlusion in image generators," April, 1996.
`Although Latham's algorithm does not employ a full-screen
`z-pyramid, it does maintain a depth hierarchy within rect-
`angular regions of the screen which is maintained by propa-
`gation of depth values.
`As an alternative to hierarchical z-buffering with a com-
`plete z-pyramid, a graphics accelerator could use a two-level
`depth hierarchy. Systems used for flight-simulation graphics
`can maintain a "zfar" value for each region of the screen.
`The screen regions are called spans and are typically 2x8
`pixels. Having spans enables "skip over" of regions where
`a primitive is occluded over an entire span.
`Another rendering algorithm which performs hierarchical
`culling in image space is hierarchical polygon tiling with
`coverage masks. If scene polygons are traversed in near-to-
`far occlusion order, resolving visibility only requires storing
`a coverage bit at each raster sample rather than a depth
`
`20
`
`
`
`4
`value, and with hierarchical polygon tiling, this coverage
`information is maintained hierarchically in a coverage pyra-
`mid having NxN decimation from level to level.
`Tiling is performed by recursive subdivision of image
`5 space, and since polygons are processed in near-to-far
`occlusion order, the basic tiling and visibility operations
`performed during subdivision can be performed efficiently
`with NxN coverage masks. This hierarchical tiling method
`can be modified to perform hierarchical z-buffering by
`10 maintaining a z-pyramid rather than a coverage pyramid and
`performing depth comparisons during the recursive subdi-
`vision procedure.
`This modified version of hierarchical tiling with coverage
`masks is believed to be the fastest algorithm available for
`is hierarchical z-buffering of polygons. However, for today's
`processors, such software implementations of this algorithm
`are not fast enough to render complex scenes in real time.
`A precursor to hierarchical polygon tiling with coverage
`masks is Meagher's method for rendering octrees, which
`renders the faces of octree cubes in near-to-far occlusion
`order using a similar hierarchical procedure.
`The ZZ-buff