Apparatus and method for generating point sample masks in a graphics display system

• US 5,369,739 A
• Filed: 07/09/1993
• Issued: 11/29/1994
• Est. Priority Date: 07/09/1993
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Akeley, Kurt
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/089,715
• Time in Patent Office: 508 Days
• Field of Search: 395/133, 395/135, 395/134, 395/162, 395/164, 395/165, 395/166, 345/118, 345/119, 345/120
• US Class Current: 345/626
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 15/405 using Z-buffer
• CPC Class Codes: G06T 2200/12 involving antialiasing

Abstract

In a computer graphics system, a method of generating a geometrically valid point sample mask corresponding to a pixel. A separate mask is generated for each edge of a polygon. These masks specify whether particular subsample points are within a half-plane defined by an edge of the polygon. This information is determined by examining the sign of vertical or horizontal distance metrics corresponding to those sample points. These separate masks are merged to form the final point sample mask. Thereby, the final point sample mask contains information specifying whether particular sample points reside within the polygon. This information is used in rendering the pixel for display by the computer graphics system.

Claims

1. In a computer system, a computer implemented method of generating a point sample mask having an array of sample points corresponding to a pixel, wherein each sample point has associated information specifying whether said sample point is inside or outside a polygon, said information being used for rendering said pixel for display by said computer system, said method comprising the steps of:

generating a first mask corresponding to a first edge of said polygon, said first mask specifying which ones of a first set of said sample points reside within a first half-plane defined by said first edge, wherein a sign of a vertical or horizontal distance metric corresponding to a first sample of said first set of sample points determines whether said first sample resides within said first half-plane;

generating a second mask corresponding to a second edge of said polygon, said second mask specifying which ones of a second set of sample points reside within a second half-plane defined by said second edge, wherein a sign of a vertical or horizontal distance metric corresponding to a second sample of said second set of sample points determines whether said second sample resides within said second half-plane;

generating a third mask corresponding to a third edge of said polygon, said third mask specifying which ones of a third set of sample points reside within a third half-plane defined by said third edge, wherein a sign of a vertical or horizontal distance metric corresponding to a third sample of said third set of sample points determines whether said third sample resides within said third half-plane;

merging said first mask, said second mask, and said third mask to generate said point sample mask.

2. The method of claim 1 further comprising the steps of:

determining whether a slope of said first edge is within a range of +1 to -1;

generating coefficients of said vertical distance metric if said slope is within said range;

generating coefficients of said horizontal distance metric if said slope is not within said range.

3. The method of claim 2 further comprising the step of interpolating vertical distance metrics for a row of sample points by performing a plurality of multiplication functions if said slope is within said range.

4. The method of claim 2 further comprising the step of interpolating vertical distance metrics for a column of sample points by performing a plurality of addition functions if said slope is within said range.

5. The method of claim 2 further comprising the step of interpolating horizontal distance metrics for a column of sample points by performing a plurality of multiplication functions if said slope is not within said range.

6. The method of claim 2 further comprising the step of interpolating horizontal distance metrics for a row of sample points by performing a plurality of addition functions if said slope is not within said range.

7. The method of claim 2, wherein said vertical distance metric is derived from:

space="preserve" listing-type="equation">Dv=Ax+y+C,

where;

Dv=distance value in pixel widths for a subsample point directly to the left or right of a pixel centerpoint;

A=(y₁ -y₀)/(x₁ -x₀ ;

C=(2x₀ y₀ -x₀ y₁ -x₁ y₀)/(x₁ -x₀);

(x₀,y₀) and (x₁,y₁)=coordinate corresponding to two vertices that define said first edge.

8. The method of claim 2, wherein a first horizontal distance metric is derived from:

space="preserve" listing-type="equation">Dh=x+By+C,

where;

Dh=distance value in pixel widths for a subsample point directly above or below a pixel centerpoint;

B=(xO-x1)/(y1-y0);

C=((x1*y0)-(x0*y1)/(y1-y0);

(x₀,y₀) and (x₁,y₁)=coordinate corresponding to two vertices that define said first edge.

9. The method of claim 8 further comprising the step of determining inside/outside status for each of said sample points by examining a sign of each corresponding vertical distance metric if said slope is within said range.

10. The method of claim 9 further comprising the step of determining inside/outside status for each of said sample points by examining a sign of each corresponding horizontal distance metric if said slope is not within said range.

11. The method of claim 10, wherein said merging step is accomplished by performing AND operations for each corresponding sample point of said first mask, said second mask, and said third mask.

12. The method of claim 11, wherein said array is comprised of an 8×

8 matrix of sample points.

13. The method of claim 12, wherein said interpolating steps are accomplished by a table lookup.

14. In a computer system, an apparatus for generating a point sample mask having an array of sample points corresponding to a pixel, wherein each sample point has associated information specifying whether said sample point is inside or outside a polygon, said information being used for rendering said pixel for display by said computer system, said apparatus comprising:

a first generator for generating a first mask corresponding to a first edge of said polygon, said first mask specifying which ones of a first set of said sample points reside within a first half-plane defined by said first edge, wherein a sign of a vertical or horizontal distance metric corresponding to a first sample of said first set of sample points determines whether said first sample resides within said first half-plane;

a second generator coupled to said first generator for generating a second mask corresponding to a second edge of said polygon, said second mask specifying which ones of a second set of sample points reside within a second half-plane defined by said second edge, wherein a sign of a vertical or horizontal distance metric corresponding to a second sample of said second set of sample points determines whether said second sample resides within said second half-plane;

a third generator coupled to said second generator for generating a third mask corresponding to a third edge of said polygon, said third mask specifying which ones of a third set of sample points reside within a third half-plane defined by said third edge, wherein a sign of a vertical or horizontal distance metric corresponding to a third sample of said third set of sample points determines whether said third sample resides within said third half-plane;

a circuit coupled to said first, said second, and said third generators for merging said first mask, said second mask, and said third mask, resulting in said point sample mask.

15. The apparatus of claim 14 further comprising:

a means for determining whether a slope of said edge is within a range of +1 to -1;

a means for generating coefficients of said vertical distance metric if said slope is within said range;

a means for generating coefficients of said horizontal distance metric if said slope is not within said range.

16. The apparatus of claim 15 further comprising a multiplier for interpolating vertical distance metrics for a row of sample points if said slope is within said range.

17. The apparatus of claim 16 further comprising an adder for interpolating vertical distance metrics for a column of sample points if said slope is within said range.

18. The apparatus of claim 17 further comprising a multiplier for interpolating horizontal distance metrics for a column of sample points if said slope is not within said range.

19. The apparatus of claim 18 further comprising an adder for interpolating horizontal distance metrics for a row of sample points if said slope is not within said range.

20. The apparatus of claim 19, wherein a first vertical distance metric is derived from:

space="preserve" listing-type="equation">Dv=Ax+y+C,

where;

Dv=distance value in pixel widths for a subsample point directly to the left or right of a pixel centerpoint;

A=(y₁ -y₀)/(x₁ -x₀ ;

C=(2x₀ y₀ -x₀ y₁ -x₁ y₀)/(x₁ -x₀);

(x₀,y₀) and (x₁,y₁)=coordinate corresponding to two vertices that define said first edge.

21. The apparatus of claim 20, wherein a first horizontal distance metric is derived from:

space="preserve" listing-type="equation">Dh=x+By+C,

where;

Dh=distance value in pixel widths for a subsample point directly above or below a pixel centerpoint;

B=(x0-x1)/(y1-y0);

C=((x1*y0)-(x0*y1)/(y1-y0);

(x₀,y₀) and (x₁,y₁)=coordinate corresponding to two vertices that define said first edge.

22. The apparatus of claim 21 further comprising a means for determining inside/outside status for each of said sample points by examining a sign of each corresponding vertical distance metric if said slope is within said range.

23. The apparatus of claim 22 further comprising a means for determining inside/outside status for each of said sample points by examining a sign of each corresponding horizontal distance metric if said slope is not within said range.

24. The apparatus of claim 23 further comprising an AND circuit for performing AND operations on each corresponding sample point of said first mask, said second mask, and said third mask to produce said point sample mask.

25. The apparatus of claim 24, wherein said array is comprised of an 8×

8 matrix of sample points.

26. The apparatus of claim 25 further comprising a table lookup for performing said interpolation.