Patent US5945997A successfully refreshed from Google Patents.
US5945997A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Block- and band-oriented traversal in three-dimensional triangle rendering
Assignee: S3 Graphics Co Ltd
•
Filing: 1997-06-26
•
Granted: 1999-08-31
•
Expires: 2017-06-26
Abstract
Abstract A system and method for traversing and rendering a graphic primitive represented in screen space, employing block- and band-oriented traversal algorithms in texture mapping. Improved performance is achieved through burst-mode texture access and texture caching in connection with a texture map subdivided into squares. Block- and band-oriented traversal facilitates minimization of page breaks and texture cache swap-out. Improved determinism is facilitated by obviating the need for pixel sorting algorithms. Improved re-use of retrieved data segments in burst-mode access is facilitated.
Inventors
- 👤 Randy X. Zhao
- 👤 Dong-Ying Kuo
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 07:31
CPC Classifications
G; G06; G06T; G06T11/00; G06T11/40
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
93 words
In a graphics system, a computer-implemented method of traversing and rendering a graphic primitive represented in screen space, comprising the steps of: a) determining a block dimension; b) subdividing the screen space according to the block dimension to define a plurality of blocks; c) for each block containing at least a portion of the graphic primitive: c.1) defining a plurality of spans within the block, the spans collectively providing a representation of the portion of the graphic primitive corresponding to the block; and c.2) performing a texture mapping operation on each defined span.
Claim 2
Dependent Claim
93 words
In a graphics system, a computer-implemented method of traversing and rendering a graphic primitive represented in screen space, comprising the steps of: a) determining a block dimension; b) subdividing the screen space according to the block dimension to define a plurality of blocks; c) for each block containing at least a portion of the graphic primitive: c.1) defining a plurality of spans within the block, the spans collectively providing a representation of the portion of the graphic primitive corresponding to the block; and c.2) performing a texture mapping operation on each defined span.
Claim 3
Dependent Claim
15 words
The method of claim 1, wherein c.1) is performed using edge- and span-walking traversal methods.
Claim 4
Dependent Claim
38 words
The method of claim 1, wherein c.2) comprises: c.2.1) for each defined span, determining a corresponding texture space line segment in a texture map; and c.2.2) retrieving data from the texture map representing the texture space line segment.
Claim 5
Dependent Claim
55 words
The method of claim 3, wherein c.2) further comprises: c.2.3) storing the retrieved data in a texture cache, wherein the texture cache is of sufficient dimension to store a texture space line segment having a maximum length determined based on the block dimension; and wherein c.2.2) further comprises selectively retrieving data from the texture cache.
Claim 6
Dependent Claim
17 words
The method of claim 4, wherein c.2.2) comprises retrieving data from the texture map using burst-mode access.
Claim 7
Dependent Claim
41 words
The method of claim 4, wherein the texture map is subdivided into a plurality of texture map divisions, and wherein c.2.2) comprises retrieving data from the texture map using burst-mode access to retrieve data corresponding to a selected texture map division.
Claim 8
Dependent Claim
13 words
The method of claim 6, wherein each texture map division is a rectangle.
Claim 9
Dependent Claim
13 words
The method of claim 6, wherein each texture map division is a square.
Claim 10
Dependent Claim
17 words
The method of claim 1, wherein c.2) comprises performing a multum in parvo map texture mapping operation.
Claim 11
Dependent Claim
58 words
The method of claim 9, wherein c.2) comprises: c.2.1) determining an appropriate scaling factor responsive to at least one of available texture space and dimension of the defined span; c.2.2) selecting a texture map representation from a plurality of texture map representations, responsive to the determined scaling factor; and c.2.3) retrieving data from the selected texture map representation.
Claim 12
Dependent Claim
53 words
The method of claim 10, wherein c.2.2) comprises: c.2.2.1) determining a logarithm of the scaling factor; c.2.2.2) responsive to the value of the logarithm containing a fractional component, rounding the value of the logarithm to the nearest integer value; and c.2.2.3) selecting a texture map representation corresponding to the value of the logarithm.
Claim 13
Dependent Claim
54 words
The method of claim 10, wherein c.2.2) comprises: c.2.2.1) determining a logarithm of the scaling factor; c.2.2.2) responsive to the value of the logarithm containing a fractional component, truncating the value of the logarithm to the next lower integer value; and c.2.2.3) selecting a texture map representation corresponding to the value of the logarithm.
Claim 14
Dependent Claim
99 words
The method of claim 10, wherein c.2.2) comprises: c.2.2.1) determining a logarithm of the scaling factor; c.2.2.2) responsive to the value of the logarithm containing a fractional component, performing the steps of: c.2.2.2.1) retrieving two texture map representations having integer values approximating the value of the logarithm; c.2.2.2.2) obtaining a filtered texture map representation by performing weighted filtering of the two retrieved texture map representations; and c.2.2.2.3) selecting the filtered texture map representation; and c.2.2.3) responsive to the value of the logarithm not containing a fractional component, selecting a texture map representation corresponding to the value of the logarithm.
Claim 15
Dependent Claim
27 words
The method of claim 1, further comprising b.1) defining a traversal path for performing c) on each block containing at least a portion of the graphic primitive.
Claim 16
Dependent Claim
18 words
The method of claim 14, wherein b.1) comprises selecting a horizontal traversal order and a vertical traversal order.
Claim 17
Dependent Claim
123 words
In a graphics system, a computer-implemented method of traversing and rendering a graphic primitive represented in screen space, comprising the steps of: a) defining a plurality of spans, collectively providing a representation of the graphic primitive; and b) performing a texture mapping operation on each defined span, by: b.1) for each defined span, determining a corresponding texture space line segment in a texture map, the texture map being subdivided into a plurality of texture map divisions; b.2) retrieving data from the texture map representing the texture space line segment, using burst-mode access to retrieve data corresponding to a selected texture map division; and b3) storing the retrieved data in a texture cache; wherein b.2) further comprises selectively retrieving data from the texture cache.
Claim 18
Dependent Claim
123 words
In a graphics system, a computer-implemented method of traversing and rendering a graphic primitive represented in screen space, comprising the steps of: a) defining a plurality of spans, collectively providing a representation of the graphic primitive; and b) performing a texture mapping operation on each defined span, by: b.1) for each defined span, determining a corresponding texture space line segment in a texture map, the texture map being subdivided into a plurality of texture map divisions; b.2) retrieving data from the texture map representing the texture space line segment, using burst-mode access to retrieve data corresponding to a selected texture map division; and b3) storing the retrieved data in a texture cache; wherein b.2) further comprises selectively retrieving data from the texture cache.
Claim 19
Dependent Claim
13 words
The method of claim 16, wherein each texture map division is a rectangle.
Claim 20
Dependent Claim
13 words
The method of claim 16, wherein each texture map division is a square.
Claim 21
Independent Claim
135 words
A system for traversing and rendering a graphic primitive represented in screen space, comprising: a primitive setup module for defining and storing representations of a graphic primitive; a frame buffer subdivided according to a block dimension to define a plurality of blocks in screen space; an edge-walk module, coupled to the primitive setup module, for, for each block containing at least a portion of the graphic primitive, performing edge-walking traversal on the portion of the graphic primitive corresponding to the block, to define a plurality of spans; and a span-walk module, coupled to the edge-walk module, for performing span-walking traversal on a span defined by the edge-walk module; and a texture mapping engine coupled to the span-walk module, for performing a texture mapping operation on the span and writing the result to the frame buffer.
Claim 22
Independent Claim
135 words
A system for traversing and rendering a graphic primitive represented in screen space, comprising: a primitive setup module for defining and storing representations of a graphic primitive; a frame buffer subdivided according to a block dimension to define a plurality of blocks in screen space; an edge-walk module, coupled to the primitive setup module, for, for each block containing at least a portion of the graphic primitive, performing edge-walking traversal on the portion of the graphic primitive corresponding to the block, to define a plurality of spans; and a span-walk module, coupled to the edge-walk module, for performing span-walking traversal on a span defined by the edge-walk module; and a texture mapping engine coupled to the span-walk module, for performing a texture mapping operation on the span and writing the result to the frame buffer.
Claim 23
Dependent Claim
19 words
The system of claim 19, further comprising a display coupled to the frame buffer for displaying the texture-mapped data.
Claim 24
Dependent Claim
50 words
The system of claim 19, further comprising: a texture memory for storing a texture map; and a texture cache coupled to the texture memory for storing selected sub-divisions of the texture memory; and wherein the texture mapping engine performs the texture mapping operation using burst-mode access to the texture cache.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-08-30 | 2003-03-01 | 2003-08-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-08-30 | 2007-03-01 | 2007-08-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-08-30 | 2011-03-01 | 2011-08-31 | $7700.00 | Window Closed / Lapsed |