凸多面体连续碰撞检测的运动轨迹分离轴算法

针对凸体间的连续碰撞检测,在距离算法(Gilbert-Johnson-Keerthi distance algorithm,GJK)基础上,提出一种采用运动轨迹分离轴计算的线性连续碰撞检测算法.该算法首先采用支撑点和投影技术,剔除必定不发生碰撞的物体,以加速碰撞检测的速度;然后,对可能发生碰撞的物体,计算2个凸体的Minkowski差集,所形成的凸包与运动路径执行GJK分离轴算法,实现在整个时间区间内一次性完成碰撞检测任务;最后,采用几何方法以及超平面与射线求解方式计算射线与凸体边界近交点,确定出第一次发生碰撞位置,并调整运动物体位置,完成碰撞响应过程.该算法不需要构造扫掠体,连续检测过程中不需要凸体间的求交计算.将文中算法应用于物体方向包围盒的连续碰撞检测,算法分析和实验结果表明,该算法对包围盒的连续碰撞检测具有较高检测精度和响应速度.

基于连续碰撞位探测的防碰撞算法研究

文章通过对IAMS算法的分析,提出了一种基于连续碰撞位探测(CCBD)的防碰撞算法.在CCBD算法中引入连续碰撞位探测机制,并把标签碰撞分为单独位碰撞和连续位碰撞两种情况进行处理.连续碰撞位探测机制能够准确获得连续碰撞位的实际存在情况从而避免了空闲时隙以及不必要的碰撞时隙的产生.理论分析和实验仿真表明,CCBD算法克服了IAMS算法的不足,在标签识别过程中表现出良好的性能.

一种快速精确的连续碰撞检测算法

为了实现运动刚体间快速精确的碰撞检测,提出了一种新的连续碰撞检测算法。利用图形硬件的计算能力,该算法在每个时间区间上实时处理,把单个时间区间划分成若干个子时间区间,使用静态和连续的定向包围盒(OBB)相交性检测方法,计算出在子时间区间内的潜在碰撞集(PCS),并结合基于图形硬件的可靠碰撞剔除方法、三角面片之间的碰撞检测方法和回退方法,计算出刚体间的初始碰撞时刻和碰撞位置.并应用于一个三维建模系统中的装配模块.实验结果表明,与传统的碰撞检测方法相比,该算法可以缩短计算时间,具有更好的性能和精度.

复杂物体连续碰撞检测动态投影分离剔除算法

针对复杂物体间碰撞检测,为提高碰撞检测效率,减少计算量,解决普通算法不直接适用于非凸体等问题,提出了一种连续碰撞检测算法。首先,该算法在初检测阶段利用基于波前法的三角网格生成,对非凸体等复杂物体表面进行网格划分,获取高质量三角形,得到三角形点、线、面参数信息;然后,用动态投影分离剔除法对三角形单元对进行高层剔除,从而剔除掉不可能发生碰撞的三角形;最后,针对可能碰撞的三角形特征对进行精确相交测试,返回发生第一次碰撞时间,完成碰撞检测。经过复杂度分析和实验论证,该算法响应速度快,在结构复杂物体的连续碰撞检测中效率较高,对于非凸体也可适用。

图形硬件加速的柔性物体连续碰撞检测

给出了一种图形硬件加速的柔性物体连续碰撞检测算法,可以实时检测复杂柔性物体场景中所有物体间碰撞和自碰撞.算法将柔性物体的碰撞检测过程进行流式分解,映射到图形硬件上并行执行,同时使用了并行流式登记算法,在图形硬件上高效实现了变长数据结构.该算法已经使用OpenCL在AMD Radeon HD5870图形硬件上实现.针对一组各具特色的柔性物体仿真场景进行测试,对比CPU（Intel Q6600@2.4GHz）上的单线程优化实现,可以获得9.2~11.4倍的计算加速.

基于GJK的凸体快速连续碰撞检测研究

针对一段时间内的多个运动物体之间的碰撞检测,提出一种基于距离算法(Gilbert-Johnson-Keerthialgorithm,GJK算法)的凸体快速连续碰撞检测算法,该算法主要通过判断一段时间内两物体之间的最小距离是否为零来检测碰撞发生情况。首先利用GJK算法在有限步骤内计算得到最小距离,检测两物体是否发生碰撞;若两物体发生碰撞,进而利用ray-casting算法确定发生碰撞的精确位置,根据环境要求做出相应响应,调整运动物体位置。仿真结果表明,对多个运动物体间的连续碰撞检测,该算法有较高的实时性和准确性。

并行连续碰撞检测算法综述

在参考大量国内外文献的基础之上,分析了GPU并行计算的连续碰撞检测算法的相关理论、研究现状和研究热点问题。目前,随着计算机图形硬件的快速发展,为了实现大型虚拟复杂动态场景实时性交互、高精度和高执行效率的目的,采用GPU并行计算与碰撞检测先进算法相结合的方式,使得连续碰撞检测算法的应用与发展都有了开创性地变革。最后对其技术难点和发展方向进行了总结与展望。

基于空间线性投影的连续碰撞检测算法

为提高复杂的高精度模型在物理仿真中的连续碰撞检测效率,本文提出了一种基于空间线性投影的连续碰撞检测算法。算法采用两级碰撞算法框架,在高层剔除阶段,综合考虑构造难度与剔除效果,确定使用离散导向多面体包围盒(26-DOPs)对基本图元进行第一次剔除;在低层剔除阶段,针对非穿透性滤波器(DNF)只能剔除不满足共面条件的碰撞对这一弊端,提出空间线性投影滤波器(Sptial Linear Projection Filter,SLPF)对不满足内部条件的碰撞对进行剔除;综合使用这两个滤波器,对基本图元进行第二次剔除。在funnel数据集和cloth;all数据集上进行实验,相比于仅使用非穿透性滤波器,结合使用非穿透性滤波器和空间线性投影滤波器时,点面碰撞剔除效率分别提高了6.71%和20.11%,边边碰撞剔除效率分别提高了5.37%和15.98%。

有趣的连续碰撞问题

在物体间连续发生碰撞的问题中，由于命题者的精心设计，有的问题不但思想性很强，同时也非常有趣，下面，选析几例，供赏析。

基于网格拓扑优化的连续碰撞检测算法

传统连续碰撞检测算法处理变形三角网格模型时需要大量冗余元素测试。为此,提出一种基于网格拓扑优化的连续碰撞检测优化算法。为减少冗余元素测试,在底层剔除使用2个步骤,采用网格拓扑进行优化,使相邻三角面片不必执行所有的15对元素测试,并使用额外包围盒进一步剔除不相交基元。实验结果表明,该算法可以减少大量的不必要元素测试,提高剔除效率及连续碰撞检测的整体性能,相比额外包围盒算法元素测试个数约减少了5/6,相比三角形表示算法和孤儿集算法元素测试个数约减少了一半。

基于两级非渗透滤波的连续碰撞检测算法

为提高高精度模型在物理仿真中的碰撞检测效率,提出了一种基于两级非渗透滤波的连续碰撞检测算法,对无碰撞可能性的基本图元对进行快速剔除。首先,通过给基本图元增加额外的层次包围盒,对没有发生重叠的基本图元对进行第一级滤除;其次,采用代数滤波器对通过第一级滤除的基本图元对进行低层滤除。实验结果表明,本方法不仅可以有效地检测出碰撞信息,而且可以在物体发生大幅度形变时发挥较好的滤波特性。

布料与精细建模物体间的碰撞检测算法研究

为解决布料与精细建模物体间碰撞检测速度慢、剔除率低等问题,提出简化模型的有向包围盒(OBB)算法和使用深度神经网络优化的连续碰撞检测(CCD)算法提高碰撞检测效率。在粗略检测阶段,提出一种简化模型的OBB算法,对于精细建模物体使用二次误差度量的表面简化法对精细模型进行简化,将简化后的模型嵌入原模型中,并利用一种快速自适应的OBB算法对简化后的模型构建包围盒。对于布料模型,构建固定球形-轴向混合包围盒和碰撞检测包围盒树。在精确检测阶段,采用全连接深度神经网络学习滤波器剔除在粗略检测阶段未发生碰撞的碰撞对,使用训练后的最优深度神经网络模型优化连续碰撞检测算法。实验结果表明,使用简化程度为90%的模型构建的OBB可以完全替代原模型的OBB,所提简化模型的OBB算法与传统OBB包围盒算法及快速自适应包围盒算法相比,在耗时上分别缩短了约64.6%、35.8%。在布料与精细建模物体交互的场景下,使用深度神经网络优化的CCD算法比使用不同类型滤波器优化的CCD算法速度更快,耗时缩短了约7%~11%。

多体系统动力学碰撞问题研究综述

对近年来多体系统碰撞动力学研究进展进行了评述,包括碰撞动力学建模理论、数值算法和实验方面的进展情况.根据各自不同假设条件将建模方法分为冲量动量法、连续碰撞力模型和基于连续介质力学的有限元方法,比较了各种建模方法在碰撞过程描述和数值性态方面的优势和局限性;对碰撞动力学实验在非接触式测量方面取得的最新进展进行了介绍,总结了实验对以上建模理论的验证研究,展示了实验研究方面的一些新发现.最后基于工程实际的需求提出多体系统碰撞动力学面临的新挑战.

多核加速的并行碰撞检测

针对复杂场景中碰撞检测算法无法满足实时性要求的问题,通过分析影响碰撞检测算法并行度的主要因素,提出一种基于数据分块思想的并行碰撞检测算法.在初始化阶段,将场景数据从空间角度进行分块;在碰撞检测阶段,由每个处理器处理一块数据以实现包围盒并行更新,同时利用静态和动态相结合的任务分配策略实现碰撞检测的并行化.在16核和24核处理器模式下与已有算法进行对比实验的结果证明,文中算法能够提升碰撞检测速度,同时具有很好的兼容性.

基于SIMD指令的柔性物体并行碰撞检测

复杂场景中柔性物体间的碰撞检测依然难以满足交互设计的要求.为了提高处理速度,文中给出了一种充分利用现代CPU的并行处理能力的碰撞检测算法.算法基于两方面的并行处理:即基于SIMD指令的指令级并行处理和基于多线程的任务级并行处理.算法给出了一种针对SIMD指令特别优化的k-DOP模型——SIMD-DOP,从理论上分析了该包围盒的高效性,并与常规的16-DOP和24-DOP进行了运行效率对比.通过使用SIMD-DOP同时在多核间进行负载均衡,算法获得了优化的并行加速.文中算法已经在一台16核工作站上针对一组复杂测试场景进行了验证.

含关节滚动轴承的多体系统碰撞动力学研究

为能深入揭示多体系统外部碰撞作用与关节滚动轴承动态载荷变化规律之间的映射关系,基于多体动力学理论、Hertz接触理论及连续碰撞力模型,提出一种可描述含关节滚动轴承多体系统碰撞动力学行为的建模方法。基于该方法,以含深沟球轴承的曲柄滑块机构及具有弹性支撑的目标刚体组成的碰撞多体系统为分析对象,深入探讨该类复杂非连续动力学系统动态响应。研究表明,碰撞作用不仅对系统宏观动力学性态产生影响,同时导致关节滚动轴承运动副等效约束反力及轴承各滚动体载荷发生突变。

漂浮基空间柔性机械臂在轨捕获碰撞分析

针对漂浮基空间柔性机械臂执行抓捕任务过程中的碰撞问题,提出了一种当机械臂末端与目标物发生碰撞时分析系统响应的方法。首先,运用悬臂梁模型和假设模态法建立了考虑臂杆空间柔性变形时空间柔性机械臂的运动学模型;然后,以赫兹阻尼模型模拟软接触碰撞过程,结合拉格朗日方程建立了系统碰撞动力学方程,并推导了关节处于自由和完全受控两种状态时在末端激励下系统的响应方程;最后,通过数值仿真实验分析了机械臂关节处于特定状态下,在末端与目标物产生碰撞接触时漂浮基空间柔性机械臂的响应。数值仿真结果表明空间柔性机械臂在执行在轨捕获任务时,由于接触碰撞产生的碰撞力可能会很大,关节承受力矩甚至可能超过其物理承受极限,同时由于碰撞冲击产生的臂杆位于运动平面内和垂直于运动平面的柔性变形大小相当,在研究柔性机械臂的碰撞响应时应当同时考虑。

基于RFID系统的改进Q值防碰撞算法

射频识别系统中UHF阶段的Q值防碰撞算法,利用参数Q值的变化动态地改变识别帧中的时隙数,以获得更高的识别效率。基于此算法,本文提出了一种改进算法。在识别帧开始时,引入一种连续碰撞检测机制,对识别标签数量进行预测,迅速地调整出最佳的Q值。通过仿真实验,系统的效率得到了提高。

虚拟齿轮测量中心的碰撞算法

介绍了虚拟齿轮测量中心的概念,同时根据齿轮测量中心测头形式将测头与工件碰撞检测分为触测式碰撞和连续扫描式碰撞,结合国内外的碰撞检测算法,分析算法在虚拟齿轮测量中心两种碰撞检测中的应用。