基于VC++6.0与OpenGL的管线碰撞算法设计

　　摘要：由于地下管线种类繁杂、分布区域广并且属性多元, 从而导致管线数据量大而且数据处理比较复杂, 为了提高管线数据的更新检查效率, 设计出了管线碰撞检测的算法, 最后基于Visual C++6.0与Open GL开发环境对算法进行了程序实现。

　　关键词：管线碰撞; 算法设计; Visual C++6.0; OpenGL;

　　1、概述

　　城市地下管线关系到城市的经济发展以及居民的日常生活, 是城市运行的不可或缺的基础设施[1]。地下管线分为排水、给水、工业、燃气、电力、通信管线等几大类, 它们连续地为城市输送着水和能量, 并传递着相关信息, 为人们的日常生活带来了很大的方便, 给城市的快速发展提供了充分有力的保障[2]。随着城市的不断发展, 地下管线也在随之不断地变换, 若现势性能够保证, 就需要随时对管线数据进行更新[3]。由于城市地下管线主要呈现分布区域广、建设年代跨度大、权属多元、线位繁复等特点, 导致管线数据采集困难, 从而不利于管线数据的更新。本文设计出基于Visual C++6.0与Open GL的管线碰撞算法, 极大地提高了管线数据的更新检查效率, 保证了数据的正确性, 使现势性也得到了相应的保障。

　　管线数据通常情况下保存于文本文档中, 为了便于与其他数据区分, 程序设计在打开文件时, 只识别.pip文件。因此在进行数据检查时, 要将文本文件转存为.pip文件。

　　2、国内外研究现状

　　近些年来, 国内外相关学者在管线碰撞检测的领域中做出了一定的成绩, 并且提出了一些有效的算法, 而且开发了相对应的软件包。碰撞检测算法可以分为静态碰撞检测算法和动态碰撞检测算法两大类。静态碰撞检测算法主要是检测静止状态下各物体间是否会发生相互碰撞, 如管线的碰撞检测, 这种算法对于实时性的要求并不高, 而对于精度的要求则比较高。动态碰撞检测算法主要是针对场景物体的相对位置在随着时间不断地变化的情况, 比如机械系统的运动仿真、机械零件的加工过程等[4]。本文阐述的是静态碰撞检测算法现状。

　　Palmer、Hubbard[5]等提出的基于层次包围盒的碰撞检测算法, 这种算法采用了层次结构模型。其原理是以尽量减少需要进行相交测试的对象数目来提高算法的实时性。在碰撞检测领域, 研究得比较多的包围盒方法有以下几种: (1) 沿坐标轴的轴向包围盒; (2) 包围球; (3) 固定方向凸包; (4) 方向包围盒。基于图像空间的碰撞检测算法通常是利用图形的硬件对物体二维图像采样以及相应深度信息来判别两物体之间的相交情况[6]。基于空间分割的碰撞检测算法是将整个的虚拟空间划分为体积相等的规则单元格, 并且将场景中的物体分割为更小的群组, 而且只对占据相同或相邻单元格的几何对象进行相交测试[7]。张着豪[8]等提出的基于矢量积的管线碰撞分析算法, 是通过两条管线的起始点坐标来建立矢量积, 利用矢量积的值进而来判断两条管线是否相交。

　　3、管线碰撞分析算法

　　3.1、构建拓扑

　　拓扑学 (topology) 是研究几何图形或空间在连续改变形状后还能保持不变的一些性质的学科。它只考虑物体间的位置关系而不考虑它们的形状和大小。在拓扑学里, 重要的拓扑性质包括连通性与紧致性[9]。管线数据主要由管线点、线来组成, 构建拓扑的目的主要是分析它们之间的“相连”关系:从一个指定管线点来搜索与之相连的下一个管线点, 搜索到之后, 再由下一个管线点开始搜索跟它相连的管线点, 这样依次来搜索, 直到搜索不到与之相连的管线点为止。

　　3.2、构建格网

　　在对管线数据进行相交分析时, 传统分析方法是将每根管线与所有管线都进行相交分析, 如果管线数据量特别大, 那样分析既费时又费力。为了解决这种问题, 我们可以通过构建格网来提高工作效率。

　　构建格网的目的主要是要统计出经过每个格网的管线索引号, 还要统计出每根管线都经过了哪些格网, 弄清楚这些关系以后, 就可以进行检查了, 这样可以减少好多的重复工作。具体算法原理如下:

　　在之前构建拓扑时, 我们就已经将所要检查的管线数据全部连成了一个虚拟的外包矩形范围, 然后我们再将这个矩形范围整体分割成结构相同、大小相等的好多个单元。再将三维管线投影到二维格网平面上, 那么管线的Z值就为零了, 这样就可以转化成二维平面进行计算了。

　　构建格网时应该注意格网不宜过大也不宜过密。因为格网太大时, 格网内所分布的管线数量就比较多, 这样分析时就相对较慢了;如果格网过密, 计算量就会增大, 这样会出现很多重复的工作。经过多次实验后得出:格网间距设为50m时综合效率最高。具体计算过程以图1为例来进行说明:

图1 格网计算图解

　　假设直线P1、P2是管线AB、CD投影到格网内的两条直线, P1的两端点坐标是 (XA, YA) 、 (XB, YB) , P2的两端点坐标是 (XC, YC) 、 (XD, YD) ;先由它们的端点坐标值分别求出它们的斜率, 再依据斜率判断直线与横轴的正半轴方向夹角。如果直线与横轴正半轴方向的夹角小于等于45°, 则表明该管线在横轴上的分布比较密集, 应以横轴为主来计算它的分布情况, 如图1中的直线P1。如果直线与横轴正半轴方向的夹角大于45°, 则说明该管线在纵轴上分布的比较密集, 就应该以纵轴为主来计算它的分布情况, 如图1中的直线P2。再根据管线坐标所经历的范围和单位格网的间距计算出管线分布的情况。经计算后, 图1中的直线P1分布于 (4) (7) (6) (10) 格网了, 直线P2分布于 (7) 格网了。由此便可以得出与每条管线相交的格网的索引号, 再以格网的单元格为单位来计算出每个格网内与该格网相交的管线的索引号, 然后进行相交分析, 这样就不用去与每根管线都进行相交分析了, 极大地提高了作业效率。

　　格网构建好之后, 对管线数据做了相关分析, 管线数据量的大小几乎对计算机的运行速率不产生影响。该方法可以应用于管线数据的前期检查与后期分析工作中, 效果良好。

　　3.3、管线碰撞分析算法与实现

　　管线碰撞分析主要是检查不同类型的管线在空间上是否存在相交, 并由此来推断实际情况中管线的设计和铺设是否合理。管线的阀门、弯头、三通连接均属于正常连接情况, 排除以上三种情况之外, 再依据格网关系进行相关判断。当两根管线段在平面位置中不处于同一格网时, 则它们在空间上就一定不会相互碰撞;当两根管线段在平面位置中处于同一格网时, 就要对管线段的起终点高程、埋深及管径等数据进行分析, 由分析结果可判断出它们在空间上是否相交。再根据几何方法来计算出两根管线间的最小距离, 将最小距离再与两管径之和进行比较:当最小连接距离小于两管线管径之和时, 则认为两管线发生了相互碰撞。

　　基于几何的管线碰撞检测算法:

　　首先判断出两根管道的中心线位置关系 (共线、相交、平行、异面) 。

　　假设一根管线段的两端点坐标分别是 (x1, y1, z1) 、 (x2, y2, z2) , 另一根管线段的两端点坐标分别是 (x3, y3, z3) 、 (x4, y4, z4) , 则两根管线段的参数方程表示如下:

　　设L为两管线段上的任意两点间距离:

　　将式 (1) 、 (2) 中的X1、Y1、Z1、X2、Y2、Z2分别代入式 (3) 中, 并用X、Y替代t1、t2, 则式 (3) 整理后可得出式 (4)

　　上式中的X、Y均为自变量, a、b、c、d、e、f均为已知数, 因此式 (4) 可表示为式 (5) :

　　(1) 若有无数解时, 则两直线平行;

　　(2) 若仅有唯一解时, 则设极值点坐标为 (X0Y0) , 若Φ (X0, Y0) =0, 则两直线相交;若Φ (X0, Y0) >0, 则两直线相交。实现后的结果如图2所示:

图2 管线碰撞检查结果图

　　4、结论

　　该算法将格网运用于管线三维碰撞检查, 基于Visual C++6.0和Open GL开发环境进行了算法的程序实现, 极大地提高了管线数据的更新检查效率, 使现势性得到了相应的保障。

　　参考文献
　　[1]郝力.城市地理信息系统及应用[M].北京:电子工业出版社, 2002:23-25.
　　[2]区福邦.城市地下管线普查技术研究与应用[M].东南大学出版社, 1999.
　　[3]城市地下管线管理系统建设项目解决方案[EB/OL].Http://gxinfo.com.cn/.
　　[4]肖翔.基于几何的三维地下供水管网碰撞分析[J].华中科技大学, 2008.
　　[5]Hubbard PM.Real-time collision detection and time critical computing.In SIVE95, The First Workshop on Simulationand Interaction in Virtual Environments I, owa City I, owa.Uni-versity of Iowa, informal proceedings, 1995 (1) :92-96.
　　[6]范昭炜.实时碰撞检测技术研究[D].杭州:浙江大学, 2003.
　　[7]霍滨焱.基于图像空间的碰撞检测算法[D].哈尔滨:哈尔滨工程大学, 2005.
　　[8]张着豪, 李隆方, 郑晓丽, 等.基于Arc Engine的城市地下管网碰撞分析研究[J].测绘与空间地理信息, 2012.
　　[9]苏子林, 韩晓玲.基于Map Info的拓扑分析算法设计与实现[J].计算机应用, 2003.