United States Patent [19]
`Baldwin
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US005798770A
`[111 Patent Number:
`[451 Date of Patent:
`
`5,798,770
`Aug. 25, 1998
`
`[54] GRAPHICS RENDERING SYSTEM WITH
`RECONFIGURABLE PIPELINE SEQUENCE
`
`[75]
`
`Inventor: David Robert Baldwin. Weybridge.
`United Kingdom
`
`[73] Assignee: 3DLabs Inc. Ltd •. Hamilton. Bermuda
`
`[21] Appl. No.: 640,620
`
`[22] Filed:
`
`May 1, 1996
`
`Related U.S. Application Data
`
`OTHER PUBLICATIONS
`
`Foley et al .. "Computer Graphics. Principles and Practice".
`2 ed in C.1996. Chapter 18. pp. 855-920.
`Kogge. P.M .. "The Microprogramming of Pipelined Proces(cid:173)
`sors". 1977. Proc. 4th Ann. Conf Parallel Procesing. IEEE.
`March. pp. 63-69.
`Computer Graphics. vol. 22. No. 4. "A display system for
`the Stellar graphics Supercomputer Model GSlOOO". Brian
`Apgar et al.. Aug. 1988.
`
`Primary Examiner-Kee M. Tung
`Attorney, Agent, or Firm-Robert Groover; Betty Formby;
`Matthew S. Anderson
`
`[60] Provisional application No. 601008,803 Dec. 18, 1995.
`
`[57]
`
`ABSTRACT
`
`[63] Continuation-in-part of Ser. No. 410,345, Mar. 24, 1995.
`Int. Cl.6
`....................................................... G06T 1/20
`[51]
`[52] U.S. Cl ............................ 345/506; 345/519; 345/509
`[58] Field of Search ..................................... 395/506. 502.
`395/507. 509. 519. 122. 130. 132. 125.
`503; 345/506. 507. 502. 509. 519. 422.
`430-432. 425. 503
`
`[56]
`
`References Cited
`
`U.S. P~ DOCUMENTS
`
`The preferred embodiment discloses a pipelined graphics
`processor in which the sequence can be dynamically recon(cid:173)
`figured (e.g. between primitives) in a rendering sequence.
`The pipeline sequence can be configured for compliance
`with specifications such as OpenGL. but may also be opti(cid:173)
`mized by reconfiguring the pipeline sequence to eliminate
`unnecessary processing. In a preferred embodiment, pixel
`elimination sequences such as depth and stencil tests are
`performed before texturing calculations are performed. so
`that unneeded pixel data is discarded before said texturing
`calculations are performed.
`
`4,866,637
`5,392,391
`
`9/1989 Gonzalez-Lopez ..................... 395/506
`211995 Caulk, Jr. et al ....................... 395/503
`
`26 Claims, 12 Drawing Sheets
`
`RASTERIZER
`
`SCISSOR
`
`TEST - STIPPLE
`
`ALPHA TEST
`
`ANTIAI.IAS I---
`APPLICATION
`
`FOG
`
`COLOR DDA
`
`~
`
`TEXTURE
`
`J_
`PIXEL
`f-- OWNERSHIP f--
`(GID)
`
`LB
`READ
`
`STENCIL
`TEST
`
`1------
`
`DEPTH
`TEST
`
`1------
`
`LB
`WRITE
`
`v~
`
`LOCALBUFFER
`
`,-----
`
`LOGICAL OP/
`FB
`WRITE I-- FRAME BUFFER 1----
`MASK
`
`COLOR
`FORIJAT I--
`(DITHER)
`
`.-- '----
`ALPHA
`FB
`BLEND I-- READ
`
`~~
`
`FRAMEBUFFER
`
`HOST
`OUT
`
`APPENDIX O
`
`Microsoft Corp. Exhibit 1005
`
`

`
`U.S. Patent
`
`Aug. 25, 1998
`
`Sheet 1 of 12
`
`5,798,770
`
`FIG. 1A
`
`WORLD COO RDINATES (3D)
`
`TRANSFORM
`
`{
`
`INTO VIEW
`TRANSFORM
`COORDINATES AND
`CANONICAL VIEW VOLUME
`
`VIEW COOR DINATES (3D)
`
`CLIP
`
`CLIP AGAINST CANONICAL
`VIEW VOLUME
`
`VIEW COOR DINATES (3D)
`
`PROJECT ON TO
`VIEW PLANE
`
`VIEW COOR DINATES (2D)
`
`TRANSFORM
`
`MAP INTO VIEW PORT
`
`NORMALIZED DEVICE COORDINATES
`
`TRANSFORM TO PHYSICAL
`DEVICE COORDINATES
`
`PHYSICAL D EVICE COORDINATES
`
`RENDER
`
`APPENDIX O
`
`Microsoft Corp. Exhibit 1005
`
`

`
`U.S. Patent
`
`VERTICES
`
`Aug. 25, 1998
`Sheet 2 of 12
`FIG. 1B
`COLOR
`INDEX
`~
`CURRENT
`COLOR
`
`VERTEX
`RASTERPOS NORMAL
`+
`CURRENT
`NORMAL
`
`5,798,770
`
`TEXCOORD
`l
`CURRENT
`TEXTURE
`COORDINATES
`
`1
`MODEL VIEW
`MATRIX
`
`LIGHTING
`AND COLORING
`
`~
`
`PRIMITIVE ASSEMBLY
`t
`APPLICATION-SPECIFIC CLIPPING
`
`• TEXGEN
`•
`MATRIX •
`
`TEXTURE
`
`l
`
`+
`PROJECTION
`MATRIX
`~
`
`1
`
`,
`
`VIEW VOLUME CLIPPING
`
`DIVIDE BY
`W; VIEWPORT
`
`•
`•
`
`f.+
`
`RASTERIZATION
`
`PER-FRAGMENT OPERATIONS
`
`•
`•
`
`FRAME BUFFER
`
`READPIXELS
`
`DRAWPIXELS
`TEXIMAGE
`
`PIXEL
`STORAGE
`MODES
`
`PIXEL
`TRANSFER
`MODES
`
`l
`
`TEXTURE f.--
`MEMORY
`
`PRIMITIVES
`
`•
`
`CURRENT
`RASTER
`POSITION
`
`FRAGMENTS
`
`PIXELS
`
`0
`
`APPENDIX O
`
`Microsoft Corp. Exhibit 1005
`
`

`
`'"" =
`'""
`'""
`
`....
`010
`\C
`....
`Ol
`
`N
`1-<
`~
`w
`
`t:r' l
`
`rJJ
`
`~
`..
`> = ~
`
`VI
`N
`
`1-<
`
`~ = ......
`~ ......
`~ • r.n •
`
`INTERFACE UNIT
`
`FRAMEBUFFER
`
`INTERFACE UNIT
`
`FRAMEBUFFER
`
`ADDRESS [24] ADDRESS (24]
`
`!
`
`t
`
`READ
`
`FRAMEBUFFER
`
`READ
`
`~
`f ! I
`
`WRITE
`
`DATA (32]
`
`I
`
`1
`
`READ
`
`DATA (32]
`
`WRITE
`
`!
`l
`
`w NOTED)
`R UNLESS OTHERWISE
`
`-1-BLEND -,-
`
`ALPHA
`
`DITHER
`
`~
`
`~
`
`LOGICAL
`
`OPS
`
`--
`
`FRAME BUFFER
`
`WRITE
`
`--
`
`OUT
`HOST
`
`GRAPH ICS PROCESSOR
`
`FIFO (OUT)
`
`INTERFACE -
`
`HOST
`
`BUFFER -1-STENCIL 1-'I-BUFFER ---
`LOCAL
`I +
`I
`
`DEPTH
`
`READ
`
`GID
`
`I
`
`WRITE
`
`LOCAL
`
`i
`
`f--
`
`TEST
`ALPHA
`
`1-
`
`-
`
`TEXTURE
`
`COLOR
`FOG
`
`1-1-
`
`DDA
`COLOR
`
`-
`
`STIPPLE
`SCISSOR 1-
`
`-
`
`RASTERIZER f-
`
`:'1
`
`t
`
`INTERFACE ---
`
`HOST
`
`GRAPH
`
`DATA (52)
`
`WRITE
`
`DATA (52)
`
`READ
`
`ADDRESS (24) ADDRE$S (24)
`
`WRITE
`
`READ
`
`LOCAL BUFFER INTERFACE UNIT
`
`FIG. 2A
`
`APPENDIX O
`
`Microsoft Corp. Exhibit 1005
`
`

`
`.....:a =
`
`~ .....:a
`00
`\C
`~ .....:a
`Ol
`
`"" s, -N
`\I). =-a
`
`-.. -~
`> = ~
`
`Ul
`N
`
`'"""" ~ = '""""
`~
`•
`d • 00
`
`i r-----------------------~-----~ ~ ~Pt ~------__ or---n--,
`
`FIG. 2B
`
`r--------,
`
`:
`I
`I
`
`~--<
`
`LB Rd H STENCIL H LB Wr
`
`G!D/Z/
`
`I
`
`I
`
`I
`
`I
`
`I
`
`BUFFER
`LOCAL
`
`LOCAL BUFFER INTERFACE
`
`I
`1 BUFFER
`FRAME-
`---------------------~--_______ _j
`I
`r
`1
`1
`I
`I
`I
`I
`I
`I
`I
`
`I u I
`
`_ST 1--
`
`ALPHA
`
`·
`I
`
`;;o
`fTI
`X
`fTI
`~h
`'=t
`c
`s:::
`
`1..-----------------.J
`TEXTURE UNIT I
`1
`1
`I
`I
`I
`
`1
`1
`1
`I
`1
`I
`r---------------,
`
`TRd
`
`TAddr
`
`TEXTURE
`
`COLOR
`FOG
`
`GLiNT2
`
`FRAMEBUFFER INTERFACE
`
`A D
`
`FB Rd
`
`DITHER 1-BLEND 1-
`
`FB W 1-LOGICAL
`
`OPS
`
`L--------
`I HOST INTERFACE J
`I
`I
`:
`. :
`I FRAMEBUFFER
`I
`'
`I
`1 L------------------0
`
`OUT
`HOST 1-
`
`~
`._.
`
`:I GRAPHICS CORE
`
`DDA
`
`COLOR
`
`;;o
`STIPPLE
`r;:1
`SCISSOR g
`
`;;o
`
`RASTERIZER
`
`.--
`
`I I
`1
`1 1
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`
`BYPASS
`
`PROCESSOR
`GRAPHICS
`
`FIFO (IN)
`PROCESSOR
`GRAPHICS
`
`BYPASS
`
`BUFFER
`LOCAL
`
`I
`V>
`V>>l
`;:g~l
`ool
`E;~l
`--lOI
`~::cl
`I
`:I:
`I
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`:
`
`~~--+--~
`
`I
`
`I
`I I FIFO (OUT)
`
`:
`
`APPENDIX O
`
`Microsoft Corp. Exhibit 1005
`
`

`
`U.S. Patent
`
`Aug. 25, 1998
`
`Sheet 5 of 12
`
`5,798,770
`
`FIG. 2C
`
`RASTERIZER
`
`SCISSOR
`TEST
`
`STIPPLE
`
`COLOR DDA
`
`ALPHA TEST
`
`ANTI ALIAS
`APPLICATION
`
`FOG
`
`TEXTURE
`
`~
`
`LB
`READ
`
`PIXEL
`OWNERSHIP
`(GID)
`
`STENCIL
`TEST
`
`DEPTH
`TEST
`
`LB
`WRITE
`
`LOCALBUFFER
`
`FB
`WRITE
`
`LOGICAL OP/
`FRAMEBUFFER
`MASK
`
`COLOR
`FORMAT
`(DITHER)
`
`ALPHA
`BLEND
`
`FB
`READ
`
`FRAME BUFFER
`
`HOST
`OUT
`
`APPENDIX O
`
`Microsoft Corp. Exhibit 1005
`
`

`
`Q
`"'I
`......:1
`Qe
`\C
`~ ......:1
`o-.
`
`~
`
`N
`1-"
`
`~
`
`s,
`~
`::r
`00
`
`~
`
`1-"
`
`tTl
`N
`~
`
`~
`
`> c
`
`~ a
`~ ......
`~
`•
`
`e • \J).
`
`""0 f-1-
`r::::t
`c
`s::::
`
`r--------------------,
`
`'
`
`WRITE
`
`LOCAL
`I
`
`I
`
`MLOCALBUFFER
`
`DEPTH
`
`MUX AND MATCH TREE
`
`GIO
`I
`
`I
`
`I
`I
`I
`I
`
`MTEXTURE
`L--------------------~
`I
`I
`I
`I
`READ
`I
`I
`BUFFER '----STENCIL r-'r-BUFFER 1-L...+.-
`I
`LOCAL
`I ..--
`I
`I
`
`-
`
`'I-
`,
`~
`
`I
`
`,
`
`TEST
`ALPHA
`
`-
`
`FOG -'r-
`
`COLOR
`TEXTURE
`
`1-
`
`I
`DDA
`COLOR
`
`TEXTURE
`
`I
`READ
`
`TEXTURE
`
`I
`ADDR
`
`:
`
`--'-
`I
`I
`1
`
`MFRAMEBUFFER
`
`',~
`
`I
`I
`I
`I
`I
`
`_ FRAMEBUFFER
`
`READ
`
`I
`
`'
`
`BLEND 1-
`ALPHA
`I
`
`-DITHER r-,
`
`',
`
`LOGICAL
`I
`
`OPS
`
`FRAMEBUFFER _
`
`WRITE
`
`I
`
`MUX AND MATCH TREE
`
`---------------------------------------~
`1
`I
`I
`
`OUT
`HOST _
`I
`
`I L____
`I
`I
`
`I
`I
`I
`I
`I
`
`r-------------------------------------------1
`
`MUX AND MATCH TREE
`
`L-------------------------------------~
`I
`I
`I
`I
`I
`I
`
`I
`I
`:::0
`r""1
`1 X
`r""1 r-------------------------------------1 ' r""1
`
`:,__
`
`1
`
`FIG. 2D
`
`r--------------,
`
`MRASTER
`
`STIPPLE H+ s
`SCISSOR
`
`:::0
`
`0
`:::0
`
`L------t-------J -
`I
`I MUX AND MATCH TREE
`I
`I
`I
`I
`INTERFACE 1
`I
`1
`
`I
`I
`I
`I
`I
`
`I
`I
`1
`
`TREE
`MATCH
`AND
`MUX
`
`INTERFACE
`
`HOST
`
`READ BACK
`
`BUS
`
`I
`
`RASTERIZER -
`
`HOST
`
`APPENDIX O
`
`Microsoft Corp. Exhibit 1005
`
`

`
`U.S. Patent
`
`Aug. 25, 1998
`
`Sheet 7 of 12
`
`5,798,770
`
`GLINT 400TX GRAPHICS PROCESSOR
`
`...
`r.-
`
`EXPANSION
`r+ ROM
`INTERFACE
`EXTERNAL VIDEO ...
`r.-
`
`LOGIC INTERFACE
`
`EPROM
`CONTROLS
`
`VIDEO
`LOGIC
`CONTROLS
`
`LOCALBUFFER MEMORY INTERFACE j.-
`
`r.-
`
`LOCALBUFFER
`
`r- LOCALBUFFER
`BYPASS
`
`1-
`
`1-
`
`PCJ
`BUS
`
`DMA
`CONTROL
`
`DATA
`FORMATTER
`
`'--
`
`1- FRAMEBUFFER
`BYPASS
`
`-
`
`VTG
`INTERFACE
`
`INPUT _
`FIFO
`
`OUTPUT
`
`FIFO -
`
`GRAPHICS
`CORE
`
`SHARED
`FRAMEBUFFER ~
`f+-
`INTERFACE
`
`t
`FRAMEBUFFER MEMORY INTERFACE r-
`t
`...
`r.-
`
`r.-
`
`VIDEO TIMING
`GENERATOR
`
`SHARED
`FRAME BUFFER
`CONTROL
`SIGNALS
`
`FRAME BUFFER
`
`TIMING
`CONTROL
`SIGNALS
`
`FIG. 2E
`
`APPENDIX O
`
`Microsoft Corp. Exhibit 1005
`
`

`
`"' .......,J
`~
`\C
`.....:.)
`._.
`01
`
`.....:.) =
`
`N
`~
`~
`00
`
`f!
`g:
`
`00
`~
`
`~
`
`~VI
`N
`
`> = ~
`
`("t> = ~
`~ ~
`•
`~ • 00
`
`~~ X
`3:: c
`Ll
`BUFFER ~r
`I
`
`INTERFACE UNIT
`
`FRAMEBUFFER
`
`FRAMEBUFFER INTERFACE UNIT
`
`READ
`~
`&;!
`,
`'H FRAMEBUFFER H ~-----~
`
`ADDRESS {24] ADDRESS [24)
`WRITE
`8 t
`£~·,•3 ~
`~··l
`
`READ
`4 t
`
`DATA [32]
`
`4
`
`•
`
`READ
`
`H BLEND
`ALPHA
`
`--------(cid:173)
`
`.----------"'
`
`,...,
`
`2
`
`DITHER
`
`LOGICAL
`
`OPS
`
`FRAMEBUFFER
`
`DATA [32]
`WRITE
`4 +
`l
`WRITE
`
`"'
`
`I HOST
`
`OUT
`
`FIG. 2F
`
`REDUCED TO
`
`32 BITS
`
`t
`
`INTERFACE 11
`
`HOST
`
`8
`
`LL
`~I
`
`:::0
`1"'1
`
`I
`
`TEST
`ALPHA
`------------·
`
`FOG
`
`COLOR
`TEXTURE
`
`,----
`
`M
`
`(52 BITS DATA, 9 BITS TAG)
`
`EXPANDED TO 61 BITS
`
`READ
`
`ADDRESS [24]
`
`READ
`
`-----;; =--;~
`~~ ~ ~ 4
`e5l
`DATA [52)
`
`">SSJ
`
`&ss,
`
`~
`
`2
`
`EXPANDED TO 49 BITS
`
`'-
`
`2
`
`DDA
`COLOR
`
`t-
`
`TEXTURE
`
`READ
`
`2
`ADOR ~
`
`H TEXTURE
`
`M r--
`~---------------
`(40 BITS DATA, 9 BITS TAG)
`
`FIFO (OUT)
`PROCESSOR
`GRAPHICS
`
`2
`
`32 1
`
`STIPPLE
`RASTERIZER H::}-ISCISSOR
`
`INTERFACE ~1-
`
`HOST
`
`FIFO (IN)
`PROCESSOR
`GRAPHICS
`
`4
`DATA [52]
`
`8
`DATA [52]
`
`4
`
`WRITE
`
`READ
`
`WRITE
`
`READ
`
`LOCAL BUFFER INTERFACE UNIT
`
`WRITE
`
`'L-0...!.-CA.:....L
`
`DEPTH
`STENCIL
`
`GID
`
`READ
`r------------1 BUFFER
`LOCAL
`------------
`
`----------
`8
`ADDRESS [24] ADDRESS [24]
`
`~
`
`'LOOK AHEAD' SPAN
`
`--~ FIFO FLAG
`
`NOTED)
`
`MESSAGE BUS (ALTERNATIVE SIZE)
`MESSAGE BUS (32 BITS DATA, 9 BITS TAG)
`
`-
`
`KEY
`
`DEEP
`
`1
`
`UNLESS OTHERWISE -
`
`~ FIFO (
`
`APPENDIX O
`
`Microsoft Corp. Exhibit 1005
`
`

`
`U.S. Patent
`
`Aug. 25, 1998
`
`Sheet 9 of 12
`
`5,798,770
`
`FIG. 3A
`
`32 BITS WIDE
`vB MBYTES DRAM
`
`LOCALBUFFER
`
`PLUG-IN CARD
`
`T CPU DOES HOS
`
`GEOME TRY PROCESSING
`\
`
`HOST CPU
`
`GLINT
`400TX
`
`4 MBYTES
`/
`
`1- ~
`
`VRAM
`
`-
`
`LUT -DAC
`
`I
`
`PCI LOCAL BUS
`
`FIG. 3B
`
`PLUG-IN CARD
`
`48 BITS WID~,
`>=10 MBYTES
`LOCALBUFFER
`
`LOCAL
`GEOMETRY
`PROCESSOR
`I
`
`GLINT
`400TX
`
`PCI-PCI
`BRIDGE
`
`16 MBYTES
`{1024x1280x32 BITS
`DOUBLE BUFFERED)
`I
`
`~---~
`
`VRAM
`
`1--- LUT-DAC
`
`I
`
`PCI LOCAL BUS
`
`APPENDIX O
`
`Microsoft Corp. Exhibit 1005
`
`

`
`U.S. Patent
`
`Aug. 25, 1998
`Sheet 10 of 12
`FIG. 3C
`
`5,798,770
`
`/e.g. S3 VISION964
`
`GUI
`ACCELERATOR
`
`I
`
`PCI
`LOCAL
`BUS
`
`PCI-PCI
`BRIDGE
`
`f - -
`
`GLINT
`400TX
`
`~---~
`
`FRAME BUFFER
`
`1-->--
`
`LUT -OAC
`
`I
`
`LOCALBUFFER
`
`PLUG-IN CARD
`
`FIG. 3D
`
`y FOR VIDEO CAPTURE
`AND PLAYBACK
`
`VIDEO
`COPROCESSOR
`
`I
`GLINT -- FRAMEBUFFER ~---- LUT-DAC
`I
`
`400TX
`
`LOCALBUFFER
`
`PLUG-IN CARD
`
`PCI
`LOCAL
`BUS
`
`PCI-PCI
`BRIDGE
`
`f - -
`
`APPENDIX O
`
`Microsoft Corp. Exhibit 1005
`
`

`
`U.S. Patent
`
`Aug. 25, 1998
`
`Sheet 11 of 12
`
`5,798,770
`
`FIG. 4A
`
`FIG. 4B
`
`Knee1~ -------
`
`Trapezoid C
`
`SUBORDINATE""-
`SIDE
`"
`
`SUBORDINATE/
`SIDE
`
`count3
`
`count2
`
`count1
`
`APPENDIX O
`
`Microsoft Corp. Exhibit 1005
`
`

`
`U.S. Patent
`
`Aug. 25, 1998
`
`Sheet 12 of 12
`
`5,798,770
`
`FROM
`SCISSOR/
`
`STIPLE - a::
`
`w
`:::c:
`u
`I--
`3:
`V)
`
`rn~
`SCISSOR/
`STIPLE
`
`---1
`
`a::
`u...J
`:::c
`u
`I--
`~
`V)
`
`rn~
`SCISSOR/
`STIPLE
`
`a::
`u...J
`:::c
`---1 u
`I--
`3::
`V)
`
`LB READ, GSD AND
`LB WRITE UNITS
`
`COLOR DDA, TEXTURE AND
`ALPHA TEST UNITS
`
`ROUTER UNIT
`FIG. 5A
`
`LB READ, GSD AND
`LB WRITE UNITS
`
`COLOR DDA, TEXTURE AND
`ALPHA TEST UNITS
`
`ROUTER UNIT
`FIG. 5B
`
`LB READ, GSD AND
`LB WRITE UNITS
`
`COLOR DDA, TEXTURE AND
`ALPHA TEST UNITS
`
`ROUTER UNIT
`FIG. 5C
`
`TO
`
`CL - FB READ
`
`a::
`w
`X w
`__,
`1--__,
`:::::1
`~
`
`ro
`FB READ
`
`f-+-
`
`a::
`w
`X
`__,
`w
`CL
`i= __,
`::::>
`~
`
`.....
`
`ro
`FB READ
`
`a::
`w
`X
`__,
`w
`CL
`1--__,
`:::::1
`~
`
`APPENDIX O
`
`Microsoft Corp. Exhibit 1005
`
`

`
`5.798.770
`
`1
`GRAPHICS RENDERING SYSTEM WITH
`RECONFIGURABLE PIPELINE SEQUENCE
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`
`This application is a continuation-in-part of 08/410.345
`filed Mar. 24, 1995, and claims priority from provisional
`60/008.803 filed Dec. 18. 1995. which is hereby incorpo(cid:173)
`rated by reference.
`
`BACKGROUND AND SUMMARY OF THE
`INVENI'ION
`
`The present application relates to computer graphics and
`animation systems. and particularly to 3D graphics render(cid:173)
`ing hardware. Background of the art and the prior
`embodiment, according to the parent application. is
`described below. Some of the distinctions of the presently
`preferred embodiment are particularly noted beginning on
`page 8.
`
`COMPUTER GRAPIDCS AND RENDERING
`
`Modern computer systems normally manipulate graphical
`objects as high-level entities. For example, a solid body may
`be described as a collection of triangles with specified
`vertices, or a straight line segment may be described by
`listing its two endpoints with three-dimensional or two(cid:173)
`dimensional coordinates. Such high-level descriptions are a
`necessary basis for high-level geometric manipulations. and
`also have the advantage of providing a compact format
`which does not consume memory space unnecessarily.
`Such higher-level representations are very convenient for
`performing the many required computations. For example.
`ray-tracing or other lighting calculations may be performed,
`and a projective transformation can be used to reduce a
`three-dimensional scene to its two-dimensional appearance
`from a given viewpoint However. when an image contain(cid:173)
`ing graphical objects is to be displayed, a very low-level
`description is needed. For example. in a conventional CRf
`display, a "flying spot" is moved across the screen (one line
`at a time). and the beam from each of three electron guns is
`switched to a desired level of intensity as the flying spot
`passes each pixel location. Thus at some point the image
`model must be translated into a data set which can be used
`by a conventional display. This operation is known as
`"rendering."
`The graphics-processing system typically interfaces to the
`display controller through a "frame store" or "frame buffer"
`of special two-port memory. which can be written to ran(cid:173)
`domly by the graphics processing system, but also provides
`the synchronous data output needed by the video output
`driver. (Digital-to-analog conversion is also provided after
`the frame buffer.) Such a frame buffer is usually imple(cid:173)
`mented using VRAM memory chips (or sometimes with
`DRAM: and special DRAM: controllers). This interface
`relieves the graphics processing system of most of the
`burden of synchronization for video output. Nevertheless.
`the amounts of data which must be moved around are very
`sizable. and the computational and data-transfer burden of
`placing the correct data into the frame buffer can still be very
`large.
`Even if the computational operations required are quite
`simple. they must be performed repeatedly on a large
`number of data points. For example. in a typical 1995
`high-end configuration. a display of 1280x1024 elements
`may need to be refreshed at 72 Hz, with a color resolution
`
`2
`of 24 bits per pixel. If blending is desired. additional bits
`(e.g. another 8 bits per pixel) will be required to store an
`"alpha" or transparency value for each pixel. This implies
`manipulation of more than 3 billion bits per second, without
`5 allowing for any of the actual computations being per(cid:173)
`formed. Thus it may be seen that this is an environment with
`unique data manipulation requirements.
`If the display is unchanging. no demand is placed on the
`rendering operations. However. some common operations
`10 (such as zooming or rotation) will require every object in the
`image space to be re-rendered. Slow rendering will make the
`rotation or zoom appear jerky. This is highly undesirable.
`Thus efficient rendering is an essential step in translating an
`image representation into the correct pixel values. This is
`15 particularly true in animation applications. where newly
`rendered updates to a computer graphics display must be
`generated at regular intervals.
`The rendering requirements of three-dimensional graph(cid:173)
`ics are particularly heavy. One reason for this is that. even
`20 after the three-dimensional model has been translated to a
`two-dimensional model. some computational tasks may be
`bequeathed to the rendering process. (For example, color
`values will need to be interpolated across a triangle or other
`primitive.) These computational tasks tend to burden the
`25 rendering process. Another reason is that since three(cid:173)
`dimensional graphics are much more lifelike. users are more
`likely to demand a fully rendered image. (By contrast. in the
`two-dimensional images created e.g. by a GUI or simple
`game, users will learn not to expect all areas of the scene to
`30 be active or filled with information.)
`FIG. lA is a very high-level view of other processes
`performed in a 3D graphics computer system. A three
`dimensional image which is defined in some fixed 3D
`coordinate system (a ''world" coordinate system) is trans-
`35 formed into a viewing volume (determined by a view
`position and direction). and the parts of the image which fall
`outside the viewing volume are discarded. The visible
`portion of the image volume is then projected onto a viewing
`plane, in accordance with the familiar rules of perspective.
`40 This produces a two-dimensional image, which is now
`mapped into device coordinates. It is important to under(cid:173)
`stand that all of these operations occur prior to the operations
`performed by the rendering subsystem of the present inven(cid:173)
`tion. FIG. lB is an expanded version of FIG. lA. and shows
`45 the flow of operations defined by the OpenGL standard.
`A vast amount of engineering effort has been invested in
`computer graphics systems. and this area is one of increasing
`activity and demands. Numerous books have discussed the
`requirements of this area; see. e.g .• ADVANCES IN COMPUIER
`50 GRAPHics (ed. Enderle 1990-); Chellappa and Sawchuk.
`DIGITAL IMAGE PROCESSING AND ANALYSIS (1985); COM(cid:173)
`PUlER GRAPmcs HARDWARE (ed. Reghbati and Lee 1988);
`COMPUIER GRAPHics: IMAGE SYNIHESIS ( ed. Joy et al. );
`Foley et al .• FuNDAMENTALS OF lNIERACTIVE CoMPU1ER
`55 GRAPmcs (2.ed. 1984); Foley. CoMPUTER GRAPmcs PRIN(cid:173)
`ciPLES & PRACTICE (2.ed. 1990); Foley, INTRODUCTION TO
`COMPUIER GRAPIDCS (1994); Giloi, Interactive Computer
`Graphics (1978); Hearn and Baker. CoMPUIER GRAPmcs
`(2.ed. 1994); Hill. COMPUIER GRAPmcs (1990); Latham,
`60 DICTIONARY OF COMPU1ER GRAPJnCS (1991); Magnenat(cid:173)
`Thalma, IMAGE SYNTIIESIS THEoRY & PRACTICE (1988);
`Newman and Sproull, PRINclPI..ES OF INTERACTIVE COM(cid:173)
`PUTER GRAPIDCS (2.ed. 1979); PlcruRE ENGINEERING ( ed. Fu
`and Kunii 1982); PICTURE PROCESSING & DIGITAL FILTERING
`65 (2.ed. Huang 1979); Prosise. How COMPUIER GRAPIDCS
`WORK ( 1994 ); Rimmer, BIT MAPPED GRAPJDCS (2.ed. 1993);
`Salmon, COMPU1ER GRAPIDCS SYSTEMS & CONCEPTS
`
`APPENDIX O
`
`Microsoft Corp. Exhibit 1005
`
`

`
`5.798.770
`
`3
`4
`The OpenGL standard provides a complete library of
`(1987); Schachter. CoMPUTER IMAGE GENERATION (1990);
`low-level graphics manipulation corrunands. which can be
`Watt. THREE-DIMENSIONAL CoMPUTER GRAPmcs (2.ed.
`used to implement three-dimensional graphics operations.
`1994); Scott Whitman. MULTIPROCESSOR ME1Hons FOR
`This standard was originally based on the proprietary stan-
`CoMPUIER GRAPmcs RENDERING; the SIGGRAPH PRo-
`CEEDINGS for the years 1980-1994; and the IEEE Computer 5 dards of Silicon Graphics, Inc .• but was later transformed
`into an open standard. It is now becoming extremely
`Graphics and Applications magazine for the years
`1990-1994.
`important. not only in high-end graphics-intensive
`Background: Graphics Animation
`workstations. but also in high-end PCs. OpenGL is sup-
`In many areas of computer graphics a succession of
`ported by Windows NT™. which makes it accessible to
`slowly changing pictures are displayed rapidly one after the 10 many PC applications.
`other. to give the impression of smooth movement, in much
`The OpenGL specification provides some constraints on
`the same way as for cartoon animation. In general the higher
`the sequence of operations. For instance. the color DDA
`the speed of the animation, the smoother (and better) the
`operations must be performed before the texturing
`result.
`operations, which must be performed before the alpha
`When an application is generating animation images, it is 15 operations. (A "DDA'' or digital differential analyzer. is a
`normally necessary not only to draw each picture into the
`conventional piece of hardware used to produce linear
`frame buffer, but also to first clear down the frame buffer,
`gradation of color (or other) values over an image area.)
`and to dear down auxiliary buffers such as depth (Z) buffers,
`Other graphics interfaces (or "APis"), such as PHIGS or
`stencil buffers, alpha buffers and others. A good treatment of
`XGL. are also current as of 1995; but at the lowest level.
`the general principles may be found in Computer Graphics: 20 OpenGL is a superset of most of these.
`Principles and Practice. James D. Foley et al .. Reading
`The OpenGL standard is described in the OPENGL PRO-
`Mass.: Addison-Wesley. A specific description of the various
`GRAMMING GUIDE (1993), the OPENGL REFERENCE
`auxiliary buffers may be found in The OpenGL Graphics
`MANUAL (1993), and a book by Segal and Akeley (of SGI)
`System: A Specification (Version 1.0), Mark Segal and Kurt
`entitled THE OPENGL GRAPmcs SYS1EM: A SPECIFICATION
`Akeley, SGL
`25 (Version 1.0).
`In most applications the value written, when clearing any
`FIG. IBis an expanded version of FIG. IA. and shows the
`given buffer. is the same at every pixel location. though
`fiow of operations defined by the OpenGL standard. Note
`different values may be used in different auxiliary buffers.
`that the most basic model is carried in terms of vertices, and
`Thus the frame buffer is often cleared to the value which
`these vertices are then assembled into primitives (such as
`corresponds to black. while the depth (Z) buffer is typically 30 triangles. lines, etc.). After all manipulation of the primitives
`cleared to a value corresponding to infinity.
`has been completed, the rendering operations will translate
`The time taken to clear down the buffers is often a
`each primitive into a set of "fragments." (A fragment is the
`significant portion of the total time taken to draw a frame, so
`portion of a primitive which affects a single pixel.) Again. it
`it is important to minimize it.
`should be noted that all operations above the block marked
`Background: Parallelism in Graphics Processing
`35 "Rasterization" would be performed by a host processor. or
`Due to the large number of at least partially independent
`possibly by a "geometry engine" (i.e. a dedicated processor
`operations which are performed in rendering, many propos-
`which performs rapid matrix multiplies and related data
`als have been made to use some form of parallel architecture
`manipulations), but would normally not be performed by a
`for graphics (and particularly for rendering). See. for
`dedicated rendering processor such as that of the presently
`example, the special issue of Computer Graphics on parallel 4<l preferred embodiment.
`rendering (September 1994). Other approaches may be
`One disadvantage of standards such as OpenGL is that
`found in earlier patent filings by the assignee of the present
`they require that texturing or other processor-intensive
`application and its predecessors, e.g. U.S. Pat. No. 5,195.
`operations be performed on data before pixel elimination
`186. and published PCT applications PCT/GB90/00987,
`tests, e.g. depth testing, is performed. which wastes proces-
`PCT/GB90/01209, PCT/GB90/01210, PCT/GB90/01212. 45 sor time by performing costly texturing calculations on
`PCT/GB90/01213. PCT/GB90/01214. PCT/GB90/01215.
`pixels which will be eliminated later in the pipeline. When
`and PCf/GB90/01216.
`the OpenGL specification is not required or when the current
`Background: Pipelined Processing Generally
`OpenGI state vector cannot eliminate pixels as a result of the
`There are several general approaches to parallel process-
`alpha test, however. it would be much more efficient to
`ing. One of the basic approaches to achieving parallelism in 50 eliminate as many pixels as possible before doing these
`computer processing is a technique known as pipelining. In
`calculations. The present awlication discloses a method and
`this technique the individual processors are. in effect. con-
`device for reordering the processing steps in the rendering
`nected in series in an assembly-line configuration: one
`pipeline to either accommodate order-specific specifications
`processor performs a first set of operations on one chunk of
`such as OpenGL. or to provide for an optimized throughput
`data. and then passes that chunk along to another processor 55 by only performing processor-intensive operations on pixels
`which will actually be displayed.
`which performs a second set of operations, while at the same
`time the first processor performs the first set operations
`Background: Texturing
`again on another chunk of data. Such architectures are
`Texture patterns are commonly used as a way to apply
`generally discussed in Kogge. THE ARcHITECIURE OF PIPE-
`realistic visual detail at the sub-polygon level. See Foley et
`LINED COMPUTERS ( 1981).
`60 al .. CoMPUIER GRAPIDCS: PRINCIPLES AND PRACTICE (2.ed.
`Background: The OpenGL™ Standard
`1990. coer. 1995), especially at pages 741-744; Paul S.
`The "OpenGL" standard is a very important software
`Heckbert. "Fundamentals of Texture Mapping and Image
`standard for graphics applications. In any computer system Warping," Thesis submitted to Dept. of EE and Computer
`which supports this standard. the operating system(s) and
`Science. University of California. Berkeley. Jun. 17, 1994;
`application software programs can make calls according to 65 Heckbert. "Survey of Computer Graphics." IEEE Computer
`the OpenGL standards. without knowing exactly what the
`Graphics. November 1986. pp.56ff. Since the surfaces are
`hardware configuration of the system is.
`transformed (by the host or geometry engine) to produce a
`
`APPENDIX O
`
`Microsoft Corp. Exhibit 1005
`
`

`
`5.798.770
`
`5
`2D view. the textures will need to be similarly transformed
`by a linear transform (normally projective or "affine"). (In
`conventional terminology. the coordinates of the object
`surface, i.e. the primitive being rendered. are referred to as
`an (s.t) coordinate space. and the map of the stored texture
`is referred to a (u.v) coordinate space.) The transformation
`in the resulting mapping means that a horizontal line in the
`(x.y) display space is very likely to correspond to a slanted
`line in the (u.v) space of the texture map. and hence many
`page breaks will occur, due to the texturing operation, as
`rendering walks along a horizontal line of pixels.
`
`Innovative System and Methods
`
`6
`FIG. 3B shows another sample graphics board
`implementation. which differs from the board of FIG. 3A in
`that more memory and an additional component is used to
`achieve higher performance.
`FIG. 3C shows another graphics board. in which the chip
`of FIG. 2B shares access to a common frame store with GUI
`accelerator chip.
`FIG. 3D shows another graphics board, in which the chip
`of FIG. 2B shares access to a common frame store with a
`10 video coprocessor (which may be used for video capture and
`playback functions.
`FIG. 4A illustrates the definition of the dominant side and
`the subordinate sides of a triangle.
`FIG. 4B illustrates the sequence of rendering an Anti(cid:173)
`aliased Line primitive.
`FIG. SA is a detailed view of the router unit of the
`presently preferred embodiment.
`FIG. SB is a detailed view of the data path through the
`20 router unit of the presently preferred embodiment when
`operating in a first mode.
`FIG. SC is a detailed view of the data path through the
`router unit of the presently preferred embodiment when
`operating in a second mode.
`
`25
`
`The preferred embodiment discloses a pipelined graphics
`processor in which the sequence can be dynamically recon- 15
`figured (e.g. between primitives) in a rendering sequence.
`The pipeline sequence can be configured for compliance
`with specifications such as OpenGL. but may also be opti(cid:173)
`mized by reconfiguring the pipeline sequence to eliminate
`unnecessary processing. In a preferred embodiment. pixel
`elimination sequences such as depth and stencil tests are
`performed before texturing calculations are performed. so
`that unneeded pixel data is discarded before said texturing
`calculations are performed.
`It is noted that the texturing operations become more
`computation-intense. early elimination of unneeded pixels
`becomes even more valuable. For example. Phong shading
`and bump mapping both require many more operations than
`more common shading and texture mapping techniques, thus
`making the system of the present application even more 30
`valuable in real-time rendering systems.
`An overhead cost is that the reconfigurable portion of the
`pipeline must be flushed at each reconfiguration--but since
`reconfiguration is normally done only on a per-primitive
`basis. or even less frequently. this is a relatively small cost.
`
`35
`
`DErAILED DESCRIPITON OF THE
`PREFERRED EM:BODIMENTS
`
`The numerous innovative teachings of the present appli(cid:173)
`cation will be described with particular reference to the
`presently preferred embodiment (by way of example. and
`not of limitation). The presently preferred embodiment is a
`GLINT™ 400TX™ 3D rendering chip. The Hardware Ref(cid:173)
`erence Manual and Programmer's Reference Manual for this
`chip describe further details of this sample embodiment.
`Both are available, as of the effective filing date of this
`application, from 3Dlabs Inc. Ltd. 181 Metro Drive. Suite
`520. San Jose Calif. 95110.
`
`BRIEF DESCR1PTION OF THE DRAWING
`The disclosed inventions will be described with reference
`to the accompanying drawings. which show important 40
`sample embodiments of the invention and which are incor(cid:173)
`porated in the specification hereof by reference, wherein:
`FIG. lA, described above, is an overview of key elements
`and processes in a 3D graphics computer system.
`FIG. lB is an expanded versionofFIG.lA. and shows the 45
`flow of operations defined by the OpenGL standard.
`FIG. 2A is an overview of the graphics rendering chip of
`the preferred embodiment of the parent case.
`FIG. 2B is an overview of the graphics rendering chip of
`the presently preferred embodiment.
`FIG. 2C is a more schematic view of the sequence of
`operations performed in the graphics rendering chip of FIG.
`2B. when operating in a first mode.
`FIG. 2D is a different view of the graphics rendering chip
`of FIG. 2B. showing the connections of a readback bus
`which provides a diagnostic pathway.
`FIG. 2E is yet another view of the graphics rendering chip
`of FIG. 2B, showing how the functions of the core pipeline
`of FIG. 2C are combined with various external interface 60
`functions.
`FIG. 2F is yet another view of the graphics rendering chip
`of FIG. 2B. showing how the details of FIFO depth and
`lookahead are implemented, in the presently preferred
`embodiment.
`FIG. 3A shows a sample graphics board which incorpo(cid:173)
`rates the chip of FIG. 2B.
`
`50
`
`Definitions
`The following definitions may help in understanding the
`exact meaning of terms used in the text of this application:
`application: a computer program which uses graphics ani(cid:173)
`mation.
`depth (Z) buffer: A memory buffer containing the depth
`component of a pixel. Used to, for example, eliminate
`hidden surfaces.
`blt double-buffering: A technique for achieving smooth
`animation. by rendering only to an undisplayed back
`buffer. and then copying the back buffer to the front once
`drawing is complete.
`Frame Count Planes: Used to allow higher animation rates by
`enabling DRAM local buffer pixel data, such as depth (Z),
`to be cleared down quickly.
`frame buffer: An area of memory con