基于CUDA道路和地形融合算法摘要：将三维可视化技术引入到高速公路的道路设计过程当中能极大提高设计效率，方便优化设计效果。在此过程中涉及到大量的耗时计算，其中最主要的计算为道路和地形融合算法。传统的计算过程因为硬件和软件的限制，计算速度一直受到比较严重的制约。本文利用GPU技术的最新进展，将基于GPU硬件的CUDA编程技术应用到道路与地形融合算法当中，通过将传统算法改造成适合运行在GPU上的并行化算法，极大地提高了图形的融合速度，缩短了用户等待的时间，改善了用户体验。通过比对不同的融合算法，结果显示基于CUDA的道路和地形融合算法在保证结果正确的前提下极大地提高了融合速度。Abstract:Introducingthree-dimensionalvisualizationtechnologyintothedesignprocessofex-presswaycangreatlyimprovethedesignefficiencyandhelpoptimizingthedesigneffect.Thisprocessinvolvesalotoftime-consumingcalculation；themainofwhichisthefusionalgorithmofroadandterrain.Duetothelimitationofhardwareandsoftwareintraditionalcalculatingprocess,thecalculatingspeedhasbeenrestrictedalot.WiththehelpofthelatestdevelopmentofGPUtechnology,thispaperappliesCUDAprogrammingtechniquebasedonGPUhardwareintothefusionalgorithmofroadandterrain・Bytransformingthetraditionalalgorithmintoparallelalgo-rithmwhichissuitableforrunningonGPU,thefusionspeedofdrawingshasbeengreatllyimproved,anduser"swaitingtimeshortenedandthususer"sexperienceim-proved.Throughthecomparisionofdifferentfusionalgo-rithms,theresultshowsthatthefusionalgorithmofroadandterrainbasedonCUDAgreatlyimprovedthefusionspeedonthepremiseofensuringcorrectresuIt.关键词：道路与地形融合算法；CUDA；三维可视化技术；并行化算法Keywords：fusionalgorithmofroadandterrain；CUDA；three-dimensionalvisualizationtechnology；parallelalgorithm中图分类号：TP391.9文献标识码：A文章编号：1006-4311(2013)21-0227-020引言在可视化的道路设计过程中，设计完道路线路及优化完线路以后，还需要将道路和当前的地形进行剪切融合一体化速度的算法，这方国内外都进行了大量的研究，也有很多显示，只有经过融合后的图形显示后才能更加具有真实感。因此提高融合的质量和速度对于整个可视化道路设计过程具有重要的意义［1、2］。道路设计中的融合主要是指道路和地形的融合。在计算机系统中，道路和地形的横切面来看，道路一般用四边形来表示，而以大量的小三角形来表示地形情况。如图1所示。数据的融合问题就是指求出与道路重叠的地形部分并将它们裁剪掉，从而可以直观显示出施工后的道路及道路与地形的匹配情况。由于道路的长度通常从几公里到几百公里甚至更多，相对于道路的横切面的宽度来说，通常要大得多，所以表示地形的小三角形数目通常非常庞大。融合过程很自然成为整个系统中最耗时的过程，如何在保证融合精度的情况下让整个融合过程在尽量少的时间内完成，是道路设计可视化系统的关键问题。从提髙融合速度的算法来看，主要可以在两个方面来进行研究。首先可以研究提高地形三角形和道路四边形的裁剪成熟高效的算法。其次可以根据表示地形的三角形数据相对独立的特点，考虑相关的并行算法，国内外在这方面也有大量的研究，包括多CPU的并行算法和基于GPU的并行算法［3］来进行加速融合过程的研究。本文首先分析了融合的具体情形，然后根据融合的特点，将传统融合算法改造成适合在多核GPU上运行的CUDA程序，从而在保证算法精度的前提下，大大提高了运行的速度，提高了用户的体验水平。1融合剪切情形分析及裁剪算法路基一般采用四边形表示，地形采用三角形表示，因此裁剪需要将地形三角形落在四边形内的部分的裁剪掉，保留四边形外的三角形。对二维空间的裁剪可采用Sutherland-Hodgman［4］或Weiler-Atherton算法［5］实现。以公路数据作为裁剪窗口，采用逐边裁剪法进行裁剪时，可以根据地形三角形和公路四边形的几何位置关系分为四类情形，即：三角形完全位于裁剪窗口的外侧或内...