基于主成分分析法的碰撞检测算法

李荀 李孔清 王嘉

摘要：基于主成分分析法，提出了一种新的碰撞检测算法。该算法利用降维的思想将多个成分转化为少数几个成分作为主成分，将研究对象的主成分作为法向量来构建K-DOP包围盒。同时通过对案例进行分析，发现在8-DOP的基础上增加两个基于主成分的法向量所构建成的12-DOP包围盒能明显提高碰撞检测的精度。

关键词：碰撞检测；主成分分析；K-DOP；包围盒；案例分析

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2019）05-0230-04

Collision Detection Algorithm based on Principal Component Analysis

LI Xun， LI Kong-qing*， WANG Jia

（School of Civil Engineering， Hunan University of Science and Technology， Xiangtan 411201， China）

Abstract： Based on the principal component analysis method， a new collision detection algorithm is proposed. The algorithm uses the thought of dimensionality reduction to transform several components into a few components as the principal component， and constructs the K-DOP bounding box by the principal component of the study object as a normal vector. At the same time， by analyzing the case， it is found that the 12-DOP bounding box，which is constructed by adding two legal vectors based on the principal component on the basis of 8-DOP， can obviously improve the accuracy of the collision detection.

Key words： Collision detection； Principal component analysis； K-DOP； Bounding box； Case analysis

建筑领域由于各专业之间信息的不对称性，常常导致发生管线碰撞的情况[1]。而BIM技术将建设、设计、施工和监理单位等项目参与方放到同一平台上，利用BIM中的碰撞检测软件可及早发现问题，避免潜在的碰撞，从而减少返工，节省人力物力。BIM技術的一个重要功能与应用就是碰撞检测[2]。当结构、机电、暖通等专业完成建模后，将所有模型都导入到碰撞检测软件（如Navisworks和Solibri等）中进行碰撞检测，可以提前预测和避免潜在的碰撞问题。碰撞检测分为硬碰撞和软碰撞两种。硬碰撞指的是实物之间的碰撞，比如风管与水管之间的管线碰撞等；软碰撞指的是实体与实体之间没有碰撞，但是安装空间不够或者管道之间的距离不符合要求等[3]。应用该技术，可以提高设计的质量和加快施工进度，并且对于后期的物业管理也大有益处。综上所述，BIM中的碰撞检测算法有重要的研究意义。本论文将针对BIM系统中的碰撞检测算法进行研究，以期提高碰撞检测的精度。

碰撞检测算法总的可以分为两类：一类是静态碰撞检测算法；另一类是动态碰撞检测算法[4]。动态碰撞检测算法主要分为空间分割法和层次包围盒法。层次包围盒法又可分为AABB、包围球、OBB和K-DOP包围盒[5]。传统检测方法通过层次包围盒技术来快速剔除不会发生碰撞的物体。首先检测两包围盒是否相交，相交后再详细检测包围盒之间的重叠部分，从而判断出物体之间是否碰撞[6]。

笔者在选用8-DOP包围盒来包围模型，然后用VC++编程来检测模型间是否碰撞时发现会出现检测失效的情况，即两模型原本不碰撞，却检测出碰撞。究其原因是该类算法采用预先给定的轴方向来构造包围盒。若物体的外形顶点分布方向严重偏离给定的方向，则很容易导致构造的包围盒过大，不够紧致，容易导致误判。为了克服固定轴的缺点，本文拟通过对顶点的分布做主成分分析，构造出动态的方向轴，最终固定轴与动态轴相结合，从而达到减少碰撞误判的可能。

1 新的碰撞检测算法的提出

1.1 包围盒类型选择

通过对包围盒类型的了解[7～10]，各包围盒之间碰撞检测算法的优劣性如表1所示。

表1 包围盒碰撞检测算法比较

在包围盒类型的选择上，两个重要的标准是紧密性和简单性[11]。从表1中可以看出，包围球和AABB的紧密性均不够好，紧密性比较好的是K-DOP和OBB。从其他方面来看，K-DOP的简单性要优于OBB，并且占用内存也相对较少。因此，本文选用K-DOP包围盒算法作为研究的基础和出发点。为简单起见，本文的检测是在二维的条件下实现的，因此，8-DOP的4个法向量分别为：（1，1，0）、（-1，1，0）、（1，0，0）、（0，1，0）。对三维问题来说，算法依然适用，只是轴向量数量增加。

1.2 基于主成分分析法的包围盒算法

基于主成分分析法的包围盒算法是利用主成分分析法[12]的思想，找到被包围体的几个主成分作为法向量，与原有法向量（1，0，0）、（0，1，0）、（1，1，0）、（-1，1，0）相结合使包围体更加紧密。

关于总体主成分有如下结论：

设[∑]是[X=（X1，X2，???，Xp）T]的协方差矩阵，[∑]的特征值为[λ1≥λ2≥???λp≥0]，相应的正交单位化特征向量为[e1，e2，???，ep]，则[X]的第i个主成分可写为：

[Yi=eTiX=ei1X1+ei2X2+???+eipXp，i=1，2，???，p] （1）

其中[ei=（ei1，ei2，???，eip）T]。这时可得到：

[Var（Yi）=eTi∑ei=λieTiei=λi，i=1，2，???，p，Cov（Yi，Yk）=eTi∑ek=λkeTiek=0，i≠k.] （2）

一般地，如果[P=（e1，e2，???，ep）]，则[P]为一正交矩阵，并且[PT∑P=∧=Diag（λ1，λ2，???，λp）]，其中[Diag（λ1，λ2，???，λp）]为对角矩阵。

设[li=（li1，li2，???，lip）T（i=1，2，???，p）]为[p]个常数向量，设[Y1=lT1X]为[X]的第一主成分，其中满足条件[lT1l1=1]。令：

[z1=（z11，z12，???，z1p）T=PTl1] （3）

则得到：

[Var（Y1）=lT1∑l1=zT1PT∑Pz1=λ1z211+λ2z212+???+λpz21p≤λ1zT1z1=λ1lT1PPTl1=λ1] （4）

并且当[z1=（1，0，???，0）T]时，等号成立。这时，

[l1=Pz1=e1] （5）

由此可知，在满足条件[lT1l1=1]时，当[l1=e1]时，[Var（Y1）]达到最大，且

[maxlT1l1=1Var（Y1）=Var（eT1X）=eT1∑e1=λ1] （6）

如果[Y2=lT2X]为[X]的第二主成分，则有[lT2l2=1]并且[Cov（Y2，Y1）=lT2∑e1=λ1lT2e1=0]。即得到[lT2l2=1]和[lT2e1=0]。

令：

[z2=（z21，z22，???，z2p）T=PTl2] （7）

则可得到：

[lT2e1=zT2PTe1=z21eT1e1+z22eT2e1+???+z2peTpe1=z21=0] （8）

因此

[Var（Y2）=l2T∑l2=z2TPT∑PTz2=z2T∧z2 =λ2z222+???+λPz2p2 ≤λ2z2Tz2=λ2l2Tl2=λ2] （9）

并且当[z2=（0，1，0，???，0）T]，也就是[l2=Pz2=e2]时，[Var（Y2）=λ2]。由此可知，當[l2=e2]时，满足条件[lT2l2=1]，[Cov（Y2，Y1）=0]并且使[Var（Y2）=λ2]达到最大值。

同理可证，对所有的p个主成分，上述结论均成立。

通过以上结论可知，若要求出X的各主成分，需要求出其协方差矩阵[∑]的各特征值及各特征值对应的正交单位化后的特征向量。然后按特征值由大到小将特征向量排序，即线性组合[X1，X2，???，Xp]分别称为X的第一，第二，…，第p个主成分，特征值对应各主成分的方差。两个物体碰撞检测时，增加的两个法向量就是两个物体各自的主成分。

2 碰撞检测算例与分析

由于K-DOP的紧密性随着K值的增大而愈紧密，因此针对传统检测方法中出现的实际不碰撞，检测结果却碰撞的检测失效情况，采用增加2个法向量的方法来优化8-DOP。增加的这两个法向量确定如下：首先是利用主成分分析法，分别计算得到两个对象的主成分作为法向量来构建12-DOP；其次是增加（1，0.57735，0）和（1，-1.73205，0）这两个确定的法向量，即30°与-60°坐标轴来构建12-DOP。

2.1 两种优化方法检测比较

对于两种增加法向量所构建的12-DOP包围盒算法来进行检测比较，通过下面五个算例来进行说明，如图1所示，其中包围对象的坐标已在图中列出，黑色实线代表包围对象，红色虚线代表增加了主成分法向量的12-DOP包围盒，黑色虚线代表增加了固定法向量的12-DOP包围盒。

通过VC++编程来检测两个对象碰撞与否，最终得到16-DOP算法的分析结果见表4所示。发现16-DOP与增加了两个基于主成分的法向量的12-DOP检测结果一致。从而验证得到在8-DOP的基础上增加两个基于主成分的法向量所构建成的12-DOP包围盒能明显提高检测的精度。

3 结论

1） 针对传统的K-DOP包围盒出现检测失效的情况，提出了基于主成分分析法的碰撞检测算法。将主成分分析法与碰撞检测技术相结合，能够使包围盒更加均匀且紧密地包围物体，提高检测精度。

2） 通过分析比较基于主成分分析法的12-DOP包围盒和基于固定法向量的12-DOP包围盒，发现前者所构建的包围盒比后者更加均匀，检测精度大大提高。

3） 既增加固定法向量又增加基于主成分的法向量所构建成16-DOP，通过碰撞检测算例验证，发现与单独增加两个主成分的法向量所构建的12-DOP包围盒碰撞检测结果一致，从而验证得到在8-DOP的基础上增加两个基于主成分的法向量所构建成的12-DOP包围盒能明显提高检测的精度。

参考文献：

[1] 李煜一.基于BIM的综合管线碰撞检测研究[D].兰州：兰州交通大学， 2014.

[2] 王咸锋，黄妙燕.基于BlM技术的碰撞检测在地铁工程中的应用研究[J].广东技术师范学院学报， 2016， 37（11）：33-39.

[3] 刘卡丁，张永成，陈丽娟.基于BIM技术的地铁车站管线综合安装碰撞分析研究[J].土木工程与管理学报， 2015（1）：53-58.

[4] 王嘉，李孔清.碰撞检测算法研究综述[J].电脑知识与技术， 2017，13（20）：202-205.

[5] 何水艳.虚拟校园的碰撞检测研究[D].武汉：华中师范大学，2006.

[6] 李建波，潘振宽，孙志军.基于包围盒与空间分解的碰撞检测算法[J].计算机科学， 2005， 32（6）：155-157.

[7] 宋城虎，闵林，朱琳，等.基于包围盒和空间分解的碰撞检测算法[J].计算机技术与发展， 2014， （1）：57-60.

[8] Xing Y S， Liu X P， Xu S P. Efficient collision detection based on AABB trees and sort algorithm[A]. In：IEEE. International Conference on Control and Automation[C]. Xiamen：IEEE ， 2010. 328-332.

[9] 章勤，黄棍，李光明.一种基于OBB的碰撞检侧算法的改进[J].华中科技大学学报（自然科学版）， 2003， 31（l）： 46-48.

[10] Klosowski J T， Held M， Mitchell J S B， et al. Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs[J]. IEEE Transactions on Visualization & Computer Graphics， 1998， 4（1）：21-36.

[11] 魏迎梅.虚拟环境中碰撞检测问题的研究[D].长沙：中国人民解放军国防科学技术大学， 2000.

[12] 张祥国，丁瑞，蒋幸幸.基于主成分分析与熵值法结合的多元评价模型的研究[J].新教育时代电子杂志：教师版，2017（18）：181.

【通联编辑：梁书】