United States Patent [19J
`Griffin et al.
`
`111111111111111111111111111111111111111111111111111111111111111111111111111
`US00588073 7 A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,880,737
`Mar. 9, 1999
`
`(54) METHOD AND SYSTEM FOR ACCESSING
`TEXTURE DATA IN ENVIRONMENTS WITH
`HIGH lATENCY IN A GRAPHICS
`RENDERING SYSTEM
`
`[75]
`
`inventors: Kent E. Griffin, Bellevue; Mark L.
`Kenworthy, Duvall; James E. Veres,
`Woodinville; Joseph W. Chauvin,
`Issaquah; M ichael A. 1belle, Bellevue;
`Howard Good, Seattle, all of Wash.
`
`[73] A'lSignee: Microsoft Corporation, Redmond,
`Wash.
`
`Slater, Mel, '·Segments on Bit-mapped Graphics Displays",
`Software-Practice and Experience, vol. 16(11), pp.
`965-980, Nov. 1986.
`
`Chrysanthou, Y and Slater, M, ''Computing Dynamic
`Changes to BSP Trees", Compwer graphics Forum, vol. II,
`No. 3, Conference Issue, pp. C-32 1 to C-342, Sep. 7-11,
`1992.
`
`Slater, Mel, et al, "Liberation from Rectangle: A Tiling
`Method for Dynamic Modification of Objects on Raster
`Displays", £urographies '88, Confereoce date, Sep. 12-16,
`1988, pp. 381-392, 1988.
`
`[21) Appl. No.: 670,553
`[22] Filed:
`Jun.27, 1996
`
`Related U.S. Application Data
`
`(63] Continuation-in-part of Ser. No. 560,114, Nov. 17, 1995,
`abandoned, and a continuation of Ser. No. 511 ,553, Aug. 4,
`1995, abandoned.
`Int. C l.6
`......................................... ........... . G06T 11/40
`[51]
`[52] U.S. C l . .............................................................. 345/430
`(58] Field of Search ..................................... 345/419-420,
`345/430-431, 433-7, 501-5
`
`[56]
`
`References Citt.>d
`U.S. PATENT DOCUMENTS
`
`4,631,690 12/ 1986 Conbout ct al. ........................ 364/5 18
`4,645,459
`2/ 1987 Graf ct al.
`................................ 434/43
`5,363,475 11/1994 Baker et al. ............................ 345/422
`5,522,018
`5/1996 Takeda et al. .......................... 345/422
`5,563,989 L0/ 1996 Billyard .................................. 345/426
`5,586,234 12/1996 Sakuraba ct al. ....................... 345/430
`1/1997 Duluk, .Jr ................................ 345/ 122
`5,596,686
`1/1997 Watkins .................................. 345/441
`5,598,517
`5,630,043
`5/1997 Ublin ...................................... 345/425
`5,634,850
`6/ 1997 Kitabara ct al. .......................... 463/33
`9/1997 Volk et al. .............................. 345/327
`5,673,401
`5,684,935 11/1997 Demcsa, 111 ct al ................... 345/419
`5,729,669
`5/ 1998 Appleton ................................. 345/422
`OTilER PUBLICATIONS
`Slater, Mel, "An Algorithm to support 3D Interaction on
`Relative ly Low Performance Graphics Systems", Comput.
`& Graphics, vol. 16, No. 3, pp. 311-315, 1992.
`
`(List continued on next page.)
`
`Primary Examiner-Rudolph J. Buche!, Jr.
`Attorney, Agent, or Firm--Klarquist Sparkman Campbell
`Leigh & Wbinston LLP
`
`[57]
`
`ABSTRACT
`
`A system for accessing texture data in a graphics rendering
`system allows texture data to be stored in memories with
`high latency or in a compressed formaL 1be system utilizes
`a texture cache to temporarily store blocks of texture data
`retrieved from an external memory during rendering opera(cid:173)
`tions. ln one implementation, geometric primitives are
`stored in a queue long enough to absorb the latency of
`fetching and possibly decompressing :a texture block. The
`geometric primitives are converted into texture block
`references, and these references are used to fetch texture
`blocks from memory. A rasterizer rasterizes each geometric
`primitives as the necessary texrure data becomes available io
`the texture cache. ln another implementation, geometric
`prim itives are converted imo pixels, including a pixel
`address, color data, and a texture request. These pixels are
`stored in a queue long enough to absorb the latency of a
`texture block fetch. ll1e texture requests are read from the
`queue and used to fetch the appropriate texture blocks. As
`texture data becomes available in the texture cache, tbe
`texture data is sampled as necessary and combined with the
`pixel data read from the queue to compute output pixels.
`
`35 Claims, 26 Drawing Sheets
`
`0001
`
`Volkswagen 1004
`
`

`
`5,880,737
`Page 2
`
`OTI-TER PUBLICATIONS
`
`Slater, Mel, et al, ''Liberation from Flatland: 3D Interaction
`Based on the Desktop Bat", Eurograplzics '91, pp. 209-221,
`1991.
`Deering, "Explorations of Display Interfaces for Virtual
`Reality", IEEE Virtual Reality, 1993 lnteroational Sympo(cid:173)
`sium, pp. 141-147, l993.
`Reichlen, "Sparccbair: A One Hundred Million Pixel Dis(cid:173)
`play", IEEE Virtual Reality, 1993 International Symposium,
`pp. 300-307, May 28, 1993.
`Foley, James D., et at, "Computer Graphics: Principles and
`Practices", Addison-Wesley Publishing Co., 2nd ed. pp.
`806-813,885-921,1990.
`Collaborative work, "Pi.xel-Planes", Pixel Planes Home
`Page, url-hllp://www.cs.unc.edur pxpl/, University of
`North Carolina, pp. 1-25, update, Sep. 26, 1995.
`Oak Technology WARPS Press Releases, "Oak Technology
`Sets New Standard for 3D Realism with Breakthrough
`WARP 5 Chip Architecture", Atlanta, GA, Jun. 19, 1997.
`Bergman, et al "lmage Rendering by Aclaptiw Refinement",
`ACM Siggraph '86, vol. 20, No.4, pp. 29-37, Aug. 18-22,
`1986.
`Chen, Chein-Liang, et al, ·'A Raster Engine for Computer
`Graphics and Image Compositing", Abstract, APCCAS '94,
`IEEE, pp. 103--108, Dec. 5-8, 1994.
`Yoo, Terry S., et at, ''Direct Visualization of Volume Data",
`IEEE Computer Graphics and Applications Magazine, vol.
`12, No. 4, pp. 63--71, Jul. 92.
`Bove, Jr., V. Michael, et a!, "Real-Time Decocting and
`Display of Structured Video", IEEE Multimedia, 1994 inter(cid:173)
`national Conference, pp. 456-462, 1994.
`Heb, Andreas, et at, "Three Dimensional Reconstruction of
`Brains from 2-Deoxyglucosc Serial Section Autoradio(cid:173)
`graphs",Jmage Processing, 1994 international Conference,
`vol. 3, pp. 290-294, 1994.
`Hu, Lincoln, "Computer Graphics in Visual Effects", COM(cid:173)
`PCON Spring '92, IEEE Computer Society inlernational
`Conference, pp. 472-474, L992.
`
`Runyon, Kenneth R., "Advanced Graphics Processor",Digi(cid:173)
`tal Avionics Systems, 1993 Conference, pp. 394-399, 1993.
`Crawfis, Roger A., et at," A Scientific Visualization Synthe(cid:173)
`sizer", Visuali.ztuion, 1991 Conference, pp. 262-267, 1991.
`Haeberli, Paul, et al, ''The Accumulation Buffer: Hardware
`Support for High-Quality Rendering", ACM Computer
`Graphics, vol. 24, No.4, pp. 309-318, Aug. L990.
`Regan, Mallhew and Ronald Pose, ·'Priority Rendering witb
`a Virtual Reality Address Recalculation Pipeline", ACM
`Siggrap!t,
`'94, Computer Grpallics Proceedings, Annual
`Conference Series, pp. 155-162, 1994.
`Regan, Mauhew and Ronald Pose, ''Low Latency Virtual
`Reality Display System", Technical report No. 92/166,
`Monash University, Victoria, Australia. pp. l-13, Sep. 1992.
`Regan, Maubew and Ronald Pose, "A Interactive Graphics
`Display Architecture", IEEE Virwal Reality, 1993 interna(cid:173)
`tional Symposium, pp. 293- 299, 1993.
`Torborg, Jay, et al, "Talisman: Commodity Realtime 3D
`Graphics for the PC",ACM Siggraph, Conference Proceed(cid:173)
`ings, pp. 353-363, Aug. 4-9, 1996.
`Deering, Michael, et at, "Leo: A System for Cost Effective
`3D Shaded Graphics", ACM Siggraph, Conference Proceed(cid:173)
`ings, pp. 101- 108, Aug. l- 6, 1993.
`Akerly, Kurt, " RealityEngine Graphics", ACM Siggrnph,
`Conference Proceeding, pp. 109-116, Aug. 1-6, 1993.
`Mcmillan, Leonard, et a!, "Plenoptic Modeling: An Image(cid:173)
`-Based Rendering System", ACM Siggraph, Conference
`Proceedings, pp. 39-46, Aug. 6-11, 1995.
`Tan, Wee-Chiew, et at, ''Low-Power polygon Renderer for
`Computer Graphics", Application Specific Array Proces(cid:173)
`sors, 1993 International Conference, pp. 200-213, 1993.
`Bae, Seong-Ok, et al, "Patch Rendering: A New Parallel
`Hardware Architecture for Fast Polygon Rendering", Cir(cid:173)
`cuits and Systems, 1991/EEE International Symposium, pp.
`307Q-3073, 1.99 1.
`
`0002
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 1 of 26
`
`5,880,737
`
`100
`
`FIG.l
`
`106
`
`IMAGE
`PREPROCESSOR
`
`104
`
`IMAGE
`PROCESSOR
`
`SYSTEM INTERFACE
`
`110
`
`108
`
`0003
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 2 of 26
`
`5,880,737
`
`FIG. 2
`
`PROCESSOR
`
`132
`
`134
`
`130 I
`
`MEMORY
`CONTROL
`
`MAIN MEMORY
`
`136
`
`BUS
`
`146
`
`144
`
`INPUT DEVICE(S)
`
`IMAGE
`PROCESSING
`HARDWARE
`
`140
`
`0004
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 3 of 26
`
`5,880,737
`
`FIG. 3
`
`160
`
`(
`
`GRAPHICS SUPPORT SOFTWARE
`
`~t
`
`HARDWARE ABSTRACTION LAYER
`
`~t
`
`!'-.
`162
`
`PROCESSOR
`(DSP)
`
`'\.
`166
`
`OTHER IMAGE
`PROCESSING
`HARDWARE
`
`1\1
`64
`
`1)8
`
`0005
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 4 of 26
`
`5,880,737
`
`FIG. 4A
`
`r - - - - - - - -1
`1 SHARED MEMORY 1
`
`I §Mx8
`2Mx8
`I RDRAM RDRAM
`I
`
`._ ___ f____
`
`l---216
`I
`I
`
`:
`
`.-------1
`I
`
`,.
`
`o
`~
`>
`~
`rx:
`)_
`
`212
`)
`
`<3
`0..
`
`ALPHA ~
`1
`I J BUFFER
`I
`I
`.....__... GSPRITE ~
`DAC
`DSP 18 TILER~ ENGINE N
`~l-._..-.---1
`\__ ~ C I ~ COLOR ~ 214
`1 BUFFER
`I
`I
`I
`'---------~I
`L--~-
`
`200
`
`204
`
`176
`
`210
`
`0006
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 5 of 26
`
`5,880,737
`
`FIG. 4B
`
`462
`
`464
`I
`
`RASTERIZER
`
`/468
`
`(410
`
`_1
`
`/466 ~
`
`ANTI-ALIAS! NG
`ENGINE
`
`~~ FRAG. BUFFERS~ PIXEL ENGINE
`
`PIXEL BUFFERS
`
`I
`
`-\
`
`472
`
`0007
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 6 of 26
`
`5,880,737
`
`DETERMINE
`OBJECT AND
`VIEWPOINT
`LOCATIONS
`
`240
`
`SELECT
`POTENTIALLY
`VISIBLE
`OBJECTS
`
`242
`
`DETERMINE
`SPRITE
`CONFIGURATION
`
`FIG. 5A
`
`(.._ __ E_N_D _ __..)No
`
`DIVIDE INTO
`CHUNKS
`
`248
`
`NO
`
`250
`
`YES
`
`TRANSFORM
`CHUNK
`
`252
`
`0008
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 7 of 26
`
`5,880,737
`
`FIG. 5B
`
`RESOLVE PIXELS
`
`258
`
`YES
`
`TILE POLYGON
`
`256
`
`COMPRESS CHUNK
`
`..__ 260
`
`STORE CHUNK
`
`262
`
`0009
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 8 of 26
`
`5,880,737
`
`DETERMINE
`GSPRITE DEPTH
`ORDER
`
`FIG. 6
`
`YES
`
`CALCULATE
`SPRITE
`TRANSFORMS
`
`BUILD SPRITE
`DISPLAY LIST
`
`286
`
`>----NO----.
`
`WAIT FOR
`FRAME SYNC
`
`290
`
`NO
`
`YES
`
`TRANSFORM
`SPRITE
`
`294
`
`COMPOSITE
`PIXELS
`
`298
`
`DISPLAY PIXELS
`
`0010
`
`

`
`00 = ~ ....:a
`
`....:a
`(.N
`
`00
`01
`
`~
`
`0\
`N
`~
`Q
`\0
`
`~
`
`~ ....
`g3
`
`\0
`~
`::c
`~
`~
`
`~
`
`~ = f""f-
`""= ~
`•
`\J).
`0 •
`
`f""f(cid:173)
`
`GSPRITES
`
`TRANSFORMED
`
`DISPLAY
`
`COMPOSITE AND
`
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`TRANSFORMS
`
`GSPRITE
`
`CALCULATE
`
`314
`
`GSPRITES
`
`TRANSFORMED
`
`DISPLAY
`
`COMPOSITE AND
`
`I
`I
`I
`I
`I
`
`I
`
`I
`I
`I
`I
`
`TRANSFORMS
`
`GSPRITE
`
`CALCULATE
`
`0011
`
`FRAME
`
`FRAME
`
`FRAME
`
`FRAME
`
`FIG. 7
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 10 of 26
`
`5,880,737
`
`FIG. 8
`
`OSP
`
`336
`
`I
`
`- - - - - - - - - - - - - - - I
`I
`I
`I
`I
`I 1-----7-- _______ I
`
`DSPCORE
`
`:
`
`r 340
`
`MEMORY
`INTERFACE I+-
`
`(342
`
`0::: w
`...J
`i=
`0
`1-
`
`PCIBUS
`•·r"T""""""""f~ CONTROLLER 1+-
`
`338
`
`{344
`
`, {346
`
`DISPLAY
`MMU
`
`DATA
`CONVERTER
`AND FORMATTER
`
`0012
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 11 of 26
`
`5,880,737
`
`382
`
`VERTEX
`CONTROL
`REGISTERS
`
`1'...384
`
`'- 386
`
`SETUP
`ENGINE
`
`L 378
`FIG. 9A
`,--- -- --- - --------------- -?t
`TILER
`· - · - · -SETUP · - · -388 · - · - · - · - · - ·I :
`r · - · - · -
`.
`I
`I
`I
`VERTEX INPUT r+
`r+
`I
`.
`~
`I
`PROCESSOR
`I
`I
`I
`I 394
`-·---· - · -· -· - ·-·-·-·-· . - · - -- - - ·-.,r
`.
`.......... ····-·sc·AN·······:
`CONVERT
`:
`.
`.
`
`TEXTURE
`ADDRESS
`GENERATOR
`
`392)
`
`1+-
`
`_M
`TEXTURE READ
`QUEUE
`~ "'- 390
`COMMAND
`
`&MEMORY h
`
`CONTROL
`
`380
`
`~
`COMPRESSED
`CACHE
`
`416
`
`I
`I
`
`") :
`
`PRIMITIVE
`REGISTERS
`3~6 ~98
`
`.
`
`.
`
`SCAN CONVERT
`ENGINE
`
`.
`.
`.
`L ......... ... ........ -.. -.... . .. . .. .. --..
`
`ENGINE \I 410
`I L\ COMPRESSION A
`....._ ____ __ _
`
`~
`I
`z
`f+--
`(/)
`I
`...J
`0
`w
`I
`z
`Ci)
`h404
`z
`rnw
`I
`<
`wz
`TEXTURE FILTER
`a:::- ~ TEXTURE CACHE ~
`:I:
`I
`Cl..(!)
`ENGINE
`()
`:::Ez
`I
`CJ)
`ow
`::J
`I
`c:c
`()
`w
`:::E
`I
`0
`~
`I ~
`w~ I
`z
`I
`C)
`z
`I
`w
`w
`I
`.....
`I
`D:
`Cl..
`I
`(/)
`(!)
`I
`a: I
`I
`I
`I
`I
`
`I
`
`~2
`
`(412
`
`/
`
`ANTI-ALIASING
`
`(/)
`0
`0
`.....
`
`~
`
`'-
`400
`
`,r
`
`PIXEL
`~
`ENGINE
`
`~6
`
`~
`
`FRAGMENT
`BUFFER($)
`\
`
`PIXEL
`BUFFERS
`\
`408
`
`I
`I
`
`ENGINE
`
`414
`
`- --
`
`0013
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 12 of 26
`
`5,880,737
`
`TILER
`
`SETUP
`
`PROCESSOR
`
`r-+
`
`SETUP
`ENGINE
`
`FIG. 9B
`378
`381
`~--·-·-·-·-·-·-·-·-·-·-·-·--~----~
`I
`l j
`388
`'
`I
`I
`VERTEX
`I
`-t VERTEX INPUT r-+
`CONTROL
`I
`I
`REGISTERS
`I
`I
`I
`~ 395
`'-- 386
`1'...384
`· - ------
`- --·-·-·-·-·-·-·-· - ·-·-· -
`'
`...... sc·AN·······.
`...........
`CONVERT
`
`393 TEXTURE READ
`...__.
`QUEUE
`
`' - -
`
`f
`
`)391
`
`'
`
`+
`COMMAND
`
`CONTROL
`
`TEXTURE CACHE
`CONTROL
`
`380
`
`:
`
`PRIMITIVE
`REGISTERS
`
`396 ~ r398
`
`~
`SCAN CONVERT
`ENGINE
`
`; .... ·•·· ........... ......
`
`TEXTURE
`REFERENCE
`DATA QUEUE
`+
`j-. TEXTURE FILTER
`ENGINE
`I"-
`(
`401
`402
`
`r+
`
`/
`416
`
`I
`
`"J:
`I
`I
`I
`I
`I
`
`(/)
`...J
`w
`z
`z
`<(
`:I:
`u
`en
`=>
`m
`::!
`~
`u.i
`z
`(.!)
`z
`w
`w
`1-
`a:
`a..
`en
`(.!)
`~
`(/)
`c
`0
`1-
`
`& MEMORY 11
`~
`~04 399
`·w
`~
`a.. :I:
`:!u ~ z
`w
`0
`0<(
`:I:
`c;;
`uu
`(..)
`<(
`(/)W
`u
`wz
`a::-
`---+ w
`a..C>
`0::
`:EZ
`=>
`ow
`1-
`u
`X
`w
`w
`c
`1-
`~
`v
`ENGINE ~
`L\ COMPRESSION A
`
`•
`
`'
`
`406
`
`~
`1-
`
`PIXEL
`FRAGMENT ~
`ENGINE
`BUFFER(S)
`
`412 "---
`
`ANTI-ALIASING
`
`'
`
`410
`
`PIXEL
`BUFFERS
`
`' 408
`
`ENGINE
`
`414
`
`~-------------------------1
`
`0014
`
`

`
`l
`l
`VERTEX INPUT
`l ~ PROCESSOR
`I
`I
`I
`I -. -
`I
`I
`I
`I
`:
`
`393 TEXTURE READ
`.._.
`QUEUE
`380
`-,
`
`1
`
`39
`\
`
`•
`}
`COMMAND
`& MEMORY
`I
`CONTROL
`., ) ~'--r-~----'
`0:!!! ~04 ............. .___,
`=eo 4
`O<t
`0()
`
`SETUP
`ENGINE AND
`PRE-
`RASTERIZER
`
`f-+
`
`.
`
`397
`
`:
`
`SCAN CONVERT
`ENGINE
`
`:.'-.. -.. r-.. """'1. • . . - . . - . -. . -. . ....., •• ' •• --' . . . .
`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 13 of 26
`
`5,880,737
`
`TILER
`
`/
`
`378
`
`383
`
`FIG. 9C
`:- r: = :-_-: = -----: =-=--~iru~-:--=---=-3;9 -_-=- :-_--: = :-_-: = -f
`
`f-+
`
`VERTEX
`CONTROL
`REGISTERS
`\.... 387
`i'-.. 384
`. - .-.-.-. -
`. -
`
`. - .-. -
`
`·l
`~ l
`jl
`·1
`II
`.. :.: .:.~.~-~:.:-=-.:.::-.V
`·.·l
`SCAN
`CONVERT
`,.......JL_..=::::::=::=:::::......., ~I
`; I
`PRIMITIVE
`; I
`REGISTERS
`TEXTURE CACHE : ...___.,.--r.....,lr-----' ; I
`396 + rJ98
`~I
`CONTROL
`:
`;1
`'
`
`..
`
`41("
`
`U)
`
`...J w
`z z
`< J:
`0
`U)
`
`:::::1 m :e
`~
`w z
`(!) z
`w
`w
`....
`~
`0..
`U)
`(!)
`
`0..
`U) c
`0 ....
`
`w
`z
`0
`:I:
`0
`U)
`~ ~
`(3
`~ (5 r--+ w _...
`;:ez
`ow
`o:::
`5
`:::::~
`frl
`"""'~ 402
`c
`
`TEXTURE FILTER
`ENGINE
`
`....
`
`(412
`
`PIXEL
`FRAGMENT ~
`ENGINE
`BUFFER(S)
`
`ANTI-ALIASING
`
`'
`
`406
`
`~
`....
`
`PIXEL
`BUFFERS
`
`v
`'
`ENGINE \I 410
`' 408
`
`\
`
`l
`COMPRESSION
`j7t14
`i
`\
`ENGINE
`~------------ - ------------1
`
`0015
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 14 of 26
`
`5,880,737
`
`FIG. 10
`
`SETUP
`PRIMITIVES
`
`H RASTERIZER ~
`417
`
`(
`416
`
`418
`
`..
`TEXTURE
`REFERENCE
`DATA QUEUE
`
`MEMORY
`
`f-+
`
`(
`419
`
`TEXTURE
`BLOCK
`FETCH
`
`(
`420
`
`422 \
`
`r---.
`
`TEXTURE
`CACHE
`
`f-+
`
`TEXTURE
`FILTER
`
`7
`421
`
`,
`
`FILTERED
`TEXTURED
`OUTPUT
`PIXELS
`(
`423
`
`0016
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 15 of 26
`
`5,880,737
`
`FIG. 11
`
`/
`
`426
`
`POST
`PRE-
`SETUP
`PRIMITIVES 1------. RASTERIZER 1---~ RASTERIZER ~
`
`TEXTURE
`BLOCK FETCH
`QUEUE
`
`FILTERED
`TEXTURED
`OUTPUT
`PIXELS
`
`TEXTURE
`MEMORY ~ BLOCK
`FETCH
`\
`429
`
`\
`430
`
`..
`
`TEXTURE
`BLOCK
`CACHE
`\
`431
`
`0017
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 16 of 26
`
`5,880,737
`
`FIG.12A
`
`GSPRITE ENGINE
`
`/442
`
`436
`
`I
`
`r- 440
`I 444
`,---+-------+-------+---,
`I
`I
`rr
`I
`-----:: ,---------------- __ _ -..-~
`I
`I
`
`I
`I
`I
`I
`I
`I
`
`DISPLAY
`CONTROL
`PROCESSOR
`
`f-+
`
`GSPRITE
`HEADER
`REGISTER
`
`f-+
`
`GSPRITE
`HEADER
`DECODER
`
`GSPRITE COMPOSITION SETUP
`
`INTERFACE
`·~ CONTROL
`
`J
`
`c::: w
`
`...J
`~
`:e
`0 c::: u.
`
`1
`
`~ 438
`z
`'/" 450
`0
`c
`w
`(/)
`(/)w
`(/)W
`(/)::I: wz
`c:::-
`wu. c..<!>
`c:::<( ~z
`ow
`~(.)
`(.)
`0
`w
`(.)
`0
`
`\sa~
`
`\
`448
`+
`
`GSPRITE
`CACHE
`
`r446
`GSPRITE
`GSPRITE
`DATA ADDRESS ~ READ QUEUE
`GENERATOR
`r _454~ __ -= ...,
`c:::
`I w
`I
`u.
`IMAGE
`I u.
`I
`PROCESSOR
`;:::)
`I
`ADDRESS
`I GENERATOR
`. I
`L
`I
`I
`I
`
`I
`
`-u.~
`
`GSPRITE
`FILTER
`ENGINE
`
`_l
`
`4~2
`
`I z
`(!)
`I 1-
`I
`(/)
`0
`I
`c..
`:::E
`I
`0
`.J._ (.)
`~0
`I
`I
`1-
`I
`456_j..-
`I IMAGE PROCESSOR!
`L _______ l
`
`_1..
`or
`
`0018
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 17 of 26
`
`5,880,737
`
`FIG. 12B
`
`GSPRITE ENGINE
`
`436
`
`/
`
`440
`
`/
`
`442
`
`/
`
`-.
`
`GSPRITE
`GSPRITE
`HEADER ~ HEADER
`REGISTER
`DECODER
`
`I 1-
`
`-. • INTERFACEf-11 READ
`14
`-
`CONTROL QUEUE
`
`444 I
`~- -- -+ - - --- - - t- - -- --- f--- -I
`I
`I
`DISPLAY
`1
`1
`CONTROL
`I
`1
`I PROCESSOR
`I
`I
`I
`I
`GSPRITE COMPOSITION SETUP
`L_ ---- --- ----- --- ---- - J
`r 447
`DATA A DDRESS
`GENERATOR +-
`(PRE-
`RASTERIZER)
`
`GSPRITE
`QUEUE
`\
`
`\
`
`453
`
`L.....--~--.::......._:---' ~5~~ - v - - - ,
`449
`I
`1
`.----
`....---~-----. I
`I
`IMAGE
`CACHE
`PROCESSOR
`I ~
`1
`451 ............
`CONTROL
`ADDRESS ~~
`1
`1 GENERATOR
`1 ~
`ffi ...J
`r---~·H (RASTERIZER)
`I
`I ~~
`I
`1- ~
`I
`I
`I
`I ~8
`+
`I
`I ~
`I
`GSPRITE
`4
`FILTER ~0
`0
`I
`I
`ENGINE
`456~
`I
`~AGE P~CESSOR:
`
`438
`
`~
`w
`...J
`t=
`::!!!
`0
`~ u.
`
`I ~
`~ 450
`z
`0
`0
`w
`wz __.
`Ci)
`cnw
`cnw
`cn::z::
`wo f---+
`~-
`~<
`a.<!>
`:!!z
`~0
`ow
`0
`0 w
`0
`0
`
`\sa ~
`
`GSPRITE
`CACHE
`
`452 )
`
`457
`
`455
`
`0019
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 18 of 26
`
`5,880,737
`
`FIG. 13
`
`COMPOSITING BUFFER
`
`480
`
`I
`
`f..--484
`
`...
`
`MEMORY
`CONTROL
`
`1 v 488
`
`SCAN LINE
`BUFFERS
`1344x32x24
`
`'-
`
`_..
`
`482 ~
`
`COMPOSITING
`LOGIC
`
`ALPHA BUFFERS
`
`1344x32x8 ~
`486
`
`(
`UJ z
`(!) z
`
`UJ
`UJ
`1-
`~
`c..
`(/)
`(!)
`==
`0
`0::
`LL.
`
`0020
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 19 of 26
`
`5,880,737
`
`514
`
`FIG. 14
`
`DAC
`
`COLOR
`LUT
`
`516
`
`COLOR
`:
`I
`I
`LUT
`___ T __ ...J
`518
`
`526
`
`524
`
`PIXEL DATA
`ROUTING
`
`FROM
`DSP
`
`CLOCK
`GENERATOR
`
`0021
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 20 of 26
`
`5,880,737
`
`FIG. 15A
`
`START
`
`VERTEX INPUT
`PROCESSOR
`PARSES THE
`INPUT STREAM
`
`STORE
`TRIANGLE INFO
`IN VERTEX
`CONTROL
`REGISTERS
`
`914
`
`916
`
`SETUP ENGINE
`CALCULATES
`EDGE
`EQUATIONS
`
`918
`
`TEXTURE
`ADDRESS
`GENERATOR
`DETERMINES
`ADDRESS OF
`TEXTURE
`CHUNKS
`
`924
`
`920
`
`SETUP ENGINE
`PASSES
`SETUP ENGINE
`TEXTURE
`PASSES EDGE
`EQUATIONS TO 1-----------+~ ADDRESSES TO
`SCAN CONVERT
`TEXTURE READ
`BLOCK
`QUEUE
`
`922
`
`0022
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 21 of 26
`
`5,880,737
`
`FIG. lSB
`
`TEXTURE READ
`REQUESTS ARE
`SENT TO THE
`COMMAND AND
`MEMORY
`CONTROL
`BLOCK
`
`926
`
`MEMORY
`CONTROL
`BLOCK FETCHES
`TEXTURE DATA
`
`928
`
`936
`
`938
`
`SCAN CONVERT
`PASSES
`TEXTURE
`ADDRESSES TO
`THE TEXTURE
`FILTER ENGINE
`
`934
`
`SCAN CONVERT
`READS EDGE
`EQUATIONS
`FROM THE
`PRIMITIVE
`REGISTERS
`
`932
`
`TEXTURE FILTER
`PASSES INFO TO
`SCAN CONVERT
`ENGINE
`
`SCAN CONVERT
`ENGINE
`CONVERTS
`TRIANGLE DATA
`
`930
`
`TEXTURE
`BLOCKS
`DECOMPRESSED
`
`DECOMPRESSED
`TEXTURE BLOCK
`CACHED IN
`TEXTURE CACHE
`
`SCAN CONVERT
`ENGINE PASSES
`INFO TO PIXEL
`ENGINE
`
`944
`
`PIXEL ENGINE
`PERFORMS
`CALCULATIONS
`
`0023
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 22 of 26
`
`5,880,737
`
`FIG.15C
`
`START
`
`1
`
`VERTEX INPUT
`PROCESSOR
`PARSES THE h
`INPUT STREAM
`
`947
`
`~
`
`STORE TRIANGLE
`INFO IN VERTEX
`CONTROL
`REGISTERS
`
`h
`
`948
`
`SETUP ENGINE
`CALCULATES h
`EDGE EQUATIONS
`
`949
`
`~
`
`SETUP ENGINE h
`
`PASSES EDGE
`EQUATIONS TO
`SCAN CONVERT
`BLOCK
`
`950
`
`0024
`
`TO
`FIG.
`15D
`~
`
`SCAN CONVERT I>
`ENGINE
`952
`CONVERTS
`TRIANGLE DATA
`
`j~
`
`SCAN
`CONVERT
`READS EDGE
`EQUATIONS FROM
`THE PRIMITIVE
`REGISTERS
`
`I>
`951
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 23 of 26
`
`5,880,737
`
`FIG.lSD
`
`FROM
`FIG.
`15C
`
`PLACE PIXEL
`DATA AND
`
`TEXTURE INFO IN --g53
`
`QUEUE
`
`/
`
`958
`
`959
`
`SCAN CONVERT
`PASSES
`DECOMPRESSED
`TEXTURE
`..
`TEXTURE BLOCK
`t---~.. ADDRESSES TO
`CACHED IN
`TEXTURE CACHE
`THE TEXTURE
`FILTER ENGINE
`
`~ --
`
`TO
`ANTI-
`ALIASING
`ENGINE
`
`)
`
`T
`
`960
`
`~,
`
`/
`
`957
`
`TEXTURE CACHE
`CONTROL
`FETCHES
`TEXTURE
`BLOCKS
`
`r----
`954
`
`TEXTURE
`BLOCKS
`DECOMPRESSED
`
`/
`
`956
`
`TEXTURE READ V 955
`MEMORY
`REQUESTS ARE
`SENT TO THE
`CONTROL
`...
`COMMAND AND t------~ .. BLOCK FETCHES
`MEMORY
`CONTROL
`BLOCK
`
`TEXTURE DATA
`
`0025
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 24 of 26
`
`5,880,737
`
`FIG. 15E
`
`START
`
`lr
`
`VERTEX INPUT
`PROCESSOR
`PARSES THE h
`INPUT STREAM
`
`961
`
`r
`QUEUE
`PRIMITIVES IN
`VERTEX
`CONTROL
`REGISTERS
`
`I>
`962
`
`h
`
`963
`
`PRE-
`RASTERIZER
`CONVERTS
`PRIMITIVES
`
`0026
`
`TO
`FIG.
`15F
`
`,j~
`
`TEXTURE CACHE h
`
`CONTROL
`FETCHES
`TEXTURE
`BLOCKS
`
`965
`
`PRE-
`RASTERIZER h
`PASSES READ
`REQUESTS TO
`THE TEXTURE
`CACHE
`CONTROL
`
`964
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 25 of 26
`
`5,880,737
`
`FIG. 15F
`
`FROM
`FIG.
`15E
`
`TEXTURE READ
`REQUESTS ARE
`SENT TO THE
`COMMAND AND r--
`MEMORY
`CONTROL
`BLOCK
`
`989
`
`/" 994
`
`_,r- 995
`
`SCAN CONVERT
`TEXTURE FILTER
`PASSES
`PASSES INFO TO
`TEXTURE
`ADDRESSES TO 1-------+~ SCAN CONVERT
`THE TEXTURE
`ENGINE
`FILTER ENGINE
`
`/" 993
`
`SCAN CONVERT
`READS EDGE
`EQUATIONS
`FROM THE
`PRIMITIVE
`REGISTERS
`
`_,r- 992
`
`MEMORY
`CONTROL
`BLOCK FETCHES r--
`990
`TEXTURE DATA
`
`v- 991
`
`SCAN CONVERT
`ENGINE
`CONVERTS
`TRIANGLE DATA
`
`DECOMPRESSED
`TEXTURE BLOCK
`TEXTURE
`1--------+~ CACHED IN
`BLOCKS
`DECOMPRESSED
`TEXTURECACHE
`
`SCAN CONVERT
`ENGINE PASSES
`INFO TO PIXEL
`ENGINE
`
`~ 999
`
`TO
`ANTI(cid:173)
`ALIASING
`ENGINE
`
`/998
`
`PIXEL ENGINE
`PERFORMS
`CALCULATIONS
`
`0027
`
`

`
`U.S. Patent
`
`Mar. 9, 1999
`
`Sheet 26 of 26
`
`5,880,737
`
`FIG. 16
`
`(
`
`660
`
`L__662
`
`~668
`
`TRANSFORMATION ~
`ENGINE
`
`TILER
`
`TILER
`COMPRESSION
`ENGINE
`
`,----- - - - -
`L
`
`664
`
`-,
`I
`I
`I
`I
`I
`I
`670 I
`I
`I
`I
`I
`I
`I
`I
`I
`L---------I
`
`TEXTURE
`MEMORY
`
`GSPRITE
`MEMORY
`
`676
`
`I
`I
`I
`
`I
`
`( 666
`
`TILER
`DECOMPRESSION
`ENGINE
`
`h
`
`672
`
`DISPLAY
`CONTROLLER
`
`GSPRITE
`DECOMPRESSION
`ENGINE
`
`674
`
`0028
`
`

`
`5,880,737
`
`1
`METHOD AND SYSTEM FOR ACCESSING
`TEXTURE DATA IN ENVIRONMENTS WITH
`HIGH LATENCY IN A GRAPHICS
`RENDERING SYSTEM
`
`REFERENCE TO PRIOR APPLICATIONS
`
`This is a continuation-in-part or application Ser. No.
`08/560,114, filed Nov. 17, 1995 now abandoned. Applica(cid:173)
`tion Ser. No. 08/ 560,114 is a continuation of application Ser.
`No. 08/511,553, filed Aug. 4, 1995, which is now aban(cid:173)
`doned.
`
`TECH NT CAL FIELD
`
`The invention generally relates to graphics rendering of t5
`graphical models, and more specifically relates to methods
`and systems for accessing texture data in high latency
`environments.
`
`BACKGROUND
`
`Graphics rendering generally refers to the process of
`converting graphical models into a d isplay image. The
`display image is typically comprised of an array of pixel
`data, sometimes referred to as a bitmap or pixmap. This
`array of pixel data maps to picture elements in tbe display
`screen of a display device. To display an image, a display
`controller transfers the pixel data to a display device, where
`it is used to illuminate the pictu re clements or '' pixels" of a
`display screen. For example in color images, the pixel data
`can include red, green and blue color intensity values used
`to illuminate the pi.'<:els of color display screen.
`Though there are a variety of display technologies, one of
`lbe most widely used is raster display technology. A raster
`display device includes an array of individual points or
`picture elements (i.e., pixels), arranged in rows and col(cid:173)
`ltmns. In a CR1~ these pixels correspond to a phosphor array
`provided on lbe glass faceplate of tbe CRT. The emission of
`light from each phosphor in lbe array is independently
`controlled by an electron beam that "scans" tbe array 40
`sequentially, one row at a ti me, in response to stored
`intensity values representative of each pixel in the image.
`In 3D graphics applications, an object in a scene is
`represented by a 30 graphical model, which ir1cludes geo(cid:173)
`metric data used to model the surface and position of tbe 45
`object, and visual attributes used to modellbe appearance of
`tbe object. There are a number of ways tbat a geometric
`model can represent a 3D object, including polygon meshes,
`parametric surfaces, or quadratic surfaces. Using a polygon
`mcsb, for example, the surface of an object is modeled with 50
`several interconnected polygons. The surface elements, in
`tbis case polygons, are referred to as geometric primitives.
`Visual attributes sucb as red, green, and blue color data, and
`possibly other model data is stored at the vertices of lbe
`polygon.
`In a process called scan converting or rasterizing, the
`geometric primitives forming the surface of the graphical
`model are converted into an array of discrete pixel data. In
`the context of 3D graphics, the visible surfaces of the objects
`in a scene are convened into an array of pixels. For surfaces 60
`represented with a mesh of polygons, for example, color
`intensity values stored at tbe vertices of each polygon are
`interpolated to compute intensity values at each of the
`discrete pixel elements covered by a polygon.
`To create more realistic and de tailed imagery, interpolated 65
`color values alone are not sufficient to create a realistic
`image. Often, additional image data stored separately from
`
`2
`the model must be used to improve image quality. For
`example, image data referred to as a texture map is often
`used to represent intricate de tail on the surface of a graphical
`model. to a process called texture mapping, a digital image
`5 called a texture map is mapped to tbe surface of a graphical
`model. In addition to texture maps, olber image data external
`to tbe graphical model is sometimes used to compute pixel
`data. For example color and opacity data is sometimes used
`to perform lighting and shading operations. As another
`10 example, a s hadow map is sometimes used to compute
`shadows cast by objects in a scene.
`Texture mapping and other fo rms of rendering operations
`that require acces.s to additional image data place tremen(cid:173)
`dous demands on a graphics rendering, system. In a typical
`texture mapping operation, the graphics rendering system
`has to retrieve at least one sample of texture data to compute
`each pixel. To generate high quality images without artifacts,
`the need to re trieve more samples of texture data increases
`because several texture samples are filte red or re-sampled to
`20 compute every pixel.
`In real time systems, a new display image must be
`generated every fraction of a second. This rigorous timing
`requirement places severe constraints on texture mapping
`because there is limited time to ret rieve texture data. The
`25 quality of lbe final image often suffers because sampling
`and/or fi ltering several texture cannot be performed due to
`the memory bandwidth limitations of the system. Support
`for high bandwidth access to texture data requires dedicated,
`fast and expensive memory systems.
`A sign ificant s ide effect of the memory bandwidth prob-
`lem outlined above is that it makes it difficult, if not
`impossible, to store texture data in compressed form. 1ex(cid:173)
`ture da ta is typically not stored in compressed form because
`35 there is not enough time to decompress texture data in a
`graphics rendering pipeline. As a result, memory require(cid:173)
`ments to store texture data can be substantial. The need for
`additional memory adds further to the expense of the system.
`
`30
`
`SUMMARY OF -n-IE INVENTION
`
`To address these and other drawbacks, the invention
`provides improved metbods and systems for accessing tex(cid:173)
`ture data. While the invention is particularly well suited for
`texture mapping, it also supports additional rendering opera(cid:173)
`tions that require access to texture memory.
`In one embodiment, geometric primitives in input data
`stream are stored in a ftrst queue long enough to absorb the
`latency of fetching a block of texture da ta from memory. The
`geometric primitives in the fi rst queue are converted into a
`texture block references, wbicb arc stored in a secood queue.
`The texture blocks referenced in this second queue are
`fetched from memory and placed in a texture cacbe. One by
`one, each primitive in the queue is rasterized. As each
`primitive is rasterizcd, texture data is retrieved from the
`55 texture cache as necessary to compute the output pixels fo r
`the current primitive. Primitives are removed from the queue
`after they are rasterized.
`In second embodiment, primitives arc rasterizcd and the
`resulting pixel data is placed in a queue long enough to
`absorb the latency of a texture block fetch. In one specific
`implementation, the entries in the queue include a pixel
`address, color data for that address, and a texture request
`comprised of the center poiot of a texture sample in tbe
`coordinates of a texture map. The texture requests are read
`from the queue and converted into texture block addresses.
`The texture blocks are [etched and placed in a texture cache.
`The entries io the queue are retrieved from the queue, aod
`
`0029
`
`

`
`5,880,737
`
`3
`associated texture data now in the texture cache is used to
`compute output pixels.
`Both approaches outlined above enable texture to be
`accessed efficiently using a texture cache. Text11re data can
`be stored in lower cost memory with higher latency. Tn
`addition, texture data can be even be stored in a compressed
`format despite the additional latency associated with decom(cid:173)
`pressing the texture data.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`5
`
`FIG. 1 is a block diagram of an image processing system.
`FIG. 2 is a block diagram of the system environment for
`an embodiment of the invcmion.
`FIG. 3 is a block diagram of system architecture for an
`embodiment.
`FIG. 4Ais a block diagram of image processing hardware
`for an embodiment.
`FIG. 4B is a block diagram illustrating portions of an
`image processor for rendering geometric primitives io an
`embodiment.
`FIGS. SA and SB are flow diagrams illustrating an over(cid:173)
`view of the rendering process in an embodiment.
`FIG. 6 is a flow diagram illustrating an overview of the
`display generation process of an embodiment.
`FIG. 7 is a diagram illustrating one aspect of display
`generation in terms of frame periods in an embodiment.
`FIG. 8 is a block diagram of a Digital Signal Processor
`(DSP) in an embodiment.
`FIGS. 9A-C are block diagrams illustrating alleroative
`embodiments of a tiler.
`FIG. lO is a block diagram illustrating a system for
`accessing texture data from memory.
`FIG. 11 is a block diagram illustrating a system for
`accessing texture data from memory.
`riGS. 12A-B are block diagrams illustrating alternative
`implementations of a gsprite engine.
`FIG. 13 is a block diagram of a compositing buffer in an 40
`embodiment.
`FIG. 14 is a block diagram of a Digital to Analog
`Converter (DAC) in an embodiment.
`FIG. 15A-F are a flow diagrams illustrating aspects of
`pixel and fragment generation in three alteroativc cmbodi- 45
`ments.
`FIG. 16 is a block diagram of a rendering architecture
`supporting compression and decompression.
`
`35
`
`4
`and a host of interactive applications. The system supports
`sophisticated user interfaces including 3-D graphics or com(cid:173)
`bined graph·ics and video. Improving upon the limited
`graphics capabilities of today's windowing environments
`for personal computers, the system can support improved
`3-D graphical user interfaces for applications ranging from
`office information processing on desktop computers to inter(cid:173)
`active television applications in a set-top box. lbe system
`makes very efficient use of memory and processor time and
`10 therefore can provide impressive image processing and
`display without unduly hindering performance of the appli(cid:173)
`cation or responsiveness of the user interface to user actions.
`FIG. 1 is a block diagram of the image processing system
`100. The image processing system comprises an image data
`15 source and store 102, an image preprocessor 104, an image
`processor 106, and a display device 108, if immediate
`display of rendered images is desired. The elements in the
`system communicate through a system interface 110. T be
`image da ta source and s tore 102 supplies image data to the
`20 system, and stores image data and commands. The image
`preprocessor 104 is responsible for manipulating the image
`data to prepare it for rendering. Examples of preprocessing
`functions include: defining objects in terms of geometric
`models, defining lighting and shadowing models, determin-
`25 ing object locations, determining the location of a viewpoint
`and light sources, and geometry processing.
`The image processor 106 renders the images, and gener(cid:173)
`ates a display image to be displayed on the display device
`108. Rendering refers to the process of creating images from
`30 models and includes such f11nctions as geometry processing
`(note tbat geometry processing can