United States Patent [19]
`Migdal et al.
`
`[54] METHOD AND SYSTEM FOR PROVIDING
`TEXTURE USING A SELECTED PORTION
`OF A TEXTURE MAP
`
`[75]
`
`Inventors: Christopher Joseph MigdaL Mt. View;
`James L. Foran. Milpitas; Michael
`Timothy Jones. Los Altos;
`Christopher Clark Tanner. San Jose,
`all of Calif.
`
`[73] Assignee: Silicon Graphics, Inc •. Mountain View,
`Calif.
`
`[21] Appl. No.: 554,047
`
`Nov. 6, 1995
`
`[22] Filed:
`Int. Cl.6
`[51]
`..................................................... G06T 11/00
`[52] U.S. Cl ............................................................... 345/430
`[58] Field of Search ..................................... 395/128-132.
`395/125-127; 345/430
`
`[56]
`
`References Cited
`
`U.S. PATENf DOCUMENTS
`
`2/1988 Bunker et al ........................... 340n28
`4,727,365
`4,974,176 1111990 Buchner et al ......................... 364/522
`3/1992 Lathrop et al .......................... 395/130
`5,097,427
`2/1996 Foran et al.
`. ........................... 395/130
`5,490,240
`
`FOREIGN PATENf DOCUMENTS
`
`9/1991 European Pat. Off ..
`0 447 227 A2
`0 513 474 A1 1111992 European Pat. Off ..
`
`OTHER PUBLICATIONS
`
`Blinn, Jim. "Jim Blinn's Corner: The Truth About Texture
`Mapping," IEEE Computer Graphics & Applications, Mar ..
`1990. pp. 78-83.
`Foley et al., "17.4.3 Other Pattern Mapping Techniques."
`Computer Graphics: Principles and Practice, 1990. pp.
`826-828.
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US005760783A
`[11] Patent Number:
`[451 Date of Patent:
`
`5,760,783
`Jun.2, 1998
`
`Cosman. M .. "Global Terrain Texture: Lowering the Cost."
`Proceedings of the 1994 !11Ulge VII Conference, Tempe.
`Arizona: The Image Society. pp. 53-64.
`Dungan. W. et al .. "Texture Tile Considerations for Raster
`Graphics," Siggraph '78 Proceedings (1978) pp. 130-134.
`Economy. R. et al .. 'The Application of Aerial Photography
`and Satellite Imagery to Flight Simulation," pp. 280-287.
`Foley et al .. Computer Graphics Principles and Practice,
`Second Edition, Addison-Wesley Publishing Company.
`Reading. Massachusetts (1990). pp. 742-743 and 826-828.
`Watt A.. Fundamentals of Three-Dimensional Computer
`Graphics, Addison-Wesley Publishing Company. USA
`(1989), pp. 227-250.
`Williams. L. "Pyramidal Parametrics." Computer Graphics,
`vol. 17. No. 3. Jul. 1983. pp. 1-15.
`Prii1Ull)' Examiner-Almis R. J ankus
`Attome)~ Agent, or Finn-Sterne. Kessler. Goldstein & Fox
`P.L.L.C.
`[57]
`
`ABSTRACT
`
`An apparatus and method for quickly and efficiently pro(cid:173)
`viding texel data relevant for displaying a textured image. A
`large amount of texture source data. such as photographic
`terrain texture. is stored as a two-dimensional or three(cid:173)
`dimensional texture MlP-map on one or more mass storage
`devices. Only a relatively small clip-map representing
`selected portions of the complete texture MIP-map is loaded
`into faster. more expensive memory. These selected texture
`MIP-map portions forming the clip-map consist of tiles
`which contain those texel values at each respective level of
`detail that are most likely to be mapped to pixels being
`rendered for display based upon the viewer's eyepoint and
`field of view. To efficiently update the clip-map in real-time,
`texel data is loaded and discarded from the edges of tiles.
`Attempts to access a texel lying outside of a particular
`clip-map tile are accommodated by utilizing a substitute
`texel value obtained from the next coarser resolution clip(cid:173)
`map tile which encompasses the sought texel.
`
`28 Claims, 14 Drawing Sheets
`
`X'
`' 540
`
`I
`a·
`/
`1------
`
`"'---- TEX1URE
`MIP-IMP
`330
`
`I CUBICAL PART
`
`PYRAI.iiOAL PART
`
`LOD[I.i+1] (
`~
`LOO[N) l
`
`Microsoft Corp. Exhibit 1007
`
`

`
`U.S. Patent
`
`Jun.2, 1998
`
`Sheet 1 of 14
`
`5,760,783
`
`/
`
`I
`
`I
`
`/
`
`/
`
`/ I I
`/I I
`
`/p L00[3]
`//.Eijt LOD[2]
`/ . / 'I/
`I
`I LOD[ 1 ]
`
`/
`
`/
`
`/
`
`/
`
`I
`
`I
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`/
`
`I
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`1 LOD[O)
`
`FIG.1 A
`
`FIG.1 8
`
`BACKGROUND
`
`FOREGROUND
`
`Microsoft Corp. Exhibit 1007
`
`

`
`-...1 "' =
`
`~
`00
`'-I
`,..
`
`,..
`Ol
`
`s, -.a::..
`
`~
`~
`
`N
`
`,.. -~
`
`~
`.....
`
`N
`
`~ a
`
`~
`~
`•
`\Jl
`•
`Cj
`
`:
`I
`I
`:
`:
`:
`:
`I
`I
`:
`:
`I
`I
`I
`
`I
`I
`
`I
`:
`I
`I
`I
`:
`I
`:
`I
`'
`i
`1
`r-----r-POLYGON DESCil\EII9i'l _____ j_ __________ ,
`
`:
`I
`I
`:
`:
`'
`:------------------------
`
`~-----='
`
`222
`
`M~O~ ~·
`226
`TEXTURE
`SUBSYSTEM ~·
`RASTER
`224
`1
`ENGINE
`GEOMETRY
`
`SUBSYSTEM
`GRAPHICS
`
`/
`
`/
`
`,
`220
`
`1
`I
`I
`
`J
`
`L _____________________________________________ J
`.+--
`:
`
`T
`
`UNI
`
`f----
`
`BUFFER
`
`228 I
`
`I
`
`I
`
`I
`
`DISPLAY
`(
`232
`
`VIDEO 1--
`(
`230
`
`FRAME
`t
`
`I
`
`:
`I
`I
`
`___ j
`
`: :
`I
`:
`I
`:
`I
`:
`I
`I
`I
`I
`:
`I
`:
`I
`I
`I
`
`" 200
`
`MASS STORAGE
`
`DEVICE
`
`ROM
`
`2
`201
`
`I
`
`08
`
`C2
`
`7
`
`BUS
`
`206
`
`?
`
`I
`I
`I
`I
`I
`I __
`I
`-----------------------l
`
`FIG.2
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`L -
`
`216
`
`j.-..J
`
`ETC.
`SOUND
`
`PROCESSOR
`
`,__
`
`202
`
`1
`
`I
`f
`
`214
`
`HARD COPY I---(cid:173)
`
`DEVICE
`
`1
`
`212
`
`f--..J
`
`C
`ONTROL
`CURSOR
`
`--._.1
`
`KEYBOARD
`
`1
`1
`I
`I
`I
`I
`1
`I
`I
`
`204
`_.._. MEMORY
`
`MAIN
`
`I
`I
`1
`I
`1
`I
`r--------£8
`
`210
`
`DISPLAY
`
`rJ
`
`Microsoft Corp. Exhibit 1007
`
`

`
`~
`QIO
`.....:a
`._.
`=" c
`.....:a
`._.
`VI
`
`""'
`~ .....
`w
`~
`r.l). =(cid:173)
`I'D
`
`~
`
`~
`.....
`J'l
`~
`
`(D a
`~ =
`d • rJ1 •
`
`1!""'1'-
`
`300
`
`302
`
`..... , 301
`
`~--
`
`------
`-----------~ -,
`----------..,
`
`.. ,,, ':t• ·-~··· :'.;-·~ .. : .... '-.~ :;.~ -----------------_}--,
`
`:. " · ..... ,..
`
`..........
`
`---..J
`
`LOD[2] [------------------3f2-;_. ~::'; ..... ·. ,:' _,., ..... ~·· 1 ---------------,
`-----------------
`--------------
`-----------------~--,
`
`------------------------
`
`LOD[ 1] [---------------------3fi:... ,: .. , .... , ..... :.· .. : ·.
`
`•------------------------~!Q_
`LOD[O] r----------------------------
`
`r-------
`
`:
`CLIP-MAP :
`
`I
`I
`
`340
`
`0
`
`X
`
`'
`---------------------·." ............. :'" ... ·; · .. ~·.,t:··.,.··til, ... · --------------..r--..... .....
`
`330
`MIP-MAP
`~
`TEXTURE
`
`307
`
`LOD[N]
`
`LOD[M+ 1)
`
`FIG.3
`
`----_:--......... 305
`
`~-----~
`
`LOD[5) [ ~=====~} ~~·<:;.;;:i:;·~~;f·:?~; :\::;:~·~:
`
`.... 303
`
`--,
`
`:o o' ~~· -------~--.......... ... 304
`
`... • •• , ·: :.;:,·~·;"·
`
`.... ~~ 0 ',•, "'·,,
`
`I
`
`0 o
`
`----------'I oo
`
`'-•.1.·:·.;.:•·,':, • ·.::,· .,
`
`L-----
`
`LOD[4] ~------------3-1-4: ·· ... · .:.···· ..
`
`'I .... ~: ... :,:~•\;,""-,,•',
`-------31'3:.._ .·-;:-•.;.~·.:.;·,:-~ ................. ...
`..
`
`·, •
`
`-------------------;.•.,"";~'.,,',.,
`r-------
`
`PYRAMIDAL PART
`
`l
`I CUBICAL PART
`
`LOD[3] ~
`
`Microsoft Corp. Exhibit 1007
`
`

`
`QC w
`.....:1
`=" =
`,.
`
`.....:1
`,.
`01
`
`""""
`.~:>.
`~
`.~:>.
`
`rJ'J =(cid:173)~ a
`
`QCI
`\C)
`""""
`\C)
`~
`~
`
`~
`
`~ = ,....
`~ = ,....
`•
`00
`~ •
`
`16k
`
`X
`
`16k
`401
`
`1~~ 32k TEXELS
`
`X
`
`........ ,
`
`-...,
`
`1----
`
`•• --------..J
`--------~
`-----------...J
`
`..........
`LOD[1] ~--------------411~:~:::~.~~:·.··~·~·:-:: ···:.~:>;·.:;.::·:~: ------------...--....
`o ----------------.J
`LOD[O] ~------------------~f1o:q ~:;·:;:~·~:· ~:.~f''1·>:·':::' :-~··) ___ ------------~--
`
`'• ••
`
`t
`
`LOD 2 I
`
`]
`
`[
`
`r
`
`I,
`
`..............
`
`I
`
`'-------------------......... ,.
`
`I" o•,o(.o ,,o
`
`ooo
`
`..
`
`L----------------------·:• ,.._,, .. flo'
`
`""--
`
`0
`
`X
`
`CLIP-MAP
`
`440
`
`(410-415)
`
`TILES
`
`0t
`-s
`
`,..-----~ .... ,.:.,;\To: ., • •.
`. ..
`LOD[3] lr------4-1_3_" ,.·:._. .. ·:.·:· .. ;A:,.,.._,::_··~'· .. ,:···:;.
`L---------------'",, • • • .,., '""
`.,:'·.;;", ·: •. ·.:.: ·• ....... ··~: ··•;.·. :· ··, ..
`••,• ,• .:.•·<· .,
`412
`••• •' ,,....
`---------------
`
`"'----PHOTOGRAPHIC
`
`TEXTURE MAP
`
`430
`
`TERRAIN
`
`1k X 1k
`405
`
`/
`
`/
`
`FIG.4A
`
`/
`
`/
`
`' / v
`'
`'
`
`'
`
`'
`
`415 ........ ::...:~ •. · ~ ·;:, •.. ~, .. ;.,,,;., '·~··:r--.
`
`'.··:·.:."....,.'.;.,:,.,.~··: .... '·'I
`
`'
`
`LOD[5]
`LOD(4] ~-~1~:----.. :· ... .-, ............ ;; ·:·.-...,,.,: ... ::·;· __ _, --.. ,,
`,__________
`
`---;_
`
`_____ ....
`------;..._
`
`-
`
`~..
`
`'o .. 0 o
`
`<o
`
`. .
`
`f ,,.
`
`~· .. , 0 ,. 1 oil 0
`
`. . .. ...
`
`•
`
`4
`
`.....
`
`1
`
`l PYRAMIDAL PART
`
`1
`{1k x 1k TILES)
`CUBICAL PART
`
`Bk X Bk
`402
`
`2k X 2k
`404
`
`4k x 4k
`
`.... .... 403
`
`....
`
`Microsoft Corp. Exhibit 1007
`
`

`
`U.S. Patent
`
`Jun. 2, 1998
`
`Sheet 5 of 14
`
`5,760,783
`
`~
`N
`
`~ (
`
`I"')
`
`/~
`- /~
`v\
`
`N
`
`...:iiC
`
`- N
`
`...:iiC
`
`....:M:
`~
`
`....:M:
`CX)
`
`N
`
`~
`~--r-......
`
`X
`
`(
`
`Microsoft Corp. Exhibit 1007
`
`

`
`U.S. Patent
`
`Jun. 2, 1998
`
`Sheet 6 of 14
`
`5,760,783
`
`LOD[2]--
`8k X 8k
`402
`
`I
`
`401
`LOD[1]
`16k X 16k
`
`420'
`
`X'
`
`400 LOD[O]
`32k X 32k
`
`FIG.4C
`
`Microsoft Corp. Exhibit 1007
`
`

`
`"' 00 w
`,_. "' =" 0
`
`Ol
`
`,_.
`
`t:r' a
`
`[11
`
`""'
`.....
`~
`......:.
`
`330
`MIP-MAP
`TEXTURE
`
`\...__
`
`---...... 304
`
`QO
`~
`~ .....
`~
`
`~
`
`~ a
`~ = t"'t-
`
`•
`rJ1
`•
`Cj
`
`302
`
`300
`
`......... ,
`
`~---
`
`-.J
`
`-------r-
`-----__ IL------
`
`I
`1-----""'
`o'
`1
`I
`I
`
`I
`I 540
`X'
`
`FIG.5
`
`LOD[N]
`
`LOD[M+1]
`
`PYRAMIDAL PART
`
`l
`
`1 CUBICAL PART
`
`'-------------------"f-::..:...:::..;:::.....:.......:tf>:.::t;.;~r..;..:.:.....::..o.+
`1
`... ------------------+ ....... ,.-,....,,....,,.-!,....,...,......,h---r-+-
`
`313
`
`... ----------------------+==-=---=-~._,.._,......,,...J:,....+
`
`:.;::::;::~·~>~·.-:-"''· :··-~· .,:·
`LOD[ 1] [===== ================~[f · ,· ... ·, ... ,~~-. · ..
`
`LOD[2] ~ __________________ 3_1_?_
`
`I
`
`I
`1(310-319)
`: TILES
`
`~----------------
`1
`r---
`
`LOD(O)
`
`r---~---T---r---,
`
`0
`
`I
`
`/
`
`i ...
`I /
`'
`X
`
`I
`I
`
`I
`I
`
`I
`I
`:
`CLIP-MAP :
`
`340
`
`Microsoft Corp. Exhibit 1007
`
`

`
`U.S. Patent
`
`Jun.2, 1998
`
`Sheet 8 of 14
`
`5,760,783
`
`I
`
`r--------.....--'
`I b
`N
`tO
`
`-N c.o
`
`-N c.o
`
`N
`N
`tO
`
`N
`N c.o
`
`0
`0
`tO
`
`0::::
`
`~ LL.I u
`(/') -X
`---,-
`1
`I
`I
`
`,/
`o~
`
`Microsoft Corp. Exhibit 1007
`
`

`
`0\ =
`
`~
`~
`.....:.
`._.
`
`.....:.
`._.
`til
`
`"' ~
`C" f!
`
`~
`.......
`
`00
`
`~
`
`.......
`...,N
`~
`
`~
`
`300
`
`(0 a
`~ =
`0 • 00 •
`
`.......
`
`I ---
`
`::,!·:-·::. ... ~· .. ""· ..... 0. 'II ··.·t.· ,,
`
`... 301
`=========---------:--...... ,
`
`. . . . . . . ··~. • .. ;~':. ------------=== == = }-..... ,
`
`.. ,t, :ft I•
`
`,: .. ::· .. ,·~· ··" .... ·· .. ~-~:·.;• ... : .... ·-..~ ------------
`
`. \
` .. ~-~..'r,-:.t,.~::.~·~;:~·.=~::;,~.;~.::-::~:~;1 --_;---...... , 306
`.. ::·.,. ··: 1·,·: ..... ·=-·: ;.;. ,.
`lJLh-:=~~::::·:::.· '.~.f .. ~:·'"·IT·
`~>· .:~ ... :.:·,<·.·:~-... '.··~·: .. ~· • .' :·<~ _____ ---
`~~·:•: : ; · ... :·:\,. ···t .. ..
`l.--=--:--:-:r:--:r::"""• T"'?'?_:~,_~.:: .. ::r·t--------}--......
`: = = = = = = = = = = =}-......... , 303
`~::~(.::.::; .;·~ ·>·:.i.:~~.:::;.~~-i::;.::;_~ 1
`i >·;· ? -'''·>''<:' >l ---============r-----302
`
`330
`MIP-MAP
`TEXTURE
`
`\...__
`
`308
`
`307
`
`319
`
`..... , 305
`
`'304
`
`~ ---,
`···I -----~---
`
`..J
`
`-
`
`~L
`
`.. . )
`
`I·~ ....... ,.
`
`\
`
`----------,
`
`~ ~ .:: ··<·=-~~r ~!;..:: :~~;:\~~ · -~:. · :1/ ~~ .. • .. \·
`{310-319):
`:
`TILES
`
`"-
`
`340 -.....j
`:
`:
`PI
`I
`r---------------1
`
`I
`
`CUP-MA
`
`FIG.7
`
`LOD[N]
`
`LOD[M+1]
`
`PYRAMIDAL PART
`
`j
`
`1 CUBICAL PART
`
`LOD[1] [===========JQ~===--~ 312
`
`L-----------------
`LOD[O] r-~----------------
`1
`
`700
`
`Microsoft Corp. Exhibit 1007
`
`

`
`U.S. Patent
`
`Jun. 2, 1998
`
`Sheet 10 of 14
`
`5,760,783
`
`START
`
`800
`
`STORE TEXTURE MIP-MAP IN A MASS ~BlO
`STORAGE DEVICE
`
`SELECT A CUP-MAP PORTION OF THE
`TEXTURE MIP-MAP BASED ON THE FIELD OF
`VIEW AND EYEPOINT LOCATION OF THE
`DISPLAY IMAGE RELATIVE TO THE TEXTURE
`PATIERN
`
`820
`r--
`
`830
`STORE THE CLIP-MAP IN A TEXTURE MEMORY ~
`
`APPLY TEXTURE TO IMAGE BY MAPPING TEXEL r-J40
`DATA FROM THE STORED CLIP-MAP TO
`CORRESPONDING PIXEL DATA
`
`DISPLAY
`NEW
`IMAGE
`
`HAS
`FIELD OF VIEW
`OR EYEPOINT
`LOCATION
`CHANGED?
`
`NO
`
`850
`~
`YES
`
`UPDATE TEXEL DATA IN
`FRINGES OF TILES IN
`THE CLIP-MAP TO
`TRACK CHANGES IN
`FIELD OF VIEW AND/OR
`EYEPOINT LOCATION
`
`FIG.8A
`
`Microsoft Corp. Exhibit 1007
`
`

`
`U.S. Patent
`
`Jun.2, 1998
`
`Sheet 11 of 14
`
`5,760,783
`
`APPLY TEXTURE
`TO NEW IMAGE ROUTINE
`
`INPUT POLYGON
`DESCRIPTION AND
`TEXTURE COORDINATES
`
`CALCULATE A LEVEL
`OF DETAIL FOR
`EACH PIXEL
`
`841
`
`842
`
`DffiRMINE THE LOD MAP
`INCLUDING TEXEL DATA
`AT AN APPROPRIATE
`RESOLUTION FOR
`EACH PIXEL
`
`843
`
`846
`
`MAP SUBSTITUTE TEXEL DATA
`FROM TILE NEAREST IN LEVEL
`NO
`~---~ OF DETAIL ENCOMPASSING THE
`TEXEL DATA AT A COARSER
`RESOLUTION TO
`CORRESPONDING PIXEL DATA
`
`845
`
`847
`
`MAP TEXEL DATA FROM THE
`CLOSEST LOD TILE TO
`CORRESPONDING PIXEL DATA
`
`STORE TEXEL AND SUBSTITUTE
`TEXEL DATA FROM THE CLIP-MAP
`WITH CORRESPONDING PIXELS
`DATA IN FRAME BUFFER
`FOR DISPLAY
`YES
`
`(
`
`GO TO STEP )
`
`FIG.BB
`
`Microsoft Corp. Exhibit 1007
`
`

`
`=" =
`
`~
`-...!
`,.
`
`.....:1
`._.
`01
`
`~ ""'
`~
`N
`~
`
`!'t> a
`t:r
`00
`
`~
`p
`~
`
`~
`
`;.,..
`
`~ a
`~ ~
`•
`00.
`d •
`
`L.L.V
`
`BUFFER
`FRAME
`;
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`I
`
`224
`
`FIG.9
`
`SUBSYSTEM
`
`',, ___ RASTER
`
`___ _j
`
`\
`I
`--,--
`
`-----
`
`----
`
`940-------------
`
`L-------
`I
`
`: TEXTURE PROCE?SOR 900
`r-----------------------------------,
`
`930
`
`FILTER
`TEXTURE
`
`-?-
`
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`i
`
`MANAGER
`MEMORY
`TEXTURE
`
`DRAM
`
`LOD
`
`COORDINATES
`
`TEXEL
`
`~-----------------------------~-----------J
`
`PIXEL DATA
`
`920
`
`~ GENERATOR
`
`.,1
`
`PIXEL
`
`---:-GENERATOR
`TEXTURE
`
`I
`I
`I
`I
`I
`
`(x,y)
`
`wl;
`
`\
`
`I
`I
`: TRIANGLE
`I
`I
`
`I ;s
`
`BUS
`
`ENGINE
`GEOMETRY
`
`(
`
`201
`BUS
`
`Microsoft Corp. Exhibit 1007
`
`

`
`~
`
`.....:e oc
`=". c ,..
`.....:e
`,..
`Ol
`
`..... ...
`..... w
`.....
`('l)
`('l)
`t:r'
`rJ1
`
`0 ......,
`
`00
`\C
`\C
`.....
`_p
`""'" ~
`
`~ a
`~ ......
`00 •
`~
`
`FIG.1 0
`
`TM
`TO
`
`COMPRESSION
`COORDINATE
`
`QUAD
`~
`1060
`
`I)
`
`(\
`
`GENERATION
`
`BLOCK
`
`LOD
`
`\
`
`r-
`{\
`
`NORMALIZER
`
`DIVIDER
`
`AND
`
`( 1030
`
`(1020
`
`( 1010
`
`CONVERSION
`
`SCAN
`
`.........
`
`COEFFICIENTS
`
`ITERATION
`GENERATE
`
`1-
`
`NORMALIZE
`
`AND
`ROTATE
`TRIANGLE
`
`10t0
`
`1140
`
`GENERATOR 240
`(X,Y) FROM PIXEL
`
`SCREEN SPACE
`DESCRIPTION IN
`
`TRIANGLE
`
`9
`~5
`8
`JS
`NGLE
`TRIA
`
`/\100
`
`VALUE
`
`pixOO, pix01, pix1 0, pix11
`______..
`
`TEXEL COORDINATES
`
`PIXEL QUAD
`
`Microsoft Corp. Exhibit 1007
`
`

`
`~
`QC
`........
`._.
`0
`Q'\
`........
`._.
`til
`
`""'
`
`~
`
`.....
`s,
`.....
`('tl a
`00 =(cid:173)
`
`~
`
`~
`
`~
`.....
`-P
`~
`
`~ = ......
`~ = ......
`~ • r.n •
`
`--TEXTURE
`
`950
`FILTER
`
`IANAGER
`~
`ORY
`~
`TEXTURE
`
`vg
`
`FIG.11
`
`DRAM
`
`'(7
`
`..().
`
`MEMORY CONTROLLER
`
`( 1130
`
`DATA
`TEXTURE
`
`ADDRESSES
`TEXTURE
`
`TEXTURE DATA
`
`GENERATOR
`ADDRESS
`
`VALUE
`LOD
`v
`
`'
`
`VALUE
`AND LOD
`PIXEL QUAD
`DECOMPRESS
`
`_\
`9
`10
`
`GENERATOR
`TEXTURE
`FROM
`
`TEXEL COORDINATES
`
`{PIXEL QUAD
`
`1110,
`
`Microsoft Corp. Exhibit 1007
`
`

`
`5,760.783
`
`1
`METHOD AND SYSTEM FOR PROVIDING
`TEXTURE USING A SELECTED PORTION
`OF A TEXTURE MAP
`
`BACKGROUND OF THE INVENI10N
`1. Field of the Invention
`The present invention pertains to the field of computer
`graphics. More particularly. the present invention relates to
`an apparatus and method for providing texel data from
`selected portions of a texture MIP-map (referred to herein as
`a clip-map).
`2. Related Art
`Computer systems are commonly used for displaying
`graphical objects on a display screen. These graphical 15
`objects include points. lines, polygons, and three dimen(cid:173)
`sional solid objects. By utilizing texture mapping
`techniques. color and other details can be applied to areas
`and surfaces of these objects. In texture mapping. a pattern
`image, also referred to as a "texture map," is combined with 20
`an area or surface of an object to produce a modified object
`with the added texture detail. For example, given the outline
`of a featureless cube and a texture map defining a wood
`grain pattern, texture mapping techniques can be used to
`''map" the wood grain pattern onto the cube. The resulting 25
`display is that of a cube that appears to be made of wood. In
`another example. vegetation and trees can be added by
`texture mapping to an otherwise barren terrain model.
`Likewise. labels can be applied onto packages or cans for
`visually conveying the appearance of an actual product. 30
`Textures mapped onto geometric surfaces provide motion
`and spatial cues that surface shading alone might not pro(cid:173)
`vide. For example. a sphere rotating about its center appears
`static until an irregular texture or pattern is affixed to its
`surface.
`The resolution of a texture varies. depending on the
`viewpoint of the observer. The texture of a block of wood
`displayed up close has a different appearance than if that
`same block of wood were to be displayed far away.
`Consequently. there needs to be some method for varying 40
`the resolution of the texture (e.g .• magnification and
`minification). One approach is to compute the variances of
`texture in real time, but this filtering is too slow for complex
`textures and/or requires expensive hardware to implement.
`A more practical approach first creates and stores a 45
`MIP-map (multum in parvo meaning "many things in a
`small place"). The MIP-map consists of a texture pattern
`pre-filtered at progressively lower or coarser resolutions and
`stored in varying levels of detail (LOD) maps. See. e.g .. the
`explanation of conventional texture MIP-mapping in Foley so
`et al .. Computer Graphics Principles and Practice, Second
`Edition, Addison-Wesley Publishing Company, Reading,
`Mass. (1990), pages 742-43 and 826-828 (incorporated by
`reference herein).
`FIG. lA shows a conventional set of texture LOD maps 55
`having pre-filtered texel data associated with a particular
`texture. Four different levels of detail (LOD[O]-LOD[3]m)
`are shown. Each successive coarser texture LOD has a
`resolution half that of the preceding LOD until a unitary
`LOD is reached representing an average of the entire high 60
`resolution base texture map LOD[O]. Thus, in FIG. lA,
`LOD[O] is an 8x8 texel array; LOD[ 1) is a 4x4 texel array;
`LOD[2] is a 2x2 texel array; and LOD [3] is a single lxl
`texel array. Of course, in practice each LOD can contain
`many more texels, for instance, LOD[O] can be 8kx8k, 65
`WD[ 1] 4kx4k. and so forth depending upon particular
`hardware or processing limits.
`
`35
`
`2
`The benefit of MIP-mapping is that filtering is only
`performed once on texel data when the MIP-map is initially
`created and stored in LOD maps. Thereafter. texels having
`a dimension commensurate with pixel size are obtained by
`5 selecting the closest LOD map having an appropriate reso(cid:173)
`lution. By obtaining texels from the pre-filtered LOD maps,
`filtering does not have to be performed during run-time.
`More sophisticated filtering operations can be executed
`beforehand during modeling without delaying real-time
`10 operation speed.
`To render a display at the appropriate image resolution. a
`texture LOD is selected based on the relationship between
`the smallest texel dimension and the display pixel size. For
`a perspective view of a landscape 100. as shown in FIG. lB.
`the displayed polygonal image is "magnified" in a fore(cid:173)
`ground region relative to polygonal regions located closer to
`the center horizon and background along the direction
`indicated by the arrow. To provide texture for pixels in the
`closest foreground region. then. texels are mapped from the
`finest resolution map LODIO]. Appropriate coarser LODs
`are used to map texel data covering pixels located further
`away from the viewer's eyepoint. Such multi-resolution
`texture MIP-mapping ensures that texels of the appropriate
`texture LOD gets selected during pixel sampling. To avoid
`discontinuities between images at varying resolutions. well(cid:173)
`known techniques such as linear interpolation are used to
`blend the texel values of two LODs nearest a particular
`image pixel.
`One significant drawback to conventional MIP-mapping.
`however. is the amount of memory consumed by the various
`texture LOD maps. Main memory in the form of a dynamic
`random access memory (DRAM) or a static random access
`memory (SRAM) is an expensive and inefficient site for a
`large texture MIP-map. Each additional level of detail map
`at a higher level of detail requires four times more memory.
`For example. a 16x16 texture array having 256 texture
`picture elements (texels), is four times bigger than an 8x8
`texture array which has 64 texels. To put this increase in
`perspective, a texture MIP-rnap having six levels of detail
`requires over 4.096 times more memory than the texture
`map at the finest resolution. Implementing large texture
`MIP-maps quickly becomes an expensive luxury. In
`addition, for large texture MIP-rnaps. many portions of the
`stored MIP-map are not used in a display image.
`Memory costs become especially prohibitive in photo(cid:173)
`graphic texture applications where the source texture, such
`as. satellite data or aerial photographs. occupy a large
`storage area. Creating a pre-filtered MIP-rnap representation
`of such source texture data further increases memory con(cid:173)
`sumption.
`This problem is further exacerbated by the fact that in
`order to increase the speed at which images are rendered for
`display, many of the high-performance computer systems
`contain multiple processors. A parallel. multiple processor
`architecture typically stores individual copies of the entire
`MIP-map in each processor memory.
`Thus, there is a need to efficiently implement large texture
`maps for display purposes so as to minimize attendant
`memory and data retrieval costs. Visual quality must not be
`sacrificed for memory savings. Final images in an improved
`texture mapping system need to be virtually indistinguish(cid:173)
`able from that of images generated by a traditional MIP-rnap
`approach.
`There is also a need to maintain real-time display speeds
`even when navigating through displays drawn from large
`texture maps. For example, flight simulations must still be
`
`Microsoft Corp. Exhibit 1007
`
`

`
`5.760.783
`
`3
`perlormed in real-time even when complex and voluminous
`source data such as satellite images of the earth or moon. are
`used to form large texture motifs.
`
`SUMMARY OF THE INVENITON
`
`25
`
`35
`
`The present invention pertains to an apparatus and method
`for providing texture by using selected portions of a texture
`MIP-map. The selected portions are referred to herein as a
`clip-map. Texel data relevant to a display image is stored.
`accessed. and updated efficiently in a clip-map in texture
`memory.
`Entire texture MIP-maps are stored onto one or more
`mass storage devices, such as hard disk drives, optical disk
`drives, tape drives, CD drives, etc. According to the present
`invention. however, only a clip-map needs to be loaded into 15
`a more expensive but quicker texture memory (e.g ..
`DRAM). Two dimensional or three dimensional texture data
`can be used. The clip-map is identified and selected from
`within a texture MIP-map based upon the display viewer's
`current eyepoint and field of view. The clip-map is com- 20
`posed of a set of selected tiles. Each tile corresponds to the
`respective portion of a texture level of detail map at or near
`the current field of view being rendered for display.
`Virtually unlimited. large amounts of texture source data
`can be accommodated as texture MIP-maps in cheap, mass
`storage devices while the actual textured image displayed at
`any given time is readily drawn from selected tiles of
`corresponding clip-maps stored in one or more texture
`memories. In one example. the clip-map consists of only 6 30
`million texels out of a total of 1.365 billion texels in a
`complete texture MIP-map-a savings of 1.36 billion texels!
`Where texture information is represented as a 8-bit color
`value, a texture memory savings of 10.9 gigabits (99.6%) is
`obtained.
`According to another feature of the present invention,
`real-time flight over a large texture map is obtained through
`efficient updating of the selected clip-maps. When the eye(cid:173)
`point of a viewer shifts. the edges of appropriate clip-map
`tiles stored in the texture memory are updated along the
`direction of the eyepoint movement. New texel data for each
`clip-map tile is read from the mass storage device and loaded
`into the texture memory to keep the selected clip-map tiles
`in line with the shifting eyepoint and field of view. In one
`particularly efficient embodiment. when the eyepoint moves
`a distance equal to one texel for a particular LOD. one texel
`row of new texture LOD data is added to the respective
`clip-map tile to keep pace with the direction of the eyepoint
`movement. The texel row in the clip-map tile which encom(cid:173)
`passes texel data furthest from the moving eyepoint is
`discarded.
`In a further feature of the present invention. a substitute
`texel value is used when an attempt is made to access a texel
`lying outside of a particular clip-map tile at the most
`appropriate resolution. The substitute texel value is obtained
`from the next coarser resolution clip-map tile which encom(cid:173)
`passes the texel being sought. The substitution texel that is
`chosen is the one closest to the location of the texel being
`accessed. Thus, this approach returns usable texel data from
`a clip-map even when mapping wayward pixels lying out- 60
`side of a particular clip-map tile. Of course, for a given
`screen size, the tile size and tile center position can be
`calculated to guarantee that there would be no wayward
`pixels.
`Finally, in one specific implementation of the present 65
`invention, texture processing is divided between a texture
`generator and a texture memory manager in a computer
`
`4
`graphics raster subsystem. Equal-sized square tiles simplify
`texel addressing. The texture generator includes a LOD
`generation block for generating an LOD value identifying a
`clip-map tile for each pixel quad. A texture memory manager
`5 readily accesses the texel data from the clip-map using tile
`offset and update offset information.
`Further embodiments, features, and advantages of the
`present inventions, as well as the structure and operation of
`the various embodiments of the present invention, are
`10 described in detail below with reference to the accompany(cid:173)
`ing drawings.
`BRIEF DESCRIPTION OF THE FIGURES
`The accompanying drawings. which are incorporated
`herein and form a part of the specification, illustrate the
`present invention and, together with the description, further
`serve to explain the principles of the invention and to enable
`a person skilled in the pertinent art to make and use the
`invention.
`In the drawings:
`FIG. lA shows a conventional multi-resolution MIP-map
`covering four levels of detail.
`FIG. lB shows a conventional example of a polygon
`perspective of a landscape to which texture MIP-mapping
`can be applied.
`FIG. 2 shows a block diagram of an example computer
`graphics system implementing the present invention.
`FIG. 3 shows a side view of a ten-level texture MIP-map
`and the selected tiles that constitute a clip-map according to
`the present invention.
`FIG. 4A shows a side view of the first six levels of a
`clip-map for photographic terrain texture in one example of
`the present invention.
`FIG. 4B shows the progressively larger areas of a terrain
`texture covered by coarser tiles in the present invention.
`FIG. 4C shows three LOD-maps and associated clip-map
`tile areas relative to an observer's field of view.
`FIG. 5 shows the shifting of selected tiles in a clip-map to
`track a change in the viewer eyepoint.
`FIGS. 6A and 6B illustrate an efficient updating of clip-
`40 map tiles according to the present invention to follow
`eyepoint changes.
`FIG. 7 shows obtaining a substitute texel value from the
`next closest clip-map tile having the highest resolution
`according to the present invention.
`FIGS. SA and 8B are flowcharts describing steps for
`obtaining a textured display image using a texture clip-map
`according to the present invention.
`FIGS. 9 to 11 are block diagrams illustrating one example
`of a computer graphics subsystem implementing the present
`invention.
`FIG. 9 shows a raster subsystem including a texture
`processor having a texture generator and a texture memory
`manager according to the present invention.
`FIG. 10 shows a block diagram of the texture generator in
`FIG. 9.
`FIG. 11 shows a block diagram of the texture memory
`manager in FIG. 9.
`The present invention will now be described with refer(cid:173)
`ence to the accompanying drawings. In the drawings, like
`reference numbers indicate identical or functionally similar
`elements. Additionally, the left-most digit(s) of a reference
`number identifies the drawing in which the reference num(cid:173)
`ber first appears.
`
`45
`
`50
`
`55
`
`D~AllEDD~RIPTIONOFT~
`PREFERRED EMBODIMENTS
`I. Overview and Discussion
`II. Terminology
`
`Microsoft Corp. Exhibit 1007
`
`

`
`5.760.783
`
`5
`
`m. Example Environment
`IV. Computer Graphics System
`V. Texture MIP-Mapping
`VL Selecting Portions of a Texture MIP-Map
`Vll. Photographic Terrain Texture
`Vffi. Updating the Clip-Map During Real-Time Operation
`IX. Efficiently Updating the Clip-Map
`X. Substitute Texel Data
`XI. Overall Clip-Map Operation
`Xll. Specific Implementation
`XDI. Square Clip-Map Tiles Example
`XIV. Conclusion
`
`6
`textures drawn from multi-resolution texture MIP-maps.
`Moreover, sophisticated texture motifs covering a large area.
`such as satellite data and aerial photographs. are preferred to
`fully exploit the advantages of the clip-map system and
`5 method described herein. As would be apparent to a person
`skilled in the pertinent art. the present invention applies
`generally to different sizes and types of texture patterns
`limited only by the imagination and resources of the user.
`Although the present invention is described herein with
`10 respect to two-dimensional texture mapping. the present
`invention can be extended to three-dimensional texture
`mapping when the requisite additional software and/or hard(cid:173)
`ware resources are added. See e.g. the commonly-assigned.
`U.S. patent application Ser. No. 08/088.716. now U.S. Pat.
`15 No. 5.490.240 (Attorney Docket No. 15-4-99.00
`(1452.0140000), filed Jul. 9. 1993. entitled "A System and
`Method of Generating Interactive Computer Graphic Images
`Incorporating Three Dimensional Textures." by James L.
`Foran et al. (incorporated herein by reference in its entirety).
`
`I. Overview and Discussion
`The present invention provides an apparatus and method
`for efficiently storing and quickly accessing texel data
`relevant for displaying a textured image. A large amount of
`texture source data is stored as a multi-resolution texture
`MIP-map on one or more mass storage devices. Only a
`relatively small clip-map representing selected portions of 20
`the complete texture MIP-map is loaded into faster. more
`expensive texture memory. These selected texture MIP-map
`portions include tiles which contain those texel values at
`each respective level of detail that are most likely to be
`mapped to pixels being rendered for display.
`When the eyepoint or field of view is changed, the tiles
`stored in the texture memory are updated accordingly. In one
`efficient embodiment for updating the clip-map in real-time,
`new texel data is read from the mass storage device and
`loaded into the fringes of tiles to track shifts in the eyepoint. 30
`To maintain the size of the clip-map, tile texel data corre(cid:173)
`sponding to locations furthest away from a new eyepoint is
`discarded. Anomalous attempts to access a texellying out(cid:173)
`side of a particular clip-map tile are accommodated by
`utilizing a substitute texel value obtained from the next 35
`coarser resolution clip-map tile which encompasses the texel
`being sought.
`
`N. Computer Graphics System
`Referring to FIG. 2, a block diagram of a computer
`graphics display system 200 is shown. System 200 drives a
`graphics subsystem 220 for generating textured display
`25 images according to the present invention. In a preferred
`implementation. the graphics subsystem 220 is utilized as a
`high-encl interactive computer graphics workstation.
`System 200 includes a host processor 202 coupled
`through a data bus 201 to a main memory 204. read only
`memory (ROM) 206. and mass storage device 208. Mass
`storage device 208 is used to store vast amounts of digital
`data relatively cheaply. For example. the mass storage
`device 208 can consist of one or more hard disk drives.
`floppy disk drives. optical disk drives. tape drives. CD ROM
`drives, or any number of other types of storage devices
`having media for storing data digitally.
`Different types of input and/or output (110) devices are
`also coupled to processor 202 for the benefit of an interactive
`user. An