前言
这篇文章是使用游戏引擎探索地图可视化的开篇。传统的地图渲染通常是在iOS/Android/Web平台进行的，为了探究更酷炫的地图展示，会记录基于UE4/Unity进行地图渲染的探索过程。
地图基础元素 - 线
线作为地图渲染的基本元素，在地图中可以代表各种形式的道路。道路数据通常以离散点串形式存储，因此如何将点串绘制成有宽度的线是渲染最关注的问题。本文记录了绘制有宽度的线的方法，并对优化线展示效果的各种线帽和拐角进行了阐述。
绘制有宽度的线
道路数据通常以离散点串和其对应线宽进行存储，为了在游戏引擎中进行显示，就需要将其扩展为有宽度的线。UE4和Unity都可以使用代码生成Mesh进行基本图元的渲染展示（UE4使用Procedural Mesh Component，Unity使用MeshFilter和MeshRenderer），而Mesh渲染的基本单位是三角形，因此问题就转化为如何根据点串和线宽，构造出一组三角形使其能够拼合产生具有宽度的线。
对于只有两个点的直线，通过获取与直线垂直的向量，向两个方向各扩展lineWidth/2长度产生顶点，划分为三角形即可。
![]()
而对于多个离散点构成的线，绘制的时候遇到2个问题：
- 仅使用相邻点计算垂直向量，导致扩充出的线拐角处会有断裂，如下图所示。可以看到，仅仅每个相邻线段进行扩充是不够的，还需要考虑如何处理线的拐角。
![]()
- 考虑处理线的拐角，但获取顶点扩充向量的方向和大小不对，导致绘制的线不等宽。下图根据相隔顶点连线的垂线确定扩充向量，但因向量随顶点位置变化而变化，因此不能作为生成等宽线的依据。
![]()
有了上面的思考，任务就变成了扩充出等宽且有拐角的线：相隔点的顶点位置会变化，但由其确定的向量方向是不变的，因此依靠顶点两侧线段的单位向量，就能确定出唯一的扩充向量。确定扩充方向后，还需要确定扩充向量的大小使得最终的线等宽。
![]()
伪代码如下，扩充方向可由线段单位向量组合确定，需要注意扩充长度并不是lineWidth/2，而是需要根据线段夹角进行计算调整。扩充向量计算好之后，即可根据离散点串生扩充顶点，根据顶点坐标剖分为三角形，构建Mesh进行渲染。
// 计算扩充方向
Vec2f a = (P1 - P0) * normalized()
Vec2f b = (P2 - P1) * normalized()
Vec2f avg = a + b
Vec2f direction = Vec2f(-avg.y, avg.x).normalized() //扩充方向为avg的垂直方向
// 计算扩充长度
float t = Abs(Asin(a × b)) / 2 // 单位向量叉乘获得夹角正弦
float length = lineWidth / 2 / Cos(t) // 根据角度调整扩充长度
绘制线帽LineCap
根据上一节操作已经可以绘制出有宽度的线，但也能够看出线在开头和结尾处都是矩形，不够优雅美观。因此本节主要会解决绘制线帽的问题。
较为常用的LineCap主要有以下三种：
- Butt 无线帽模式，上一节绘制的线默认即为Butt
- Round 在线的两端添加额外的半圆，其半径为lineWidth/2
- Square 在线两端添加额外的矩形，其高度为lineWidth/2
![]()
Square形式的线帽绘制较为简单，只需要在开头和结尾部分根据延伸方向额外添加矩形即可，两个矩形可以很简单的划分为四个三角形，添加在画线mesh中一同渲染。而Round形式的半圆线帽在绘制上就麻烦了许多，在实践过程中主要探索了以下三个方案：
1、使用三角形近似绘制半圆
最直观的方式就是直接绘制半圆线帽，但是渲染的最小单元是三角形，因此只能通过添加多个三角形近似表示半圆。这种方式需要根据添加三角形的个数，进行几何运算确定各个顶点坐标，通过三角形组合成半圆，虽然方法直观可行，但为了使线帽圆滑，额外添加的较多顶点和进行的大量运算都会对性能带来影响，存在性能和效果的取舍。
![]()
2、使用图片近似绘制半圆
第二种方案借助图片可以省去添加额外顶点和进行数学计算的步骤，近似得到半圆线帽。
![]()
图片工具大小为16×16像素，左右两部分分别绘制半圆和矩形。对于半圆部分，内部点透明度设置为1，圆弧上覆盖的像素点，通过调低透明度值弱化锯齿感，圆弧之外部分则将透明度设置为0，整体使用透明度构建出近似的半圆。矩形部分则作为工具，用于填充非线帽部分。
这种方案在构建线Mesh时，与Square线帽方案一致，但需要将纹理uv值也与顶点进行绑定。Square线帽额外添加的矩形绑定图片左侧半圆的uv，而原有线部分绑定右侧矩形uv即可。渲染时，可以在片元着色器中逐像素提取到映射的图片颜色值，输出颜色使用顶点原色，但透明度值采用图片的透明度值，从而将圆弧外侧像素剔除。使用该方案需要开启透明度混合，从而不显示圆弧外侧像素。
这种方案也是半圆的近似表示，在距离较近观察时会出现圆弧线帽发虚，原因是受限于图片大小，如果增加图片大小可以缓解问题，但也会增加开销，也需要做性能和效果的取舍平衡。
3、逐像素绘制半圆
第三种方案由方案二演进而来，不是使用图片剔除像素，而是借助于半圆的特性，在片元着色器中剔除所有不满足条件的像素，做到绘制像素级的半圆线帽。其主要原理是在添加Square线帽后，判断渲染时像素距离线起始顶点距离，若超过lineWidth/2（即红色部分）则剔除像素，从而逐像素绘制出半圆线帽。
![]()
像素剔除会在片元着色器中并行进行，效率高但无法存储上下文信息，而剔除逻辑需要获取圆心信息，同时片元着色器的坐标已经转化为裁剪空间的齐次坐标，无法进行几何运算，因此需要将一些辅助信息传递到片元着色器中进行操作。
辅助信息定义为二维向量geometryInfo，其含义为顶点在线中的相对位置，点串的起点作为(0,0)，终点作为(1,0)，中间的点根据距离转化为[0,1]间的数值。根据扩充向量得到的顶点，则根据扩充方向，向量y值赋值为1或-1。因为已经人为定义了线宽为2的相对坐标系，因此线帽上顶点的辅助信息x值可以转化为-1和2，这样任何小于0和大于1的x值都可以表示该点是线帽部分，而且可以很方便的和(0,0)、(1,0)做距离计算，并与半圆半径1进行比较。
![]()
geometryInfo绑定在每个顶点传入shader后，会在片元着色器中按像素进行线性插值，因此每一个像素都会获得一个可以标识自己局部位置的辅助信息，借助于该信息进行距离判断就可以进行像素剔除，这里展示的是Unity Shader代码，UE4可以在Material中还原逻辑。
fixed4 frag (v2f i) : SV_Target
{
if(i.geometryInfo.x < 0) // 起点侧线帽
{
if(dot(float2(i.geometryInfo.x, i.geometryInfo.y), float2(i.geometryInfo.x, i.geometryInfo.y)) > 1)
{
discard; // 距离圆心距离大于1则剔除
}
}
else if(i.geometryInfo.x > 1) // 终点侧线帽
{
if(dot(float2(i.geometryInfo.x - 1, i.geometryInfo.y), float2(i.geometryInfo.x - 1, i.geometryInfo.y)) > 1)
{
discard;
}
}
return i.color;
}
使用该方案生成的圆角，在近距离观看时因为线帽的渲染像素增多，因此也不会产生虚化或者锯齿感，能够得到圆滑的效果。
![]()
绘制线拐角LineJoin
线帽已经圆润优雅之后，同时也发现绘制的线在一些极端情况下拐角会存在bad case。例如下图所示，对于夹角较小的线会产生非常大的尖角；而对于线段呈直角情况显示的也同样是直角拐角，不够圆润美观。本节主要会解决绘制线拐角的问题。
![]()
较为常用的LineJoin主要有以下三种：
- Miter 尖角样式，上一节绘制的线即属于Miter
- Bevel 切角样式，以横切面替代尖角
- Round 圆角样式，以圆弧替代尖角
![]()
有了扩充线和线帽的绘制经验，从上图可以看出Bevel和Round样式不需要根据线段夹角计算扩充向量。绘制时按照矩形扩展后，Bevel样式只需要根据扩充顶点补齐一个三角形构成切面。而对于Round样式，除了起终点外，每一个顶点扩充处根据矩形方向绘制两个半圆，叠加就能达到圆拐角效果。
![]()
半圆部分的绘制原理和绘制半圆线帽一样，添加矩形再剔除多余像素，因此需要将geometryInfo扩充为四维向量，后两位表示顶点在当前段的相对位置，同样在片元着色器中进行像素剔除。这里片元着色器的代码逻辑与圆角线帽类似，不再赘述。最终的拐角效果如下图。
![]()
整体的绘制流程可以简单总结为下图，等宽线作为线渲染的主体，线帽/拐角作为线渲染的效果优化项。在具体实践中，可以通过设置配置项的方式方便的更改线帽/拐角的样式。
![]()
作者：程序员阿Tu
链接：https://zhuanlan.zhihu.com/p/266026334
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
