Method for generating a subpixel mask for computer graphics system and apparatus thereof

• US 5,544,294 A
• Filed: 09/22/1994
• Issued: 08/06/1996
• Est. Priority Date: 12/28/1993
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Wee, Young-cheul, Choi, Sang-gil, Cho, Jun-hyoung
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US08/310,321
• Time in Patent Office: 684 Days
• Field of Search: 395/141, 395/131, 395/126, 395/127, 395/128, 395/129-132, 395/133, 395/142, 382/254, 382/258, 382/266, 382/269, 382/274
• US Class Current: 345/441
• CPC Class Codes: G06T 2200/12 involving antialiasing
• CPC Class Codes: G06T 3/403 Edge-driven scaling; Edge-based scaling
• CPC Class Codes: G09G 5/20 Function-generator circuits, e.g. circle generators line or curve smoothing circuits

Abstract

In a computer graphics system, a method for generating a subpixel mask for polygon edges directly by an operation without using a look-up table, includes the steps of forming subblocks by dividing a pixel into n subpixels depending on the slope of the polygon edge, calculating subblock coverage which is a distance from the pixel boundary to the intersection point of n subblocks and polygon edge, and generating an n×n subpixel mask depending on the calculated subblock coverage. In an apparatus using the method, edge-generated aliasing is removed.

Claims

1. A method for generating an n×

n subpixel mask of a pixel for antialiasing by receiving Δ

X and Δ

Y values of an edge having a slope and an initial value of a cross distance, the method comprising the steps of;

forming subblocks by dividing the pixel into n subblocks depending on the slope;

calculating a subblock coverage by;

determining a pair of reference points depending on the slope of the edge,

calculating cross distances (de) defined by the distance from one of the reference points to an intersection point of the edge and a pixel boundary,

subtracting a slope ratio value from a first cross distance after calculating a corresponding cross distance from the initial value of the first cross distance by an interpolation method and calculating slope ratio values of the formed subblocks, including calculating a slope ratio value (m_k), by drawing a first line parallel to another pixel boundary line at the intersection point and then obtaining a distance from the first line to the edge, in the subblock units, and calculating the subblock coverage (h_k) as h_k =de-m_k ; and

generating an n×

n subpixel mask depending on the calculated subblock coverage, whereby aliasing generated at the edge is removed.

2. The method for generating a subpixel mask for antialiasing as claimed in claim 1, wherein the subblock forming step includes the steps of:

forming n column subblocks if an absolute value of the slope of the edge is no larger than one; and

forming n row subblocks if the absolute value of the slope of the edge is greater than one.

3. The method for generating a subpixel mask for antialiasing as claimed in claim 1 wherein the reference point determining step includes utilizing top left and bottom right vertices of the pixel as the reference points if the slope of the edge is positive and utilizing bottom left and top right vertices of the pixel as the reference points if the slope of the edge is negative.

4. The method for generating a subpixel mask for antialiasing as claimed in claim 1 wherein the cross distance calculating includes comparing a value of the first cross distance with a value of a corresponding cross distance and selecting the value of the cross distance having an absolute value no larger than one as the cross distance value to be used in calculating the subblock coverage, and selecting the value of the cross distance that is positive if the absolute values of the cross distances are both no larger than one.

5. The method for generating a subpixel mask for antialiasing as claimed in claim 1 wherein calculating the slope ratio value includes sequentially obtaining Δ

Y values in the order of said column subblocks (k) using the formula ##EQU3## with respect to column subblocks, and sequentially obtaining Δ

X values in the order of said row subblocks (k) using the formula ##EQU4## with respect to row subblocks.

6. The method for generating a subpixel mask for antialiasing as claimed in claim 1, wherein said n×

n subpixel mask generating step includes the steps of;

obtaining an error correction value by adding and sorting the subblock coverage;

converting the subblock coverage and error correction value into data for setting a subpixel mask; and

setting a subpixel mask depending on a magnitude of the slope, the data, and sign of the first cross distance.

7. The method for generating a subpixel mask for antialiasing as claimed in claim 6, wherein converting is performed such that the subblock coverage and the error correction value are converted into data composed of log₂ n+1 bits.

8. The method for generating a subpixel mask for antialiasing as claimed in claim 6, wherein subpixel mask setting step includes setting the subpixel mask in column subblock units depending on said converted data if an absolute value of the slope is less than or equal to one, and setting the subpixel mask in row subblock units depending on said converted data if the absolute value of the slope is greater than one.

9. The method for generating a subpixel mask for antialiasing as claimed in claim 6, wherein subpixel mask setting includes setting the subpixel mask to a first value depending on the data and then outputting the first value if the sign of the first cross distance is positive, and setting the subpixel mask to an inverse of the first value if the sign of the first cross distance is negative.

10. An apparatus for generating an n×

n subpixel mask of a pixel for antialiasing in a computer graphics system by receiving Δ

X and Δ

Y values of an edge having a slope and an initial value of a cross distance, the apparatus comprising;

a slope ratio value calculator for calculating a slope ratio value by selecting the Δ

X or the Δ

Y value depending on the slope;

a cross distance interpolator for calculating the cross distance necessary for computing subblock coverage using an interpolation method, receiving the initial value of the cross distance, and selecting the initial value for use in computing the subblock coverage;

a subblock coverage calculator for calculating the subblock coverage, receiving the slope ratio value output from said slope ratio value calculator and the cross distance output from said cross distance interpolator, wherein said subblock coverage calculator includes a plurality of subtractors for subtracting an output of said subblock coverage calculator from an output of said cross distance interpolator;

data converting means receiving the subblock coverage output from said subblock coverage calculator for converting the subblock coverage into data for setting a subpixel mask; and

a subpixel mask generator, receiving the data from said data converting means, for generating an n×

n subpixel mask depending on the slope and the cross distance output from said cross distance interpolator, whereby aliasing generated at the edge is removed.

11. The apparatus for generating a subpixel mask for antialiasing as claimed in claim 10, wherein the Δ

Y value is selected as the input to said slope ratio value calculator if the slope is positive and the Δ

X value is selected as the input to said slope ratio value calculator if the slope is negative.

12. The apparatus for generating a subpixel mask for antialiasing as claimed in claim 10, wherein said slope ratio value calculator includes:

a plurality of shift registers for shifting by a predetermined number of bits, receiving the selected Δ

X or Δ

Y value; and

a plurality of adders for summing outputs of said plurality of shift registers.

13. The apparatus for generating a subpixel mask for antialiasing as claimed in claim 10, wherein said data converting means includes:

an error corrector for generating an error correction value by adding and sorting outputs of said subblock coverage calculator; and

a data converter for converting outputs of said subblock coverage calculator and said error corrector into the data for setting the subpixel mask.

14. The apparatus for generating a subpixel mask for antialiasing as claimed in claim 10, wherein said subpixel mask generator includes n×

n D flip-flops for setting output values depending on the data in column subblock units if the absolute value of the slope is less no larger than one and setting the output values depending on the data in row subblock units if the absolute value of the slope is greater than one, and for outputting the output values to non-inverted output ports when the sign of the cross distance is positive and for outputting the output values to inverted output ports when the sign of the cross distance is negative.

15. An apparatus for generating a subpixel mask of a computer graphics system wherein aliasing generated at triangle edges is removed, said apparatus comprising:

a first edge processor for generating an n×

n subpixel mask for a pixel passing over a first edge by receiving the Δ

X1 and Δ

Y1 values of the first edge and an initial value of a cross distance;

a second edge processor for generating an n×

n subpixel mask for a pixel passing over a second edge by receiving Δ

X2 and Δ

Y2 values of the second edge and the initial value of the cross distance;

a third edge processor for generating an n×

n subpixel mask for a pixel passing over a third edge by receiving Δ

X3 and Δ

Y3 values of the third edge and the initial value of the cross distance; and

an AND gate for performing an AND operation, receiving the outputs of said first, second, and third edge processors.

16. A method for generating an n×

n subpixel mask of a pixel for antialiasing by receiving Δ

X and Δ

Y values of an edge having a slope and an initial value of a cross distance, the method comprising;

forming subblocks by dividing the pixel into n subblocks depending on the slope;

calculating subblock coverage by subtracting a slope ratio value from a first cross distance after calculating a corresponding cross distance from the initial value of the first cross distance by an interpolation method and calculating slope ratio values of the formed subblocks;

generating an n×

n subpixel mask depending on the calculated subblock coverage, whereby aliasing generated at the edge is removed;

obtaining an error correction value by adding and sorting the subblock coverage;

converting the subblock coverage and error correction value into data for setting a subpixel mask; and

setting a subpixel mask depending on the magnitude of the slope, the data, and sign of the first cross distance.