基于粒子群优化的并行碰撞检测系统及方法.docx

基于粒子群优化的并行碰撞检测系统及方法专利名称：基于粒子群优化的并行碰撞检测系统及方法技术领域：本发明关于一种并行碰撞检测系统及方法，特别是涉及一种基于粒子群优化的并行碰撞检测系统及方法背景技术：碰撞问题多年来一直受到较多的关注，碰撞检测方法在计算几何、计算机动画、CAD/CAM，仿真机器人和虚拟现实等领域中都有较好的应用前景近二十多年来，研究人员在碰撞检测领域中做了相当多有意义的工作提出一些较为成熟的方法从总体上将这些方法分为两大类几何分解法和分层包围盒法前者是将整个虚拟空间划分为相等体积的小的单元格，只对占居了同一单元格或相邻单元格的几何对象进行相交计算比较典型的例子有八叉树、k-d树、BSP树等这类方法的特点为方法复杂、精度高分层包围盒的核心思想是用体积略大而几何特性简单的包围盒来近似地描述复杂的几何对象，从而通过判断包围盒是否重叠来粗略估计两检测对象是否碰撞，此外可以通过构造树状分层结构一步步逼近几何模型，提高检测精度分层包围盒由于其方法简单、效率相对高，也是一种广泛应用的碰撞检测方法但其检测精度较低另外，现有的动态碰撞检测方法自身还存在一些问题如检测中刺穿现象和遗漏情况等传统的多物体间的碰撞检测方法一般时间复杂度为0(n2)，不能满足实时性的要求，不利于碰撞检测快速实现。

基于空间分割技术的几何分解方法，影响该方法效率的一个重要因素是分区的多少，而分区的数目又较难把握八叉树和其它几何模型在解决碰撞检测的框架之间的几何干涉问题时，不会大幅度提高方法效率采用分层包围盒技术来加速多面体场景的碰撞检测，但一般的包围盒方法作为一个整体的方法，检测精度低，效率提高并不明显发明内容为克服上述现有技术存在的不足，本发明之一目的在于提供一种基于粒子群优化的并行碰撞检测系统及方法，其可以在提高碰撞检测速度的同时保证较高的精度，而且适用于大规模复杂场景的实时动态碰撞检测为达上述及其它目的，本发明提出一种基于粒子群优化的并性碰撞检测系统，至少包括构建搜索空间模组，用于构建三维空间内两个物体之间存在的特征对构成的二维离散空间，以将碰撞检测问题转化成在一个由两物体特征对序号构成的离散空间中的复杂组合优化问题；多面体剖分模组，用于将三维空间的多面体剖分得到四面体的包围盒，并行取多个四面体的包围盒特征对；以及并行碰撞检测模组，利用粒子群优化方法对提取的多个四面体包围盒特征对并行求解，输出结果及碰撞元素进一步地，该多面体剖分模组以包围盒的中心点作为特征对象进行采样进一步地，如权利要求2所述的一种基于粒子群优化的并性碰撞检测系统，其特征在于，该并行碰撞检测模组还包括初始化模组，用于随机初始化粒子的位置与速度；适应度计算模组，利用辅助进程并行计算所有粒子的适应度值，并发送给主控进程;比较模组，利用主控进程接收到粒子的适应度值，将其与个体极值、全局极值比较，若该适应度值优于此时粒子的个体极值或全局极值，则更新粒子的个体极值或全局极值，否则不进行更新；判断模组，用于判断是否满足终止条件，若满足终止条件，则启动输出模组输出结果及碰撞元素，否则启动更新模组； 更新模组，根据位置更新公式及速度更新公式更新粒子的和速度，并启动该适应度计算模组重新计算粒子的适应度值；以及输出模组，用于输出结果及碰撞兀素。

进一步地，该适应度计算模组采用如下公式计算适应度值F = (a · x_b · x)2+(a · y-b · y)2+ (a · z~b · z)2其中{a，b}为一个特征对，(x，y，z)是真实的物体空间中点的坐标进一步地,若Pi 具体实施例方式以下通过特定的具体实例并结合本发明的实施方式，本领域技术人员可由本说明书所揭示的内容轻易地了解本发明的其它优点与功效本发明亦可通过其它不同的具体实例加以施行或应用，本说明书中的各项细节亦可基于不同观点与应用，在不背离本发明的精神下进行各种修饰与变更在介绍本发明的系统及方法之前，先对粒子群优化方法、本发明的基本思想及理论基础作一介绍粒子群优化方法PSO (Partical Swarm Optimization)是近年来发展起来的一种新的进化方法EA(Evolutionary Algorithm)它也是从随机解出发,通过迭代寻找最优解，它也是通过适应度来评价解的品质，它通过追随当前搜索到的最优值来寻找全局最优这种方法有实现容易、精度高、收敛快等优点本发明将其引入到碰撞检测领域，把三维物体空间内的碰撞检测问题转化为一个二维离散解空间内的优化问题，应用粒子群方法来完成碰撞检测过程中局部最小特征对的搜索过程。

由于基于特征采样的随机碰撞检测方法的核心是通过在物体上采样作为初始假想碰撞对，然后通过逐步跟踪采样对到达局部最小来进行碰撞检测因此有必要在碰撞检测之前进行特征采样进行特征采样应先确定特征的类型由于随机碰撞检测方法将碰撞问题转化为搜索两个物体上的特征之间的距离问题，因此，所选特征间的距离就必须是可以计算的 基于特征采样的随机碰撞检测方法直接对物体进行特征采样方法的特征对象一般是组成物体几何模型的基本几何元素，如点、三角形、四面体等其中，判断基本几何元素间是否发生干涉时，方法本身要求用户设定距离阈值如果设定的距离阈值较大，则会增加一些没有干涉的几何元素对如果设定的距离阈值较小，就容易漏掉一些已发生干涉的几何元素对因此，本发明将基于特征采样的随机碰撞检测方法进行改进不再把几何模型的顶点作为粒子群方法中运动粒子的特征对，而是选用几何模型多面体剖分得到的四面体的包围盒，即以基本几何元素的包围盒作为特征对象而层次包围盒的核心思想是用体积略大而几何特性简单的包围盒来来近似描述复杂的几何对象，从而只需对包围盒重叠的对象进行进一步的相交测试进行碰撞检测时，首先判断基本几何元素的包围盒是否发生干涉，如发生干涉，则进行基本几何元素的干涉检测。

这就克服了以基本几何元素为特征对象的随机碰撞检测方法中容易漏掉干涉元素的情况，可以很大程度地提高方法的精确度最后，为了进一步提高检测速度，引入并行思想实现基于PSO优化的并行碰撞检测，该方法把碰撞检测问题转化到两个模型的特征对序号构成的空间内的优化问题，并结合多面体剖分方法，将优化模型充分并行化，然后采用粒子群优化方法并行求解，引入并行思想，从而使基于PSO优化技术的并行碰撞检测方法能较好提高碰撞检测速度图1为本发明一种基于粒子群优化的并行碰撞检测系统的系统架构图如图1所示，本发明基于粒子群优化的并行碰撞检测系统，至少包括构建搜索空间模组10、多面体剖分模组11以及并行碰撞检测模组12构建搜索空间模组10用于构建三维空间内两个物体之间存在的特征对构成的二维离散空间，以将碰撞检测问题转化成在一个由两物体特征对序号构成的离散空间中的复杂组合优化问题两个物体的碰撞检测可以简单描述为三维空间内两个物体之间是否存在至少一对特征对(ai; bp，其中 e A(0 权利要求1.一种基于粒子群优化的并性碰撞检测系统，至少包括 构建搜索空间模组，用于构建三维空间内两个物体之间存在的特征对构成的二维离散空间，以将碰撞检测问题转化成在一个由两物体特征对序号构成的离散空间中的复杂组合优化问题； 多面体剖分模组，用于将三维空间的多面体剖分得到四面体的包围盒，并行取多个四面体的包围盒特征对；以及 并行碰撞检测模组，利用粒子群优化方法对提取的多个四面体包围盒特征对并行求解，输出结果及碰撞元素。

2.如权利要求1所述的一种基于粒子群优化的并性碰撞检测系统，其特征在于该多面体剖分模组以包围盒的中心点作为特征对象进行采样3.如权利要求2所述的一种基于粒子群优化的并性碰撞检测系统，其特征在于，该并行碰撞检测模组还包括 初始化模组，用于随机初始化粒子的位置与速度； 适应度计算模组，利用辅助进程并行计算所有粒子的适应度值，并发送给主控进程； 比较模组，利用主控进程接收到粒子的适应度值，将其与个体极值、全局极值比较，若该适应度值优于此时粒子的个体极值或全局极值，则更新粒子的个体极值或全局极值，否则不进行更新； 判断模组，用于判断是否满足终止条件，若满足终止条件，则启动输出模组输出结果及碰撞元素，否则启动更新模组； 更新模组，根据位置更新公式及速度更新公式更新粒子的和速度，并启动该适应度计算模组重新计算粒子的适应度值；以及 输出模组，用于输出结果及碰撞兀素4.如权利要求3所述的一种基于粒子群优化的并性碰撞检测系统，其特征在于，该适应度计算模组采用如下公式计算适应度值 F = (a x~b x)2+ (a y-b y)2+ (a z_b z)2 其中{a, b}为一个特征对，(x, y, z)是真实的物体空间中点的坐标。

5.如权利要求4所述的一种基于粒子群优化的并性碰撞检测系统，其特征在于gPi全文摘要本发明公开了一种基于粒子群优化的并性碰撞检测系统及方法，该系统至少包括构建搜索空间模组，用于构建三维空间内两个物体之间存在的特征对构成的二维离散空间，以将碰撞检测问题转化成在一个由两物体特征对序号构成的离散空间中的复杂组合优化问题；多面体剖分模组，用于将三维空间的多面体剖分得到四面体的包围盒，并行取多个四面体的包围盒特征对；以及并行碰撞检测模组，利用粒子群优化方法对提取的多个四面体包围盒特征对并行求解，输出结果及碰撞元素，通过本发明，可在提高碰撞检测速度的同时保证较高的精度，而且本发明可适用于大规模复杂场景的实时动态碰撞检测。