Anti-Aliasing is a tricky thing. If you decided you like AGG and it finally solves all your problems in 2D graphics, it's a mistake. Nothing of the kind. The more you worry about the quality the more problems there are exposed.
Let us start with a simple rectangle.
Here we have a rectangle with exact integral coordinates (1,1,4,4). Everything looks fine, but to understand and see how the Anti-Aliasing and Subpixel Accuracy work let's shift it to 0.5 pixel by X and Y:
The pixels have intensities proportional to the area of the pixel covered by the rectangle. In practice it means that the rectangle looks blur. It's not a caprice, it's a necessity because only in this case we can preserve the visual area covered by the rectangle the same, regardless of its subpixel position. The initial rectangle covers 9 pixels. If we just round off the coordinates, the resulting rectangle can be drawn as 4 pixels and it can be drawn as 16 pixels, depending on the position and the rounding rules. So that, the “blurness” is much less evil than "jitter" because it allows you to keep the image much more consistent.
Now let's try to calculate an outline of one pixel width around this square:
This is an ideal case. In prcatice we cannot draw anything between pixels, so the result will look even more blur:
There are no fully covered pixels at all and this fact creates the problem of line alignment. Bad news is that there's no ideal solution of it, we'll have to sacrifice something. The good news is there are several partial solutions that can be satisfactory. First, let's try to add 0.5 to the coordinates of theoutline. Remember, if we add 0.5 to the filled rectangle too, the ones without outlines will look blur (see above).
Looks perfect while the outline is 100% opaque. If we have a translucent boundary it will look worse:
The translucency can be implicit, for example, if we draw a line of 0.5 pixel width, it's simulated with translucency! It will look better if we shift both, the fill and its outline.
But remember, it will look worse if it's not outlined. Still, The first solution is to shift everything to 0.5 pixel, which can be appropriate when you have outlines in all cases.
The second solution is to shift only outlines, keeping the filled polygons as they are. In this case you must be sure you always have the outline of at least 1 pixel width. That's not a good restriction. You can do even better, shifting only those polygons that have an outline (stroke). But in this case you can have some inconsistency between polygons with and without strokes.
The shifting transformer is very simple:
namespace agg{
class trans_shift {
public:
trans_shift() : m_shift(0.0) {}
trans_shift(double s) : m_shift(s) {}
void shift(double s) { m_shift = s; }
double shift() const { return m_shift; }
void transform(double* x, double* y) const
{
*x += m_shift;
*y += m_shift;
}
private: double m_shift;
};}
And its use is simple too:
agg::trans_shift ts(0.5);agg::conv_transform<source_class, agg::trans_shift> shift(source, ts);
That is, it's included into the pipeline as yet another transformer. If you use the affine transformer (most probably you will), you can do without this additional converter. Just add the following, after the matrix is formed:
mtx *= agg::trans_affine_translate(0.5, 0.5);
In this case there will be no additional “performance fee”. Of course, you will have to worry about when and where to add this shift (see cases above).
There is one more solution and it can be even better. Nobody says that we need to apply the same shift to all coordinates. In case of our rectangle there can be inner or outer outline:
You can achive this with using conv_contour, see also Demo conv_contour.cpp.
But there are some problems too. First of all, the “insideness” becomes important, whileconv_stroke doesn't care about it. So that, you should preserve or detect the orientation of the contours, not to mention that self-intersecting polygons don't have a univocal orientation, they can have only a “prevaling” orientation.
The second problem is where to apply this transformation. It should be definitely done beforestroke converter. But there is a contradiction with the succeeding affine transformations. Take the zoom operation, for example. If you want the line widths to be consistent with the transformations, you have to use the affine transformer after the outline is calculated. If it's done before, you can change the stroke width respectively, but in this case you breake the integrity if you have different scaling coefficients by X and Y.
If you are absolutely sure you will never use different scaling coefficients by X and Y, you can transform paths before calculating the outline. In other words, the sequence of the conversions is important and it can be contadictive. Besides, you have to decide if you only need to correct the “0.5 problem” or to have the true inner or outer stroke.
The conclusion is that there's no ideal solution. But the whole idea of Anti-Grain Geometry is that it's you who chooses the neccessary pipelines and solve your problem-orinted tasks. Thare are no other APIs that allow you to have this flexibility.
摘自：http://sourceforge.net/p/vector-agg/mailman/vector-agg-general/?viewmonth=200308
First of all, let me thank you for the suggestions
perfectly explained.
The other thing is that the "rectangle" optimization
doesn't make much sense in comparison with "hline"
one. It complicates things a lot with miserable
result. In fact, the low-level rectangle()
uses hline().
I agree with you completely that solid polygons can be
optimized and it can be done in a way you described.
But first let me tell you about the rasterization
algorithm. Honestly, I don't understand completely the
math (calculating part, outline_aa::render_scanline)
and I guess we'll have to ask David Turner to explain
it if we need.
The algorithm consists of three phases - decomposing
the path into square cells (pixels), sorting the
cells, and "sweeping" the scanlines.
When you call rasterizer.move_to() it accumulates
cells (pixels) that are crossed by the path. It also
calculates the coverage value for each cell (the area
of the cell that the polygon covers). After it's done
all the cells are sorted by Y and then by X with a
modified quick-sort (actually, I sort pointers to the
cells). Finally, method render() "sweeps" the sorted
cells and converts them into a number of scanlines. It
sums all the cells with the same coordinates in order
to calculate right cover value (it happens when the
pixel is crossed more than once by different edges of
the path). It guarantees correct cover values even if
a complex polygon is so small that it falls into one
pixel. This is the main advantage of the algorithm
because it allows you to render very thin objects
correctly (simulating very thin lines with proper
fading).
Function render() creates a scanline that consists of
a number of horizontal spans and then calls
renderer::render() that actually draws the scanline.
I see two major possibilities to optimize rendering.
1. Using agg::scanline_p32 instead of
agg::scanline_u8. Here 'p' and 'u' refer to 'packed'
and 'unpacked'. Packed means that all the cells in the
scanline that have equal cover value are represented
as a horizontal line with x,y,length, and cover.
'Unpacked' means that every cell in the scanline has
its own cover value even if they are all the same. So,
the straight way is to use agg::scanline_p32 and to
optimize renderer_scanline::render(). There're two
notes. First, it makes sense if the area of the
objects is large enough, that is, rendering small
glyphs is more efficient with using agg::scanline_u8
because of less branched code. Second, it works only
for solid color filling. For gradients, images,
Gouraud we'll have to process the scanline
pixel-by-pixel anyway. From this point of view using
agg::scanline_p32 doesn't make much sense either.
Still, solid filling is a very common operation and
it'd be very good to optimize it. We'll have the best
result when the color is opaque. But we can optimize
translucent colors too! Here we can use the fact of
the relative coherence of the background image. For
solid span we calculate (alpha-blend) the first pixel
and then check if the color of the next pixel is the
same we simply put previously calculated value.
It's all very good, but it doesn't help much to speed
up drawing thin strokes. In this case the distribution
of spent time is quite different. The most time
consuming operation in this case is qick_sort. You can
ultra-optimize the scanline rendering but you won't
achieve much because scanlines in this case are very
short and they don't play any considerable role.
There's the second posibility of optimization.
2. We cannot get rid of rasterizing and calculating
cells (outline_aa::render_line) but we can play with
quick-sort. Namely, we don't have to sort the whole
path but only each scanline. If the sorting algorithm
had exactly linear complexity it would't make sense.
But it's faster to sort 100 arrays of 10 elements each
than one array of 1000 elements. In case of
rasterizing a thin line we usually have 2, 3, or 4
cells in the scanline. Simple insertion sort works
faster than the quick-sort in these cases. It looks
rather promising but it requires a kind of smart
memory managing (it requires reallocs and I wouldn't
rely on that they are fast and painless).
agg::scanline_p32 is not finished yet. '32' refers to
the maximal capacity of the coverage value - 32 bits,
but I'd add one more template argument in order to use
8-bit values.
McSeem
--- eric jones <eric@...> wrote:
> Hey Group,
>
> Thinking out loud and long winded...
>
> I've just started exploring the process for building
> an optimized
> renderer for general (anti-aliased, thick, etc.)
> veritical/horizontal
> lines and rectangles. Since I haven't poked around
> much in this part of
> agg, it is all high-level. Forgive me if this all
> falls under the
> category of "obvious," but I have not done much with
> low level graphic
> algorithms before. I am just trying to figure out
> what the important
> abstractions are and hopefully get some ideas about
> where to plug such
> ideas into agg.
> The easiest place to start looking is at drawing a
> single, solid ( i.e:
> non-dashed but potentially semi-transparent),
> vertical/horizontal line
> with arbitrary thickness and end-caps. The line can
> be broken into
> three basic regions - the two end regions and the
> middle region. For a
> horizontal line, the regions can be labeled as so:
>
> End1 Middle End2
>
> Lets look at the middle region of pixels first
> because it is the
> simplest to render. For example, if our line
> horizontal line is 5
> pixels (scanlines) thick, the "cover" value for all
> the pixels on a
> single scanline will be the same because the
> antialiasing algorithm
> would return the same alpha value for all of these
> pixels (I hope I am
> using the cover term correctly here). For example,
> the 5 scanlines of
> the middle region might have alpha values (assume
> 0-9 as full alpha
> range) of 1, 5, 9, 5, and 1 respectively resulting
> in the following
> alpha mask for the middle region's applied to the
> line's color value.
>
> 111111111111111111111111111111111111
> 555555555555555555555555555555555555
> 999999999999999999999999999999999999
> 555555555555555555555555555555555555
> 111111111111111111111111111111111111
>
> Based on this, we only have to calculate alpha once
> for the line and
> then call the hline() method (with the alpha
> blending patch) 5 times -
> once for each scanline. I'm guessing this would be
> a decent speed win
> over the current algorithm. Is this a correct
> assumption McSeem? Also,
> it makes hline() and vline() great candidates for
> platform dependent
> optimization in the future (SSE2, the Intel Image
> library, or whatever)
> because making them fast would speed up a large
> amount of the general
> cases.
>
> As for the end regions, they need a "complex"
> anti-aliasing algorithm
> applied to them where the "cover" value each pixel
> value is treated
> independently. This is similar to the current
> rendering approach, but
> we can't just treat the end-caps as polygons and
> feed them into the
> current path render because antialiasing is applied
> from one side (left
> on End1, right on End2). McSeem, is this right or
> is there some way for
> the current path renderer to handle this?
>
> Here are the alpha values of my (fictitious) width=5
> line with rounded
> end-caps broken out by the region in which they are
> rendered.
>
> End1 Middle End2
> 111111111111111111111111111111111111
> 123 555555555555555555555555555555555555
> 321
> 1257 999999999999999999999999999999999999
> 7521
> 123 555555555555555555555555555555555555
> 321
> 111111111111111111111111111111111111
>
>
> Hmmm. I guess, with thicker lines, there would
> really be another region
> of interest:
>
> Top-Middle
> End1 Center-Middle End2
> Bottom-Middle
>
> Here, the ends are rendered the same way as before.
> The Top-Middle and
> Bottom-Middle are regions would be the anti-aliasing
> "blend-in" regions
> of the line and rendered as previously discussed for
> the "Middle"
> region. The Center-Middle section would be the area
> of the line that
> has a constant alpha cover of 9 and could be filled
> with a call to the
> rectangle() primitive. So, breaking out the Top,
> Center and Bottom
> regions, assuming a new line of with 10, we would
> have something like:
>
> 111111111111111111111111111111111111
> Top-Middle
> 555555555555555555555555555555555555
>
> 999999999999999999999999999999999999
> 999999999999999999999999999999999999
> 999999999999999999999999999999999999
> Center-Middle
> 999999999999999999999999999999999999
> 999999999999999999999999999999999999
> 999999999999999999999999999999999999
>
> 555555555555555555555555555555555555
> Bottom-Middle
> 111111111111111111111111111111111111
>
> So, I guess this all can be generalize by saying
> there are three major
> types of regions for anti-aliased rendering of any
> type of object be it
> a thick line, a rectangle, or an arbitrary path:
>
> 1. Quickly varying areas where the alpha is
> calculated for each
> pixel.
> 2. Slowly varying areas where alpha is calculated
> for an entire
> row
> (vertical or horizontal) at a time.
> 3. Constant areas where the alpha doesn't
> change. This could be,
> but
> doesn't have to be a rectangular region.
>
> It happens that it is fairly simple to break
> horizontal/vertical lines
> and rectangles into these regions. The vertical
> line is the same as the
> horizontal if we exchange "scan-column" for
> "scanline." As for a
> rectangle, we have to deal with the joins in the
> corners. Its regions
> would break down as follows:
>
> TL-Corner Top-Middle TR-Corner
> Left-Middle Center-Middle Right Middle
> BL-Corner Bottom-Middle BR-Corner
>
> Here, the Corners are all "quickly varying," the Top
> and Bottom Middle
> are "slowly varying" using calls to the hline()
> primitive, the Left and
> Right Middle are "slowly varying" using calls to the
> vline()
> primitive(), and the Center-Middle is, again,
> constant.
>
> I'm most interested in the cases that are described
> above, but it occurs
> to me that it is possible to decompose arbitrary
> paths up into these
> three types of regions prior to calling a renderer.
> This
> domain-decomposition might be so expensive that it
> swamps any benefits
> in some cases -- I am not experienced with such
> algorithms. I would
> think that there is some way to do it, perhaps on a
> per scanline basis
> instead of on the entire path, that would provide a
> speed improvement.
>
> Back to horz/vert lines and rectangles. I still
> need to handle dashed
> lines. I'm guess the way to do this is pass this
> through
本文转自fengyuzaitu 51CTO博客，原文链接：http://blog.51cto.com/fengyuzaitu/1972930，如需转载请自行联系原作者
