United States Patent [19J
`Tarolli et al.
`
`111111111111111111111111111111111111111111111111111111111111111111111111111
`US005822452A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,822,452
`Oct. 13, 1998
`
`(54) SYSTEM AND METHOD FOR NARROW
`CHANNEL COMPRESSION
`
`[75]
`
`Inventors: Gary Tm-olli, Concord, Mass.; Scott
`Sellers, Menlo Park, Calif.; James E.
`Margeson, ill, Santa Clara, Calif.;
`Murali Sundaresan, Sunnyvale, Calif.
`
`[73] Assignee: 3Dfx Interactive, Inc., San Jose, Calif.
`
`[21] Appl. No.: 641,208
`
`Apr. 30, 1996
`[22] Filed:
`Int. C l.6 •..••..••..•...•..•............... •...•......•...•..... G06K 9/00
`[51]
`[52] U.S. CJ . ........................... 382/166; 382/232; 345/431
`[58] Field of Sem·ch ..................................... 382/ 232, 166;
`395/131; 345/139, 431
`
`[56]
`
`References C ited
`
`U.S. PATENT DOCUMENTS
`
`2/1990 Chandler ................................. 395/131
`4,905,164
`4,965,745 10/1990 Economy eL al. ...................... 364/5 18
`
`Primary Examiner-Jose L. Couso
`Assistam Examiner-Anb Hong Do
`Auorne)~ Agent, or Firn1~enwick & West LLP
`
`[57]
`
`ABSTRACT
`
`A system and method for compres.siog a nd decompressing a
`texture image tbat: (1) compresses eac.h texel to 8 bits, and
`wben decompressed, eacb texel is of a quality comparable to
`a 256 color paleuized image; (2) increases the efficiency of
`the decompres.sion system and method by eliminating com(cid:173)
`plex operations, e.g., multiplication; and (3) increases the
`efficiency of the system and method when switchi ng
`between textures lhat use dilferent pale ues, when compared
`to conventional system and methods. The invention com(cid:173)
`pres.ses a texture image, stores tbe compres.sed texture
`image, and quickly and efficiently decompresses the textwe
`image when determining a value of a pixel. Tbe texture
`image compression technique utilizes a palletized color
`space tha t more closely matches the colors in the texture
`image while allocating an unequal number of bits to the
`color channels. Eacb texel in tbe texture image is converted
`to an 8-bil value in the selected color :space, and a decom(cid:173)
`pression table is generated tbat represents tbe RGB values
`for tbe eacb texel stored in tbe selected color space. In order
`to map tbe texture image to the object, one or more texels
`that are associated witb eacb pixel are decompressed. Tbe
`present invention quickly and efficiently derompresses eacb
`texel using a hardware decompression unit. Tbe decompres(cid:173)
`sion unit does not perform any multiplication operations.
`
`13 Claims, 10 Drawing Sheets
`
`1102
`
`1104
`
`1106
`
`1t08
`
`1110
`
`1112
`
`11 14
`
`Add the First Channel
`Entry, the Red Value
`of the 2d Channel,
`and the Red Value of
`1he 3d ChaMel in a
`First Adder
`
`Add the FirS1 Channel
`Entry, the Green
`Value of 1he 2d
`Channel, end the
`Green Value of the 3d
`Channel in a Second
`Adder
`
`Add the First Channel
`Enlty, the Blue Value
`of tho 2d Chann~l.
`and the Blue Value of
`the 3d Channel in a
`Third Adder
`
`Retum
`
`0001
`
`Volkswagen 1005
`
`

`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 1 of 10
`
`5,822,452
`
`v- 102
`
`PROCESSOR
`
`104 ~
`
`MEMORY
`
`~ COMPRESSION r ~
`
`MODULE
`
`122
`
`l
`
`l
`
`( 106
`
`PROCESSOR / MEMORY BUS
`
`I/' 1oa
`
`VOBUS
`CONTROLLER
`
`( 110
`
`r 112
`
`MONITOR
`
`VOBUS
`
`( 114
`
`( 116
`
`GRAPHICS
`ENGINE
`
`1/0 DEVICE
`
`I
`
`I
`
`FIGURE 1
`
`0002
`
`

`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 2 of 10
`
`5,822,452
`
`v- 110
`
`(
`
`202
`
`FRAME
`BUFFER
`MEMORY
`
`(114
`
`218C
`
`I
`
`r 22ac .----__,
`TEXTURE
`TMU
`1---...---~ MEMORY
`020C '-... ..-..---..--_; ~6C \
`'=.210C
`' - 212C
`•
`
`v 216
`
`2208_..;'
`
`1'-- 218B
`
`FRAME +(cid:173)
`BUFFER
`INTERFACE
`
`TMU
`
`2288
`
`r
`
`.------.
`TEXTURE
`1---...---~ MEMORY
`\...
`226B ~ 2128
`
`'- 2108
`
`1.___ _ ___.~-.I· i f \
`• •
`• •
`e y
`220A
`.___,
`r
`
`218A
`
`228A
`- r
`....-
`
`.----__,
`TEXTURE
`MEMORY
`
`~6A \
`
`' - 210A
`
`' - 212A
`
`206 \
`
`,..--1-----l...---,
`
`DAC
`
`TMU
`
`112~
`
`MONITOR
`
`FIGURE 2
`
`0003
`
`

`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 3 of' 10
`
`5,822,452
`
`320A \
`
`I
`
`r--
`
`DU
`
`320B'
`
`r--
`
`DU
`
`320C """\
`
`r-
`
`DU
`
`320D '
`
`DU
`
`r
`
`(
`210C
`
`218~
`
`220B
`
`TEXTURE
`MEMORY
`
`228
`
`2C
`,r- 21
`
`r- 226
`
`;-- 308
`
`-
`306
`~
`
`v
`
`~ 318
`
`TEXTURE
`MEMORY
`ADDRESSER
`
`t
`
`LOD
`DITHERER
`
`TRIANGLE
`ITERATION
`UNIT
`
`t
`
`i
`
`(
`
`I,;,;
`8
`
`f-
`
`8
`-r-
`
`8
`
`8
`r+- ,
`v
`
`r-
`
`.__
`
`CONTROL
`REGISTER
`
`\... 324
`
`\. 216
`
`I I
`
`BILINEAR ~ 322
`BLENDING
`UNIT
`
`24
`~
`
`,
`
`,.3o4
`
`TMU
`
`TCU
`
`r 21 8C
`
`\... 22 oc
`
`FIGURE 3
`
`0004
`
`

`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 4 of 10
`
`5,822,452
`
`404
`
`406
`
`408
`
`410
`
`Compress Color
`Components and
`Generate Values
`for
`Decompression
`Table
`
`Select
`Decompression
`Table
`
`Store
`Decompression
`Table in TMU
`
`Decompress
`Color
`Components in
`TMU for each
`texel
`
`Figure 4
`
`0005
`
`

`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 5 of 10
`
`5,822,452
`
`Yes
`
`502
`
`504
`
`506
`
`508
`
`510
`
`514
`
`516
`
`Convert Image to
`Selected Color
`Space
`
`be Represented
`
`Convert Each
`Texel in the
`Image to a New
`8-bit Value
`
`Determine
`Decompression
`Values for Table
`
`Rgure 5
`
`0006
`
`

`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 6 of 10
`
`5,822,452
`
`FIGURE 6A
`
`FIGURE 68
`
`FIGURE 6C
`
`FIGURE 7
`
`y
`Index
`0000
`0001
`0010
`0011
`0100
`0101
`0110
`0111
`1000
`1001
`1010
`1011
`1100
`1101
`1110
`1111
`
`A
`Index
`00
`01
`10
`11
`
`8
`Index
`00
`01
`10
`11
`
`y
`Value
`20
`32
`43
`55
`66
`78
`89
`101
`112
`124
`135
`147
`158
`170
`181
`193
`
`A
`Value
`-27
`-8
`9
`28
`
`8
`Value
`-10
`-5
`0
`4
`
`Decomp.
`Table
`Address
`0
`1
`2
`3
`4
`5
`6
`7
`8
`9
`10
`11
`
`Decompression
`Table
`Value
`Ox372b2014
`Ox65594e42
`Ox93877c70
`Oxclb5aa9e
`Ox079c0eld
`Ox07e00409
`Ox0027fbf6
`Ox006fflel
`Ox07e80def
`Ox07f407t7
`OxOOOOOOOO
`Ox000bfa07
`
`0007
`
`

`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 7 of 10
`
`5,822,452
`
`SET UF HIDDEN LAYER
`NEURONS (HLN)
`
`INITIALIZE Y, A, 8
`NEURONS IN HLN
`
`REDUCE INPUT IMAGE
`INTO A REPRESENTATIVE
`SAMPLE OF INPUT
`COLORS
`
`COMPUTE THE WEIGHTS
`OF ALL INPUT LAYER
`NEURONS (ILN)
`
`SELECT AN INPUT
`VECTOR
`
`DETERMINE TWO ILN'S
`THAT MOST CLOSELY
`MATCH THE INPUT
`VECTOR
`
`MODIFY WEIGHT OF THE
`TWO ILN'S AND
`ASSOCIATED HLN
`
`DETERMINE INPUT
`VECTOR CYCLE ERROR
`
`YES
`
`YES
`
`802
`
`806
`
`808
`
`810
`
`814
`
`816
`
`818
`
`820
`
`822
`
`824
`
`FIGURE 8
`
`0008
`
`

`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 8 of 10
`
`5,822,452
`
`No
`
`G)
`G)
`G)
`
`---
`-.. -
`
`Y, .. .. ..
`GJ
`GJ
`Ao • -
`
`902
`
`• - 904
`
`Input Layer Neurons
`
`Hidden Layer Neurons
`
`Figure 9
`
`0009
`
`

`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 9 of 10
`
`5,822,452
`
`Table select
`-
`
`Figure 10
`va
`
`/
`
`r 320
`
`DU
`
`,., 4Y
`
`/
`
`.......
`
`2A
`
`/
`
`v28
`
`/
`
`(2x16)x8 Y -Channel
`Lookup RAM
`
`(2x4)X27 A-Channel
`Lookup RAM
`
`(2x4)x27 8-Channel
`Lookup RAM
`
`v8
`
`1002A _)
`
`1004A -~ /
`2
`
`10028 _)
`
`10048 \
`
`>
`
`1002C _)
`
`v21
`
`/
`
`1004C ""\
`
`/
`
`....... 27
`
`J >
`
`8
`
`/ v / /
`
`9 Red ,.,9 Red
`/
`
`8
`
`/ v / /
`
`9Grn V 9Gm
`/
`
`8
`
`/ v
`
`9 Blu
`/ v
`/ v
`
`9 Blu
`
`1006A ....../ v 11
`
`/
`
`10068 _./ v 11
`
`/
`
`1006C _./
`
`/
`
`11
`
`/
`
`I ClampOO-FF
`
`I
`
`'-.1008A
`
`I Clamp 00-FF
`
`I
`
`~
`
`r1o1oA
`
`[>
`
`,... 8 Red
`
`/
`
`l Clamp 00-FF
`
`I
`
`'-1008C
`
`C>
`
`r1o1oc
`
`V 8Biu
`
`/
`
`'-10088
`
`r 1o1os
`
`,., SGrn
`
`/
`
`24
`
`/
`
`/
`
`0010
`
`

`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 10 of 10
`
`5,822,452
`
`c-
`Begin •
`Compressed T exel v-
`
`Decompose
`
`Texture Value into
`Three Channel
`Values
`
`Determine the
`Assoc1ated Entry
`
`For each Channel v-
`+
`Decompose Entry into r-
`
`Red, Green, and Blue
`Values
`
`+
`Entry, the Red Value v-
`
`Add the First Channel
`
`of the 2d Channel,
`and the Red Value of
`the 3d Channel in a
`
`First Adder •
`Value of the 2d r-
`
`Add the First Channel
`Entry, the Green
`
`Channel, and the
`Green Value of the 3d
`Channel in a Second
`Adder
`
`Add the First Channel
`
`•
`Entry, the Blue Value r-
`
`1102
`
`1104
`
`1106
`
`1108
`
`1110
`
`1112
`
`of the 2d Channel,
`and the Blue Value of
`the 3d Channel in a
`Third Adder
`
`•
`• Return
`
`1114
`Clamp the output of ~
`each Adder to 00-FF
`
`)
`
`Figure 11
`
`0011
`
`

`
`5,822,452
`
`1
`SYSTEM AND METHOD FOR NARROW
`CHANNEL COMPRESSION
`
`CROSS-REFERENCES TO RELATED
`APPLICAf'lONS
`
`The subject maHer of tbis application is related to the
`subject maHer of the fo llowing applications:
`application Ser. No. 08/552,740, entitled ' 'TEXTURE
`COMPOSITING APPA R ~TUS AND METHOD",
`filed on 03 Nov. 1995, by Gary Tarolli, Scott Sellers,
`and James E. Margeson, III; and
`applicatioo Ser. No. 08/640,450, entitled "SYSTEM AND
`METHOD FOR LEVEL OF DETAIL DITHERING",
`filed on 30 Apr. 1996, by Gary Tarolli, ScotL Sellers,
`and James E. Margeson, Ill;
`U.S. patent application Ser. No. 08/640,070, entitled
`'·SYSTEM AND METHOD FOR SELECTING A
`COLOR SPACE USING A NEURAL NETWORK",
`filed on 30 Apr. 1996, by Murali Sundaresan;
`all of the above applications are incorporated by reference
`herein in their entirety.
`
`BACKGROUND OF THE INVENTION
`
`J. Field of the Invention
`The present invention relates generally to the field of
`image processing, and more particularly to the field of
`texture image data compression.
`2. Description of Background Art
`Recent advances in computer performance have enabled
`grapbic systems to provide more realistic grapbical images
`using personal computers and borne video game computers.
`In such graphic systems, some procedure must be imple(cid:173)
`mented to "render" or draw grapbic primitives to the screen
`of the system. Graphic primitives are basic components of a
`graphic picture, for example a polygon or a vector. AJl
`graphic pictures are formed with combinations of these
`graphic primitives and many procedures may be utilized to
`perform graphic primitive rendering.
`Conventional graphic systems perform such graphic
`primitive rendering procedures using a frame bu lfer. A frame
`buffer generally includes a plurality of computer memory
`chips that store information concerning pixel activation on
`the system's display screen. Generally, the frame buffer
`includes au of the graphic da ta information that will be
`written onto the screen.
`Early graphic systems displayed images representing
`objects having extremely smooth surfaces. That is, textures,
`bumps, scratches, or other surface features were not mod(cid:173)
`eled. In order to improve the quality of the image, texture
`mapping was developed to model the complexity of real
`world surface images. In general, texture mapping is the
`mapping of an image or function onto a surface in th ree
`dimensions. Texture mapping is a relatively efficient tech(cid:173)
`nique fo r creating the appearance of a complex image
`without the tedium and computational cost of rendering
`th ree dimensional detail that might be found on a surface of
`an object.
`Many parameters have been texture mapped in conven(cid:173)
`tional systems. Some of these parameters include surface
`color, specular reflection, no rmal vector perturbation,
`specularity, tra nsparency, diffuse reflections, and shadows.
`In texture mapping, a source image known as the " texture"
`is mapped onto a surface in three dimensional space. The
`
`5
`
`2
`three dimensional surface is then mapped to the destination
`image. The desti nation image is then displayed on a graphic
`display screen. Examples of the texture of an object include
`the gravel on a highway or scuff marks on a wooden surface.
`A texture map comprises texture elements, i.e., texels. The
`values of these texels are stored in texture memory. Texture
`memory is a valuable and scarce resource in a graphics
`system. In order to more efficiently utilize the texture
`memory, the da ta represen ti ng the texture map can be
`10 compressed. In conventional systems, each texel is repre(cid:173)
`sented as a 16-bit or 24-bit val ue in the red-green-blue
`(RGB) color space. When each texel is 16-bits, the red color
`component can be represented with 5-bits, the green color
`component can be represented with 6-bits, and the blue color
`15 component can be represented with 5-bits. When the texels
`in a texel map are represented in this manner, the texel
`representation is called an RGB565 image. Similarly, a texel
`can be represented as a 24-bit value with each color com(cid:173)
`ponent (channel) represen ted with 8-bits. Such a texel rep-
`20 resentation is called a RGB888 image.
`A fi rst conventional technique for compressing da ta in a
`texture map is to reduce the RGB565 image or the RGB888
`image to a RGB332 image. That is, tbe 16-bit image or 24
`bit-image is reduced to an 8-bit image. When reducing a
`25 RGB888 image to a RGB332 image, the number of bits
`representing each color channel contribution to the texel is
`reduced from 8-bits to 3-bits, for the red channel and the
`green channel, and from 8-bits to 2-bits, for the blue
`channel. One technique for reducing the number of bits used
`30 for each color channel is to use only the most significant bits
`from the uncompressed image. For example, if a RGB888
`image is reduced to a RGB332 image the compressed 3-bit
`representation is equal to the three most significant bits
`(MSB) of the uncompressed 8-bit red channel representa-
`35 tion. The compressed 3-bit green channel representation is
`equal to the three MSB's of the uncornpressed 8-bit green
`channel representation. Similarly, the compressed 2-bit blue
`channel representation is equal to the two MSB's of the
`uncompressed 8-bit blue channel represen tation.
`A second conventional technique for reducing the number
`of bits used for eacb color channel is to determine a
`predefined number of MSB's, e.g., in a RGB332 image the
`three MSB's of the red channel olf the uncompressed
`RGB888 image arc determined. Instead of setting each texel
`45 value equal to these three bits, the values of a group of texels
`are dithered across an area using conventional d ithering
`techniques. A benefit of this technique is that the hardware
`required to implement the data compression and data
`decompression is inexpensive. However, the data loss is
`so bigh and the decompressed image quality is poor.
`A second conventional technique for compressing da ta in
`a texture image is to paUetize the texture image. When
`palellizing a texture image, a small palette of colors is
`selected, e.g., 16 or 256 colors. Each texel in the uncom-
`55 pressed texture image is represented by a predetermined
`number of bits, e.g., 16-bits, 24-bits, or 32-bits. Each texel
`is translated into a 4-bit or an 8-bit indexed range of colors
`where the indices for each texel refer to the color in the
`reduced palette that is closest to the color in the uncom-
`60 pressed image. Each color in the color palette is represented
`by tbrec bytes, ooe byte for each color cbannel, e.g., red,
`green, and blue. A technique for reducing a color texture
`image to a compressed 256 color palentized image is given
`in Burger, Heckbert's Median Cut Algorithm, Interactive
`65 Computer Graph ics: Functional, Procedural, and Device(cid:173)
`Level Methods (1989) that is hereby incorporated by refer(cid:173)
`ence in its entirety. Accordingly, the uncompressed texel
`
`40
`
`0012
`
`

`
`5,822,452
`
`3
`image is compressed into a 4-bit or an 8-bit palettized image,
`thereby compressing the texture image by a factor between
`2 and 8. In many situations, compressing a 32-bit texture
`image into a 256 color palcttized texture results in an image
`that is virtually indistinguishable form the uncompres.sed 5
`texel image.
`llowever, there are several problems with using palettized
`images as textures in a graphic system. One problem with
`using palettized images is that if the graphic system imple(cid:173)
`ments bil inear filtering, described below, four texels are 10
`accessed in the texture memory wben determ ining the value
`of a single pixel. If these four texel accesses occur in
`parallel, as is preferred, eacb of tbe four texels arc simul(cid:173)
`taneously translated through a 256 color palette. The bard(cid:173)
`ware for implementing tbis technique requires a 256 entry 15
`table of three bytes each, having four read ports. This
`bardware is expensive.
`A second problem with using palettized images as tex(cid:173)
`tures in a graphics system is that when switching between
`textures that use diiierent palettes, at least 768 bytes (256 20
`colors muhipHed by three bytes) are downloaded into tbe
`hardware to ensure that the new texture bas the appropriate
`palette installed. In graphic systems where textures are
`frequen tly switched between, such a large palelle size
`reduces the efficiency of the system.
`What is needed is a system and method for compressing
`and decompressing a texture image that: (1) compresses
`each texel to 8 bits, and when decompressed, each texel is
`of a quality comparable to a 256 color palettized image; (2)
`increases the efficiency or the decompression system and
`method by eliminating complex operations, e.g., multipH(cid:173)
`cation; (3) increases the efficiency of the system and method
`when switcbing between textures that use different palettes,
`when compared to conventional system and methods; and 35
`(4) automatically determines a compression color space for
`each texture image.
`
`30
`
`25
`
`SUMMARY OF THE INVENTION
`
`The invention is a system and method for compressing 40
`and dccomprcs.sing a texture image tbat: (1) compresses
`each texel to 8 bits, and when decompressed, each texel is
`of a quality comparable to a 256 color palettizecl image; (2)
`increases the efficiency of tbe clecompres.sion system and
`method by eliminating complex operations, e.g., multipH- 45
`cation; (3) increases tbc efficiency of the system and method
`when switching between textures that use different palettes,
`when compared to conventional system and methods; and
`(4) automatically determines a compression color space for
`each texture image.
`The method and apparatus of the present invention com(cid:173)
`presses a texture image, stores the compressed texture
`image, and quickly and efficiently decompresses the texture
`image when determining a value of a pixel. The texture
`image compression technique utilizes a paUetized color 55
`space that more closely matches the colors in the texture
`image while allocating an unequal number of bits to the
`color channels. Tbe texture image is, typically, a red-green(cid:173)
`blue (RGB) color channel representation. The present inven(cid:173)
`tion selects a compression color space manually, or 60
`preferable, using a computer-based neural network algo(cid:173)
`rithm. '!'be invention initializes the neural network that
`includes an input layer of neurons and a bidden layer of
`neurons, e.g., Y neurons, A neurons, and B neurons. Each
`input layer neuron bas an associated weigbt that is equal to 65
`the combination of the weights of a Y neuron, an A neuron,
`and a B neuron that is as.sociated with each input layer
`
`50
`
`0013
`
`4
`neuron. The texel image is reduced into a representative
`sample of colors and input vectors from the texel image are
`randomly selected. For each input vector, the present inven(cid:173)
`tion determines the two input layer neurons that most closely
`match the input vector and modifies the weights of the two
`input layer neurons to more closely match the value of the
`input vector. The weight of the two matching input layer
`neurons are modilled by modifying the weights of the three
`associated hidden layer neurons. After analyzing all input
`vectors, the invention determines an error value. Tbe error
`value is associated witb a first analysis cycle of randomly
`received input vectors. The cycle repeats until the error
`value stabilizes or is equal to zero. The weights of the hidden
`layer neurons represent tbe Y, A, and B~cbaooel values of the
`optimal compression color space.
`Each texcl in the texture image is converted to an 8-bit
`value in the selected color space, and a decompression table
`is generated that represents the RGB values for the each
`texel stored in tbe selected color space. Wben rendering a
`pixel representing an object with a texture, the teXlure image
`is mapped to the representation of the object. In order to map
`the texture image to the object, one or more tcxels that are
`associated with each pixel arc decompressed. The present
`invention quickly and efficiently decompresses each tcxel
`using a hardware decompression unit. The decompression
`unit includes three adders and memory for storing the
`decompression table. Each texel is rep resented by 8-bi!s.
`The 8-bits are indices into the decompression table. T he
`decompression table represents the red, green, and blue
`components of pre-selected values in the YAB color space.
`The decompression unit combines three reel components,
`three of green components, and three blue components to
`generate a 24-bit representation of each texel.
`In order to switch between textures that utilize a new
`palette, the decompression table associated with the new
`palette is retrieved and stored in the decompression unit and
`the 8-bit tcxcl representations are retrieved and stored in a
`texture memory unit.
`BRIEF DESCRIP'l10N OF THE DRAWINGS
`FIG. 1 is an illustration of a computer system in wbicb the
`preferred embodiment of the present invention operates.
`FIG. 2 is an illustration of the graphic engine of the
`preferred embod.imeot of tbc present invention.
`FIG. 3 is an illustration of a texture mapping unit and
`texture memory according to the preferred embodiment of
`the present invention.
`FIG. 4 is a flow chart of the operation of the method of the
`preferred embodiment of the present in vention.
`FIG. 5 is a flow chart of tbe technique for compressing
`color components and gcneratiog values of a decompression
`table.
`FIG. 6A is an illustration of a Y index and an associated
`Y representation value according to a first example o[ an
`embodiment of the present invention.
`FIG. 6B is an illust ration o[ ao A index and an associated
`A representation value according to a first example of an
`embodiment o( the present invention.
`FIG. 6C is an illust ration of a B index and an associated
`B representation value according to a first example of an
`embodiment of the present invention.
`FIG. 7 is an illustration of a decompression table of the
`first example according to an embodiment of the present
`invention.
`FIG. 8 is a flowchart of the YAB color space selection
`process using the color space neural network technique of
`tbe preferred embodiment of the present iovcolioo .
`
`

`
`5,822,452
`
`5
`FIG. 9 is a representation of input layer neurons and
`bidden layer neurons in a neural network.
`FIG. 10 is an iJiustration of the decompression unit
`according to the preferred embodiment of the present inven(cid:173)
`tion.
`FIG. 11 ~'> a How chart of the operation of the decom(cid:173)
`pression unit according to the preferred embodiment of the
`present invention.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`15
`
`6
`210 receives a texture color/alpha input signal from a
`previous TMU 210. The texture color/ alpha input signal is
`received via tbc input/output texture color signal line 218,
`and the input/output textu.re alpha signal line 220 . Each
`5 TMU 210 generates a texture color/alpba output signal. This
`texture color/alpha output signal is transmilled on another
`input/output texture color line 218 and another input/output
`alpha texture color line 220. The texture color value gener(cid:173)
`ated by the TI IU 210C that is the last in the chain ofTMU's
`10 210 is tra nsmilled to the Fl31 204. The TMU 210 is described
`in greater detail below with reference to FIGS. 3-U .
`FIG. 3 is an illustration of a lMU 210 and a texture
`memory unit 212 of tbe present invention. Eaeb TMU 210
`includes a control register 324, a triangle iteration uoit 318,
`a level of detail (LOD) ditberer 306, a texture memory
`addresser 308, four decompression units (DU) 320, a bilin-
`ear blending unit 322, and a texture composite uoit (TCU)
`304. lbc TMU 210 and the LOD ditbc rer 306 arc described
`in greater detail in co-pendiog patent application entitled
`LOD Dilliering Apparatlls and Method, referenced above.
`Tbe TCU 304 is described in greater detai l in co-pending
`application entitled Texture ComposiJion Apparatus and
`Method, referenced above. The triangle iteratioo unit 318 is
`initialized and synchronized with otber triangle iteration
`units located in other TMU's 210A, 210B, and in tbe Frame
`Duller Interface 204 by a control signal received on control
`line 216 and stored in tbe control register 324. Once initial(cid:173)
`ized and synchronized, the triangle iteration uni t318 renders
`objects usiog a shape, e .g., a triaogle. in a predetermined
`manner. The triangle iteration unit 3 18 iterates tbrougb each
`pixel in an object and sends the pixel coordinates and tbe
`LOD va lue to the LOD ditberer. The LOD Ditherer 306
`receives the pixel coordinates for eacb pixel from a triangle
`iteration unit 3 18. For each pixel, the LOD ditherer 306
`determines the mipmap [rom which the pixel value is
`generated and outputs tbe mipmap level to the texture
`memory addresser 308. For each pixel. tbe texl\lre memory
`addresser 308 outputs tbe mipmap address to the texture
`memory 212C via address signal line 226. Based upon tbc
`40 mipmap address, tbe textme memory outputs four texture
`signals to tbc TMU 210 representing the values of four
`texels, in the determined mipmap. These four texel values
`are used to determioe the pixel va lue, as described below. In
`the preferred embodiment, each DU 320 receives an 8-bit
`45 signal representing the value of one texcl from the deter(cid:173)
`mined mipmap. Each decompression uni t generates a 24-bit
`red-green-blue (RGB) color signal from the received 8-bit
`signal. The decompres.o;;ed RGB signal generated by each
`DU 320 represents the value of one o[ the lour texels. The
`so four texel values arc combined io a bilinear blending uoi t
`322 and a single 24 bit RGB signal is output from the
`bilinear blending unit 322 representing tbe value of a pixel.
`Before decompressing the tcxcl values, the texel values
`are compressed. ln tbe preferred embodiment, tbe texel
`ss values are compressed off-line, i.e., all texel image com(cid:173)
`pression occurs before decompressing any texels or deter(cid:173)
`mining the value of any pixels. One reason for this is that the
`decompression technique is dynamic io tbat eacb pixel can
`be represented by any of a large number of combinations of
`60 texel values based upon, for example, texcl pitcb, the LOD
`value, and pixel posit ion relative to tbc texel map.
`Accordingly, the compression process reduces Lbe texture
`memory 2U size requirements and tbe decompression logic
`in the DU 320 by compressing the data in a manner that
`65 optimizes the texel representation size in relation to the texel
`representation quality after decompression. In addition, all
`decomprcs.sion multiplication operations are performed dur-
`
`A preferred embodiment of the present in described now
`described with reference to the figures where like reference
`numbers indicate identical or functionally similar elements.
`Also in the figures, the left most digit(s) of each reference
`number correspond(s) to the figure in which the reference
`number is first used.
`FIG. 1 is an illustration of a computer system 1110 in
`which the preferred embodiment of tbe present invention 20
`operates. In the preferred embodiment, the computer system
`100 is a conventional personal computer, e.g., an IBM
`compatible personal computer having a non-conventional
`graphics engine 114 and a non-conventional compression
`module 122 stored in conventional random access memory 25
`(RAM) 104. In an alternate embodiment, the computer
`system is a video game p latform, e.g., a Nintendo game
`platform, commerciall y available from Nintendo of
`America, Inc., Red mond, Wash. In t he p referred
`embodiment, tbe processor 102 of tbe computer system 100 30
`is a Pemium processor, commercially available from INTEL
`Corporation, Santa Clara, Calif. The processor/memory bus
`106 and the input/output (1/0) bus 110 are conventional. A
`conventional l/0 bus controller 108 controls the data flow
`between the I/0 bus 110 and tbe processor/memory bus 106. 35
`Conventional input/output devices 116, e.g., a keyboard, are
`connected to the l/0 bus 110. A conventional computer
`monitor 112 is driven by the grapbi<.:s engine unit 114. The
`graphics engine unit 114 is described in greater detail below
`with reference to FIGS. 2-11.
`FIG. 2 is an illustration of the graphics engine unit l14 of
`the present invention. A frame buffer interface (FBI) 204 is
`coupled to the 1/0 bus 110. Tbe FBI 204 is also coupled to
`a frame buffer memory 202, a conventional digital-to-analog
`converter (DAC) 206, and one or more texture mapping
`units (TMU) 210. The DAC 206 is also coupled to tbe
`monitor 112. Each TMU 210 is also connected to a texture
`memory 212. Tile FBI 204 is, preferably, an application
`specific integrated circuit (ASIC) that serves as an l/0 slave
`device, and all communication from tbc processor 102 to the
`graphics engine 114 is performed through the FBI 204. The
`FBI 204 implements basic tbree dimensional primitives
`including Gouraud shading, depth buffering, and ditbcriog.
`The FBI 204 also controls the output to the monitor 112.
`Each TMU 210 is also, preferably, an ASIC. The TMU
`210 performs composite texture mapping including texture
`morphing, and texture filtering. The operation of the TMU
`210 is described io greater detail below with reference to
`FIGS. 2-11. Preferably, the frame buffer memory 202 and
`the texture memory 212 are extended-data-out (EDO)
`dynamic random access memory (DRAM). The TMU 210
`receives a control sigoal CfRL from tbe FBI 204 via a
`cootrol signal line 216. ln addition, each THU 210 receives
`a local texture signal from its associated texture memory
`212. The local texture signal is received via a local texture
`signal li.ne 228 in response to an add ress request from the
`TMU via the address signal lioe 226. In additioo, each TMU
`
`0014
`
`

`
`5,822,452
`
`7
`ing the compression phase. The compression techniques of
`the preferred embodiment wiU now be described and lbeo
`the decompression technique and the decompression bard(cid:173)
`ware will be described.
`FIG. 4 is a flow chart of lbe operation of the preferred 5
`embodiment of the present invention. Tbe compression
`module 122 compresses 404 the color compooenL'> and
`generates values for the decompression table. As described
`above, this process is performed for all texel images. After
`all texel images have been compressed and the computer
`100 is operati ng an appUcation program, the graphics engine
`114 begins the decompression process by selecting 406 a
`decompression table generated by tbe compression module
`122. One or more decompression tables are stored 408 in the
`DU 320 and the DU 320 decompresses 410 the texels to
`determine pixel values that are displayed on the monitor 112.
`Tbe process of compressing 404 the color components and
`generating values for the decompression table is now set
`fort b.
`Ao; described above, in conventional systems texels are
`represented using ROB color channels. However the present
`invention uses a YAB color space. Each texel is represented
`by 8-bits in the YAB color space, e.g., 4 bits for the
`Y-cbaonel, and 2-bits each for of the A-channel and the
`B-channel. In addition, the 8-bits do not represent the
`channel values directly. Instead, the channel bits index a
`channel palette. For example, theY-channel has a 16 entry
`palette that is indexed by the 4-bits of the Y-channel texel
`representation, the A-channel and the B-cbannel have a four
`entry palette that are each indexed by the 2-bit A-channel
`and B-cbannel texel representation. The use of a YAB color
`space achieves data compression using fewer bits per texel,
`like the RGB332, while providing a high quality image
`comparable to the palettized textures. However, since the
`size of the palettes arc significantly smaller when compared
`to the 256-color paletlized texture, expensive hardware
`implementation is avoided and palette downloading is sig(cid:173)
`nificantly faster. For example, more texel maps can be stored
`in the texture memory 212 using the present invention when
`compared to storing textu.re maps having a 256-color palette.
`One example of the YAB color space is a YlQ color space.
`Some distinctions between the YIQ color space and the
`traditional ROB color space are now set forth. The tradi(cid:173)
`tional ROB color space used in computer graphics bas
`redundant infom1ation in each of the red, green, and blue
`channels. There are alternate color spaces, such as the YlQ
`color space, that provide image quality that is as goo