从手机地图的演进谈抗锯齿直线渲染技术

传统手机地图主要由以下几类要素构成：面要素（公园、绿地、水系等），线要素（国道、省道、铁路、地铁等）、点要素（兴趣点、maker）。建筑物等。面、点、建筑物的渲染技术相对比较简单，唯独线的渲染一直是地图渲染技术中最难最核心的技术点。下面介绍直线渲染的演进。

1、 栅格地图时代

栅格地图：即通过图片的方式来显示地图。由于早期手机硬件性能的限制，故选择将地图图片的生产放到服务端，客户端只需将图片拼接起来，性能消耗较低。 这种方式客户端就谈不上直线的渲染了。

2、 矢量2D地图时代

进入矢量2D时代，通过将矢量线划数据预处理，直接绘制到计算机屏幕上，相比栅格地图时代：

1)      减少数据流量，矢量表达在更多情况下更紧凑；

2)      更加灵活，使用矢量数据客户端渲染地方式，软件可以有更灵活地策略控制图上所要显示的要素；

3)      支持更快地数据更新，当数据以矢量形式表达后，数据的增删改都和栅格底图解耦了，于是，再也不用为修改一个重要地点信息而要重新渲染一大片的数据而忧愁了，数据运维就舒了长长的一口气。

针对直线的渲染、早期图形学渲染直线算法主要算法包括DDA算法、中点画线法以及Bresenham算法。其中，Bresenham算法最为常见。

Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。仍然假定直线斜率在0~1之间，该方法类似于中点法，由一个误差项符号决定下一个象素点。

算法原理如下：过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列象素中与此交点最近的象素。该算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列的所求象素。

如图所示，设直线方程为yi 1=yi k(xi 1-xi) k。假设列坐标象素已经确定为xi，其行坐标为yi。那么下一个象素的列坐标为xi＋1，而行坐标要么为yi，要么递增1为yi＋1。是否增1取决于误差项d的值。误差项d的初值d0＝0，x坐标每增加1，d的值相应递增直线的斜率值k，即d＝d＋k。一旦  d≥1，就把它减去1，这样保证d在0、1之间。当d≥0.5时，直线与垂线x=xi＋1交点最接近于当前象素(xi，yi)的右上方象素(xi＋1，yi＋1)；而当d<0.5时，更接近于右方象素(xi＋1，yi)。为方便计算，令e＝d－0.5，e的初值为－0.5，增量为k。当e≥0时，取当前象素(xi，yi)的右上方象素(xi＋1，yi＋1)；而当e<0时，取(xi，yi)右方象素(xi＋1，yi)。

对直线、圆及椭圆这些最基本元素的生成速度和显示质量的改进，在图形处理系统中具有重要的应有价值。

但是如果仅仅按照上述算法进行直线渲染，它们生成线条具有明显的“锯齿形”即它们会发生走样现象。

“锯齿”是走样的一种形式。而走样是光栅显示的一种固有性质，产生走样现象的原因是像素本质上的离散性。（因为我是以有限的像素，去逼近包含无限点的直线的）

走样现象包括：

1)          光栅图形产生的阶梯形（锯齿形）

2)          图形中包含相对微小的物体时，这些物体在静态图形中容易被丢弃或忽略（小物体由于走样而消失）

3)          在动画序列中时隐时现，产生闪烁（因为有的时候显示，有的时候不显示）

那么如何降低由于采样不足而产生的走样现象呢？

图形学将用于减少或消除走样效果的技术，称为反走样。由于图形的走样现象对图形的质量有很大影响，几乎所有图形处理系统都要对基本图形进行反走样处理。

反走样技术涉及到某种形式的“模糊”来产生更平滑的图像。

对于在白色背景中的黑色矩形，通过在矩形的边界附近掺入一些灰色像素，可以柔化从黑到白的尖锐变化。从远处观察这幅图像时，人眼能够把这些缓和变化的暗影融合在一起，从而看到了更加平滑的边界。

主要有两种反走样方法：

1)          非加权区域采样方法

算法原理：根据物体的覆盖率计算像素的颜色。（覆盖率：某个像素区域被物体覆盖的比例）。

以此类推，进行计算。因为进行了颜色的灰度处理，产生了渐变的效果，所以锯齿变得平滑。

非加权区域采样方法的两个缺点：

1)          像素的亮度与相交区域的面积成正比，而与相交区域落在像素内的位置无关，这仍然会导致锯齿效应。

2)          直线条上沿理想直线方向的相邻两个像素有时会有较大的灰度差。

因为每个像素的权值是一样的，这是它的主要缺点。因此这个算法也被称为非加权区域采样算法。

2)          加权区域采样方法

非加权区域采样方法没有考虑，亮度不仅取决于所占的面积，还需要取决于这个物体里像素中心的远近。所以介绍加权区域采样方法。

加权区域采样方法：这种方法更适合人视觉系统对图像信息的处理方式，反走样效果更好。

算法原理：将直线段看做是具有一定宽度的狭长矩形。当直线段与像素有相交时，根据相交区域与像素中心的距离来决定其对像素亮度的贡献（比重）。

简单来说：直线段对一个像素亮度的贡献正比于相交区域与像素中心的距离。

计算方法：设置相交区域面积与像素中心距离的权函数（高斯函数）反映相交面积对整个像素亮度的贡献大小，利用权函数积分求相交区域面积，用它乘以像素可设置最大亮度值，即可得到该像素实际显示的亮度值。

上述的计算方法比较复杂，我们可采用离散计算方法。

3、移动互联网手机地图时代

随着计算机图形学的不断发展，应用于移动平台的OpenGL ES应运而生，直线渲染方法的可扩展性越来越强，其中主要包括基于纹理的抗锯齿直线渲染和利用Shader渲染两种方式：

1.           基于纹理的抗锯齿直线渲染：

简单的进行直线的渲染，肯定会出现“锯齿“的现象。因此，预先准备好一个圆形纹理，纹理本身边缘做了alpha渐变，在进行直线渲染的时候，将该纹理绑定，边缘处可以直接利用纹理本身的特性进行抗锯齿。

2.       shader渲染

在OpenGL es 2.0及以后的版本，就从固定管线渲染变化为了流水管线。流水管线允许开发灵活的定制图形渲染过程，其中的桥梁就是shader。

对于线要素，由于线要素存在线宽，因此绘制到地图上可以理解为面状要素的渲染。通过将线要素拆分多个三角形可以实现这一过程。

如图所示，一段线段可以拆分为六个三角形，其中线段两边的两组三角形组成一个渐变的四边形，中间的两个三角形组成一个四边形作为线段的主体部分。渐变的部分可以在线要素在边缘消隐的时候，提供抗锯齿效果。当比例尺变大的时候，这将呈现高品质的绘线效果。

但是，对于每一条线段，生成六个三角形意味着需要八个顶点数据，这需要大量的内存。我尝试每条线段使用两个顶点数据，但是这种方式会导致每条线段渲染的时候需要三次绘制调用。为了保持渲染的质量，我们需要减少每一帧的绘制次数调用。

OpenGL绘制分两个阶段。首先，顶点属性传递到顶点着色器。顶点着色器是一个基本的小函数片段，它能够转换每一个顶点（模型坐标系统）到一个新的顶点（屏幕坐标系统）。有了这样的基础，可以在每一帧渲染的时候进行数据的再利用。

三个连续的顶点数据构成一个三角形。范围内的所有片元都会被片元着色器处理，也称之为像素着色器。当顶点着色器对顶点数据里面所有顶点进行处理后，紧接着，片元着色器会对三角形里面的所有像素进行处理，具体反映的是每个像素的颜色。最简单的情形，像素的颜色会被赋值为一个常量值，像这样。

void main() {

    gl_FragColor = vec4(0, 0, 0, 1);

}

这里的颜色排列是RGBA,在这里例子中，所有的片元都被渲染为不透明的黑色。如果我们渲染的线要素是通过线要素切分的三角形加上在每个三角形上固定的颜色组成的，其结果也会是一堆锯齿线。因此要达到抗锯齿的效果，对于接近边缘的部分，需要降低其Alpha值。在向顶点着色器传递顶点数据的时候，OpenGL允许我们对每个顶点数据进行属性赋值。

这些属性值可以被传递到片元着色器中，有趣的是，每个片元不能直接和单个顶点产生联系，却可以在三个离散值中通过片元到三个顶点的距离进行插值。而这些插值能够在顶点中提供渐变的效果，这个也是线绘制方法的基础。

在地图中绘制线要素，我们有如下几个要求：

1        变化的线宽用户需要来回的放大缩小操作，这就要求我们在每一帧渲染的时候动态更改线宽，但是与此同时不能一次次的拆分线段为三角形。因此，这就意味着最终顶点的位置应该是在渲染的过程中，由顶点着色器去帮忙计算的。

2        端头端尾（butt,round,square）线段绘制开始和结束部分的处理。

3        线段交接处（miter,round,bevel）线段交接处的处理。线切分

由于这里需要做到线宽的动态改变，因此不能在初始阶段就对线进行拆分。这里，我对同一个顶点进行一次拷贝，因此对于一条线段，数组中包含四个顶点数据。

我计算了线段的垂线并且绑定到每个顶点上，第一个顶点绑定正向的单位法向量，第二个顶点绑定负向的单位法向量。单位法向量如图小箭头所示。

在我们的顶点着色器中，通过将顶点的单位法向量乘以线宽，可以在每一帧的绘图调用达到动态更改宽度的效果，最终生成两个三角形，如图红色虚线所示。

顶点着色器代码示例如下：

attribute vec2 a_pos;

attribute vec2 a_normal;

uniform float u_linewidth;

uniform mat4 u_mv_matrix;

uniform mat4 u_p_matrix;

void main() {

    vec4 delta = vec4(a_normal * u_linewidth, 0, 0);

    vec4 pos = u_mv_matrix * vec4(a_pos, 0, 1);

    gl_Position = u_p_matrix * (pos delta);

}

在main函数中，将单位向量乘以线宽可以得到实际线宽。顶点的实际位置（屏幕坐标）则通过模型/视图变换矩阵得到。后面，我增加了额外向量是的线宽独立于模型/视图放缩。最后，通过投影矩阵，得到顶点在投影空间的位置。

现在线段可以通过线宽动态生成，但是我们仍然没有对线段进行抗锯齿。为了达到这种效果，我们需要使用单位向量，但是这次是在片元着色器中体现。在顶点着色器中，我们仅仅是将单位向量传递给了片元着色器。现在，OpenGL在单位向量进行插值，这使得片元着色器接收的向量是渐变的。这也意味着不存在单位向量了，因为它们的长度不足1。当我们计算向量的长度的时候，我们计算的是片元到原始线段的距离，范围在0~1之间。我们可以使用这个距离去计算片元的Alpha值。如果与线宽产生关联，我们可以在线宽去”feather”距离范围内对不同距离的片元赋值不同的Alpha值。在linewidth - feather and linewidth feather 之间，我们对其从0~1进行Alpha赋值，对于比这个距离远的片元，我们Alpha值赋为0。

除去线宽的影响，我们可以单独改变feather的值去得到模糊的线，也可以得到阴影。我们也可以将它设置为0，这样得到的线就是带锯齿的线。

针对线交界处，上面所说的是对单个线段的处理，但是大多数情况下，我们都会遇到多条线段两两连接的情况。当线段连接的时候，我们需要选择一个线连接方案并且如图所示移动顶点数据。

线段交接处的处理往往是直线渲染最为复杂的部分，手机地图要求线段交接处尽量的圆润，保证图幅效果的美观。

对于一条直线的渲染，在端头处通常的做法是进行三角形切割，尽量的进行圆形拟合。但是往往后果是会引入大量三角形面片，造成内存开销。本文做法如图所示，顶点在vao处理时，会记录一个距离坐标点距离的因子z,通过z值来达到圆形交接的效果。具体实施如下：

如图，端头新增4个三角形。其中，对于向外延伸的部分，分为两个对称的三角形1、2，我们认为AB 长度为1，通过线段夹角，可以很容易算出三角形长边的长度，这个长度作为交点C的z值。对于三角形1，在顶点着色器传递到片元着色器中，光栅化处理时，会把面片中的所有片元进行z插值，插值的依据是透视校正，可以认为AC方向z值是一直增大的。因此，利用该特性，我们对alpha进行相应处理，设定一个R值，作为alpha分界线。R取值范围在0-1之间，0-R范围alpha = 1,R-1范围alpha进行插值渐变，从1-0，>1时alpha = 0，通过该处理，端头处虽然是尖锐的三角形面片，实际显示确实抗锯齿的圆角。

4、未来

上文介绍了不同时代直线渲染的方式，随着计算机图形学的不断发展，还会存在更多方式进行地图渲染的展现。就目前手机地图来说，使用图形学的特性还算少之又少，手机地图方面可以做的事情还有很多，如何高效率的进行地图绘制，如何更真实的进行地图展现都将是未来的研究重点。