基于BSP空间分割法的核级管道三维碰撞检查方法研究

吴启涛 黄捷 孙冠宇 刘雨晨

摘 要

在PDMS平台设计了基于核级管道的碰撞检查模块，同时兼顾速度与精度的需求。本文分析了常见的碰撞检查方法，设计了一种新的碰撞检查流程，分别研究了BSP空间分割法及包围盒算法的优势，将其应用于新的检查流程中，将碰撞检查模块中，采用并行包围盒法检查，得到碰撞检查结果。

关键词

碰撞检查;BSP空间分割法;包围盒算法;并行检查

中图分类号： TP391.41                文献标识码： A

DOI：10.19694/j.cnki.issn2095-2457 . 2020 . 17 . 69

Abstract

The collision check module based on nuclear-grade pipeline is designed on PDMS platform. At the same time， the requirements of speed and precision are considered. This paper analyzes the common collision inspection methods， designs a new collision inspection process， and studies the BSP spatial segmentation method. The advantage of the bounding box algorithm is applied to the new inspection process. In the collision check module， the parallel bounding box method is used to check the collision check result keywords： Collision check BSP spatial segmentation method bounding box algorithm parallel check.

Key words

Collision check; BSP spatial segmentation method; Bounding box algorithm; Parallel checking

0 前言

三維数字化设计已经在工程领域全面普及，PDMS等三维设计软件成为管道设计中不可或缺的工具。伴随着计算机硬件的迅猛发展，图形处理性能不断提升，基于三维空间的碰撞检测算法的研究也越来越深入。在实际工程应用中，模型碰撞检查工作需要设计校核人员进行大量烦琐的工作。由于核级管道三维设计的严谨性，而且传统的三维碰撞检查流程不能同时兼顾速度与精度。通过研究，将空间分割法应用于碰撞检查流程能将有效分配计算资源，该方法首先对三维模型分类，再根据分类结果进行并行包围盒法碰撞检查，同时兼顾了设计工作的精度与速度。在实际设计工作中，是否能够快速地得到准确结果，将直接影响到设计人员工作进度。

1 算法基础及比较

1.1 BSP二叉空间分割法

BSP二叉空间分割法，是一种自适应空间剖分法，它的基本思想是基于任何平面都可以将空间分割成两个半空间这样一个事实。在运行时使用一个预先计算好的树来得到多边形从后向前的列表。所有位于这个平面一侧的点定义一个半空间，位于另一侧的点定义为另一个半空间。在任何半空间中有一个平面，会进一步将此半空间分割为更小的两个子空间。使用多边形列表将这一过程一直进行下去，将子空间分割得越来越小，直到构造成一个二叉树。在这个树中，进行分割的多边形被存储在树的节点，所有位于子空间中的多边形都在相应的子树上，这一规则适用于树中每一个节点。选择一个平面投影，将多边形映射为直线段，如图1所示，从多边形A开始构造一个BSP树。

通过A平面的分割得到BSP树，如图2所示。

BSP二叉空间分割法不但在多边形剪切方面表现出色，而且还能有效地运用world-object式的碰撞检测。BSP树的遍历是使用BSP的一个基本技术。碰撞检测本质上减少了树的遍历或搜索。它能在早期排除大量的多边形，所以在最后我们仅仅是对少数面进行碰撞检测。

1.2 层次包围盒法

碰撞检查中普遍需用到包围盒法进行计算。包围盒树构建的方法需要根据实际需求进行选取。根据包围盒类型的不同，可以分为AABB层次包围盒、k-dop层次树等算法、Sphere包围球、OBB层次包围盒等算法。

包围球Sphere：基本思想是根据目标的坐标计算出球心c，由此确定半径r，得到一个最小的球体可以包住目标。

沿坐标轴的包围盒AABB：指包含对象且边平行于坐标轴的最小长方体。当两个AABB包围盒在三个坐标轴上的投影区间同时重叠时，则相交。

方向包围盒OBB：指包含对象且相对于坐标轴方向任意的最小长方体。包围盒的方向的选择与效率息息相关。

k-dop包围盒：包含当前对象为要求。自身所有面的法向量均来自一个固定的方向集合的凸包，固定方向集的选取对包围盒效率有着直接影响。

2 碰撞检查流程设计

核级管道碰撞检查要求精确度高响应快，再根据碰撞检查算法各自的性能特点，现设计一种新的碰撞检查流程。

该流程利用BSP空间分割法将待检查模型进行分割，将碰撞模型分为两类，其中不需要高精度检查的模型用速度较快的AABB包围盒进行碰撞检查，需要细致检查的检查模型用K-dop包围盒进行碰撞检查。既满足时间复杂度的要求，也满足核级管道精度高的特点。

3 仿真與结果分析

3.1 实验设计

基于PDMS平台，开发针对管道的碰撞检查功能模块，将新设计的碰撞检查流程植入功能模块中。主要实现管道模型在布置过程中实时的完成与周围建筑物的碰撞检查，包括管道、支吊架、设备、土建等9个级别的检查。

用实例验证新碰撞检查流程的性能优势。选择实际工程中6根管道作为实验对象，对比单一的包围盒算法与新碰撞检查流程，通过耗时及碰撞结果对比得到新设计流程的优势。

3.2 结果分析

6根管道经过新的碰撞检查流程，同时对比精度最高的k-dop包围盒及速度最快的Sphere包围盒，时间对比结果如图4所示。

通过三种碰撞检查算法用时对比，新的碰撞检查算法用时趋近于构造代价最小的Sphere包围盒法，远远小于k-dop包围盒法。接下来对比碰撞检查效果，对比结果如图5所示。

通过碰撞检查效果对比，新碰撞检查流程接近于k-dop包围盒算法，再通过时间对比的结果分析，新碰撞检查流程的效率要优于现有单一的碰撞检查算法，并行包围盒算法发挥了作用，减轻了设计人员工作的时间成本。

4 结束语

针对管道设计中的碰撞检查问题，本文通过对目标模型进行BSP分割预处理，将模型拆分为速度和效率两类模型，用K-dop和AABB包围盒并行检查。通过新的碰撞检查算法流程，解决了碰撞检查效率低等问题，随着模型体量的增加，新的碰撞检查算法的效率优势愈发明显。本文通过实验证明了算法的可行性和有效性，说明新的碰撞检查算法应用于核级管道设计效果显著。

参考文献

[1]黄晓康.基于BSP和四叉树的场景管理研究[D].南京理工大学，2008.

[2]乔云婷，张弘.基于BSP树的三维场景渲染方法研究[J].渭南师范学院学报，2014，29（15）：86-89.

[3]靳雁霞，秦志鹏，李照.融合R-Sphere包围球的变形体碰撞检测算法[J].计算机工程与设计，2017，38（01）：92-96.

[4]邓峻生，毛世峰，刘旭峰，叶民友.基于AABB树的聚变堆形变部件碰撞检测算法[J].计算机系统应用，2018，27（11）：161-167.

[5]刘超，蒋夏军，施慧彬.基于OBB包围盒碰撞检测算法的改进[J].计算机技术与发展，2018，28（06）：43-48.

[6]Fang Zhigang， Jiang Jianxun， Xu Jie. Efficient Collision Detection Using a Dual K-DOP-Sphere Bounding Volume Hierarchy[P]. Information Technology and Applications （IFITA）， 2010 International Forum on，2010.

[7]郑延斌，郭凌云，刘晶晶.基于混合包围盒的碰撞检测优化算法[J].计算机工程与科学，2013，35（04）：87-92.