Block- and band-oriented traversal in three-dimensional triangle rendering

US 5,945,997 A
Filed: 06/26/1997
Issued: 08/31/1999
Est. Priority Date: 06/26/1997
Status: Expired due to Term

- Alert
- Pin

Associated Cases

Associated Defendants

First Claim

Patent Images

1. 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.

View all claims

4 Assignments

Timeline View

Assignment View

Litigations

0 Petitions

Accused Products

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.

101 Citations

View as Search Results

21 Claims

1. 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.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
- - 2. The method of claim 1, wherein c.1) is performed using edge- and span-walking traversal methods.
  - 3. 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.
  - 4. 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.
  - 5. The method of claim 4, wherein c.2.2) comprises retrieving data from the texture map using burst-mode access.
  - 6. 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.
  - 7. The method of claim 6, wherein each texture map division is a rectangle.
  - 8. The method of claim 6, wherein each texture map division is a square.
  - 9. The method of claim 1, wherein c.2) comprises performing a multum in parvo map texture mapping operation.
  - 10. 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.
  - 11. 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.
  - 12. 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.
  - 13. 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.
  - 14. 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.
  - 15. The method of claim 14, wherein b.1) comprises selecting a horizontal traversal order and a vertical traversal order.

16. 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.
- View Dependent Claims (17, 18)
- - 17. The method of claim 16, wherein each texture map division is a rectangle.
  - 18. The method of claim 16, wherein each texture map division is a square.

19. 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.
- View Dependent Claims (20, 21)
- - 20. The system of claim 19, further comprising a display coupled to the frame buffer for displaying the texture-mapped data.
  - 21. 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.

Specification

Resources

Litigation Campaign Assessment

Litigation Data

Current Assignee
S3 Graphics Co., Ltd. (HTC Corporation)
Original Assignee
S3 Inc. (SONICblue Incorporated)
Inventors
Kuo, Dong-Ying, Zhao, Randy X.
Primary Examiner(s)
Nguyen, Phu K.
Assistant Examiner(s)
Vo, Cliff N.

Application Number

US08/883,536
Time in Patent Office

796 Days
Field of Search

345/418, 345/419, 345/420, 345/429, 345/430, 345/431
US Class Current

345/581
CPC Class Codes

G06T 11/40 Filling a planar surface by...

Block- and band-oriented traversal in three-dimensional triangle rendering

First Claim

4 Assignments

Litigations

0 Petitions

Accused Products

Abstract

101 Citations

21 Claims

Specification

Solutions

Use Cases

Quick Links

Block- and band-oriented traversal in three-dimensional triangle rendering

First Claim

4 Assignments

Subscription Required

Subscription Required

Litigations

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

101 Citations

21 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links