CN101901590B

CN101901590B - Method and system for anti-sawtooth polygonal rasterization

Info

Publication number: CN101901590B
Application number: CN 200910142114
Authority: CN
Inventors: 白向晖; 洲镰康; 谭志明
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 2009-05-25
Filing date: 2009-05-25
Publication date: 2013-01-16
Anticipated expiration: 2029-05-25
Also published as: CN101901590A

Abstract

The invention discloses a method and a system for anti-aliased polygonal rasterization. The method for the anti-aliased polygonal rasterization comprises the following steps of: calculating a side equation of each side of a polygon by using vertex coordinates of the polygon; judging whether a rasterization segment which is used for rasterizing the polygon intersects with the polygon by using the side equation of each side, and if so, calculating the intersecting area of the rasterization segment and the polygon; and mixing the polygon and the display background of the polygon according to the intersecting area. By performing the anti-aliased polygonal rasterization, the method does not need to repeatedly sample the rasterization segment. Therefore, the needed calculation amount is effectively reduced.

Description

The method and system that is used for the polygonal gird of anti-sawtooth

Technical field

The present invention relates to the graphics process field, relate more specifically to a kind of method and system of the polygonal gird for anti-sawtooth.

Background technology

The rasterizing of figure is a kind of processing procedure (that is, figure being carried out the processing procedure of pixelation) that polar plot is converted to bitmap.The task that polygon on the raster graphic display subsystem is scanned conversion is to determine to be positioned at the coordinate of the pixel of the polygon on the two-dimensional grating lattice.The pixel that illuminates fully on many line segments that comprise this polygon is similar to this polygonal notch cuttype pattern with generation.

Existing for anti-sawtooth (namely, what the technology of polygonal gird anti-notch cuttype pattern) adopted usually is the method for multiple sampling, namely, a plurality of points of rasterizing segment are sampled and calculated the sampled value of each sampled point, thereby then a plurality of sampled values are carried out the color value that filtering obtains the rasterizing segment.

Can be found out that by the above the technology of existing polygonal gird for anti-sawtooth is consuming time and calculation of complex not only, and when realizing with example, in hardware, will need the support of expensive additional hardware.If the raster graphic display subsystem is a sufficiently high subsystem of performance, then the technology of the above-mentioned polygonal gird that is used for anti-sawtooth can realize polygonal gird well.Yet, for graphic system cheaply, need to make compromise aspect the raster graphic Graphics Processing speed, to have the competitive power on the price.In this graphic system, the use of Reduced Instruction Set Computer (RISC) CPU (central processing unit) (CPU) will make the needed degrees of compromise in processor performance aspect minimum.But, use the polygonal gird method of traditional anti-sawtooth will make the graphic response in these graphic systems seem slow.So, need a kind of faster and calculate the relatively simple system and method that is used for the polygonal gird of anti-sawtooth than conventional art.

Summary of the invention

One or more problems in view of the above the invention provides a kind of method and system of the polygonal gird for anti-sawtooth.

The method of the polygonal gird that is used for anti-sawtooth according to an aspect of the present invention comprises: utilize polygonal apex coordinate to calculate the limit equation on polygonal each bar limit; Utilize the limit equation on each bar limit to judge for the rasterizing segment of polygon being carried out rasterizing whether intersect with polygon; If intersect, then computation grid segment and polygonal crossing area; And according to crossing area, the display background at polygon and polygon place is mixed.

The system of the polygonal gird that is used for anti-sawtooth according to a further aspect in the invention comprises: the equation computing unit is used for utilizing polygonal apex coordinate to calculate the limit equation on polygonal each bar limit; Intersect judging unit, be used for utilizing the limit equation on each bar limit to judge for the rasterizing segment of polygon being carried out rasterizing whether intersect with polygon; The area computing unit is used in the crossing situation of rasterizing segment and polygon computation grid segment and polygonal crossing area; And the figure mixed cell, be used for according to intersecting area the display background at polygon and polygon place being mixed.

Adopt the present invention to carry out the polygonal gird of anti-sawtooth, do not need the rasterizing segment is carried out multiple sampling, thereby effectively reduced required calculated amount.

Description of drawings

From below in conjunction with the present invention may be better understood the description of accompanying drawing to the specific embodiment of the present invention, wherein:

Fig. 1 shows the block diagram according to the system of the polygonal gird that is used for anti-sawtooth of the embodiment of the invention;

Fig. 2 shows the detailed diagram of the spider module in the system shown in Figure 1;

Fig. 3 shows the block diagram of the system of the polygonal gird that is used for according to another embodiment of the present invention anti-sawtooth;

Fig. 4 shows Fig. 1 carries out the main process of polygonal gird to the system of the polygonal gird for anti-sawtooth shown in Figure 2 process flow diagram;

Fig. 5 shows the polygonal contrast synoptic diagram that the method/system of the polygonal gird of polygon that the method/system of the polygonal gird of anti-sawtooth not draws and anti-sawtooth is drawn;

Fig. 6 shows the synoptic diagram of the various relations on rasterizing segment and a polygonal limit; And

Fig. 7 shows the synoptic diagram that rasterizing segment and polygon intersect and be positioned at the situation outside polygonal many limits.

Embodiment

The below will describe feature and the exemplary embodiment of various aspects of the present invention in detail.In the following detailed description, many details have been proposed, in order to complete understanding of the present invention is provided.But, it will be apparent to those skilled in the art that in the situation of some details that the present invention can be in not needing these details and implement.The below only is in order to provide better understanding of the present invention by example of the present invention is shown to the description of embodiment.Any concrete configuration and the algorithm that propose below the present invention never is limited to, but any modification, replacement and the improvement that have covered under the premise of without departing from the spirit of the present invention element, parts and algorithm.In the the accompanying drawings and the following description, known structure and technology are not shown, in order to avoid the present invention are caused unnecessary bluring.

Fig. 1 shows the block diagram according to the system of the polygonal gird that is used for anti-sawtooth of the embodiment of the invention.As shown in Figure 1, the system 100 that should be used for the polygonal gird of anti-sawtooth comprises: vertex information storer 102 is used for the polygonal apex coordinate that storage need to be carried out rasterizing; Conversion and projection module 104 are used for reading apex coordinate from the vertex information storer, and apex coordinate are projected on the device coordinate; Arrange and spider module 106, be used for the use device coordinate and find out the pixel (that is, the rasterizing segment) that is positioned at polygon, and calculate the display parameter (color/texture) of these pixels; Frame buffer 108 is used for the display parameter of these pixels are carried out buffer memory; And image display module 110, for the polygon after the show grid processing.

Particularly, conversion and projection module 104 read the polygonal apex coordinate that need to carry out rasterizing from vertex information storer 102, and apex coordinate is projected on the device coordinate; Setting and spider module 106 use device coordinates are found out the pixel that is positioned at polygon, and calculate the display parameter (color or texture) of these pixels, then with these parameter read-in frame buffers 108.At last, image display module 110 utilizes the polygon after parameter in the frame buffer is come show grid.

Fig. 2 shows setting in the system shown in Figure 1 and the detailed diagram of spider module.As shown in Figure 2, the setting unit 1062 in setting and the spider module 106 is obtained the apex coordinate on polygonal each summit, and uses these apex coordinates to calculate the limit equation on polygonal each bar limit.Setting unit 1062 with the coefficient information of the limit equation on each bar limit send to arrange and spider module 106 in traversal unit 1064 so that the traversal unit carries out following processing: judge according to the limit equation on polygonal each bar limit whether the rasterizing segment crossing with polygon; If intersect, then computation grid segment and polygonal crossing area; Utilize the apex coordinate of rasterizing segment that polygonal display parameter (for example, color/parametric texture) are carried out interpolation; And utilize the crossing area that calculates, the display parameter after the polygonal interpolation are mixed with the display parameter of display background.

Fig. 3 shows the system that is used for according to another embodiment of the present invention the polygonal gird of anti-sawtooth.As shown in Figure 3, the system 300 that should be used for the polygonal gird of anti-sawtooth comprises: equation computing unit 302 is used for utilizing polygonal apex coordinate to calculate the limit equation on polygonal each bar limit; Intersect judging unit 304, be used for utilizing the limit equation on each bar limit to judge for the rasterizing segment of polygon being carried out rasterizing whether intersect with polygon; Area computing unit 306 is used in the crossing situation of rasterizing segment and polygon computation grid segment and polygonal crossing area; And figure mixed cell 308, be used for according to intersecting area the display background at polygon and polygon place being mixed.Wherein, area computing unit 306 further comprises the first computing unit 3062 and the second computing unit 3064, and the first computing unit 3062 further comprises intersection edges acquiring unit 3062-2, calculation block setting unit 3062-4 and sheet basal area computing unit 3062-6.

Fig. 4 shows Fig. 1 carries out the main process of polygonal gird to the system of the polygonal gird that is used for anti-sawtooth shown in Figure 3 process flow diagram.As shown in Figure 4, this process comprises: S402, utilize polygonal apex coordinate to calculate the limit equation on polygonal each bar limit; S404 utilizes the limit equation on each bar limit to judge for the rasterizing segment of polygon being carried out rasterizing whether intersect with polygon; S406, if intersect, then computation grid segment and polygonal crossing area; And S408, according to crossing area, the display background at polygon and polygon place is mixed.

For example, step S402 can finish by the setting unit 1062 in the setting shown in Fig. 1 and Fig. 2 and the spider module 106, and step S404～S408 can finish by the traversal unit 1064 in the setting shown in Fig. 1 and Fig. 2 and the spider module 106.Perhaps, step S402～S408 can be finished by the equation computing unit 302 shown in Fig. 3, crossing judging unit 304, area computing unit 306 and figure mixed cell 308 respectively.

In the polygonal gird method of anti-sawtooth not, only judge whether the center of rasterizing segment is positioned at polygon.If be positioned at polygon, judge that then this rasterizing segment is for being drawn.In the polygonal gird method of anti-sawtooth, need to judge polygonal inside whether with the rasterizing segment in part crossing.Fig. 5 shows the polygonal contrast synoptic diagram that the method/system of the polygonal gird of polygon that the method/system of the polygonal gird of anti-sawtooth not draws and anti-sawtooth is drawn.As can be seen from the figure, the technology of the polygonal gird by adopting anti-sawtooth can make the more natural of polygonal border and background transition, thereby can avoid producing jagged edge effect.

The below specifically describes the detailed processing procedure of step S404～S408:

Step S404 utilizes the limit equation on each bar limit to judge for the rasterizing segment of polygon being carried out rasterizing whether intersect with polygon.Fig. 6 shows the synoptic diagram of the various relations on rasterizing segment and a polygonal limit.

The limit equation of supposing n limit shape (n 〉=3) is ei (x, y)=ai*x+bi*y+ci, (i=0,1,2 ..., n-1), the centre coordinate of rasterizing segment is (x, y), and four summits are V0 (x-0.5, y-0.5), V1 (x+0.5, y-0.5), V2 (x-0.5, y+0.5), V3 (x+0.5, y+0.5).When meeting the following conditions, judge that rasterizing segment and polygon intersect: the rasterizing segment is positioned in the polygonal bounding box (that is, comprising this polygonal minimum rectangle); For polygonal any limit, from four summits of rasterizing segment, select a summit Vt (xt, yt), this summit for the limit equation value ei (xt, yt) of this edge for just.Wherein, the selection of Vt (xt, yt) is that the coefficient (ai, bi) of the limit equation by this edge obtains.When ai＞=0 and bi＞=0, Vt=V3; When ai＞=0 and bi＜0, Vt=V1; When ai＜0 and bi＞=0, Vt=V2; And when ai＜0 and bi＜0, Vt=V0.Deterministic process is achieved as follows particularly:

for(i＝0；i＜n；i++＝

{

if(a[i]≥0)dx＝0.5；else dx＝-0.5；

if(b[i]≥0)dy＝0.5；else dy＝-0.5；

xt＝x+dx；

yt＝y+dy；

if(a[i]*xt+b[i]*yt+c[i]≤0)return false；

}

return true；

S406, if intersect, then computation grid segment and polygonal crossing area.This step comprises 5 sub-steps:

1) part of finding out the rasterizing segment is positioned at its outer polygonal limit.This step for example can be finished by intersection edges acquiring unit 3062-2.

The limit equation of supposing n limit shape is ei (x, y)=ai*x+bi*y+ci, (i=0,1,2 ..., n-1), the coordinate at the center of rasterizing segment is (x, y), and four summits are V0 (x-0.5, y-0.5), V1 (x+0.5, y-0.5), V2 (x-0.5, y+0.5), V3 (x+0.5, y+0.5).From four summits of rasterizing segment, select a summit Vt (xt, yt), if this summit for the limit equation value of a certain limit ei not for just, judge that then this rasterizing segment has this edge ei zone in addition.Deterministic process is achieved as follows particularly:

if(a[i]≥0)dx＝-0.5；else dx＝0.5；

if(b[i]≥0)dy＝-0.5；else dy＝0.5；

xt＝x+dx；

yt＝y+dy；

if(a[i]*xt+b[i]*yt+c[i]≤0)return true；

else return false；

2) the rasterizing segment is set in step 1) in the calculation block of perimeter on the limit that draws.This step for example can be finished by calculation block setting unit 3062-4.

Suppose that the limit that the rasterizing segment has its perimeter is ei (x, y), and e[i] the x coordinate on two summits be xmin[i] and xmax[i] (xmin[i]＜xmax[i]=.Four summits of calculation block are (xs, ys), (xs, ye), (xe, ys), (xe, ye).Wherein, if xmin[i] and xmax[i] be not positioned at the inside of rasterizing segment, then the position of calculation block is exactly the position at rasterizing segment place; If xmin[i] or xmax[i] be positioned at the inside of rasterizing segment, corresponding xs then, xe need to be modified to xmin[i] and xmax[i], concrete computation process is as follows:

if(xt＝＝x+0.5)

{

if(xt＞xmax[i])xs＝xmax[i]；else xs＝xt；

if(x-0.5＜xmin[i])xe＝xmin[i]；else xe＝x-0.5；

}

else

{//xt＝＝x-0.5

if(xt＜xmin[i])xs＝xmin[i]；else xs＝xt；

if(x+0.5＞xmax[i])xe＝xmax[i]；else xe＝x+0.5；

}

if(yt＝＝y-0.5)

{ys＝yt；ye＝y+0.5}；

else

{ys＝yt；ye＝y-0.5}

3) the computation grid segment is in step 1) in the area in zone of outside on the limit that draws.

Four summits of calculation block are V0 (xs, ys), V1 (xe, ys), V2 (xs, ye), V3 (xe, ye).The e[i of V0/V1/V2/V3] value is for e0[i]/e1[i]/e2[i]/e3[i].The area Soe[i of the perimeter in the rasterizing segment] as follows:

e0[i]	＜0	＜0	＜0	＜0	＞＝0
						e1[i]	＞＝0	＜0	＜0	＞＝0	/
e2[i]	＞＝0	＞＝0	＜0	＜0	/
						Soe[i]	\|e0[i]/a\|＊\|e0[i]/b\|/2	(\|e0[i]/b\|+\|e1[i]/b\|)/2	1-(\|e3[i]/a\|＊\|e3[i]/b\|/2)	(\|e0[i]/a\|+\|e2[i]/a\|)/2	0

4) to the rasterizing segment in step 1) in the area summation of all perimeters on the limit that draws.

for(i＝0；i＜n；i++)

{

Sop+＝Soe[i]

}

Wherein, if the most left polygonal or summit, the rightmost side is positioned at the rasterizing segment, then need cumulative perimeter.Fig. 7 shows the synoptic diagram that rasterizing segment and polygon intersect and be positioned at the situation outside polygonal many limits.

The x coordinate of supposing summit, the polygonal leftmost side is gxmin, the x coordinate on summit, the rightmost side is gxmax, (x-0.5＜gxmin＜x+0.5=, then the area on the gxmin left side (gxmin-x+0.5) needs additionally cumulative if gxmin is positioned at the rasterizing segment.Equally, (x-0.5＜gxmax＜x+0.5), then the area (x+0.5-gxmax) on gxmax the right needs additionally cumulative if gxmax is positioned at the rasterizing segment.

If(x-0.5＜gxmin＜x+0.5＝Sop+＝gxmin-x+0.5；

If(x-0.5＜gxmax＜x+0.5＝Sop+＝x+0.5-gxmax；

Substep 3) and 4) for example can be finished by sheet basal area computing unit 3062-6.From above for substep 1)～5) description can find out that these substeps are processing procedures that the computation grid segment is positioned at the area of the outer segment part of polygon, this process for example can be finished by the first computing unit 3062.

5) last, draw crossing area by equation coverage=1-Sop.This step for example can be finished by the second computing unit 3064.

S408 according to crossing area, mixes the display background at polygon and polygon place.Parameter after the polygonal interpolation is mixed with context parameter, to realize the effect of anti-sawtooth.Wherein, blending ratio is for intersecting area.

P＝Pb*(1-Coverage)+Pi*Coverage；

Wherein, Pb is context parameter, and Pi is the parameter after the interpolation.

In sum, the polygonal girdization that adopts the present invention to carry out anti-sawtooth does not need the rasterizing segment is carried out multiple sampling, thereby has effectively reduced required calculated amount.

It should be noted that, above-described each module and/or each unit (for example can use the hardware of pre-programmed or firmware components, special IC (ASIC)) realizes, also can use to comprise erasable remove also data processing equipment or other relevant assembly realization of programmable ROM (read-only memory) (EEPROM).

It will be understood by those skilled in the art that also to have how optional embodiment and the improved procedure that can be used in the present invention embodiment, and above-mentioned embodiment and example only are the explanations of one or more embodiment.Therefore, scope of the present invention is only limited by appended claims.

Claims

1. A method for anti-aliasing polygon rasterization, comprising:

calculating edge equations of each edge of the polygon using the vertex coordinates of the polygon;

Using the edge equations of the edges to determine whether the rasterization segment used to rasterize the polygon intersects the polygon;

if so, computing the intersection area of the rasterized segment with the polygon; and

Blending the polygon and the display background where the polygon is located according to the intersection area, wherein

The process of calculating the intersection area of the rasterized segment and the polygon includes:

calculating the area of a segment portion of the rasterized segment that lies outside the polygon;

The intersection area of the rasterized segment with the polygon is calculated by subtracting the total area of the rasterized segment from the area of the segment portion.

2. The method for anti-aliasing polygon rasterization according to claim 1, wherein when the rasterization fragment is located within the bounding box of the polygon and at least one of the rasterization fragments When the edge equation value of the vertex relative to any edge of the polygon is greater than zero, the rasterized segment intersects the polygon, wherein the bounding box is a minimum rectangle including the polygon.

3. The method for anti-aliasing polygon rasterization according to claim 1, wherein the process of calculating the area of the fragment portion comprises:

Finding an edge of the polygon outside which a part of the rasterization fragment is located according to an edge equation value of each vertex of the rasterization fragment relative to each edge of the polygon;

According to the coordinate values of each vertex of the rasterization fragment and the coordinate values of the two endpoints of a side of the polygon, set the fragment portion used to calculate the fragment located outside a side of the polygon in the rasterization fragment The calculation box for the area of ;

Using the calculation box, an area of a segment portion of the rasterized segment located outside one side of the polygon is calculated.

4. The method for anti-aliasing polygon rasterization according to claim 3, characterized in that, when the leftmost or rightmost vertex of the polygon is located in the calculation frame, the raster The area accumulation of the segment parts of the gridded segment located outside the multiple sides of the polygon is accumulated, and the accumulation result is used as the area of the segment part of the rasterized segment located outside the polygon.

5. A system for anti-aliasing polygon rasterization, comprising:

an equation calculation unit, configured to calculate an edge equation of each edge of the polygon using the coordinates of the vertices of the polygon;

an intersection judging unit, configured to judge whether the rasterization segment used to rasterize the polygon intersects the polygon by using the edge equations of the edges;

an area calculating unit for calculating an intersection area of the rasterized segment and the polygon in the case where the rasterized segment intersects the polygon; and

a graphic blending unit, configured to blend the polygon and the display background where the polygon is located according to the intersection area, wherein

The area calculation unit includes:

a first calculating unit, configured to calculate an area of a segment part of the rasterized segment located outside the polygon;

The second calculation unit is configured to calculate the intersection area of the rasterized segment and the polygon by subtracting the total area of the rasterized segment from the area of the segment part.

6. The system for anti-aliasing polygon rasterization according to claim 5, wherein at least one of said rasterized fragments is located within the bounding box of said polygon and said rasterized fragments When the edge equation value of the vertex relative to any edge of the polygon is greater than zero, the rasterized segment intersects the polygon, wherein the bounding box is a minimum rectangle including the polygon.

7. The system for anti-aliasing polygon rasterization according to claim 5, wherein the first computing unit comprises:

An intersecting edge acquiring unit, configured to find, according to the edge equation values of each vertex of the rasterized segment relative to each edge of the polygon, one of the polygons where a part of the rasterized segment is located outside. side;

The calculation frame setting unit is used to set the coordinate value of each vertex of the rasterization fragment and the coordinate values of the two endpoints of a side of the polygon to calculate the position of the rasterization fragment located in the polygon. A calculation box for the area of the fragment part outside a side;

A segment area calculation unit configured to calculate an area of a segment portion of the rasterized segment located outside one side of the polygon using the calculation frame.

8. The system for anti-aliasing polygon rasterization according to claim 7, wherein when the leftmost or rightmost vertex of the polygon is located in the calculation frame, the The system for anti-aliasing polygon rasterization accumulates the area of the fragment part of the rasterized fragment located outside the multiple sides of the polygon, and uses the accumulated result as the area of the rasterized fragment located outside the polygon. The area of the fragment.