开发者社区> 技术小胖子> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

AGG第四十八课 抗锯齿说明一

简介:
+关注继续查看

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,如需转载请自行联系原作者


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
保存微信文章中的图片为jpeg格式
保存微信文章中的图片为jpeg格式
12 0
关于Apache Log4j2 安全漏洞的说明
关于Apache Log4j2 安全漏洞的说明如下
160 0
《JavaScript设计模式》——第2章 写的都是看到的——面向对象编程 2.1两种编程风格——面向过程与面向对象
面向对象编程就是将你的需求抽象成一个对象,然后针对这个对象分析其特征(属性)与动作(方法)。这个对象我们称之为类。面向对象编程思想其中有一个特点就是封装,就是说把你需要的功能放在一个对象里。比如你大学毕业你来公司携带的行李物品没有一件一件拿过来,而是要将他们放在一个旅行箱里,这样不论携带还是管理都会更方便一些。
1378 0
Node.js编程快餐(1) - 按行读取文本文件
Node.js与其它语言一样,提供了对文本文件按照行来读的功能。不过与Ruby,Python等语言不同,Node.js的File System对象并不提供迭代访问功能,要借用一个独立模块readline来实现这个功能.
3065 0
x3d
[转]所有编程皆为 Web 编程
Web编程还远远没有达到完美的境地。其实,还有点乱!没错,随便会写点代码的人就能三下两下地搞出一个糟糕的Web应用;也确实,99%的Web 应用都似狗屎一堆。但是,这也意味着,相当“聪明”的程序员们正在将他们的成果展现在成百上千(或者成千上万,甚至几百万)的用户面前,而这在互联网盛行 之前是绝无可能的   把软件按照Web应用的形式重整一下,即使软件本身并 不怎么样,这也使得程序员们能够把他们的软件展现在某个地方的某人面前。
627 0
Asp.Net Web API 2第十五课——Model Validation(模型验证)
前言 阅读本文之前,您也可以到Asp.Net Web API 2 系列导航进行查看 http://www.cnblogs.com/aehyok/p/3446289.html 本文参考链接文章地址http://www.asp.net/web-api/overview/formats-and-model-binding/model-validation-in-aspnet-web-api 当客户端发送数据给你的Web API时,你通常希望在做其它处理之前先对数据进行验证。
963 0
python 教程 第十八章、 Web编程
第十八章、 Web编程 import urllib2 LOGIN = 'jin' PASSWD = 'Welcome' URL = 'https://tlv-tools-qc:8443/qcbin/start_a.
875 0
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载