基于图像空间的快速碰撞检测算法

为了满足日益复杂的虚拟环境中碰撞检测的高实时性要求,提出一种基于图像空间的快速碰撞检测算法,有效利用了图形处理器(GPU)的加速功能。该算法以基于物体空间的凸块层次二叉树技术及方向包围盒(OBB)之间的碰撞检测为前提,可快速排除场景中明显不相交的凸块;然后通过生成的凸块潜在碰撞检测集,在RECODE算法的基础上,得到一种运行效率更高的碰撞检测算法。实验结果表明,在同等复杂的虚拟环境中,尤其是复杂度较高的虚拟环境中,该算法具有更高的碰撞检测实时性,取得了良好的效果。     

RECODE: an image‐based collision detection algorithm

Object interactions are ubiquitous in interactive computer graphics, 3D object motion simulations, virtual reality and robotics applications. Most collision detection algorithms are based on geometrical object‐space interference tests. Some algorithms have employed an image‐space approach to the collision detection problem. In this paper we demonstrate an image‐space collision detection process that allows substantial computational savings during the image‐space interference test. This approach makes efficient use of the graphics rendering hardware for real‐time complex object interactions. Copyright © 1999 John Wiley & Sons, Ltd.     

虚拟装配中快速碰撞检测算法的研究与实现

针对虚拟装配中碰撞检测的特殊要求，提出了一种基于包围盒与空间剖分法的两级碰撞检测算法HSDHBB。该算法首先用空间剖分法找出潜在的相交区域，然后用包围盒求得碰撞的三角面片对和精确的碰撞点。给出了层次包围盒树的构造方法和空间网格的剖分方法，在空间剖分中采用哈希表的数据结构加快检索速度。最后，在CATIA环境中实现了该算法，结果表明该算法能够满足虚拟装配系统的实时性和精确性的要求。     

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

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

基于质点-弹簧模型碰撞检测算法的改进

碰撞检测技术在织物的模拟等方面中有着广泛的应用.在采用质点-弹簧模型对柔性表面进行建模,对网格曲面进行三角划分后,为环境中的物体建立各自的方向包围盒(OBB).用改进的碰撞检测和自碰撞检测算法对柔性织物及其所处三维空间中的物体进行处理,提高了柔性织物动态仿真的速度.     

基于Sphere-OBB的改进碰撞检测算法及其应用

静态或动态环境中两个或者多个几何模型之间的碰撞检测是计算机图形学基础问题之一,基于层次包围盒的碰撞检测算法是一种比较有效的碰撞检测算法。提出了OBB包围盒与球包围盒相结合的高效碰撞检测算法,该算法既具有OBB的包围紧密性,又具有球包围盒的测试简便性。用高效的球包围盒排除大量距离远的不相交物体,剩下距离近的物体用分离轴测试,其中一些分离轴效率更高应该优先被测试。将该算法用于虚拟针灸训练系统,实验结果表明算法减少了查询时间并增强了实时性。     

Hybrid image‐based collision detection in Java 3D

Collision detection is highly important in computer graphics and virtual reality. Most collision detection methods are object‐based, relying on testing the geometrical interference of objects, and their performance therefore depends on the geometrical complexity of the objects. Recently, image‐based methods have gained increasing acceptance for their simplicity in implementation, robustness with respect to the object geometry, and the potential to distribute the computational burden onto graphics hardware. However, all existing image‐based methods require direct calls to OpenGL, but so far there is no direct way to access OpenGL through the Java 3D API. Although Java 3D provides its own built‐in collision detection classes, they are either incorrect or inefficient. In this paper, we present a hybrid image‐based collision detection method in Java 3D, which incorporates the Java 3D built‐in collision detection and the image‐based collision detection in our specially devised scene graph. In addition, we take advantage of the fact that the 3D position of successive offscreen views (i.e. virtual views perceived by the probing object) does not change significantly and thereby reduce the occurrences of offscreen rendering, so that the collision detection becomes even faster (up to 50% in our case). Experimental results prove the correctness and efficiency of our method. Copyright © 2006 John Wiley & Sons, Ltd.     

OSH碰撞检测的改进算法

Tescher提出的OSH碰撞检测算法,因算法的有效性被应用在需要提供空间映射对的各种场合。但算法仅仅通过求解重心坐标的权值来判断是否侵入,而无法测试侵入深度和求解接触法线,造成算法对于形成合理碰撞响应有一定限制。针对这一问题,提出使用SDM方法求解侵入参数,加入惩罚力提供变形体碰撞响应,结合约束力保证距离面积体积的守恒,从而形成有效的OSH碰撞检测环境。     

基于图像空间的复杂模型碰撞检测算法

提出一种使用图形硬件用于复杂模型间的快速的碰撞检测算法.算法是基于CULLIDE的执行GPU可见性查询来减少物体模型间没有邻近特征的子集,描述了一个分类方案计算物体潜在碰撞集和碰撞自由子集,提高了裁减的性能.为了减少CPU的负载,利用GPU的可编程性,在GPU上进行精确的物体相交计算.     

基于改进碰撞检测算法的肝门静脉结扎仿真

为了对虚拟肝脏手术中肝门静脉的结扎进行仿真,提出了一种改进的碰撞检测算法。改进的碰撞检测算法主要包括三个方面:缝合线的自碰撞检测、缝合线的运动分解,以及缝合线与肝门静脉模型的碰撞检测。缝合线的模拟采用跟踪控制点FTL算法,采用包围球法对缝合线进行自碰撞检测;提出运动分解方法来防止缝合线发生自穿透;将包围球法和空间网格划分法相结合,实现缝合线和肝门静脉之间的碰撞检测;同时,肝门静脉的形变采用设置刚体核的几何模型来模拟,使用虚拟弹簧振子来实现结扎时的触觉反馈。将改进的碰撞检测算法运用到虚拟肝脏手术中,满足虚拟场景中真实感和实时性的要求。     

ADS-B信息的球状模型飞行冲突探测算法

随着空中飞行流量日趋增大,飞行器自由飞行过程中发生碰撞的可能性也越来越大,针对飞行器周围空域进行合理划分,给出了一种基于ADS-B信息的球状模型飞行冲突探测算法.该算法结合ADS-B的原理和特点,运用球状模型取代圆柱体模型对飞行器周围空域进行建模,然后进行冲突目标初选,对可能发生冲突飞行器的位置、航迹交叉点、距离进行计算并预估到达时间,与门限值比较判断能否发生碰撞,最后,对算法进行仿真.结果验证:算法能够更准确并且快速地完成冲突探测,并对驾驶员发出冲突告警,对防止飞行冲突的发生具有积极作用.     

基于着色算法的并行碰撞检测算法*

提出了一种基于着色算法的并行碰撞检测算法,利用AABB包围盒较好的紧密性和包围球计算简单的优点以及并行算法中的分治策略构建物体的混合包围体层次(S-AABB);然后采用破对称技术中的典型算法——着色算法,将每棵任务树编码,以产生各不相同的类别,并将不同的类别指派到不同的并行机,在并行机上采用多线程技术执行相同的类别的任务树的遍历,来检测是否有碰撞发生。实验结果表明,与现有的经典的I-COLLIDE等算法相比,该算法在效率、精确性方面具有明显优势,能够满足交互式复杂虚拟环境的实时性和精确性的要求。     

改进的基于AABB包围盒的碰撞检测算法

介绍了一种改进的基于AABB包围盒的碰撞检测算法,通过对对象不断的分割逐步构造出贴近对象的层次包围盒,在碰撞检测阶段对其逐层遍历以实现精确而快速的碰撞检测.实验结果表明,与层次包围球算法相比,该方法在构造二叉树和进行精确的碰撞检测时,性能都有较为明显的提高.     

虚拟环境中优化的OBB碰撞检测算法研究

碰撞检测是计算机图形学的研究热点之一,基于包围盒的碰撞检测算法是一种比较有效的碰撞检测算法.OBB紧密性较好,能有效提高系统的检测效率,但是相交测试的代价太大,根据AABB易于构造、计算简单但紧密性差的特点,提出并实现了优化的OBB碰撞检测算法.实验结果证明:优化算法能够较大幅度地提高了碰撞检测的实时性能,取得较好的效果.     

基于空间剖分的碰撞检测算法研究

针对虚拟环境中物体碰撞检测效率不高的问题,提出了一种基于空间剖分的碰撞检测算法。利用物体空间分布特性以及运动物体碰撞行为的局部性,先用空域分割中定性-定量结合的方法快速确定可能碰撞的物体对,再用混合层次包围盒进行精确测试,明显地提高了碰撞检测速度。实验分析表明,该算法不仅可实现复杂场景下多个物体同时发生碰撞的检测,也能保证算法在物体高速运动时的有效性。     

一种基于感兴趣区域提取的新型SVD图像压缩算法

提出了一种基于感兴趣区域提取的新型奇异值分解（SVD）图像编码算法（SODSVD）。根据图像的区域复杂度、视觉注意等指标运用感兴趣区域提取技术将图像自适应分块,而对每一小块,根据其复杂度进行不同秩的奇异值分解算法,从而达到图像压缩的目的。同时还提出了一种简单的基于感兴趣区域的图像划分策略。实验结果表明,在PSNR和bpp等评价指标上,新方法有明显优势。     

基于层次包围盒的碰撞检测算法的存储优化

介绍了基于层次包围盒的碰撞检测算法的存储优化方法。该方法从存储空间的角度来改进基于AABB树的碰撞检测算法。根据AABB树的构造过程,减少内部节点的AABB包围盒的存储字节数;基于快速三角形相交测试算法,从叶节点结构里去掉包围盒信息,将叶节点从存储结构中删除。实验表明,利用AABB包围盒和叶节点的存储优化,既减少了算法的存储空间又加快了算法的执行时间。     

基于AABB树的碰撞检测算法的内存优化

介绍了从存储空间角度来改进基于AABB树的碰撞检测算法的方法.根据有关三角形间快速相交测试算法和三角形与包围盒间的快速相交测试算法,略过包围盒间的相交测试,从叶节点结构里去掉包围盒信息,将叶节点从存储结构中删除.对一棵含有N个节点的 AABB 树而言,可以节约一半节点的内存空间.实验表明,利用 AABB 树叶节点的内存优化,减少了算法所需的内存空间且加快了算法的执行时间.     

改进型蜂窝状空间分解的实时碰撞检测

目前高速、精确的碰撞检测研究已经成为了虚拟现实领域研究的热点。在图像空间的碰撞检测研究基础上,设计了基于蜂窝状空间分解的碰撞检测算法。首先完成非碰撞多面体的快速剔除,对碰撞多面体局部进行空间分解,进而,反向投影构建碰撞模型局部子包围盒,完成沿相反方向进行子包围盒蜂窝状空间分解,将碰撞检测转化为判断在下一帧中多面体蜂窝子空间内局部子多面体截面到对方阈值线的距离值与对方所设定阈值大小的关系问题,完成任意多面体间的精细碰撞检测。摆脱了图形硬件信息存储的限制,也使基于图像空间的碰撞检测适用于任意多面体,提高了碰撞检测的速度和精度。     

Efficient collision detection using a dual OBB-sphere bounding volume hierarchy

We present an efficient algorithm for collision detection between static rigid objects using a dual bounding volume hierarchy which consists of an oriented bounding box (OBB) tree enhanced with bounding spheres. This approach combines the compactness of OBBs and the simplicity of spheres. The majority of distant objects are separated using the simpler sphere tests. The remaining objects are in close proximity, where some separation axes are significantly more effective than others. We select 5 from among the 15 potential separating axes for OBBs. Experimental results show that our algorithm achieves considerable speedup in most cases with respect to the existing OBB algorithms.