(12)UK Patent Application (19)GB (11)2 343 599 (13)A
`
`(43) Date of A Publication 10.05.2000
`
`(21) Application No 9824407.2
`
`(22} Date of Filing 06.11.1998
`
`(71} Applicant(s)
`Imagination Technologies Umited
`(Incorporated in the United Kingdom)
`Home Park Estate, KINGS LANGLEY. Hertfordshire,
`WD4 SLZ. United Kingdom
`
`(72)
`
`lnventor(s}
`Simon Pearce
`
`(74) Agent and/or Address for Service
`Reddie & Grose
`16 Theobalds Road, LONDON, WC1X SPL,
`United Kingdom
`
`(51}
`
`INT CL7
`G06T 15/00
`
`(52) UK Cl {Edition R )
`H4TTBEC
`
`GB 2245460A
`EP 0718797 A
`
`GB 2284526 A
`GB 2171579 A
`
`{56} Documents Cited
`GB 2288304 A
`GB 2240016 A
`US5831625A
`NINTENDO $4 URL:
`http://home.earthlink.netf ~aquavfdeo/n64
`specs.html
`http: //www.wintemet.com/ ~mr_n64/sys.htm URLS:
`http://www.scs.ryers,on.ca/ ~h2jang/gfx.html
`http://www.intel.ie/technology/3d/docs/
`
`(58} Field of Search
`UK CL (Edition Q } H4T TBBA TBBK TBEA TBEC TBEE
`INT CL6 G06T 1/6011/0011/4015/0015/50
`ONUNE:EPOQUE, INTERNET.
`
`(54) Abstract Title
`Texturing systems for use in three-dimensional imaging systems
`
`(57) A texturing sys1em for use in a three-dimensional imaging system comprises a memory (22) for storing
`mip-map data for use in texturing an image, the mip-map data comprising a hierarchical series of mip-maps of
`different levels of decreasing resolution. Data is received at an input (26) indicating the type of mip-map data
`required and the level of the mip-map or mip-maps from which the data is to be taken. A controller (24)
`retrieves from the memory the mip-map data required in accordance with the input data, and this data is
`stored in a cache (30). A lower-level mip-map generator (36) generates portions of the mip-map which Is next
`below, in the hierarchical series, the mip-map of which portions are held in the cache. A trilinear interpolator
`(34) receives from the cache mip-map data from one level of mip-map and from the lower-level mip-map
`generator data from the next lower level of mip·map, and interpolates one output texel from input texels from
`the two mlp-map levels.
`The texture data is represented by arbitrary compressed codes, in which selected compressed code
`values define principal colors and other compressed code values define intermediate colors which can be
`formed by selected weighted averages of principal colors, the corresponding code values also being weighted
`averages of the code values of the selected principal colors. The lower-level mip-map generator (36}
`interpolates an output texel from a plurality of input texels by operating on the compressed code values.
`
`TRIUJ<EAA
`TEXTURED
`PIXEl
`
`............. .. ..... ..... .. ... ........... ... . --- ......
`FIG.4
`
`At least one drawing originally filed was informal and the print reproduced here is taken from a later filed formal copy.
`
`The print reflects an assignment of the application under the provisions of Section 30 of the Patents Act 1977.
`
`G>
`OJ
`
`)>
`
`0001
`
`Volkswagen 1010
`
`

`
`· ..
`
`1 I 9
`
`c
`
`A
`
`0
`
`B
`
`X
`0
`
`FIG. 1
`
`C'
`
`c
`
`A
`
`D'
`
`B'
`
`FIG. 2
`
`. ·~;;·,.~
`;,;;_ ... ·~; ~
`t. "'~''( o
`';.:#:~;
`:···.JI:
`(t'~·:?
`
`I
`
`~: ... -
`
`128x128
`
`C!l
`
`•
`
`64 X 64 32 x 32 etc.
`FIG. 3
`
`0002
`
`.,
`<·
`\. .......... (, .
`<-
`
`"
`
`,.
`\J()Q-;>00
`0
`
`GOOO
`
`

`
`~
`
`'
`
`~ , . ,.
`
`~
`
`..
`,.
`
`,.,
`c
`c
`0
`
`()((
`
`,.
`< ,. (;
`<
`'
`I .. c
`
`r
`~
`
`(•
`
`r
`
`(
`
`38
`
`INTERPOLATOR ~
`
`J\
`
`PIXEL
`
`TEXTURED
`TRILINEAR
`
`TRILINEAR
`
`N -<D
`
`)
`34
`
`'
`' y
`
`____:J,
`' x4·
`'
`
`,
`,
`
`x4:
`
`FIG. 4
`
`GENERATOR
`
`MIP-MAP
`
`LOWER LEVEL
`
`l
`36
`
`x16
`
`I
`
`32
`)
`
`-
`
`30 COMPRESSED
`
`TEXTURE
`
`CACHE
`
`TEXELS
`
`DECOMPRESSED
`
`/20
`
`UNIT
`
`DECOMPRESSION
`
`CACHE
`
`TEXTURE
`
`:
`•
`
`__., TEXTURE
`
`~--~~--~COMPRESSED
`
`•
`
`,.
`
`•
`
`•
`
`'"'
`
`•
`
`I
`
`V"-24
`
`CONTROLLER
`
`MEMORY
`
`SYSTEM n
`
`l--22
`
`MEMORY
`
`28
`
`26
`
`GENERATOR
`
`ADDRESS
`TEXTURE
`
`PARAMETERS
`
`TEXTURE
`
`0003
`
`

`
`3/9
`
`UPPER LEVEL MIP-MAP
`TEXELS REQUIRED FOR
`LOWER LEVEL GENERATION
`
`SELECTED {
`UPPER
`LEVEL
`MIP-MAP
`TEXTURES
`
`DECOMPRESSED TEXELS
`
`~~ 00
`~~ 0 0
`0 0 ~@]
`@J@JG@J
`
`UNSELECTED UPPER LEVEL
`MIP-MAP TEXTURES
`
`FIG. 5
`
`SELECTED
`LOWER LEVEL
`MIP-MAP
`TEXTURES
`
`...
`•.·
`....... ~ .... ., ~
`
`.·.:. ..
`
`0004
`
`

`
`4/9
`
`UPPER LEVEL MIP-MAP TEXTURES
`
`COMPRESSED 1----i--f----i--1---+--1---+-~ COMPRESSED
`WORD1
`WORD2
`
`r.:lr:.l
`L...:.U L.J
`
`COMPRESSED 1---J--J..---4--1~-1--11---1-----l COMPRESSED
`WORD3
`WORD4
`
`LOWER LEVEL MIP-MAP TEXTURES
`
`COMPRESSED t--+-t;:::=t=::::;:::;-fr:==t=::;:::;-t-+--1 COMPRESSED
`,.·-· :-;.>:
`· . . , ·..
`WORD 1
`WORD 2
`~ .. ~ .. :~: ~~ :~r:-· ~~~.
`. .. .
`
`.· ... - • '
`. . -~~ ~~;·r:~
`COMPRESSED 1--+--~=t==t-==t=~l--4--___..j COMPRESSED
`WORD 3
`WORD4
`
`-
`. .... ; ..
`
`~
`
`v ... ·· - L. ',
`~
`
`FIG. 6
`
`0005
`
`

`
`()'1 -
`
`<0
`
`;
`\
`
`'
`,.
`
`0
`
`'
`('• ,.
`
`r ~ '
`'
`<
`t
`'
`• ' ., <
`,, ,.
`'
`
`n
`
`70
`
`, 66
`
`62
`
`60
`
`28
`
`TEXELS
`UPPER
`
`4
`
`DECODE
`LOWER
`
`POLATOR
`
`INTER-
`LINEAR
`
`TRI-
`
`TEXELS
`UPPER
`
`4
`
`68
`
`FIG. 7
`
`x4
`
`UNIT4
`
`DEPRESSION
`
`UNIT3
`
`DEPRESSION
`
`x4
`
`FILTER
`
`UNIT2
`
`DEPRESSION
`
`TEXTURE 4
`
`COMPRESSED
`
`CACHED
`
`TEXTURE 3
`
`COMPRESSED
`
`CACHED
`
`ADDRESS 4
`TEXTURE
`
`ADDRESS 3
`TEXTURE
`
`RATOR
`GENE-
`
`ADDRESS
`TEXTURE
`
`ADDRESS 2
`TEXTURE
`
`0006
`
`I
`
`UNIT 1
`
`DEPRESSION
`
`TEXTURE 1
`
`COMPRESSED
`
`CACHED
`
`58
`
`ARBITER
`
`MEMORY CONTROLLER
`
`

`
`.........
`
`6/9
`
`UPPER LEVEL MIP-MAP TEXTURES
`
`DD
`COMPRESSED t-D-· --+-D----1.__--t----f-+----+-+-~ COMPRESSED
`WORD1
`WORD2
`
`COMPRESSED t---+--t---+--1-----t--t---+---1 COMPRESSED
`WORD3
`WORD4
`
`LOWER LEVEL MIP-MAP TEXTURES
`
`r, ... -
`
`• .
`
`,·
`v
`...... :•.;; <.,. •
`
`"
`
`COMPRESSED ~-1--+----+--t-~-4-----l~~ COMPRESSED
`WORD3
`WORD4
`
`FIG. 8
`
`0007
`
`

`
`\\I ~
`
`TEXELS
`UPPER
`
`4
`
`POLATOR
`
`INTER-
`LINEAR
`
`TRI-
`
`CATOR
`DEALLO-
`
`DU
`
`..
`
`' (
`
`'
`~ .. '
`n
`' '
`' ' "
`<
`
`'
`,.
`(
`
`64
`
`84
`
`s·s
`
`62
`
`82
`
`~
`
`60
`
`~~r:nMPRI=~~s::n I
`
`I
`
`lcoMPRESSEDI
`
`I
`
`i.
`
`<D
`
`-.J -
`
`TEXELj
`UPPER
`
`4
`
`I
`
`•I
`
`A~
`
`FIG. 9
`
`80
`
`/
`
`I' 1:1\I:L;:)
`
`I " nnu . .aA-"-.1 a
`
`I
`
`CAlOR
`
`TEXTURE 3
`
`COMPRESSED ALLO-
`DU
`
`CACHED
`
`r
`
`..J.
`
`TEXTURE 2
`
`COMPRESSED
`
`CACHED
`
`~I
`TEXTURE 1
`
`COMPRESSED
`
`I CACHED
`
`58
`
`ARBITER
`
`24
`
`MEMORY CONTROLLER I
`
`28
`
`ADDRESS 4
`TEXTURE
`
`..
`
`ADDRESS 3
`TEXTURE
`
`RATOR
`GENE-
`
`ADDRESS
`TEXTURE
`
`ADDRC~S 2
`TEXTURE
`
`0008
`
`

`
`POLATOR
`
`INTER-
`LINEAR
`
`TRI-
`
`co -<0
`
`,
`TEXEL~
`UPPER
`
`4
`
`•
`
`TEXELS
`UPPER
`
`4
`
`' i
`
`I"
`v~ xl BOOK ~
`CODE-~
`
`FILTER~ LOOKUP
`
`x4
`
`x1
`
`QUADRA DU
`
`GATOR
`DEALLO-
`
`x4
`~
`v~ xl BOOK ~
`!---'1
`TERTIARY DU
`
`FILTER F LOOKUP
`
`CODE-
`
`x1
`
`DU
`
`rr'
`v~ xl BOOK ~
`k
`
`FILTER ~ LOOKUP
`
`x4
`
`CODE-
`
`1'-'ECONDARY DU x2
`
`rr'
`BOOK ~
`k
`
`CODE-
`
`FILTER~ LOOKUP
`
`v~ x1
`
`x4
`
`X4
`
`PRIMARY DU
`
`1
`82
`
`I
`
`92
`
`LOOKUP
`INDEX
`
`~
`
`t"tl
`1--J,
`
`" LOOKUP
`~ INDEX
`
`1-J-
`
`LOOKUP
`INDEX
`
`::::::
`
`I"
`LJ..,
`
`LOOKUP
`
`INDEX
`
`~
`
`t"tl
`H
`
`,
`
`•
`
`j.
`
`..
`
`j.
`
`!r-TEXTURE 4
`COMPRESSED
`
`CACHED
`
`CATOR
`COMPRESSED ALLO-
`DU
`
`TEXTURE 3
`
`1
`
`CACHED
`
`..
`
`'I
`]CACHE 3
`
`j.l
`
`!r-
`
`(
`
`( r(
`
`'
`,,
`
`·.
`
`I
`
`J..
`
`l
`
`..
`~ ..
` ~·
`(o "
`"
`
`)
`
`.,
`
`l
`
`t
`I
`'
`
`..
`
`'
`
`)
`
`CACHE 4
`
`.J...
`
`TEXTURE 2
`
`I
`
`COMPRESSED
`
`~
`CACHE 2 ~
`__.. ~
`
`CACHED
`
`I
`
`r--~
`t--~
`
`TEXTURE 1
`
`COMPRESSED
`
`CACHED
`
`J..----58
`
`ARBITER
`
`), TEXTURE
`
`COMPRESSED
`
`., -
`
`~ CACHE1
`TEXTURE l
`
`ADDRESS 1
`
`v24
`
`MEMORY CONTROLLER
`
`28
`
`ADDRESS 4
`TEXTURE
`
`ADDRESS 3
`TEXTURE
`
`RATOR
`GENE-
`
`ADDRESS
`TEXTURE
`
`ADDRESS 2
`TEXTURE
`
`0009
`
`

`
`9/9
`
`C2
`
`FIG. 11
`
`. .. .
`
`•'
`
`., •. I;..
`
`2 BIT INDEXES 0
`0
`0
`0
`
`0 0
`0
`~ 0
`0
`
`0 ~ 0
`0 0
`0 D
`I \.1-INDEX 1
`D
`
`-INDEX 2
`
`-INDEXO
`
`16 BIT COLOUR
`
`- INDEX 3
`
`FIG. 12
`
`0010
`
`

`
`2343599
`
`-
`
`l
`
`-
`
`TEXTURING SYSTEMS FOR USE IN
`
`THREE-DIMENSIONAL IMAGING SYSTEMS
`
`s
`
`10
`
`15
`
`20
`
`25
`
`30
`
`Field of the Invention
`This invention relates to texturing systems for use
`in three-dimensional imaging systems, such as are used in
`computer displays . Such texturing systems are for example
`employed in the display of computer games.
`
`Prior Art
`The following prior documents and materials should be
`referred to for further information on the background to
`this technology. Certain of them are referred to where
`convenient by number in the subsequent description:
`[1) Catmull, E., "A Subdivision Algorithm for Computer
`Display of Curved Surfaces", Ph.D. Thesis, report
`UTEC-Csc-74-133, Computer Sciences Department, University ·
`of Utah, Salt Lake City, UT, December 1974.
`[2) Blinn, J.F . and M.E. Newell, ~Texture and Reflection
`in Computer Generated Images", CACM, 19(10), October 1976,
`542-547.
`(3} Wolberg, G., "Digital Image Warping",, IEEE Computer
`Society Press, Los Alamitos, CA, 1990.
`[4) Williams, L., "Pyramidal Parametrics", SiGGRAPH 83,
`pages 1-11.
`[5) VideoLogic, "Apocalypse 3Dx data", available from
`VideoLogic Limited, Kings Langley, England.
`[6) Microsoft Corporation, "Texture and Rendering Engine
`Compression (TREC) ", Microsoft Technical Brief, internet
`address: www.microsoft.com/hwdev/devdes/whntrec . htm
`[7] Beers, A. C. Agrawala, M. and Chaddha, N., "Rendering
`from Compressed Textures", 1996 Computer Graphics Annual
`Conference, page 373 .
`(8] Hakura, z.s. and Gupta, A. "The design and analysis
`of a cache architecture for texture mapping", Computer
`Architecture News, Vol.25, no.2, pp.l08 - 20, May 1997 .
`
`0011
`
`

`
`- 2 -
`
`"Method and
`(9) United States Patent US-A-5,612,747
`apparatus for vector quantization caching in a real time
`video coder".
`[10) United Kingdom Patent Application GB-A-2,297,886
`"Texturing and shading of 3-D Images " Applicants :
`VideoLogic Limited.
`[11 ) Gray, R. M., "Vector Quantization", IEEE Transactions
`on Communications, January 1980, pp.4-20.
`[12) Koegel Buford, J., "Multimedia Systems",
`Addison-Wesley publishing company, 1994.
`[ 13) Foley, F. and van Darn, A., "Computer Graphics
`Principles and Practice", Addison-Wesley publishing
`company, 1990.
`[14) Microsoft, "DirectX 6.0 SDK Documentation", Microsoft
`Corporation, 1 Microsoft Way, Redmond, USA. Internet
`address: www.microsoft.com/directx.
`
`Background of the Invention
`Computer based images are commonly formed of an array
`of picture elements or pixels. Each surface to be
`displayed may be represented by the pixels within a
`polygon, commonly a triangle . The surface is given color,
`texture and/or shading by an operation known as "texture
`mapping". Textures are stored as arrays of pixels,
`conveniently termed texels (texture pixels) . Thus
`"texture mapping" involves the mapping of a 20
`(two-dimensional) array of texels onto another 2D array of
`pixels representing a surface in a 3D (three-dimensional)
`scene. This technique was developed by ·Catmull (ref. 1]
`and refined by Blinn and Newell [ref. 2) . Perspective
`texture mapping involves rotating and trans l ating the
`texture map so that its perspective appears correct on the
`fina l
`image. Texture mapping improves the realism of the
`scene by giving the sur!ace of an object a realistic
`finish. An example of this is mapping a marbl e texture to
`the surface of a statue, giving the statue the appearance
`that it is made of marble. For a large scene many
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`0012
`
`

`
`- 3 -
`
`different texture bitmaps are required to represent all
`the different textures which might be present in the
`scene.
`As just noted, a 3D scene is usually represented by a
`number of polygons or triangles.
`In order to fill a
`polygon with a texture, each pixel on its surface is used
`to calculate the co-ordinate of a texel in the texture
`map. The nearest texel to the one calculated in the
`texture map may be used to shade the finally displayed
`pixel. This is called point sampling . Alternatively,
`bilinear filtering or bilinear interpolation may be used
`to improve the quality of the textured image .
`In bilinear
`filtering the point in the texture map from which the 20
`pixel is to be mapped onto the 3D surface is calculated to
`sub-pixel accuracy. Bilinear filtering or interpolation
`is then used to blend the four closest pixels to this
`calculated position in the texture map in order to atta i n
`a more accurate representation of the pixel color. This is
`illustrated in the accompanying Figure 1, where the texels
`A, B, C, and D are blended to provide a texel value for a
`pixel at point x on the two-dimensional image plane. This
`operation of bilinear, i.e. two-axis, filtering (or
`interpolation) is further described in ref. 3 .
`Trilinear (three-axis) filtering is the same process
`over the four closest pixels on two different mip-map
`levels [ref. 4]. This is illustrated in Figure 2 of the
`present application. Mip-maps are copies of the original
`texture map which have been pre-processed by being
`filtered so as to be successively reduced to half the
`resolution. MIP here stands for MULTIM IMPARVO. This is
`repeated until the resulting image is 1 pixel in size
`(this assumes that the texture is square and of a size
`which is a power of 2), so that there are a hierarchi cal
`series of the mip-maps. Figure 3 shows an example of a
`brick texture at 128 x 128 resolution with the associated
`lower mip-map levels. A mip-map can be thought of as a
`pyramid.
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`0013
`
`

`
`- 4 -
`
`Texture filtering has the effect of reducing the
`occurrence of aliasing when sampling textures. For more
`information on aliasing see ref. 3.
`Three-dimensional image generation is computationally
`intensive. Animated 30 images for games and Computer
`Aided Design (CAD) applications are becoming increasingly
`expensive in terms of processing powe r , as scenes become
`more photo-real and images are required to respond in
`real-time. A large number of floating point calculations
`are required to determine the geometry of the polygon
`·
`structure in the scene and a large number of arithmetic
`operations are required to fill and shade the polygons.
`Dedicated hardware is available [ref. 5) that can perform
`these operations many times more efficiently than
`software . Accesses to stored databases are also a
`limiting factor to performance . Local memory in dedicated
`hardware can reduce the effect of any memory access
`bottlenecks. Texture mapping is particularly memory
`intensive especially when performing a filtering (that is,
`interpolation) operation where many texture pixels are
`read for every pixel that is mapped onto the display.
`The ·size of a 20 texture map data is therefore
`reduced by texture compression so that it can be located
`into a smaller memory space. A small memory requirement
`leads to lower system costs. The original texture map can
`then be retrieved from the compressed data by
`decompression . As 3D scenes become more realis t ic,
`texture maps become larger and more numerous, making the
`use of texture compression more important. Several
`schemes have already been developed including Texture and
`Rendering Engine Compression (TREC) from Microsoft
`[ref. 6]. Beers [ref. 7] first discussed the technique of
`rendering images from compressed textures.
`It is convenient at this point to consider, and
`define, the various types of memory that are available to
`the system designer. The term "local memory" refers to
`solid state semiconductor memory located close to the
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`0014
`
`

`
`- 5 -
`
`memory control semiconductor device or circuit. The term
`"internal memory" refers to memory located within the
`particular semiconductor device being referred to.
`"External memory" is any memory outside the semiconductor
`device. Local memory can be DRAM based. DRAM is an
`acronym for Dynamic Random Access Memory, which is a
`solid-state semiconductor. Synchronous DRAM {SDRAM)
`enables data accesses to be co-ordinated by a clock
`signal.
`SDRAM has a higher access bandwidth capability
`than DRAM due to its pipelined architecture but is more
`expensive. Local memory and internal memory can be DRAM
`or SDRAM based. External memory can be sold- state or a
`mass storage array such as a hard disk . Semiconductor
`memory is very expensive and makes up a large percentage
`of the overall cost of a computer system.
`DRAM is addressed over a multiplexed address bus,
`that is, the address needed to access an individual data
`item is transmitted to the memory device in two parts.
`The core memory array in the DRAM device is a rectangular
`matrix where a single data item is addressed when a row
`control line and a column control line are activated at
`the same time . This requires a separate row and column
`address.
`If the row address does not change between
`sequential accesses, then only the column address needs to
`be transmitted. A row of data in the DRAM array is known
`as a page. When the row address remains unchanged between
`accesses, the accesses are said to be "in page" .
`"In
`page" accesses are much quicker than those that span two
`or more pages, and memory system designers endeavour to
`keep bursts of accesses in page. Some memory devices,
`such as SDRAM, make use of multiple memory banks to
`improve performance . Each memory bank can have its own
`page open, permitting data accesses to separate areas of
`memory without breaking page.
`One technique used to improve memory performance is
`"Memory Caching" in which the result of all external
`memory accesses is stored in a separate internal memory.
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`0015
`
`

`
`- 6 -
`
`This internal memory can be accessed much faster than
`external memory .
`If the result of a particular memory
`access already resides in the cache, then the cache is
`read instead of the external memory. This has the effect
`of reducing traffic to the external memory, and therefore
`reducing the "bandwidthu requirements of that memory. The
`bandwidth requirement of a memory system is often directly
`related to the cost of that system.
`In a fixed bandwidth
`system an increased bandwidth requirement can lead to a
`reduction of overall system performance .
`Texturing is the most performance-intensive process
`of 3D imaging as it requires all textures to be retrieved
`from memory. Techniques such as trilinear and bilinear
`filtering (interpolation) require up to eight texture
`pixels or texels to be retrieved from memory for every
`pixel projected onto the display, as described above and
`illustrated in Figures 1 and 2. Texturing therefore
`requires a very high bandwidth path into memory. Texture
`caching can be employed to reduce the texturing bandwidth
`requirement and increase system performance. The optimum
`performance objective is to be able to read all necessary
`texels in one processing pipeline clock cycle. Some work
`has already been done on studying the effects of using a
`cache to improve the performance of texture accesses
`(ref. 8}. Hakura demonstrates how caches can be highly
`effective for texture mapping graphics, and concludes that
`the effective memory to bandwidth ratio can be reduced by
`a factor of three to fifteen using certain caching
`strategies .
`As previously indicated, texture mapping is used to
`improve 3D image quality by mapping high detail onto a
`surface of a 3D object. This should be done without
`complicating the object's geometry. However, texture
`mapping produces a wide variety of visual artefacts,
`including aliasing [ref. 13). Bilinear filtering [ref . 3 )
`is used to improve the quality of the resulting image but
`there remain many artefacts that bilinear filtering cannot
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`0016
`
`

`
`- 7 -
`
`solve, including depth aliasing . Depth aliasing is the
`result of the texture getting more compressed as an object
`moves further from the viewpoint. This form of aliasing
`can be resolved by use of mip-maps [ref. 4], but there is
`still a problem called mip-banding. Mi p-banding occurs
`during the transition period between mip-maps when the
`texture changes from one level of detail to another.
`This may appear for example on a road, seen in the
`foreground, which disappears into the distance .
`Successi ve mip-maps are used along the road and the
`transition from one mip-map to the next can be visible.
`This problem can be solved with the application of
`trilinear filtering (ref. 4], which interpolates the l evel
`of detail between mip-maps, as described above.
`The best form of trilinear filtering is that which is
`performed on a per-pixel basis. This requires eight
`texture pixels (texels) to produce the final on- screen
`pixel. As these texels can be located anywhere in memory,
`eight separate memory reads are often required. Trilinear
`filtering is performed between two mip- levels, and so four
`memory reads occur from one mip- map location and four from
`another . Textures are usually stored in local memory,
`although system memory texturing is becoming more popular.
`These memories have a f i nite bandwidth and are very often
`required to serve as a resource to memory for many
`different applications . Set-up parameters, depth
`information, and display information are usually stored in
`local memory, and system applications are usually run from
`system memory. Eight individual memory reads per pixel is
`usually beyond the capabilities of many memory systems.
`Added to page change between mip- maps, this often achieves
`less than adequate 3D performance.
`The memory bandwidths required for a trilinear
`texture access system is dependent on the number of memory
`accesses needed for each texture filtering operation and
`the pixel throughput performance demanded by the
`application . Equation 1 shows how the texture bandwidth
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`0017
`
`

`
`- 8 -
`
`can be determined. The equation also shows how the
`bandwidth of page breaks must also be taken into account.
`
`Bandwidth,,,., = ((Accessesp,nt" Width,.,,..,)+ (AccessesP•t•_h,•t x Width,.,,..,)) x Throughputpmt
`
`Equation (1)
`
`Where:
`
`is the texture bandwidth demanded from the
`Bandwidthe.x=•
`memory measured in bytes/s. This is not the memory
`bandwidth that can be supplied by the memory.
`is the average number of memory accesses per
`pixel. Not all the required texels can be read in
`one access, even with the right data width.
`AccessesPAve_'breu is the average number of memory access
`slots lost to page breaks per pixel . A single page
`break using SDRAM requires at least 8 accesses slots.
`Width_ry is the width of the memory data bus, measured in
`bytes. This has to be at least 8 bytes (64 bits) to
`ensure that four texels can be read in one clock
`cycle.
`Throughputptx•l is the pixel throughput demanded by the
`application, measured in pixels/s. For most modern
`applications this is around 100 Mpixels/s .
`
`The average accesses per pixel is the number of
`separate memory accesses required to retrieve all data
`necessary for the filtering operation. Using a 64-bit
`memory bus, maximum throughput is achieved if four 16-bit
`texels are required ~nd they reside in the same data word .
`Unfortunately this is not always the case and very often
`the texture data resides in two or four separate words.
`Equation 2 shows how Accessespix•l can be found, taking into
`account the varying number of accesses for a single
`texture operation .
`
`5
`
`10
`
`15
`
`20
`
`25
`
`3C
`
`0018
`
`

`
`- 9 -
`
`((Pe~cenragt,,11," 1) •(Perctntageiodl• x 2) + (Pt~ctnrage,,.~,..,,, " 4) x Mipmaps)
`Facto, ~.,,.,11.,.
`
`... Equation (2}
`
`Where:
`Percentage.Lt>gl• is the percentage of single mip-map accesses
`that can be retrieved in one memory access.
`Percentage-1 • is the percentage of single mip-map accesses
`that can be retrieved in two memory accesses.
`Percentage.,.,..drar>1• is the percentage of single mip-map
`accesses that can be retrieved in four memory
`accesses.
`Mipmaps is the number of mip-maps involved in the filter
`operation.
`Factorc:a.pnu1.,,. is the compression factor if the texture is
`compressed.
`
`The average number of accesses is calculated by
`taking into account the likelihood that all data will be
`retrieved in single, double or quadruple accesses. The
`equation also takes account of the number of mip-maps
`required in the filtering operation, trilinear filtering
`uses two but bilinear requires only one. The equation
`also shows how the average number of accesses is reduced
`linearly with compression. Obviously the less data there
`is to fetch the less memory accesses that are required and
`the more likely all the data will reside in the same data
`word.
`
`Equation 1 thus shows that, even with the use of
`texture caches, the physical memory bandwidth requirement
`still remains beyond the scope of any viable memory
`system. For this reason texture compression is employed,
`not only to reduce the physical size of the stored
`texture, with its associated reduction in memory cost, but
`alsc to reduce the volume of texture data that is
`transferred from that memory.
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`0019
`
`

`
`- 10 -
`
`Equation 2 shows how the compression factor affects
`the number of memory accesses . High performance,
`dedicated hardware can be used to decompress the textures
`in real-time after they have been read from memory. Many
`texture compression techniques have been tried, including:
`Vector Quantisation (VQ) [ref. 11); Color lookup tables
`(CLUT) or Palletisation [ref. 12]; Discrete Cosine
`Transformation (OCT) [ref. 12]; and several proprietary
`techniques [refs. 6 and 14) . But each has its associated
`problems: VQ and Palletised require two memory reads or
`large internal data caches and quality can be limited; OCT
`requires a large amount of decompression logic, and with a
`limited silicon budget this can be unfeasible; and many
`proprietary techniques provide limited compress ion ratios
`and quality. As Equation 1 demonstrates, these techniques
`only go part way towards resolving the bandwidth
`requirements of trilinear filtering.
`Memory access streams that continuously swap between
`different memory banks can have a large effect on
`performance. Equation 1 shows how dominant page breaks
`are to the performance of texture filtering as a whole.
`For trilinear filtering, page breaks can be particularly
`problematic, where a number of mip-maps can often span
`more than one memory page.
`3D imaging techniques often demand such a high level
`of performance that only dedicated hardware solutions can
`be used . This often requires the development of a special
`silicon chip. As well as performing texture mapping, the
`chip will often be called upon to perform all the geometry
`processing, polygon set up,
`image projection, illumination
`calculations, fogging calculations, hidden surface
`removal, and display control. Therefore it is critical
`that each stage in the generation of a 30 image is made as
`small as possible to enable all processes to fit on the
`same silicon die. As well as requiring a large memory
`bandwidth, a trilinear filtering operation can only be
`implemented in a large amount of logic and therefore
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`0020
`
`

`
`- 11 -
`
`silicon area. It is important that an optimum solution be
`found that limits the required logic, and therefore cost,
`to a minimum.
`It is seen from the foregoing that the requirements
`of memory, speed and ease of construction of the chip are
`very substantial and are taxed to the full in 3D imaging,
`particularly when texture mapping. Even using all
`available techniques for meeting the requirements, the
`constraints are still very difficult to meet if high
`quality real-time imaging is to be achieved.
`
`Summary of the Invention
`The invention in its various aspects is defined in
`the independent claims below, to which reference should
`now be made. Advantageous features are set forth in the
`appendant claims.
`Preferred embodiments of the invention are described
`below with reference to the drawings.
`In these
`embodiments the efficiency of trilinear texture filtering
`is improved by the generation of the lower-level texture
`mip-map on the fly from the upper-level mip-map, and with
`the use of texture caching and texture decompression as a
`means of meeting the high memory bandwidth requirements.
`Removing the need to read the lower-level mip-map in a
`separate memory access, removes page break problems and
`enhances performance .
`More particularly, the preferred texturing systems
`comprise a memory for storing mip-map data for use in
`texturing an i mage, the mip-map data comprising a
`hierarchical series of mip-maps of different levels of
`decreasing resolution. Data is received at an input
`indicating the type of mip-map data required and the level
`of the mip-map or mip-maps from which the data is to be
`taken. A controller retrieves from the memory the mip-map
`data required in accordance with the input data, and this
`data is stored in a cache. A lower-level mip-map
`generator generates portions of the mip-map which is next
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`0021
`
`

`
`- 12 -
`
`below, in the hierarchical series, the mip-map of which
`portions are held in the cache. A trilinear interpolator
`receives from the cache mip-map data from one level of
`mip-map and from the lower - level mip-map generator data
`from the next lower level of mip-map, and interpolates one
`output texel from input texels from the two mip-map
`levels.
`Some data compression schemes lend themselves well to
`the generation of lower mip-maps on the fly by providing
`the required quantity of decompressed data and by closely
`supporting the filtering algorithm used to generate the
`lower-level mip-map . These techniques may be used to
`enhance the performance and quality of a 3D rendered image
`while minimising the hardware overhead.
`In one preferred embodiment, the texture data is
`represented by arbitrary compressed codes, in which
`selected compressed code values define principal colors
`and other compressed code values define intermediate
`colors which can be formed by selected weighted averages
`of principal colors, the corresponding code values also
`being weighted averages of the code values of the selected
`principal colors. The lower-level mip-map generator
`interpolates an output texel from a plurality of input
`texels by operating on the compressed code values.
`
`Brief Description of the Drawings
`The invention will now be described in more detail,
`by way of example, with reference to the drawings, in
`which:
`Figure l is a diagram illustrating bilinear filter ing
`of the texture map in an imaging system;
`Figure 2 is a similar diagram illustrating trilinear
`filtering of the texture map in an imaging system;
`Figure 3 illustrates a series of mip- maps;
`Figure 4 is a block schematic diagram of part of an
`imaging system in accordance with the present invention;
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`0022
`
`

`
`- 13 -
`
`Figure 5 is a diagram illustrating the operation of
`the embodiment of Figure 4;
`Figur e 6 illustrates the storage of texture words in
`a worst-case scenario;
`Fi gure 7 is a block schematic diagram similar to
`Figure 4 of a second embodiment of the invention using
`four caches and four decompression units in parallel;
`Figure 8 illustrates in similar manner to Figure 6
`the storage of texture words in a best-case scenario;
`Fi gure 9 is a block diagram of a modification of the
`embodiment of Figure 7, in which the decompression units
`are dynamically re-allocated;
`Figure 10 is a block diagram of another modification
`of the circuit of Figure 7; and
`Figures 11 and 12 illustrate how interpolation can be
`directly applied to compressed texture codes .
`
`Detail ed Description of the Preferre d Embodiments
`Figure 4 shows a speci fic embodiment of a text uring
`system in accordance with the invention . The texturing
`system 20 comprises a memory system 22 forming part of the
`memory used by the imagi ng system as a whole, and which is
`controlled in known manner by a memory controller 24. The
`memory 22 holds inter a1ia a compressed texture map, and
`the output of the memory through the memory controller 24
`consists of compressed texture from the requested part of
`the texture map. Parameters defining the texture requ i red
`for any surface are received at an input 26 and applied to
`a texture address generator 28 to address the part of the
`memory 22 where the desired texture is located. The
`compressed texture is retrieved from memory by the memory
`controller 24 and held in a texture cache 30. The
`retrieved texture will correspond to a particular texture
`type representing the type of surface to be displayed.
`For example this may be part of a brick wa l l or the
`surface of a road. This surface texture will be held in
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`0023
`
`

`
`- 14 -
`
`mip- map form, as described above, actually in compressed
`mip-map form, and the mip-ma