基于CUDA的道路与地形融合算法

【前言】基于CUDA的道路与地形融合算法由文秘帮小编整理而成，但愿对你的学习工作带来帮助。0 引言 在可视化的道路设计过程中，设计完道路线路及优化完线路以后，还需要将道路和当前的地形进行剪切融合一体化显示，只有经过融合后的图形显示后才能更加具有真实感。因此提高融合的质量和速度对于整个可视化道路设计过程具有重要的意义[1、2]。 道路设计中的融合...

摘要： 将三维可视化技术引入到高速公路的道路设计过程当中能极大提高设计效率，方便优化设计效果。在此过程中涉及到大量的耗时计算，其中最主要的计算为道路和地形融合算法。传统的计算过程因为硬件和软件的限制，计算速度一直受到比较严重的制约。本文利用GPU技术的最新进展，将基于GPU硬件的cuda编程技术应用到道路与地形融合算法当中，通过将传统算法改造成适合运行在GPU上的并行化算法，极大地提高了图形的融合速度，缩短了用户等待的时间，改善了用户体验。通过比对不同的融合算法，结果显示基于CUDA的道路和地形融合算法在保证结果正确的前提下极大地提高了融合速度。

Abstract： Introducing three-dimensional visualization technology into the design process of expressway can greatly improve the design efficiency and help optimizing the design effect. This process involves a lot of time-consuming calculation； the main of which is the fusion algorithm of road and terrain. Due to the limitation of hardware and software in traditional calculating process， the calculating speed has been restricted a lot. With the help of the latest development of GPU technology， this paper applies CUDA programming technique based on GPU hardware into the fusion algorithm of road and terrain. By transforming the traditional algorithm into parallel algorithm which is suitable for running on GPU， the fusion speed of drawings has been greatlly improved， and user's waiting time shortened and thus user's experience improved. Through the comparision of different fusion algorithms， the result shows that the fusion algorithm of road and terrain based on CUDA greatly improved the fusion speed on the premise of ensuring correct result.

关键词： 道路与地形融合算法；CUDA；三维可视化技术；并行化算法

Key words： fusion algorithm of road and terrain；CUDA；three-dimensional visualization technology；parallel algorithm

中图分类号：TP391.9 文献标识码：A 文章编号：1006-4311（2013）21-0227-02

0 引言

在可视化的道路设计过程中，设计完道路线路及优化完线路以后，还需要将道路和当前的地形进行剪切融合一体化显示，只有经过融合后的图形显示后才能更加具有真实感。因此提高融合的质量和速度对于整个可视化道路设计过程具有重要的意义[1、2]。

道路设计中的融合主要是指道路和地形的融合。在计算机系统中，道路和地形的横切面来看，道路一般用四边形来表示，而以大量的小三角形来表示地形情况。如图1所示。数据的融合问题就是指求出与道路重叠的地形部分并将它们裁剪掉，从而可以直观显示出施工后的道路及道路与地形的匹配情况。

由于道路的长度通常从几公里到几百公里甚至更多，相对于道路的横切面的宽度来说，通常要大得多，所以表示地形的小三角形数目通常非常庞大。融合过程很自然成为整个系统中最耗时的过程，如何在保证融合精度的情况下让整个融合过程在尽量少的时间内完成，是道路设计可视化系统的关键问题。

从提高融合速度的算法来看，主要可以在两个方面来进行研究。首先可以研究提高地形三角形和道路四边形的裁剪速度的算法，这方面国内外都进行了大量的研究，也有很多成熟高效的算法。其次可以根据表示地形的三角形数据相对独立的特点，考虑相关的并行算法，国内外在这方面也有大量的研究，包括多CPU的并行算法和基于GPU的并行算法[3]来进行加速融合过程的研究。

本文首先分析了融合的具体情形，然后根据融合的特点，将传统融合算法改造成适合在多核GPU上运行的CUDA程序，从而在保证算法精度的前提下，大大提高了运行的速度，提高了用户的体验水平。

1 融合剪切情形分析及裁剪算法

路基一般采用四边形表示，地形采用三角形表示，因此裁剪需要将地形三角形落在四边形内的部分的裁剪掉，保留四边形外的三角形。对二维空间的裁剪可采用Sutherland-Hodgman[4]或Weiler-Atherton算法[5]实现。以公路数据作为裁剪窗口，采用逐边裁剪法进行裁剪时，可以根据地形三角形和公路四边形的几何位置关系分为四类情形，即：三角形完全位于裁剪窗口的外侧或内侧，三角形与裁剪窗口有两个内交点或外交点，三角形与裁剪窗口有两个交点及三角形与当前裁剪线由交点且一个交点为三角形顶点这四种情形。

将待裁剪三角形列表存放在*tri_candidate，将经裁剪算法判断需要保留下来的三角形列表放在*tri_reservered中。则具体每种情况的剪切算法分析如下：

1.1 三角形完全位于裁剪窗口单侧 三角形完全位于裁剪窗口的单侧时示意图如图2所示。

图2中a、c、d三种场景中三角形需要保留下来，所以只需将三角形放入*tri_reservered列表中保存；b、e、f场景中将三角形放入*tri_candidate列表中，因为三角形可能被裁剪线裁剪。

1.2 三角形与裁剪窗口有两个内交点或外交点 此时情形如图3所示。

图3中a、b两种情形裁剪的情况分别对应图4中a、b。这两种情况拆分后都生成三个三角形，位于裁剪线左侧的三角形都存入列表*tri_reservered中，位于裁剪线右侧的三角形都存入*tri_candidate中。图3中c、d两种情况由于和当前裁剪线没有相交，整个三角形存入*tri_candidate中。

1.3 三角形与裁剪窗口有交点且一个交点为三角形的顶点 此时的情形如图5所示。

对于上图5（a）情形，求出第三边与裁剪边的交点，将原三角形分为裁剪边左边和右边两个三角形，左边三角形存入*tri_reservered，另一边三角形存入*tri_candidate中。其余情形裁剪对三角形的分拆比较简单，如果裁剪边的一个或者两个顶点位于三角形内部，就分别将裁剪边的顶点连接到三角形的另两个顶点，分拆后的三角形如果位于裁剪边的左边，则放入*tri_reservered，其余的三角形列入列表*tri_candidate中。

1.4 三角形与裁剪窗口有两个交点的其它情况 如图6所示，三角形与裁剪边（包括裁剪边延长线）有两个交点的情形有如图6几种情况。

对于图6的各种情形，如果裁剪边顶点位于三角形内部，则连接该顶点与三角形的各个顶点，将原三角形拆分成若干小三角形，如果三角形位于裁剪边的左边则将其存入列表*tri_reservered中，否则放入*tri_candidate列表中。

以图6b为例，正确的拆分方法如图7所示，三角形ade、abd存入*tri_reservered中，三角形ace、cde、bcd存入*tri_candidate列表中。

2 基于CUDA的融合裁剪算法

自从CUDA架构诞生以来，基于GPU的大规模计算得到了广泛的应用。基于CUDA架构的设计将任务分到若干个block上执行，各个block之间相互独立，每个block又分为若干个thread，thread之间并行的执行任务，同一个block之内的thread之间存在较紧密的同步机制。在存储器设计上，也分为全局显存、常量显存、纹理显存、block内共享显存、thread局部显存、thread寄存器等不同的层次。在利用GPU进行大规模计算的时候，将并行计算部分放到设备上运行，利用CPU-GPU的协调工作来完成任务[6]。基于以上CUDA软件架构及存储器特点，block内的并行任务要尽量相同并且有一定的数据关联才能最大限度地利用GPU的计算性能。根据这个要求将路基与地形剪切任务按以下流程进行设计。以上算法的关键在于按照各种情况进行分类，并将相同类的任务尽量放到同一个block内进行并行处理，由于地形数据量极其巨大，所以分类工作能减少half-warp内的分支，从而能提高程序的并行效率。

3 实验结果及讨论

综上所述，本文将地形和道路的融合任务分为两个步骤，首先判断地形和道路的位置关系并依据该位置关系将待处理地形三角形进行分类，然后将具有相同位置关系的三角形分配到同一个block中求交点位置等计算，最后按照本文讨论的拆分策略进行地形三角形拆分到相应的数据结构中。经过大量的实验显示，采用本文介绍的方法能够充分利用CUDA架构的优点，在保证融合精度的同时得到比较满意的融合速度。

参考文献：

[1]朱娟，徐雪林.道路模型与TIN地形无缝融合算法研究[J].微计算机信息，2009，8-3（25）：146-148.

[2]王光霞，刘宁，万刚.虚拟地形环境中道路与地形模型融合算法研究及精度评价[J].测绘学报，2005，11（34）：337-342.

[3]李建明，马淑芳，钱昆明.基于GPU加速的分形地形生成方法[J].2010，4（22）：1075-1078.

[4]Ivan E. Sutherland， Gary W. Hodgman. Reentrant polygon clipping[J].Communications of the ACM.1974，1（17）：32-42.

[5]Kevin Weiler， Peter Atherton. Hidden surface removal using polygon area sorting[J].SIGGRAPH '77 Proceedings of the 4th annual conference on Computer graphics and interactive techniques， 1977：214-222.

[6]Erik Lindholem， John Nickolls， Stuart Oberman， John Montrym， NVIDIA. NVIDIA TESLA： A unified graphics and computing architecture. Micro， IEEE， 2008， 28（2）： 39-55.