一种三维天际线快速提取和显示算法

付仲良 谭均铭

1 武汉大学遥感信息工程学院，湖北武汉，430079

天际线是城市整体景观的体现，反映了城市的文化内涵和经济发展水平。当前多采用图像处理的方法在数码照片中提取天际线，但二维图像无法表达三维真实世界中的复杂实体对象之间的关系，也无法动态获取不同观察角度下的天际线。因此，需要一种能够全方位显示天际线与真实地表环境的空间关系，且能在加载了大数据量城市模型的三维场景中快速提取和显示天际线的算法。

目前，国内外建筑规划领域对天际线的研究主要集中在天际线的评价指标上［1］，而天际线作为特征线提取主要应用在小型飞行器导航避障、地理图像标注等方面［2⁃6］，多采用基于区域的分割分类和边缘检测等图像处理方法。Fang等［7］采用基于亮度梯度的区域增长算法对相机拍摄的城市全景照片的每列像素由上到下检测亮度值，将其与阈值进行比较，从而提取天际线像素点。Saurer等［8］采用支持向量机（support vector machine，SVM）算法对颜色、纹理等特征训练分类器，分割天空和地形。边缘检测方面，Yang等［9］采用Canny滤波边缘检测算法提取画面的拓扑信息，并以山峰最高点和两侧低点为种子点延伸构建天际线。刘松涛等［10］采用形态学滤波和Hough变换等方法来识别海天相接线。在软件方面，吕亚霓［11］使用ArcGIS平台的天际线工具导入三维模型，计算选定视野面上的虚拟阻挡点，并将其连接成线，投影在圆柱上展开成二维平面以展示天际线轮廓。基于图像处理的方法存在云雾等干扰天际线提取的问题，软件获得的只是二维平面上的天际线轮廓，不适用于在真三维场景中实时提取天际线，无法获取最真实城市天际线的视角感官。而在三维天际线的提取方面，虽有一些系统的功能实现，如超图Super Map 3D，但并没有文献对其中的方法进行描述和研究。

针对这些问题，本文从天际线的定义入手，采用视线跟踪算法，在三维场景中从视点引出若干束视线，将其与场景中的建筑物模型相交的第一个点作为天际线点，按顺序连接成线。由于场景中数据量制约了相交检测的速度，采取基于Open MP的中央处理器（central processing unit，CPU）并行策略来加速算法。在动态场景浏览过程中，利用显卡图形处理器（graphics processing unit，GPU）渲染管线中的模板测试动态渲染建筑物与天相接的轮廓线。针对三维场景数据量大、场景实时变换的特性，该算法能充分利用CPU的计算能力提高三维天际线提取的速度，并利用GPU渲染管线，实现天际线流畅渲染。

1 基于OpenMP并行视线跟踪求交算法提取天际线

视线跟踪求交算法通过追踪视点到视线空间内任意一点所经过的路径，检测其与场景中物体的交点。根据天际线的定义，即物体与天相接的轮廓线，利用视线跟踪求交算法提取天际线的主要思想如下：

首先获取当前视角下相机的透视投影矩阵，解算出视锥体远近裁剪面大小，并得到远裁剪面4个角点的投影坐标，通过投影变换的逆变换得到4个角点的世界坐标。然后，以视点到远裁剪平面左上角点为起始方向，视点到远裁剪平面右上角点为水平扫描终止方向，计算水平扫描角，以视点到远裁剪面左下角点为垂直扫描终止方向，计算垂直扫角。最后，在水平方向（X轴）从左至右，垂直方向（Y轴）从上到下的每一个角度采样位置跟踪视线，与场景相交取到的第一个交点即为天际线点，连接成线。

视线跟踪求交算法本身蕴含一定的并行性，其中包含双重嵌套循环，即在X方向扫描循环过程中进行Y方向扫描循环。Open MP是应用在共享内存处理器上的并行编程标准，使用fork⁃join并行机制，主线程遇到定义的并行区域时会创建一组工作线程，在此区域内，多个工作线程可以执行相同的代码块或使用工作共享结构体分担不同的任务，并行区结束，多线程组同步，工作线程终止，主线程继续执行。因此，OpenMP非常适合用来执行循环语句。

并行视线跟踪求交算法具体实现步骤如下：

1）初始化视线空间X轴方向（方位角）和Y轴方向（俯仰角）的步长as和es以控制迭代次数，并声明一个数组vs用于存储天际线点。

2）根据投影相机空间参数解算俯仰角ea和视点到远裁剪面距离（视距）r，远裁剪面左上、右上、左下、右下4个角点A、B、C、D的世界坐标。

3）设置线程数，开启多线程并行计算，由as和直线方程在水平方位依次计算远裁剪面上边的点坐标po和平行的下边点坐标pd。并根据视点e和po、pd三点共圆的约束，以r为半径解算圆方程。并以es为步长在ea上插值得到弧形扫描线上的点坐标集合vp。

4）对于方位步长上每次扫描得到的vp，遍历数组，并引视点到数组中点为视线，与场景中的物体进行相交检测，将相交取得的第一个交点作为天际线点存储到vs中，结束遍历，跳出循环。

5）若计数未超过as，则跳转到步骤3）；若计数超过as，则结束并行，并由主线程将vs中的点按顺序连接成天际线。

双重循环中存在数据依赖，即第二层循环的输入参数vp由第一层循环结果得到。因此，为了保证两个循环由同一线程处理，在最外层循环采用OpenMP制导语句#pragma omp parallel for可以使整个区域代码由同一线程执行。

在线程的调度优化上，使用schedule方法将总循环次数平均分配给每个线程。如分配每个线程处理3个循环，线程0执行i=0、1、2，线程1执行i=3、4、5，依此类推。使用该方法需要注意vs数组中点的顺序问题，可以通过每个线程ID标识每个线程计算得到的vs[ID]数组，在并行块中设置barrier路障，等待所有线程都到达，将数组按顺序合并后才能通过进入下一次多线程的并行计算。并行视线跟踪求交算法提取天际线的程序结构流程图见图1。

图1 利用并行视线跟踪求交算法提取天际线的流程Fig.1 Flow Chart of Skyline Extraction with Parallel Line⁃of⁃Sight Tracking Intersection Algorithm

2 基于GPU渲染管线模板测试实时渲染天际线

在三维场景动态浏览过程中，视点和视线空间随每一帧的变化而变化，若采用视线跟踪求交算法实时提取天际线，CPU计算量激增，超出了多核CPU并行处理的能力，因此需要考虑利用GPU渲染管线。为了充分利用渲染管线的高效处理能力，考虑在光栅化阶段利用GPU对三维天际线进行实时渲染。具体为光栅化阶段中的融合阶段，这一阶段主要负责将像素着色阶段生成的片段颜色与当前存储在颜色缓存中的颜色合并，以及解决可见性问题，通过深度缓存测试渲染离视点更近的图元，并对该位置上的z值和颜色进行更新。而在写入深度缓存前，还可通过模板缓存记录渲染图元位置的离屏缓存，用以控制渲染到颜色缓存和z⁃深度缓存。这种技巧也叫模板测试，可用于三维渲染中物体轮廓线的显示，它完全利用GPU计算，显示效率高，可用于实时渲染三维天际线。具体步骤如下：

1）首先清除模板缓冲区。在第一次绘制时，启用模板测试，正常绘制物体，设置模板测试总能通过，并规定模板测试未通过时，保留模板值。模板测试通过，但深度测试未通过时，保留模板值。模板测试和深度测试都通过时，用参考值1替换模板值。这样就使需要绘制的图元区域，即地面物体的模板值为1，而其他部分，即天空背景模板值为0。

2）设置正面剔除，以线框形式绘制地物图元的背面多边形，并赋予线的宽度和颜色等材质属性，使其略宽于原始物体。

3）绘制步骤2）中放大的物体时，设置模板值不为1时通过模板测试。并规定模板测试未通过时，保留模板值。模板测试通过，但深度测试未通过时，保留模板值。模板测试和深度测试都通过时，用参考值1替换模板值。这样就使模板缓冲区不为1的地方，即天空背景通过模板测试。

两次绘制场景，将第二次以线框形式绘制的三维物体叠加到第一次绘制的原始物体上，通过模板测试剔除模板区域内的线框，保留模板区域0值和1值相交区域的线框，即天空背景和地物相接的线段，达到天际线渲染的效果。

3 实验与分析

本文的三维城市模型数据来源于四川省崇州市城区倾斜摄影模型数据。数据量为22.7 GB，以瓦片形式组织。算法运行平台配置为Core i5 2.4 GHz、8 GB内存、256 GB硬盘；算法运行环境为Win⁃dows10 64位操作系统，Visual Studio2010编译环境，Open Scene Graph三维渲染引擎。

1）实验1：并行视线跟踪求交算法。设置线程数为2，不同循环次数（即水平方向步长×垂直方向步长）下串行算法与并行算法的耗时比较见表1。可以看出，基于Open MP的视线跟踪求交算法能明显提高算法的执行效率，但是由于该算法是简单的循环扫描，循环次数的增大对加速比的影响不大。

表1 不同循环次数下算法运行的时间Tab.1 Time Consumption of Algorithms with Different Number of Cycles

在此基础上，考虑通过提高线程数来加快算法运行的速度。不同线程数下算法运行速度见图2。基于并行计算的算法随着开辟线程数增加，速度有一定的提高。但是随着线程数增多，加速效果也越来越不明显，主要是因为线程之间通信的开销。

图2 不同线程数下算法运行速度Fig.2 Excution Time in Different Number of Processors

通过视线追踪求交算法提取到的三维天际线效果如图3所示。

图3 利用视线跟踪求交算法提取的三维天际线Fig.3 3D Skyline Extracted by Line⁃of⁃Sight Tracking Intersection Algorithm

2）实验2：基于GPU渲染管线模板测试的三维天际线实时渲染。城市模型三维场景中数据量大，若每一帧都通过视线跟踪求交计算天际线，会严重影响系统性能。本文尝试在渲染的最后阶段，利用显卡GPU渲染管线模板测试分离地物和天空，描绘邻接的边界线。由于模板测试属于硬件层的渲染，通过光栅化技术在屏幕上对模型片元着色，节省了大量系统计算和内存空间。

在场景数据量不同的条件下，基于模板测试与基于Open MP并行算法的时间耗时见图4。随着三维场景中数据量增大，片元数增多，占用的内存和CPU增大，导致基于OpenMP的并行算法耗时增加，不适用于在动态场景变化中实时生成天际线。基于GPU模板测试的算法利用了屏幕的缓存技术，在硬件层面对天际线进行显示，耗时随场景数据量增大的变化较小，能在毫秒级别对天际线进行渲染。但是这种算法丢失了天际线的几何属性，只能作为渲染显示，无法提取天际线几何信息。因此，需要结合射线求交算法实现天际线的快速提取和显示。通过街景漫游功能，动态变换场景，实时生成并流畅显示天际线，帧数在54帧/s左右。三维天际线街景动态浏览见图5。

图4 两种算法耗时对比Fig.4 Time Consumption Comparison of the Two Algorithms

图5 三维天际线街景动态浏览Fig.5 Dynamic Browsing of 3D Skyline Street View

4 结束语

源于城市规划对天际线设计和控制的需求，针对当前天际线提取算法多为二维图像处理的方法，且在大数据量城市模型三维场景下计算效率低的问题，本文提出一种采用Open MP并行加速的视线跟踪求交算法，在真三维场景中提取天际线，并在视角动态变化时，通过GPU渲染管线的模板测试显示天际线。实验证明，此算法能快速提取三维天际线的几何结构，并具有良好的显示效果。针对提取出的三维天际线点，需要进一步研究相关拟合简化算法，以平滑天际线，达到更好的显示效果。