AntiAliased反走样技术的一个负面影响

在现代大部分的绘制引擎中,反走样技术都是提高绘制质量的一个有力的手段,因为它可以使得线端的绘制非常的平滑.

下面是一个对比效果图:

但是技术世界总是这样的不完美,使用反走样技术也会带来一些问题,我给出一个实例.

在GIS的几何体绘制中,线串的绘制是很常见的.有很多的线串之间往往是首位相接的,这样在绘制的时候,会产生一些其他的效果,下面是我们的对比效果图:

左边是使用反走样技术的,右边是不使用反走样技术的.左边的线端比较的平滑,右边的有毛刺现象.但是左边的图像在中间有几条不太明显的小细条,这是怎么造成的呢?

通过审查原始的矢量数据我们知道,在小竖条的地方是线串的首位相接点.也就是说,在首位相接的地方出现了小竖条,

我们看一下使用反走样技术图像的一个放大结果:

通过上面的图像我们可以知道,反走样技术本质上就是在渲染图像的时候,使得渲染像素点的颜色值和其周围的颜色值中和,使得反差不至于太大,从而消除毛刺现象.但是这样带来的问题是,在线端首位相接的地方,本来应该黄色的首尾处,由于反走样的中和,颜色已经发生了轻微的变动.这样造成的后果是,在相接处,会出现样色不同的细小的条文.在没有使用反走样技术的地方,就不会出现这种情况.

如果把这些琐碎的小线段合并起来,就会没有这种情况,但是这需要很大的工作量.

或者,我们可以只是在首尾相接处不使用反走样技术,而在其他地方使用反走样技术,但是这样在实现上很难控制,也难以实现.

先记录下来,慢慢寻求解决之道吧.

基于冲突检测的标注算法

问题描述

输入:

N个图层, 每个图层具有M_i个要素. 图层的类型或者是二维的点图层,或者是二维的线图层,或者是二维的面图层.要求在一定的约束条件下,为每个图层的每个要素进行标注,输出地图.

约束条件:

1. 标注之间不能压盖

2. 重要的图层首先进行标注

3. 同一个图层之间, 重要要素首先进行标注

4. 用户可以控制注记之间的疏密程度

5. 在用户的控制下,点要素的矢量符号不可以被标注压盖

输出:

按照用户约束条件的带有矢量符号和标注符号的地图输出

解决方案

对N个图层进行矢量符号的渲染

对N个图层进行标注符号的渲染

Begin

初始化冲突检测对象ConfilictDetector

按照图层的重要性进行排序

FOR EACH 点符号的不可以被压盖的点图层

Begin

      FOR EACH 点图层里面的点要素

      Begin

          取得点要素对应的点符号的大小和位置,构造BOX,添加到冲突检测对象ConfilictDetector

       End

End

FOR EACH 图层

Begin

       按照重要性对图层的要素进行排序

       FOR EACH 图层里面的要素

       Begin

             取得要素标注的候选位置和大小,构造BOX集合(一个对应于单点标注,多个对应于多点标注)

             使用冲突检测对象ConfilictDetector对BOX集合进行冲突检测

             如果有冲突,那么寻找下一个候选位置,重新进行循环

             如果没有冲突,摆放注记,同时按照用户控制疏密的要求,调整BOX的大小,然后把这些BOX添加到突检测对象ConfilictDetector里面

       End

End

End

输出渲染结果

详细解释

1. 点要素的矢量符号不可以被标注压盖

下面是一个比较极端的标注地图,由于没有控制矢量符号被标注压盖,显得比较凌乱(当然标注之间没有压盖)

如果在这种情况下控制注记不要压盖矢量符号,那么效果可能会更好一些.我们目前还没有实现这个功能,因为这样做会带来的问题是:存在只有矢量符号,而没有标注的情况,这在地图上一般是不允许的.

另外,我们可以通过扩大比例尺使得矢量符号之间是界面效果更好一些.从这个角度讲,在这种比例尺下,根本不应该显示标注.

但是增加这个功能,将增加无级比例尺下地图的显示效果

2. 用户可以控制注记之间的疏密程度

注记之间不冲突是地图发布的一个基本要求,但是注记之间如果比较密集,地图显示效果也是不好的.例如下图:

注记密集,是因为一个已经摆放的注记只是要求这个注记所占的范围不允许再放其他的注记.如下图所示,最左边的两个”四环”,每个汉字使用红色的矩形框标志其外包矩形,在我们进行冲突检测的时候,我们只是把这四个外包加入了冲突检测集;虽然注记之间不再冲突,但是注记密集,效果也不是很好.

假定最左边的”四环”是首先标注的,如果我们把这两个外包进行一定的修正,然后再放入冲突检测集,那么我们可以控制第二个四环就不会出现.如下图:

由于第一个”四环”添加到冲突检测集的外包进行了放大,第二个”四环”再进行冲突检测的时候,已经不满足要求,所以不会出现.

可能存在的问题

1. 注记和矢量符号之间不能压盖

我们现在只是控制注记不能压盖点的矢量符号,并没有控制点注记对线符号的压盖,或者点注记对面符号的压盖等.

2. 注记的分行

我们现在还没有考虑注记的分行,但是这个并不是一个实质性的困难.

结论

冲突检测在我们这个算法体系中占有重要的位置,所以我们说这是一个”基于冲突检测的注记算法”.

Gdiplus的AdjustableArrowCap实现SIC的StrokeArrowStyle

相对于Qt的绘制引擎,Gdiplus的功能要更丰富一些.比如我使用Qt的引擎绘制箭头风格,这要我自己计算位置,然后使用路径填充实现.Gdiplus提供了AdjustableArrowCap类,使得实现StrokeArrowStyle比较的方便,我只需要计算沿线的位置,剩下的绘制工作交给Gdiplus即可.

AdjustableArrowCap提供了Height和Width两个属性来控制箭头的大小,并且通过WidthScale来控制和画笔宽度的比例关系,这个默认的关系是1.0.

下面是测试代码:

    AdjustableArrowCap myArrow(8, 8, true);
    Pen arrowPen(Color(255, 0, 0, 0),1);
    arrowPen.SetCustomEndCap(&myArrow);
    graphics.DrawLine(&arrowPen, Point(0, 100), Point(400, 100));
    arrowPen.SetWidth(2);
    graphics.DrawLine(&arrowPen, Point(0, 200), Point(400, 200));
    arrowPen.SetWidth(4);
    graphics.DrawLine(&arrowPen, Point(0, 300), Point(400, 300));
    arrowPen.SetWidth(8);
    graphics.DrawLine(&arrowPen, Point(0, 400), Point(400, 400));
    myArrow.SetWidthScale(2);
    arrowPen.SetCustomStartCap(&myArrow);
    graphics.DrawLine(&arrowPen, Point(0, 500), Point(400, 500));

下面是效果图:

我们看到箭头的大小随着画笔的宽度而变化,下面是统计数据.

箭头初始大小	线宽大小	箭头大小
8	1	16
8	2	16
8	4	32
8	8	64

 

那么问题是:

1) 为什么线宽是1的时候,箭头的大小不是初始大小8,而是16?

2) 线宽大小和箭头大小并没有完全的呈现比例关系,在1的时候出现了例外,为什么?

3)在所有的这些情况下,AdjustableArrowCap的WidthScale属性都是1,但是箭头大小并不是固定的,而是随着线宽的变化而变化,这样WidthScale是不是没有必要存在?

这些问题我还没有找到答案,暂时放在这里吧.

线符号的箭头风格的定义

但我们绘制直线的时候,我们有的时候需要定义线符号的箭头风格.例如google地图.

线符号的箭头风格不同于GDI画笔要素的线帽LineCap.我们看看LineCap的定义:

1)定义线端(包括线尾和线头)的形状

2)一般的有Flat,Round,Sqaure等

线符号的箭头风格,包含的要素有

1)箭头大小

2)起始间隔长度,重复箭头长度,重复间隔长度,结束间隔长度

3)箭头风格,例如,实心还是线头等

4) 是否绘制起始箭头(hasHead),是否绘制终止箭头(hasTail),箭头是否必须直线绘制(isStraight)

定义如下:

class StrokeArrowStyle: public DisplayObject{
    public:
        virtual ~StrokeArrowStyle(){}
        virtual real_t getInitialGap() const = 0;
        virtual real_t getFinalGap() const = 0;
        virtual real_t getRepeatedGap() const = 0;
        virtual real_t getLength() const = 0;
        virtual real_t getArrowSize() const = 0;
        virtual bool hasHead() const = 0;
        virtual bool hasTail() const = 0;
        virtual bool isStraight() const = 0;
        virtual int getStyle() const = 0;
        virtual void setInitialGap(real_t igap) = 0;
        virtual void setFinalGap(real_t fgap) = 0;
        virtual void setRepeatedGap(real_t gap) = 0;
        virtual void setLength(real_t length) = 0;
        virtual void setArrowSize(real_t size) = 0;
        virtual void setHead(bool has) = 0;
        virtual void setTail(bool has) = 0;
        virtual void setStraight(bool straight) = 0;
        virtual void setStyle(int style) = 0;
        virtual StrokeArrowStyle* clone() const = 0;
    };

每个参数的含义和上面的图表相一致,至于style,则是我们的一个扩充的手段,目前只支持实心和空心箭头两种.

另外,我们看到大多数的地图的箭头风格都不会标志在线端的拐弯处,所以我们的实现算法就是尽量的避让拐弯的地方.当然,这样的避让会导致在极端的情况下,线符号不能够绘制,但是在这种情况下,本身也确实不需要绘制.

windows GDI 资源的限制

GDI资源是一种很重要的资源,windows在每个线程内部都会限制GDI资源的使用.一般来说,windows对GDI资源的限制在每个线程内部是10000,一旦超过这个限制,那么就会出现错误的结果.

在使用Qt和windows相互调用的时候,::GetDC(NULL)返回值竟然是NULL,也就是说,我得不到整个显示器的GDI资源,这是不可思议的;而::GetLastError()返回的值也是0,这使得我的调试也无法进行.

后来我搜索了一下,才发现了"windows对GDI资源的限制在每个线程内部是10000"这个事实.于是我打开任务管理器,并且选择显示列GDI资源,发现我的程序的GDI资源在没有任何输入的情况下,GDI的资源自动的增长,知道到达10000这个临界值,并且出现assert失败的情况;而程序的停止点就是::GetDC(NULL).

至于我的程序为什么会出现GDI资源不断增长的情况,是因为我在一个定时器的程序中调用了像素到毫米的转换函数,而这个函数调用了GetDevCaps函数,传入的HDC是通过::GetDC(NULL)得到的,但是我忘记了通过::ReleaseDC(NULL,dc)释放这个资源.这样,由于定时器的作用,导致资源不断的生长,直至程序崩溃.

C++终于去掉了无用的负担

在herb suter的blog中,2010-3-8至2010-3-13在美国匹斯堡举行的C++标准委员会做出了两个决定:

1)删除"Export Template"特性.

注意是删除而不是压制.也就是说,C++根本就是不打算再支持"Export Template"特性了,以后也不会支持.

大快人心,早该做这个决定了!

我记得有些专家还通过某些宏技巧,来延迟对"Export Template"特性的支持,使得代码看上去非常的吃力(一旦和宏关联起来,总是这个样子);现在终于可以理直气壮的要求库代码干净一些了.

C++模板的特性使得接口和接口放在一起,这虽然不符合工程上的某些需要;但是C++的面板特性本来就不是针对工程需求,它是针对成熟的函数库,模板库的.如果要在某个领域(比如GIS),抽象接口,然后使用模板技术实现,则既不符合C++模板特性的要求,也不符合工程的要求.这再次证明了即是一项技术非常的优秀,但是也不是放之四海而皆准的.所谓的具体问题具体分析,又让我们回到了哲学的命题上.

而且,对于成熟的函数库和容器库而言,暴露其内部的实现,这对于代码者而言,是一种巨大的学习资源,符合开源的精神.

2)压制"异常规范",增加关键字noexcept

异常规范本来就是名存实亡的东西,委员会保守起见才压制,我想说不定下一次就会删除这个特性了.

只是增加"noexcept",让我非常的看不懂.委员会在增加关键字上向来是非常慎重的,这次不知道为什么这么鲁莽.

总体而言,herb suter对这次会议的评价非常高,甚至和C++98标准相提并论.看来我们真的可以期待C++11了.

BY:C相应的标准C1x也要在2012年左右诞生.

缓存对程序的影响

从sutter的bolg得到另外一个大牛igor的blog,语言非常的明白.读了以后总结一下:

1. 内存访问对性能的影响.作者例子是一个16倍的循环和一个单一的循环的性能相差无几,主要说明对性能影响的决定因素是内存访问.
2. 缓存大小(cache line)对性能的影响.缓存一般是64byte,这个数值直接的影响了循环的步长
3. 缓存的级别和大小.一般有两级缓存,分成数据和指令缓存.
4. 指令并行.独立指令的执行回是的程序更好的利用多核
5. 缓存关联.缓存和内存之间的映射方式也影响程序的性能
6. 缓存的虚假共享.因为并行,是的数据的共享控制更加的困难,共享缓存也变得难以控制
7. 硬件复杂性.硬件的优化策略是不同的,这使得有的程序性能很难预测和解释.

这里的例子是和硬件直接的相关的,这使得在高层的应用优化的参考价值不大.例如,以字节为单位的文件读写可以把缓存控制1024字节,因为这样可以和内存页大小结合起来.但是对于我们基于要素的图层缓存就很难配置,因为要素本身的大小是变化的(不像文件以字节为单位).我想这里的优化应该是和要素的平均大小结合起来设计图层的缓存.

我看过很多的文章都说,对程序不要过早的优化,原因之一是程序员的预测一般不一定是准确的,这当然也和硬件本身的复杂性有关;另外一个也就是缓存大小的最优配置也需要在实践中摸索.

最好的方式提供默认值,并且允许用户动态修改.

使用GDIPLUS的MeatureString得到字符串的外包

我们使用Gdiplus实现display插件的时候,需要根据字符串的内容预先得到其外包,用于背景绘制或者冲突检测;Gdiplus提供了MeatureString函数,基于此函数可以得到字符串的外包.

在没有实现TextBackground接口以前,我一直没有发现这个函数的问题.现在使用这个函数,我发现得到的外包总是比预想的要大一些.这样实现TextBackground,相对于Qt的实现,背景总会大一些.

搜索了一下,得到如下的解释:Gdiplus使用文本反走样和文本提示等技术,得到的外包总比实际的要大一些.作者也提供了两种方法得到比较合适的外包.

我对上面的两个方法都不是很满意,我可以使用GDI的方法GetTextExtentPoint32得到外包,这个外包经过我的测试是比较合适的.

但是后来我又发现,使用这个外包在Gdiplus线控制文本的输出,有的时候字符串会被截断,这说明这个外包小了.我使用格式化的参数控制不要截断外包,但是在某些特殊的情况下,字符串的输出会有一些重叠,虽然重叠量很小.

这可真是两难呀!

最后我的做法是:

1) 在需要背景绘制的时候,我使用Gdi的方法得到外包,因为这个时候得到的外包一般会增大一些(TextBackground::getExtraSpacing),这正好可以弥补Gdi得到的外包较小的缺陷

2)在其他的时候,使用Gdiplus的方法.

希望以后微软升级这个东西,我就不要做这样的workaround了.

文本符号的背景设计

我们的符号设计基本上满足一定的要求了,从功能行看,还缺少文本背景的设计和箭头符号的设计;这里我们说明文本背景的设计.

我们先看一个google的实例.

文本背景和文本的halo效果是不同的,但是一般的情况下二者不会共存;因为他们的目的都是为了增加文本的可读性.使用一种技术即可达到文本可读性增强的目的.

如果我们从一般的角度描述文本背景,那么有哪些控制参数呢?

1. 背景填充Fill,一般是某种颜色的填充
2. 背景轮廓线的形状shape
3. 绘制背景轮廓线形状的Stroke,可以按照Stroke的方式定义
4. 间隔extraSpacing,这跟文本格式化的参数一样,严格来说有上下左右四个参数,但是我们也可以使用一个参数简化

如果我们考虑更加复杂的情况,例如背景由几个形状组成(可以定义为一个multipolygon),每个部分使用不同的填充和绘制模式.这虽然全面,但是也并不实用.

这四个参数构成了TextBackground的接口,用于控制文本背景.Fill,Stroke和extraSpacing都比较容易理解和定义,shape如何定义?

我们常见的形状有矩形,圆角矩形和椭圆形(我还见到美国地图的花形等),定义个Geometry描述这个形状显得过于复杂,在这里我觉得使用一个枚举型就可以了,把常见的形状枚举出来,例如矩形,圆角矩形和椭圆形等.

当然以后还会有其他的形状,并且还可能是多部分的,我们可以统一的枚举在这个变量里面.从这个意义上,它不是一个形状,而是一种风格,所以我们的接口也定义为Style.

总结如下:

1) Fill* getFill()

2)Stroke* getStroke()

3)double getExtraSpacing()

4) int getStyle()

我们可以和ArcGIS对比一下关于文本背景的设计.

ArcGIS的设计非常的灵活,其形状基本上可以定义为一个具体的Geometry,也可以是存储在字体文件中的一个预定义的形状,并且符号之间可以相互嵌套.这样在灵活性上它就几乎达到了极致.但是其代价就是复杂性,这对序列化和使用都带来了不方便.

我觉得我们的设计是在复杂性和灵活性上去的了一个折中.

这样的设计对我们先前的实现有什么影响呢?

最大的一个影响就是关于文本区域的大小.原来进行冲突检测,只要取得文本本身的大小即可;现在还有考虑背景的大小.不过这并不困难.

异步调用的模式

今天读了sutter的文章 Prefer Futures to Baked-In “Async APIs”, 下面是一些体会.

多线程编程是复杂的,保证正确的使用多线程,应该在使用模式上寻找突破.也就是说,我们应该枚举一些经过实践证明的,易用的异步调用模式.

以前我就有一些这样的感觉,不过总是模糊的,经验性的.sutter一直在做这方面的工作,他在这篇文章中对比了微软现在使用的BeginXXX/EndXXX的模式和新型的Future模式.

BeginXXX/EndXXX模式的主要缺点:

1. 对API设计者而言,这是侵入式的方法,破坏了原来API的简洁性. 一个API分成3个,复杂性随之而来
2. 对API的使用者而言,必须要按照固定的次序调用,Begin,Wait,End;否则,轻者资源泄漏,重者程序崩溃
3. 增加形式上的复杂性.因为有的用户并不需要等待,只要执行完毕即可
4. 这种方法没有给予用户机会如何进行异步调用,比如是否使用线程池等

当然,使用Future模式就好多了,在和lambda结合以后,在形式上会更加的简洁.

看完以后,我的疑问是,微软为什么留着Future不同,而提供了BeginXXX/EndXXX这种蹩脚的模式呢?继而哑然而笑,当然是因为微软当时还没有足够的技术积累使用Future模式了,下一个版本就要提供了,这当然是出于市场的需要.

Future模式的出现,表明在操作系统底层,编程语言设计层面的工作已经比较完善(我们不在需要复杂的直接用thread的了);在应用层面的工作就是按照所谓的数据流,任务流模式分解,然后使用这些工具(Future).

另外给我的提示是(和我原来的感觉一样):在API设计层面上不要过多的考虑多线程调用,就像早期的单线程API一样设计.在多线程环境下使用是调用者的事情.