Method and system for reducing a polygon bounding box

Patent metadata

Field	Value
Publication number	US-9633458-B2
Application number	US-201213356551-A
Country	US
Kind code	B2
Filing date	Jan 23, 2012
Priority date	Jan 23, 2012
Publication date	Apr 25, 2017
Grant date	Apr 25, 2017

Abstract

In a graphics processing pipeline, a processing unit establishes a bounding box around a polygon in order to identify sample points that are covered by the polygon. For a given sample point included within the bounding box, the processing unit constructs a set of lines that intersect at the sample point, where each line in the set of lines is parallel to at least one side of the polygon. When all vertices of the polygon reside on one side of at least one line in the set of lines, the processing unit may reduce the size of the bounding box to exclude the sample point.

First claim

The invention claimed is:

1. A computer-implemented method for culling sample points associated with a polygon having N edges and N vertices, the method comprising:
establishing a bounding box that encompasses the polygon;
identifying a plurality of sample points included within the bounding box;
for each sample point included in the plurality of sample points:
constructing a set of multiple lines that intersect one another at the sample point, wherein each line included in the set of multiple lines is parallel to at least one corresponding line constructed to intersect each other sample point included in the plurality of sample points;
determining that the sample point resides outside the polygon by determining that all of the N vertices of the polygon reside on a first side of any of the lines included in the set of multiple lines that intersect one another at the sample point; and
upon determining that the sample point lies outside the polygon, reducing the size of the bounding box until the sample point is excluded from the bounding box.

2. The computer-implemented method of claim 1 , wherein the set of multiple lines comprises two lines positioned substantially perpendicular to one another, wherein each of the two lines is positioned at a substantially 45 degree angle relative to at least one edge of a pixel that includes the sample point.

3. The computer-implemented method of claim 1 , wherein the set of multiple lines includes N lines, each of the N lines is substantially parallel to a different one of the N edges of the polygon, N being an integer.

4. The computer-implemented method of claim 1 , wherein constructing the set of multiple lines comprises:
determining N slope values, wherein each of the N slope values corresponds to a different one of the N edges of the polygon;
rounding each of the N slope values to generate N rounded slope values; and
constructing N lines to generate the set of multiple lines, wherein each of the N lines is associated with a different one of the N rounded slope values, N being an integer.

5. The computer-implemented method of claim 1 , further comprising:
constructing a different set of multiple lines for each of the other sample points included within the bounding box;
determining that each of the N vertices of the polygon resides on one side of any of the lines in each of the different sets of multiple lines; and
culling each of the other sample points by collapsing the bounding box.

6. The computer-implemented method of claim 1 , wherein the sample point is one of a plurality of sample points residing within a pixel.

7. The computer-implemented method of claim 1 , wherein the polygon comprises a triangle.

8. A non-transitory computer-readable medium storing program instructions that, when executed by a processing unit, cause the processing unit to cull sample points associated with a polygon having N edges and N vertices by performing the steps of:
establishing a bounding box that encompasses the polygon;
identifying a plurality of sample points included within the bounding box;
for each sample point included in the plurality of sample points:
constructing a set of multiple lines that intersect one another at the sample point, wherein each line included in the set of multiple lines is parallel to at least one corresponding line constructed to intersect each other sample point included in the plurality of sample points;
determining that the sample point resides outside the polygon by determining that all of the N vertices of the polygon reside on a first side of any of the lines included in the set of multiple lines that intersect one another at the sample point; and
upon determining that the sample point lies outside the polygon, reducing the size of the bounding box until the sample point is excluded from the bounding box.

9. The non-transitory computer-readable medium of claim 8 , wherein the set of multiple lines comprises two lines positioned substantially perpendicular to one another, wherein each of the two lines is positioned at a substantially 45 degree angle relative to at least one edge of a pixel that includes the sample point.

10. The non-transitory computer-readable medium of claim 8 , wherein the set of multiple lines includes N lines, each of the N lines is substantially parallel to a different one of the N edges of the polygon, N being an integer.

11. The non-transitory computer-readable medium of claim 8 , wherein the step of constructing the set of multiple lines comprises:
determining N slope values, wherein each of the N slope values corresponds to a different one of the N edges of the polygon;
rounding each of the N slope values to generate N rounded slope values; and
constructing N lines to generate the set of multiple lines, wherein each of the N lines is associated with a different one of the N rounded slope values, N being an integer.

12. The non-transitory computer-readable medium of claim 8 , further comprising the steps of:
constructing a different set of multiple lines for each of the other sample points included within the bounding box;
determining that each of the N vertices of the polygon resides on one side of any of the lines in each of the different sets of multiple lines; and
culling each of the other sample points by collapsing the bounding box.

13. The non-transitory computer-readable medium of claim 8 , wherein the sample point is one of a plurality of sample points residing within a pixel.

14. The non-transitory computer-readable medium of claim 8 , wherein the polygon comprises a triangle.

15. A computing device configured to cull sample points associated with a polygon having N edges and N vertices, comprising:
a processing unit configured to:
establish a bounding box that encompasses the polygon;
identify a plurality of sample points included within the bounding box;
for each sample point included in the plurality of sample points:
construct a set of multiple lines that intersect one another at the sample point, wherein each line included in the set of multiple lines is parallel to at least one corresponding line constructed to intersect each other sample point included in the plurality of sample points;
determine that the sample point resides outside the polygon by determining that all of the N vertices of the polygon reside on a first side of any of the lines included in the set of multiple lines that intersect one another at the sample point; and
upon determining that the sample point lies outside the polygon, reduce the size of the bounding box until the sample point is excluded from the bounding box.

16. The computing device of claim 15 , further comprising:
a memory coupled to the processing unit and storing program instructions that, when executed by the processing unit, cause the processing unit to:
establish the bounding box;
identify the sample point;
construct the set of multiple lines;
determine that all of the N vertices of the polygon reside on a first side of at least one line included in the set of multiple lines; and
reduce the size of the bounding box until the sample point is excluded from the bounding box.

17. The computing device of claim 15 , wherein the set of multiple lines comprises two lines positioned substantially perpendicular to one another, wherein each of the two lines is positioned at a substantially 45 degree angle relative to at least one edge of a pixel that includes the sample point.

18. The computing device of claim 15 , wherein the set of multiple lines includes N lines, each of th

Assignees

• Steiner Walter R
• Lum Eric
• Kirkland Dale L
• Heinrich Steven James
• Patrick David Charles
• Nvidia Corp

Inventors

• Steiner Walter R
• Lum Eric
• Kirkland Dale L
• Heinrich Steven James
• Patrick David Charles

Classifications

• G06T11/40 Primary

  Filling planar surfaces by adding surface attributes, e.g. adding colours or textures · CPC title

• G06T11/00

  Two-dimensional [2D] image generation · CPC title