System and method for rendering an image

• US 6,323,874 B1
• Filed: 02/08/1999
• Issued: 11/27/2001
• Est. Priority Date: 02/08/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Gossett, Carroll Philip
• Primary Examiner(s): Luu, Matthew
• Assistant Examiner(s): HAVAN, THU THAO
• Application Number:
  US09/246,136
• Time in Patent Office: 1,023 Days
• Field of Search: 345/433, 345/430, 345/419, 345/436, 345/473, 345/501, 345/507, 345/431, 345/619, 345/621, 707/6, 707/104, 382/235, 382/266
• US Class Current: 345/619
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree

Abstract

A system and method for rendering a graphic object that recursively subdivides a frame buffer into rectangular regions in an order determined by a space-filling curve. Each rectangular region is tested to determine if the region includes at least part of the object to be rendered. If it contains at least part of the object to be rendered, then the region is subdivided. In accordance with the present invention, the same tests are performed on the subdivided regions. This proceeds until the size of a subdivided rectangular region reaches a predetermined limit, whereupon the pixels in the subdivided region are rendered on a pixel-by-pixel basis.

Claims

1. A method for rendering a primitive, comprising the steps of:

a. subdividing a frame buffer into rectangular regions;

b. testing each rectangular region to determine if the rectangular region includes at least part of the primitive to be rendered, each rectangular region tested in an order determined by a space-filling curve;

c. if a rectangular region is determined to include at least part of the primitive to be rendered, then recursively subdividing the rectangular region, and testing each successive subdivision in an order determined by the space-filling curve to determine if the subdivision contains at least part of the primitive to be rendered; and

d. if the size of a subdivided rectangular region is equal to m×

n pixels, then rendering the pixels of the subdivided rectangular region if it is determined to contain at least part of the primitive to be rendered.

2. The method of claim 1, wherein only the coordinates of a single corner of each rectangular region is passed along from one recursive level to the next, and wherein at the next recursive level, other corners of a rectangular region are generated from the single corner by applying predetermined deltas in horizontal, vertical and diagonal directions from the single corner.

3. The method of claim 1, wherein adds are implemented in carry-save form.

4. The method of claim 3, wherein only the carry of the sign bits are propagated from one recursive level to the next.

5. The method of claim 3, wherein the carry-save bits are propagated only when the sign of an area is needed.

6. The method of claim 3, wherein a least significant carry-save bit is truncated.

7. The method of claim 3, further comprising the step of determining that all of the pixels contained in a rectangular region are entirely on one side of an edge of an object to be rendered, and further comprising the step of truncating a most significant carry-save bit.

8. A method for rendering a triangle having three vertices, comprising the steps of:

a. recursively subdividing a frame buffer into four rectangular regions, each rectangular region having four corners,

b. for each rectangular region in an order determined by a space-filling curve;

i. calculating the signed area of the triangle to be rendered;

ii. calculating the signed area of a triangular region defined by two vertices of the triangle to be rendered and a corner of the rectangular region, for each distinct pair of vertices of the triangle to be rendered, and for each of the four corners of the rectangular region, to obtain twelve signed triangular region numbers;

iii. determining if the rectangular region falls at least partly within the boundaries of a box with four corners and four edges drawn around the triangle to be rendered, the edges of the box being parallel to the edges of the frame buffer, and the box being drawn such that each vertex of the triangle to be rendered contacts an edge or a corner of the box;

c. if for each edge of the triangle to be rendered, at least one corner of the rectangular region forms a triangle with an area of the same sign as the triangle to be rendered, and if the rectangular region falls at least partly within the boundaries of the box, then recursively subdividing the rectangular region until the size of the rectangular region is equal to mxn pixels, m and n being integers;

d. when the size of the rectangular region is equal to mxn pixels, then rendering the pixels;

e. if one or more edges of the triangle to be rendered form triangles with all four corners of the rectangular region with areas of opposite sign to the triangle to be rendered, or if no part of the rectangular region lies within the boundaries of the box, then stopping to recursively subdivide the rectangular region.

9. A method for rendering a polygon, comprising the steps of:

a. recursively subdividing a frame buffer into four rectangular regions, each rectangular region having four corners,

b. for each rectangular region in an order determined by a space-filling curve;

i. calculating the signed area of the polygon to be rendered;

ii. calculating the signed area of a triangular region defined by two vertices of the polygon to be rendered and a corner of the rectangular region, for each distinct pair of vertices of the polygon to be rendered, and for each of the four corners of the rectangular region;

iii. determining if the rectangular region falls at least partly within the boundaries of a box with four corners and four edges drawn around the polygon to be rendered, the edges of the box being parallel to the edges of the frame buffer, and the box being drawn such that the boundaries of the box enclose the minimum area needed to entirely contain the polygon therein;

c. if for each edge of the polygon to be rendered, at least one corner of the rectangular region forms a triangle with an area of the same sign as the polygon to be rendered, and if the rectangular region falls at least partly within the boundaries of the box, then recursively subdividing the rectangular region until the size of the rectangular region is equal to mxn pixels, m and n being integers;

d. when the size of the rectangular region is equal to mxn pixels, then rendering the pixels;

e. if one or more edges of the polygon to be rendered form triangles with all four corners of the rectangular region with areas of opposite sign to the polygon to be rendered, or if no part of the rectangular region lies within the boundaries of the box, then stopping to recursively subdivide the rectangular region.

10. A method for rendering a line represented as a quadrilateral with two parallel edges, comprising the steps of:

a. recursively subdividing a frame buffer into four rectangular regions, each rectangular region having four corners,

b. for each rectangular region in an order determined by a space-filling curve;

i. enclosing the line in a bounding box, the bounding box having four corners and four edges, the edges of the box being parallel to the edges of the frame buffer, and the box being drawn such that the boundaries of the box enclose the minimum area needed to entirely contain that portion of the line that falls within the frame buffer, the bounding box forming an end edge of the line where the line intersects the bounding box;

ii. calculating the signed area of the quadrilateral formed by the two parallel edges of the line and the end edges of the line;

iii. calculating the signed area of a triangular region defined by two vertices of the quadrilateral and a corner of the rectangular region, for each distinct pair of vertices of the quadrilateral, and for each of the four corners of the rectangular region;

iv. determining if the region falls at least partly within the bounding box;

c. if for each edge of the quadrilateral, at least one corner of the rectangular region forms a triangle with an area of the same sign as the quadrilateral, and if the rectangular region falls at least partly within the boundaries of the box, then recursively subdividing the rectangular region until the size of the rectangular region equal mxn pixels, m and n being integers;

d. when the size of the rectangular region is equal to mxn pixels, then rendering the pixels;

e. if one or more edges of the quadrilateral form triangles with all four corners of the rectangular region having areas of opposite sign to the triangle to be rendered, or if no part of the rectangular region lies within the boundaries of the box, then stopping to recursively subdivide the rectangular region.

11. An apparatus for rendering a polygon, comprising:

a. a processor;

b. a memory that stores rendering instructions adapted to be executed on said processor to recursively subdivide a frame buffer into rectangular regions, and for each rectangular region in an order determined by a space-filling curve, calculate the signed area of the polygon to be rendered, calculate the signed area of a triangular region defined by two vertices of the polygon to be rendered and a corner of the rectangular region, for each distinct pair of vertices of the polygon to be rendered, and for each of the four corners of the rectangular region, determine if the region falls at least partly within the boundaries of a box with four corners and four edges drawn around the polygon to be rendered, the edges of the box being parallel to the edges of the frame buffer, and the box being drawn such that the boundaries of the box enclose the minimum area needed to entirely contain the polygon therein, and if for each edge of the polygon to be rendered, at least one corner of the rectangular region forms a triangle with an area of the same sign as the polygon to be rendered, and if the rectangular region falls at least partly within the boundaries of the box, then recursively subdivide the rectangular region until the size of the rectangular region is equal to mxn pixels, m and n being integers, and when the size of the rectangular region is equal to mxn pixels, then to render the pixels, while if one or more edges of the polygon to be rendered form triangles with all four corners of the rectangular region with areas of opposite sign to the polygon to be rendered, or if no part of the rectangular region lies within the boundaries of the box, then to stop recursively subdividing the rectangular region, said memory coupled to said processor.

12. The apparatus of claim 11, further comprising a port adapted to be coupled to a display, said port coupled to said memory and said processor.

13. The apparatus of claim 11, further comprising a display on which the pixels are rendered.

14. An apparatus for rendering a primitive, comprising:

a. a processor; and

b. a memory that stores rendering instructions adapted to be executed on said processor to subdivide a frame buffer into rectangular regions, test each rectangular region to determine if the rectangular region includes at least part of the primitive to be rendered, each rectangular region being tested in an order determined by a space-filling curve, and if a rectangular region includes at least part of the primitive to be rendered, then to recursively subdivide the rectangular region, test each successive subdivision in an order determined by the space-filling curve to determine if the subdivision contains at least part of the primitive to be rendered, and if the size of a subdivision is less than m×

n pixels, then to render the subdivision if it is determined to contain at least part of the primitive to be rendered, said memory coupled to said processor.

15. A system for rendering a polygon, comprising:

a. means for recursively subdividing a frame buffer into four rectangular regions, each rectangular region having four corners,

b. means for, in an order determined by a space-filling curve, calculating the signed area of the polygon to be rendered, calculating the signed area of a triangular region defined by two vertices of the polygon to be rendered and a corner of the rectangular region, for each distinct pair of vertices of the polygon to be rendered, and for each of the four corners of the rectangular region, and determining if the region falls at least partly within the boundaries of a box with four corners and four edges drawn around the polygon to be rendered, the edges of the box being parallel to the edges of the frame buffer, and the box being drawn such that the boundaries of the box enclose the minimum area needed to entirely contain the polygon therein;

c. means for determining if for each edge of the polygon to be rendered at least one corner of the rectangular region forms a triangle with an area of the same sign as the polygon to be rendered

d. means for determining if the rectangular region falls at least partly within the boundaries of the box;

e. means for recursively subdividing the rectangular region until the size of the rectangular region is equal to mxn pixels, m and n being integers;

f. means for rendering the pixels of the rectangular area when the size of the rectangular region is equal to mxn pixels;

g. means for determining if one or more edges of the polygon to be rendered form triangles with all four corners of the rectangular region with areas of opposite sign to the polygon to be rendered; and

h. means for determining if no part of the rectangular region lies within the boundaries of the box.