基于几何的三维地下供水管网碰撞分析 50页

'华中科技大学硕士学位论文[12]多数应用的需求，目前仍是碰撞检测算法研究的重点和热点。此外，通过采用自[13][14]适应步长技术等可以在一定程度上减少离散碰撞检测算法的不足。[6]连续碰撞检测算法的研究一般涉及到四维时空问题或结构空间精确的建模。这类算法能较好地解决离散碰撞检测算法存在的问题，但通常计算速度较慢，需要作进一步的研究才能适用于大规模场景中的实时碰撞检测。研究人员在实时碰撞检测方面展开了一系列研究，取得了一些成果。目前，大部分实时性好的碰撞检测算法都属于离散碰撞检测算法。纵观这些算法，大致可分为基于图形和基于图像的碰撞检测算法。这两类算法的主要区别在于是利用物体三维几何特性进行求交计算，还是利用物体二维的图像及深度信息来进行相交分析。其中在基于图形的碰撞检测上，[15]研究人员已经做了大量的工作，形成了层次包围盒法和空间分割法等成熟算法[16][17]。基于图像的碰撞检测算法能有效利用图形硬件的绘制加速功能来提高碰撞检测算法的效率，特别是近几年图形硬件技术的飞速发展，图形硬件在性能不断提高的同时还具备了可编程的功能，使得基于图像的碰撞检测算法进入了一个新的发展[18]阶段。2.2主要的碰撞检测算法2.2.1基于四维空间交集测试的碰撞检测[4]四维空间交集测试是碰撞检测最原始也是最精确的算法。假设三维空间中有n个运动模型，随着时间改变位置和姿态，通俗地讲碰撞检测就是判断模型之间是否发生了碰撞。设三维几何空间为R，用三维几何坐标系统F表w示，在F中用F表示模型A所占的集合，显然F是F的子集、那么F随着时间的wAAww变化构成了一个四维空间坐标系统C，模型A沿着一定轨迹运动，就形成了C的子ww集表示为C。碰撞检测就判断CCIII...C≠Φ是否成立。给出一个二维碰撞检A12m测的例子，如图2-1，其中（a）是两个二维模型A、A及其运行轨迹；（b）和（c）125 华中科技大学硕士学位论文表示C、C；（d）表示C、C的交集。1212图2-1二维模型的移动构成三维集合这种方法在理论上给出了碰撞检测的精确方法，但是它的实现代价非常高，其中的瓶颈问题就是四维集合C的计算。这种计算的复杂度在实际中是不能接受的，所A以必须采用一些折中的方法，即牺牲计算的精度，提高计算的速度。2.2.2基于图形的碰撞检测算法基于图形的实时碰撞检测算法主要分为层次包围盒法(hierarchicalbounding[19]bolumes)和空间分割法(spacedecomposition)两类。这两类算法都使用了层次结构模型。其目标都是尽可能地减少需进行相交测试的几何对象的数目以提高算法的实时性。空间分割法由于存储量大、灵活性差，通常适用于稀疏环境中分布比较均匀的几何对象间的碰撞检测；层次包围盒法则应用得更为广泛，适用于复杂环境中的碰撞检测。6 华中科技大学硕士学位论文2.2.2.1基于层次包围盒的碰撞检测碰撞检测领域中研究最多的包围盒主要有：包围球(Sphere)、沿坐标轴的轴向包围盒(AABBAxis-AlignedBoundingBoxes)、方向包围盒(OBBOrientedBoundingBox)、固定方向凸包(FDHFixedDirectionHull或K-DopsDiscreteOrientationPolytope)等。下面分别简单介绍一下它们在碰撞检测中的应用。并对应于每一类的包围盒的代表性算法进行介绍描述。图2-2几种典型包围盒的构造方式1、包围球(Sphere)一个给定对象的包围球（Sphere）被定义为包含该对象的最小球体。球是相当简单的几何体，只需要圆心和半径就可以完全表示出一个球体。计算一个给定对象的包围球体，首先需要分别计算基本几何元素集合中所有元素的顶点的x坐标、y坐标和z坐标的平均值以确定包围球的球心O，再由球心与三个最大值坐标所确定的点间的距离计算半径r。包围球可表示为：2222R=−{(,,)|(xyzxC)+(yC−)+(zC−)max(,x)1234（4）min(,yyy)>max(,y)1234四个条件其中之一，那么矩形必不相交。3.2基于几何的碰撞分析在地下供水管网工程的管道设计中,容易出现管道在空间碰撞(两管道的管体一部分重叠,或管道外表面的净间距小于设计要求)。管道碰撞人工检查工作量大，且难以保证没有遗漏。因此，有必要利用先进的计算机管理和设计技术来解决供水管网的碰撞问题。由于管道的空间形状比较单一，可将管道视为三维圆柱体，采用图形学中三维实[42][43]体的碰撞检测算法。根据三维管道设计的具体特点和工程需要，实际的管道碰撞分为两种情况：（1）实际的物理碰撞；（2）管道净空距离过小的情况。例如某些管道净空要求如表3-1所示：20 华中科技大学硕士学位论文表3-1管道最小净距净距类别保温管道不保温管道两根平行布置管道的净距/mm>150>200空间交叉的两管道的净距/mm>100>150但是，考虑到实际工程的具体情况，本论文中的算法暂不考虑管道净空距离过小的情况，仅考虑实际管道的物理碰撞。将管道简化为附带有管径信息的空间线段(管道的中心线)，问题从而转化为求两空间线段的最小连线长度(在两线段上各任取一点，由此，可以形成一个连线长度的集合，该集合中的最小值即为最小连线长度)。由于，碰撞检测程序必须区分两管道是正常的通过，还是发生碰撞，因此，使用了基于几何的判断方法。首先，判断两管道中心线的位置关系(共线、平行、相交、异面)，根据不同的情形，再判断其进一步的位置关系，计算两线段的最小连线长度L，并与设计所要求的两管道半径（两半径分别R和R）之和进行比较。当LRR<+时,即认为发生了碰撞。12123.2.1碰撞检测算法[44]两空间线段的位置关系有共线、平行、相交和异面几种情况。在不同情况下判断两线段的位置关系，从而得出管道是否碰撞的结论。不同的情况下，碰撞分析的情况不同，主要分三类讨论，总的流程如图3-2所示：图3-2碰撞分析总流程图21 华中科技大学硕士学位论文1、两线段所在的直线相交（1）交点均在两线段内部，此时两线段相交，管道发生碰撞。即两水平管道，空间交叉，但标高（z坐标）相同，于是两管道发生碰撞。（2）交点至少在一条线段的延长线上，计算两线段端点连线长度(两两相连，共4个)，并分别从一线段的端点到另一线段作垂线(共4个)，若垂足在另一线段内，则计算垂距，找出这些端点连线长度和所得垂距中的最小者L，若L小于管道半minmin径之和，则发生碰撞。a.垂线段最小b.端点连线最小图3-3交点至少在一条线段的延长线上如图3-3中两个图形为例，在图a中，AB与CD是要进行碰撞检测的管道。中垂线段DE尽管小于BF，但E在AB的延长线上，不符合要求，BF代表了两管道的最小距离；而在图b中BE、DF不符合要求，CH长于DB，DB代表了两管道的最小间距。算法流程如图3-4：22 华中科技大学硕士学位论文图3-4两线段所在直线相交算法流程图2、两线段平行或共线(1)两线段共线，其中，如果一条线段的任一端点在另一线段上，则判定这两条管段发生碰撞；反之，则不是碰撞。(2)两线段平行：①如果有一条线段的端点到另一线段的垂足在另一线段内或端点上，则计算两平行线段的间距L，若该间距小于两管道半径之和，即LRR<+，则发生碰撞。这通12常发生在两并排布置的管道，间距不符合设计要求。②如果垂足均在线段外，则计算两两端点距离的最小者L，看L是否小于两minmin管线半径之和，若LRR<+，则发生碰撞；反之，则未发生碰撞。12算法流程如图3-5：23 华中科技大学硕士学位论文图3-5两线段平行或共线算法流程图3、两线段异面两管道异面的情况是现实中安装管道过程中出现得最多最频繁的情况，是一个一般性的情况，所以必需着重考虑。两线段异面的处理与两线段相交类似。直线相交可以看作两直线异面的特例，沿公垂线拉近两异面直线，当公垂线段长度为0时，异面直线就变为相交。首先，计算两直线的公垂线段的长度，若长度大于要求值，即LRR>+，则肯12定不会发生碰撞，否则要进行以下分析：（1）公垂线段的两垂足均在两线段内部，则发生碰撞。这通常发生在两水平管道空间交叉，但其标高差小，使得两管道“打架”，或交叉处的净距不满足设计规范要求。也可能是一段水平管道旁。有一竖直管道通过，尽管图纸上两单线表示的管道有一些距离，但实际管道已经碰撞。24 华中科技大学硕士学位论文（2）两垂足至少有一个在一条线段的外部，计算两线段的两两端点连线长度(共4个)；并分别从一线段的一端点到另一线段作垂线(共4个)，若垂足在另一线段内，计算垂距；找出这些端点连线长度和所得垂距中的最小者，若小于管道两半径之和，则管道发生碰撞；反之，则未发生碰撞。其计算方式和两直线相交的情况相同，两直线相交可以看作两异面直线距离为零的特殊情况。算法流程如图3-6所示：两线段异面计算两直线的公垂线段的长度L公垂线段的两垂足至少有两垂足均在否L>R1+R2否一个在一条线两线段内部段的外部计算8个距离是得到距离最小者L发生碰撞未发生碰撞否L。三向量不共面，如图3-10所示图3-10三向量不共面rrrπrrrr当a，b，c构成右手系时，0≤θ<，hc=*cosθ，因此()*abcShV×⋅==。2rrrπrr当a，b，c构成左手系时，≤θ<π，hc=−*cos(πθθ)=−c*cos，因此，2rrr()abcShV×⋅=−*=−。3.3.2基于混合积的线段位置判定准则[50]设有两线段PP，QQ，如图3-11所示：121232 华中科技大学硕士学位论文图3-11混合积的判定准则PZ，QZ垂直PP，QQ所在平面。若(,,)0PPPQPZ≥成右手系，且111121212111(,,)0PPPQPZ≤成左手系；或者(,,)0PPPQPZ≤成左手系，且(,,)0PPPQPZ≥121211211112121成右手系，则可判定点P，P在线段QQ两侧。同理，若(,,)0QQQPQZ≥成右手1212121111系，且(,,)0QQQPQZ≤成左手系；或者(,,)0QQQPQZ≤成左手系，且121211121111(,,)0QQQPQZ≥成右手系，则可判定Q，Q在线段PP两侧。1212111212图3-12平面内任意线段所以，线段PP，QQ相交的判定条件，即充分必要条件是：1212⎧Δ≤:(PPPQPZPPPQPZ,,)(,,)011211112121⎨(3-22)⎩Δ≤:(QQQPQZQQQPQZ,,)(,,)0212111112121133 华中科技大学硕士学位论文要特别注意的是：当Δ=0或Δ=0，或两者都为0时，包含了线段顶点重合、12线段重合、顶点在线段上3种情况。下面化简判定条件，由混合积计算公式aaaxyz(,,)abc=bbb(3-23)xyzcccxyz取PZ，QZ为单位向量(0,0,1)，其他向量的第3维分量全部为0。111则有Δ=()PP⋅PQ−PP⋅PQ()PP⋅PP−PP⋅PP≤0(3-24)1121XYYXXYYX1121112121212Δ=()QQ⋅QP−QQ⋅QP()QQ⋅QP−QQ⋅QQ≤0(3-25)2121XY1121YX1121XY2121YX2将相应的点坐标代入判断即可。算法流程图如图3-13所示：输入线段P1P2，Q1Q2的坐标计算Δ1，Δ2的值Δ1≤0，且Δ1，Δ2有且仅有一Δ1，Δ2至少有Δ1=0，且Δ2=0Δ2≤0个为0一个大于0两线段一般性一线段的顶点两线段重合相交在另一线段上两线段相交两线段不相交图3-13混合积判断线段相交算法流程34 华中科技大学硕士学位论文4地下供水管网碰撞分析系统及其实现4.1系统框架在理论分析的基础上，本论文对地下供水管网碰撞分析进行了系统具体实现。[51][52]本碰撞分析系统是在“武汉市水务集团地下供水管线三维显示系统”（以下简称“三维显示系统”）的基础上进行开发和设计。三维显示系统在已开发的GIS系统提供的管网地理数据的基础上，对武汉市地下管网系统的重要节点进行三维重建和图形显示，以利于用户对地下管网系统有更加逼真，直观的认识和理解，便于今后的管网设计、改造和维护。系统建立了独立的数据库，数据库中的数据与GIS系统的数据库有联系但不完全依赖于GIS系统的数据库。软件系统的数据库从GIS系统导出的文本格式的交换文件(SQD文件)中获取所需的部分数据。三维显示系统的数据库从SQD文件中获取图形数据和部分属性数据，运用图形数据显示二维平面图形和三维空间图形，运用属性数据确定管线和设备的三维特性。本碰撞分析的架构完全基于三维显示系统，其用于进行碰撞分析的数据也完全来源于三维显示系统中真实的地形数据，这样使得碰撞分析后的结果更加真实和精确。整个系统的结构如图4-1所示：35 华中科技大学硕士学位论文GIS据库二维系统数SQDDXF文件系统数据库图4-1系统结构图首先在GIS系统客户端上从GIS数据库中获取一块管网区域的SQD文件，将此SQD文件放到本系统客户端。在系统客户端上传SQD文件到预处理服务器，由预处理服务器将SQD文件中的图形数据和属性数据导入本数据库。SQD文件中的数据导入到本数据库中后，在本系统客户端就可以利用现有数据进行三维显示、二维显示、设备属性显示和碰撞分析等功能。在进行碰撞分析时，需要将新增的管线数据通过DXF文件的方式导入到数据库中，其导入方法和流程与SQD导入过程一样。4.2主要模块介绍本系统的主要模块包括：碰撞分析模块、三维显示模块、网络传输模块和文件解析模块。其它一些次要模块还包括：数据库管理模块、数据封装模块、二维显示模块、多线程处理模块、缓冲区处理模块和用户权限管理模块等等。模块关系图如图4-2所示：36 华中科技大学硕士学位论文预处理服网务络器通数数客数模讯据据据块与户封封库数装装端模据应模模模块传用块块输块服模务块器模块图4-2系统模块关系图4.2.1数据库设计和文件解析1、数据库的设计[53]本系统数据库的设计，其数据来源主要依赖于SQD和DXF文件解析出的字符，这些字符来确定数据库中的相应字段和数据。数据库的建立能够更好的进行数据管理和用户权限的维护。在数据库中存放有各重要区域（区域范围不超过11km×km）的供水管网的图形数据和属性数据，它们是系统的数据来源。数据库主要包含以下数据表：表4-1三维显示数据库的主要数据表数据表名称说明REGIONDESCRIPTION_TAB区域信息表。要显示三维图形的重点区域的信息。POINT_TAB点表。每个点代表某个重点区域的管网的某个供水设备。PIPE_TAB线表。每段线代表某个重点区域的某段供水管段。EQUIPMENT_TYPE设备类型标。重点区域内的某个设备的类型PROPERTY_TAB供水设备的属性表PRIVILEGE_TAB用户权限管理信息表37 华中科技大学硕士学位论文在系统的程序设计中采用的是ADO（ActiveXDataObject）访问数据库，ADO是Microsoft数据库应用程序开发的新接口，是建立在OLEDB之上的高层数据库访问技术，它非常简单易用，并不失灵活性。在ADO中的类库中包含有这样的三个智能指针，它们分别是：_ConnectionPtr，_RecordsetPtr，_CommandPtr。下面我们就针对这三个智能指针分别进行介绍：_ConnectionPtr，用来管理连接一个数据源提供者所要求的信息，并可通过Open和Close的方法来打开一个到数据源提供者的活连接（LiveConnection）。另外还可以建立和管理事务，如BeginTrans，CommitTrans和RollBackTrans。最后可以通过Excute这种方法在数据源上执行命令；_RecordsetPtr，封装数据源提供者返回的记录集合。使用该类可以浏览返回的记录，也可以插入一个新的记录，或者更新和删除一个已经有的记录；_CommandPtr，封装了一个要发送到数据库的命令串（比如通常用的SQL查询语句）。该命令可以是一个表的名字，或者一个存储过程，或者一个依赖数据源的串。ADO数据库开发的基本流程如下：(1)初始化COM库，引入ADO库定义文件(2)用Connection对象连接数据库(3)利用建立好的连接，通过Connection、Command对象执行SQL命令，或利用Recordset对象取得结果记录集进行查询、处理。(4)使用完毕后关闭连接释放对象。为了更方便地访问数据库，在程序实现中我们采用了封装的方式，将对数据库的各种操作都对一般的程序隐藏起来。通过封装，我们让后续开发者可以更方便地访问数据库，对程序和数据的安全也起了一定的保护作用。2、文件的解析本系统文件解析包括SQD文件和DXF文件的解析。SQD文件中的数据主要用来显示已有管网区域中管网的三维图形。DXF文件中数据是新增管线的数据来源。只有得到这两种管线数据，才能将两种数据进行碰撞分析，这样就能分析出新增管线是否和已有的管网发生碰撞。38 华中科技大学硕士学位论文SQD文件是SiCAD/Open系统的文本格式的交换文件，其文件的分析结果如表4-2所示：表4-2SQD文件内各元素含义表SQD文件内图形元素描述用于何种图形对象PG点供水设备LI直线供水管段BO弧供水管段TX文本管段或设备说明SY符号已知类型的供水设备按照此表，对照SiCAD/Open用户手册，可以获取以上各种类型图形元素的图形参数值。将此图形元素值输入数据库即可获得某区域的所有管网设备和管段的图形数据和重要属性数据。DXF（AutodeskDrawingExchangeFormat）文件是AutoCAD中的矢量文件格式，它以ASCII码方式存储文件，在表现图形的大小方面十分精确。许多软件都支持DXF格式的输入与输出。这样就更易于用不同软件设计出不同的管线导入到本系统中进行碰撞分析。DXF文件的主要结构如下：1、标题段（HEADER）：有关图形的一般信息都可以在文件的这一节找到，每一个参数具有一个变量名和一个相关值。2、表段（TABLES）：包含的指定项的定义，它包括：线形表（LTYPE）、层表（LYER）、字体表（STYLE）、视图表（VIEW）等等。3、块段（BLOCKS）：包含块定义实体，这些实体描述了图形种组成每个块的实体。4、实体段（ENTITIES）：这一段含有实体，包括任何块的调用。5、ENDOFFILE（文件结束）。更为具体的DXF文件格式可在通用的DXF文件格式手册中详细查到。39 华中科技大学硕士学位论文4.2.2网络传输模块如图4-1所示，预处理服务器在对SQD或DXF文件进行解析之前需要先接收从客户端上传的SQD或DXF文件，应用服务器在数据库中获取数据之后，需要将这些数据传送到客户端。网络传输模块就是要完成在预处理服务器和客户端之间、应用服务器和客户端之间传送数据的功能。本模块主要包括以下两类数据的传输：1、利用Ftp协议将SQDDXF文件从客户端传送到预处理服务器。首先，在预处理服务器端安装一个FTP服务器（本系统安装的是Server-U），然后调用MFC中的FTP类完成文件上传功能。2、利用Socket（套接字）在应用服务器和客户端进行数据的传输。Socket是对TCP/IP协议的封装和抽象。利用VisualC++6.0进行Socket网络通讯模块的开发可以采取两种技术途径：1、直接利用VC6的CSocket类来进行；2、利用微软公司提供的Winsock控件来进行。Winsock控件是微软公司开发的ActiveX控件，其内部封装了Socket的功能，性能稳定，便于开发使用，为方便开发起见，本模块采用Winsock控件来实现Socket的功能。其详细实现如下：在每一个客户端有1个Winsock控件，用来连接应用服务器。在应用服务器端有1+n(0<=n<=30)个Winsock控件，其中有一个固定的Winsock控件用来监听客户端Winsock控件的连接请求，当有一个客户端的Winsock控件发出连接请求时，服务器将动态地创建一个Winsock控件用来与该客户端建立Socket连接，然后可以在建立的Socket中进行数据传输。动态创建的Winsock控件存放在服务器端的Winsock矢量中。当某一个Winsock控件5分钟内未从客户端接收数据时，认为此Winsock控件无效，应将此Winsock控件关闭、销毁、回收系统资源、压缩Winsock矢量大小。每当服务器端收到客户端的连接请求时，对Winsock矢量进行上述有效性检查。处理流程如图4-3所示：40 华中科技大学硕士学位论文开始否监听客户端的连接请求是否有新的连接请求创建新的Winsock控件，与客户端是建立套接字连接，并把该控件添加到Winsock控件矢量(Vector)中检查Winsock控件矢量客户端与服务器端进行否数据传输是否有某个Winsock控件在5分否钟之内未从客户端收到数据？数据传输完毕是是关闭并销毁该Winsock控件，回收内存等系统资源，压缩Winsock控件矢量结束图4-3基于Winsock控件的网络通讯流程4.2.3三维显示模块三维显示模块主要用来显示空间管网复杂的三维结构，并显示碰撞分析后的碰撞结果。当进入操作界面后，通过选择指定区域，如图4-4所示，在三维显示区显示出该区域管网的空间三维图形，该图形应反映指定区域的管线拓扑结构和标准设备图形。在该区域内图形可任意放大、缩小和移动。41 华中科技大学硕士学位论文图4-4选择指定区域三维显示数据的来源是通过支持C++的跨平台的boost库来建立三维管网的拓扑结构，再通过三维可视化工具箱VTK（VisualizationToolKit）来显示出三维图形，其基本流程图如4-5所示：系统数据库提取管线信息提取标准件类型标准件库显示管线以及附属设施图4-5三维显示流程和系统显示过程[54]boost是一个准标准库，相当于C++标准模板库STL的延续和扩充，它的设计理念和STL比较接近，都是利用泛型让复用达到最大化。对比STL，boost更加实用。STL集中在算法部分，而boost包含了不少工具类，可以完成比较具体的工作。boost主要包含一下几个大类：字符串及文本处理、容器、迭代子(Iterator)、算法、函数对象和高阶编程、泛型编程、模板元编程、预处理元编程、并发编程、数42 华中科技大学硕士学位论文学相关、纠错和测试、数据结构、输入/输出、跨语言支持、内存相关、语法分析、杂项。有一些库是跨类别包含的，既属于这个类别又属于那个类别。在本论文的系统设计中主要使用了boost库中的graph类，它提供了图的容器和相关算法，将管网数据抽象成一个图结构，这样就能够很容易地将数据提供给VTK的三维显示接口，显示管网三维图形。[55]VTK(VisualizationToolKit)是一个开放源码、自由获取的软件系统，全世界的数以万计的研究人员和开发人员用它来进行3D计算机图形，图像处理，可视化。VTK包含一个c++类库，众多的翻译接口层，包括Tcl/Tk，Java，Python。VTK是一个用于可视化应用程序构造与运行的支撑环境，它是在三维函数库OpenGL的基础上采用面向对象的设计方法发展起来的，它将可视化开发过程中会经常遇到的细节屏蔽起来，并将一些常用的算法封装起来。比如VTK将表面重建中比较常见的MarchingCubes算法封装起来，以类的形式给以支持，这样在对三维规则点阵数据进行表面重建时就不必再重复编写MarchingCubes算法的代码，而直接使用VTK中已经提供的vtkMarchingCubes类。VTK给从事可视化应用程序开发工作的研究人员提供直接的技术支持，是一个强大的可视化开发工具，它为用户使提供了极大的方便性和灵活性。[56]VTK基本显示流程如图4-6所示：图4-6VTK显示流程地下供水管网的组成元件可以分成两种类型：供水管段和供水设备。供水管段可以统一用圆柱形来建模，而供水设备有多种类型，形状也各异，为此，采用专门的建模软43 华中科技大学硕士学位论文件预先做好各个设备的三维模型，并且存为STL标准模型文件格式，供VTK调用。在三维管网的拓扑结构（图结构）生成后，本模块将输入的图结构转换为VTK内部支持的polydata类的对象，对于拓扑结构中的管段，使用vtkTubeFilter对数据进行建模和三维可视化，对于拓扑结构中的设备，使用Glyph(浮雕)技术，将其镶嵌在管段上，从而实现整个管网的三维显示。4.2.4碰撞分析模块碰撞分析模块主要功能是在新设计管线时，判断新增的管线与已有的管网是否存在着碰撞情况。如果经过碰撞测试没有发生碰撞，那么证明新设计的管线在理论上设计上是可行的，不会与旧的管网发生碰撞；如果检测发现碰撞，那么本模块可以找到发生碰撞的位置，根据相应得到的位置在CAD图纸中进行调整，直到不发生碰撞。碰撞分析模块的功能包括：DXF文件入库、显示三维新管线、显示三维旧管线、显示二维新管线、显示二维旧管线、预碰撞分析、几何碰撞分析、快速碰撞分析、碰撞位置输出、二维中显示碰撞结果和三维中显示碰撞结果等。其碰撞分析的流程如图4-7所示：图4-7碰撞分析流程44 华中科技大学硕士学位论文SQD文件是指需要设计新增管线所在区域的SQD文件，DXF文件是指在此区域中所设计的新增管线的DXF文件。预碰撞判断是在数据量很大的时候可以提前进行粗略的预碰撞分析，如果未发生碰撞可直接确定没有碰撞发生；如果发生碰撞则必须进一步进行碰撞分析。如果数据量不大或想直接得到精确的碰撞结果，则可跳过预碰撞分析直接进入碰撞分析。碰撞分析过程中可以选择几何碰撞分析和快速碰撞分析，几何碰撞分析主要运用第三章所讲的基于几何空间位置关系的检测方法；快速碰撞分析主要运用基于混合积求交的检测方法，并结合运用了基于几何空间位置关系的检测方法。由于引入混合积的检测方法绝大多数在二维平面中完成运算，所以其算法的速度更快。两种方法最后得到的碰撞结果完全一样，不存在算法偏差的问题。在发生碰撞后，可以选择立即在列表中查看碰撞发生的位置，也可以选择稍后查看，如图4-8所示：图4-8碰撞位置输出同时，也可以在二维和三维的显示区域中直观的看到发生碰撞的位置。在三维显示中更是可以清楚的看到管道的走向和发生碰撞的部位。如图4-9、4-10所示：图4-9二维碰撞显示前后对比45 华中科技大学硕士学位论文图4-10三维碰撞显示前后对比其中，二维显示区用小红叉来表示发生碰撞的位置，三维显示区用小圆球来表示发生碰撞的位置。如果管道发生碰撞，可以在本系统的高度剖面图中修改相应管道的高程（Z坐标），直到管道不发生碰撞为止，如图4-11如示，碰撞点随高程的调整逐渐减少。(a)三个碰撞点(b)两个碰撞点46 华中科技大学硕士学位论文(c)一个碰撞点(d)无碰撞点图4-11调整过后管道未发生碰撞如果高程的调整还不能满足管道碰撞的要求，那可以将新增管道的DXF文件拿到CAD软件中进行位置的调整，调整时可以参考碰撞给出的碰撞点的位置坐标。调整好后再入库进行碰撞分析，这样最终可以设计出符合要求的管道。4.2.5其它模块1、数据封装模块本模块的功能旨在采用XML格式对各种类型的数据进行标准化封装，以便在客户端和服务器端进行数据的传输和处理。管网的三维显示和碰撞分析是在客户端完成的。为完成此任务，客户端需从数据库中获取必要的数据。数据从数据库中获取后必须以一定的格式组织好，这一步称为包装(Packaging），然后通过网络传输到客户端，客户端接收到这些格式化的数据，将三维显示所需的数据从中提取出来，这一步称为解析(Depackaging），才能进行显示。为了保证通用性和可操控性，在本系统中采取了根据XML规范来包装数据的方法，实现数据的格式化的要求。数据包装和解析子模块完成把数据包装成XML数据包以及解析XML数据包从而获取原始数据的任务。用XML规范来包装数据必须体现客户端对数据的不同需求，因此，必须根据不47 华中科技大学硕士学位论文同数据类型设计不同格式的XML数据包。按照客户端界面的功能要求，本模块一共设计了以下数据类型的XML数据包：用户登录、获取用户信息、修改用户信息、修改用户权限、添加用户、删除用户、修改密码、SQD文件入库、显示区域描述信息、读取区域内管线和设备数据、删除区域、获取和设置点的坐标、获取和更新设备属性。各类型XML数据包统一处理子模块统一完成对各种数据类型的XML数据包的统一处理，为其他模块对本模块功能的调用提供统一的接口。2、常用数据缓冲区模块用户登录和打开区域列表是客户端经常要进行的两种操作，这两种操作所需要的用户信息数据和区域描述信息数据数据量不大但是被频繁使用。为了提高这两种常见操作的响应速度，可以把用户信息和区域描述信息读入到应用服务器的缓冲区。这样，当客户端用户执行这两种操作时，应用服务器在接收到客户端发送来的相应请求包后，可以直接到缓冲区中读取数据，而不必每次去数据库中读取，从而节省了每次进行数据库连接和访问数据库的时间，提高了客户端用户登录和打开区域列表的响应速度。3、服务器多线程处理模块由于应用服务器要同时与多达30个客户端进行通讯和处理数据，因此服务器端必须采取多线程技术进行处理，以满足客户端的响应速度要求。本模块实现了服务器端的多线程数据处理。每个客户端在应用服务器端有一个对应的响应队列，用来存放要发送往该客户端的响应包。当应用服务器接收到一个客户端发送来的数据包时，立刻启动一个新的线程对此数据进行处理，如果是请求包，则访问数据库，将获得的响应数据封装为响应包，放到该客户端对应的发送队列中，并向主线程发送一个自定义消息WM_SEND_DATA，通知主线程将发送队列的第一个数据包发送到客户端；如果是反馈包，则直接向主线程发送消息WM_SEND_DATA,通知主线程将发送队列的下一个响应包发送到客户端。处理完毕后，该线程正常退出。在多线程处理过程中要用到的共享资源需采取必要的同步措施。48 华中科技大学硕士学位论文4.2.6实验结果分析1、碰撞分析的正确性根据系统的设计要求，从原GIS系统中导出一块某广场区域的SQD文件，将此广场区域的SQD文件导入到本碰撞分析系统中。然后在CAD软件中设计几根管道，并导出其DXF文件，将此新增管道的DXF导入到系统中。文件导入完毕后，可以不断对高程（X坐标）进行调整，然后进行碰撞分析，其调整后碰撞与不碰的结果如图4-12所示：(a)二维未碰撞(b)二维发生碰撞(c)三维未碰撞(d)三维发生碰撞图4-12实验结果显示49 华中科技大学硕士学位论文在以上(c)(d)两张三维显示图中，可以明显的看到管道在空间中的位置，其发生碰撞的位置清晰的标出，碰撞位置坐标如表4-3所示：表4-3碰撞位置坐标X轴Y轴Z轴坐标值（m）537723.0633376719.0000.000此坐标与实际发生碰撞的位置坐标完全相符。同样，在图4-1中所示碰撞点的位置坐标如表4-4：表4-4碰撞位置坐标X轴Y轴Z轴537769.6883376488.0000.000坐标值(m)537810.2503376518.7500.000537793.0003376501.2500.000此表中的数据与实际发生碰撞的位置坐标完全相符。以上两表中的数据充分证明了碰撞结果的正确性。2、两种算法的速度比较第一种算法是完全基于几何的三维管道碰撞分析，第二种引入混合积的三维管道碰撞分析。由于在第二种算法中绝大多数管道的碰撞分析都是在二维平面中完成，并且在二维平面中线段相交是利用混合积的方法来判断，只有在二维中相交的线段才会调用基于几何的碰撞分析算法，这样就大大提高了运算的速度。下面就利用某广场的数据来进行有三个碰撞点存在情况下的速度比较实验。某广场二维三维图如图4-13所示：50 华中科技大学硕士学位论文(a)某广场二维图形(b)某广场三维图形图4-13三个点发生碰撞图形在这种情况下，用基于几何的碰撞分析算法和快速的碰撞分析算法分别做6次运算，其运算所需的时间如表4-5所示：表4-5某区域碰撞分析耗时比较序列123456平均几何算法耗时(ms)21.6721.2521.4121.8822.0122.0321.71快速算法耗时(ms)11.1211.2511.0911.4111.3411.5611.29由上表可知，快速算法平均耗时S=11.29(ms)，几何算法平均耗时fS=21.71(ms)，从数据上可以看来，快速算法的碰撞分析速度明显提高。n但是由于此区域中已有管道数为333条，设备点为343个，新增管道数为5条，设备点为6个，整体数目较少。所以在分别进行两种碰撞分析时，并不能完全感受到速度上的差异。为了更充分证明快速算法在速度上的优势，以下模拟三组数据：（1）已有管道数100000，新增管道10；（2）已有管道10000，新增管道100；（3）已有管道1000，新增管道1000。其中，设备的坐标点x范围在500000m至600000m之间，y范围在3000000m至4000000m之间，管道半径设为600mm。结论如表所示：51 华中科技大学硕士学位论文表4-6已有管道100000，新增管道10序列123456平均几何算法耗时(ms)2235215621412265215622502200快速算法耗时(ms)796704719797719781753表4-7已有管道10000，新增管道100序列123456平均几何算法耗时(ms)2406246824382437245324212437快速算法耗时(ms)875860906875906875883表4-8已有管道1000，新增管道1000序列123456平均几何算法耗时(ms)2437242124212437246824372436快速算法耗时(ms)875875860875860859867由以上三个表可以看出，当管道数量足够大时，快速算法的速度优势逐渐体现出61来。在总管道数目为10数量级时，快速算法所用的时间约为几何算法，速度提高3显著。目前系统受限于三维显示区域的大小，由于导入过大的区域时三维显示速度明显过慢，所以系统暂时只能导入11km×km大小的区域，这样显示区域内的管道数目相对较少，快速算法的优势还不能充分体现。但是，随着系统的升级和改善，导入区域的范围会越来越大，甚至导入整个城市的地下供水管网数据，届时，快速碰撞算法的优势就能够充分发挥。52 华中科技大学硕士学位论文5总结与展望5.1本文总结本文首先介绍了碰撞分析的概念及其典型算法。然后着重介绍了基于几何的空间管道的碰撞分析算法，并在该算法的基础上建立了一个管道碰撞分析试验系统。围绕着基于几何的空间管道碰撞分析算法的研究，作者展开了如下的研究工作：1、基于几何的空间管道碰撞分析技术的研究。根据地下供水管网的形态和走向特点，把地下供水管网看成一根根相连的圆柱体模型，然后利用空间解析几何的一般方法，分情况讨论管段之间的碰撞情况将碰撞的结果保存输出。2、引入混合积的管道碰撞分析技术的研究。针对地下供水管网是一块广阔区域且管道高程坐标变化不大的特点，可以进一步将三维地下供水管网模型简化为一个二维管网模型。利用空间向量混合积的方法，判断平面上两管道是否发生碰撞，如发生碰撞，则进一步针对这两条管道用基于几何碰撞分析算法来判断是否发生碰撞；如未发生碰撞，则可以确定两管道未发生碰撞。由于绝对大多数运算都是在二维平面中完成，所以此种算法可以大大提高运算速度。3、基于几何的空间管网碰撞分析系统原型的研究。根据理论和实验研究的结果，利用软件工程的方法，在原空间管网三维显示系统的基础上，设计了一个“基于几何的空间管网碰撞分析系统”的原型。此系统原型能够显示新旧管线的二维和三维图形；能够进行管网的预碰撞分析，基于几何的碰撞分析，引入混合积的碰撞分析；能够输出管道碰撞的结果，并将结果显示在二维和三维显示区域。作者主要开发完成了碰撞分析、用户管理以及部分文件解析、网络传输、三维显示、侧视图显示等模块的内容。虽然以上的研究内容都是针对城市地下供水管道的，但其基本理论和方法同样适用于其它管道模型，例如地下通信网，电缆，排水管道等，因而具有广泛的应用价值。53 华中科技大学硕士学位论文5.2研究展望由于时间和数据来源等因素的限制，而且空间地下供水管道碰撞分析的内容复杂，有些问题还有待进一步研究、完善，具体包括的关键问题有：1、将设备因素考虑进来，做更加精确的碰撞分析研究。在本论文中，管网中所有管段被看成单一的圆柱体模型，但在实际管网中，还存在水井、消防栓、阀门等等二十多种设备，这些设备本身具体固定的形状和大小。当管道之间没有发生碰撞时，并不能保证这些设备之间或设备和管道之间没有发生碰撞。所以进一步将设备的碰撞情况考虑进来是非常有必要的。2、提高碰撞分析算法的速度。本论文中主要提出了两种算法，基于几何和基于混合积的碰撞分析算法，而快速碰撞分析算法在管道发生碰撞时也得调用基于几何的碰撞分析算法。虽然快速算法在速度上有2至3倍的提高，但随着系统的升级，可能会面临着管网空间走向更复杂、数据量更大的管网碰撞分析，所以进一步提高算法速度很有必要。3、在本系统中完成管道设计和碰撞分析的一体化。现行系统中新增管道的数据来源于DXF文件，这样当管道发生碰撞时不能及时的修改管道位置，而必要在CAD中修改相应的DXF文件，然后再次导入。如何在系统中增加一个设计、修改管道的功能模块是非常有应用价值的。54'