一种快速的可变形物体的碰撞检测算法

为实现虚拟环境中可变形物体与刚体间实时的碰撞检测,提出了一种快速的基于混合包围盒层次结构的并行碰撞检测算法。算法充分利用包围盒在检测速度和精度上的不同侧重,对可变形物体建立Sphere和AABB混合包围盒层次树,对刚体建立Sphere和OBB混合包围盒层次树;每个物体的混合包围盒层次树又分成上层、中层和下层,每层使用不同的包围盒;在碰撞检测遍历时,上层使用Sphere和Sphere相交检测快速排除不相交物体,在中层使用Sphere和OBB的相交检测进一步排除物体相交的可能性,在下层使用AABB和OBB的相交检测较精确地确定物体是否相交;采用多线程技术,在多核设备上实现并行碰撞检测算法。实验结果表明,与经典的AABB算法相比较,该算法在效率方面具有明显优势,能够满足可变形物体与刚体的碰撞检测要求。     

一种优化的可变形物体碰撞检测算法

对可变形物体的碰撞检测提出了一种优化的加速算法。算法在Sean Curtis[1]等人提出的特征三角形检测算法的基础上,增加了点和边的基本元素动态分配,并且用多叉树代替二叉树,提高了碰撞检测的效率。新算法可以应用于所有以三角形为基本单位的模型,能够显著地减少基本元素对的检测,并且可以和传统的层次包围盒法结合使用。用提出的优化加速算法对连续碰撞检测中的球-布模型和人体模特-服装模型进行了检测,实验表明,改进的算法相比原算法减少了元素检测的对数,缩短了检测时间,性能提升非常明显。     

虚拟手术中快速碰撞检测方法的研究

为了解决虚拟手术的快速碰撞检测问题,提出了一种新的基于层次包围盒的快速碰撞检测方法。文中基于虚拟手术中器官组织是软体模型且规模巨大,而手术器械是刚体模型且结构简单这一特点,从层次包围盒构造、包围盒树遍历和精确相交测试三个方面改进算法。仿真实验表明该算法能正确有效地处理虚拟手术中的碰撞检测,与标准库RAPID对比,随着软体模型规模的增大,该方法能显著提高碰撞检测的效率。     

一种基于骨架的可变形物体建模方法

提出了一种新的基于骨架的混合型的软组织建模方法，用于虚拟手术仿真及手术训练。介绍了通过自动的方法抽取物体的骨架，建立物体的表面物理模型、体物理模型以及对应的计算模型。还介绍了利用骨架进行碰撞检测及外力计算的方法并介绍了实验的软件结构及实验结果。     

在GPU上基于物体空间的碰撞检测

碰撞检测是模拟现实世界关键要素,也是计算机图形学研究的核心内容.提出了一种利用GPU的SIMD、遮挡查询和浮点纹理功能等特性进行碰撞检测的新方法.算法同时遍历一对基于传统的CPU方法的包围体层次树,在遍历的过程中进行所有必要的运算,包括最后的三角形相交测试都是在GPU的顶点着色器和像素着色器中进行的.测试结果显示达到预期的效果.不同于其它的基于GPU的方法,本算法的所有计算都在物体空间中进行,而且对多边形模型的形状和拓扑结构不作任何要求.     

动画柔性可变形物体的弹簧模型研究

连续变形模型通常用控制点网格表示，用这些点间的相互作用模糊弹性属性。该文给出了一个可变形弹簧模型和动画布料的弹力公式，在公式中将布料属性当作外部弹力考虑，可适当适当地设置布料的弹性属性，简单地考虑模型点间的相互作用，较精确地描述布料的行为。     

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

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

机械加工过程仿真中运动物体的碰撞检测

本文提出了一种表达实体的八叉树层次球状模型和基于这种模型的运动物体之间的碰撞检测算法。机械加工过程的图形仿真对ＮＣ程序的检验是十分有用的，因为编程者或加工操作者能够很方便地看到加工的效果。由于在加工过程中，刀具和工件等都是运动物体，而要从图形上直接目测运动物体之间的碰撞情况是十分困难的。所以，本文提出了一种表示运动物体的模型及相应的碰撞检测算法。一个物体可用一个八叉树层次球模型来表示，其运动可以用节点的外接球的球心的运动来表示，它是时间的函数。通过求解满足碰撞条件的方程，我们可以得到两运动物体碰撞时间和位置。本文最后对碰撞检测算法的特性进行了分析。     

虚拟物体间碰撞检测系统的设计

X3D是开放式的基于WEB的虚拟现实3D标准,是XML和VRML集成应用技术。首先介绍了X3D的碰撞检测的模型;其次描述了碰撞检测算法;通过X3D规范中提供的可扩展的插件机制,提出了一种用于X3D的碰撞检测系统的结构,通过测试该系统,它能够在具有大量的运动物体的环境中进行较为准确的碰撞检测,实时性和健壮性也基本上达到应用的要求。     

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

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

大规模柔体的连续碰撞检测算法

目的 针对大规模复杂柔体碰撞检测中速率低的问题,在两级碰撞算法基础上加入新的剔除算法——过滤器,得到了更好的效率。方法 在碰撞检测的高级阶段,通过实验确定基于离散导向多面体包围盒(26-DOPs)的包围盒层次树(BVHs);低级阶段,混合使用代表性三角形和孤集两种方法;增加新剔除算法——过滤器,针对已有的非共线性过滤器(NCF)的缺陷,提出解决方案;提出新的过滤器-条件过滤器(DCF),它在非穿透性过滤器(DNF)和NCF剔除之后生效,进一步提高算法效率。结果 在cloth_ball数据集下,相比于仅使用DNF,使用DNF和NCFI(改进的NCF)时,点面碰撞(VF)测试数量减少了85.90%,而使用DNF+NFCI+和DCF时,这一比例为87.94%。结论 本文算法对于一般情况下的大规模柔体的碰撞检测具有普适性,特别是碰撞处理中发生三角形翻转,DCF和NCF失效的情况下,本文提出的条件过滤器能起到很好剔除作用,提高总体效率。     

基于质点的可变形体自碰撞检测

自碰撞检测是可变形体模拟过程中最耗时的环节,提出一种使用图形硬件的快速算法。算法以质点而非三角形作为自碰撞检测的基本单元,用球体包围以质点为中心的局部区域,再用AABB包围该球体的运动轨迹并将数据组织成纹理送入GPU,通过两遍离屏渲染计算出碰撞对集合及每个碰撞对的碰撞发生时间,算法复杂度为O(n)。实验结果表明,使用该算法在大规模布料模拟中检测自碰撞,效率较高。     

蒙皮骨骼动画的碰撞检测研究

提出了一种利用蒙皮骨骼的特点改进的碰撞检测算法,该算法使用层次包围体为基础,改进了OBB树的生成和更新。实验证明,该算法提高了碰撞检测的效率,能满足复杂3D人物的碰撞检测需求。     

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

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

动态织物与复杂模型的快速碰撞检测方法

柔性物体因为自身的物理机械性能非常复杂,并且材料的多样性、结构的复杂性、形状的不规则性都给柔性物体的造型和运动仿真带来了很大的困难。该文中,选择常见的柔性物体织物为研究对象,以质点-弹簧模型为织物结构模型,提出了一种利用OpenGL的选择模式,快速获得织物模型上所有质点到多面体模型最短距离,从而实现织物与复杂模型之间碰撞检测的方法,该方法充分利用了图形卡硬件的管道渲染功能,可以应用于织物对任意三维多面体模型间的距离测定及碰撞检测,具有较高的通用性。     

基于八叉树精确划分型值点的碰撞检测算法

针对虚拟现实中碰撞检测的快速计算问题,提出一种新的粗略碰撞检测与精确碰撞检测相结合的检测算法。首先利用AABB包围盒法排除不可能相交的物体,然后对可能发生碰撞的包围盒采用八叉树算法进行空间分割,在包围盒内找到由型值点形成的三角形面片,利用三角形面片的碰撞检测算法精确地判断物体是否碰撞。通过与OBB包围盒算法的碰撞检测数据对比,验证了该方法的有效性。     

基于改进粒子群的快速碰撞检测算法研究

针对碰撞检测算法精度低、实时性差等问题,提出了一种基于改进粒子群的快速碰撞检测算法。将粒子群优化算法引入到随机碰撞检测问题中,通过混合层次包围盒缩小粒子搜索空间。利用特征采样将虚拟空间内复杂的碰撞检测转换为二维离散空间中的搜索问题。算法对标准粒子群方程进行了优化处理,通过去除速度项来加快算法后期的收敛速度,在算法中引入高斯扰动缩短粒子跳出局部最优的时间,有效提高了算法的精度。通过实验验证,该算法具有较高的精度、实时性好,能够满足碰撞检测的应用要求。     

融合智能算法的变形体碰撞检测算法研究

针对变形体碰撞检测算法的准确性与实时性问题,提出了一种融合智能算法的变形体碰撞检测算法。在随机碰撞检测的基础上,使用层次包围技术缩小粒子搜索空间,采用一种融合基于量子行为的粒子群算法与差分进化算法的混合智能算法进行搜索。该方法以局部吸引子作为差分变异基础,在扩大种群多样性的同时加快了算法收敛速度,有效地解决了传统智能算法不适应离散空间计算问题以及早熟收敛问题。针对随机碰撞粒子搜索空间特点,混合算法的引入大大提高了碰撞检测算法的检测效率,解决了检测过程中的穿刺与遗漏现象。经实验验证该方法在很大程度上提高了变形体碰撞检测的实时性与准确性。