An Adaptive Spatial Subdivision of the Object Space for Fast Collision Detection of Animated Rigid Bodies

Collision detection tests between objects dominate run time simulation of rigid body animation. Traditionally, hierarchical bounding box tests are used to minimize collision detection time. But the bounding boxes do not take shapes of the objects into account which results in a large number of collision detection tests. We propose an adaptive spatial subdivision of the object space based on octree structure to rectify this problem. We also present a technique for efficiently updating this structure periodically during the simulation.     

Binary Ostensibly-Implicit Trees for Fast Collision Detection

We present a simple, efficient and low-memory technique, targeting fast construction of bounding volume hierarchies (BVH) for broad-phase collision detection. To achieve this, we devise a novel representation of BVH trees in memory. We develop a mapping of the implicit index representation to compact memory locations, based on simple bit-shifts, to then construct and evaluate bounding volume test trees (BVTT) during collision detection with real-time performance. We model the topology of the BVH tree implicitly as binary encodings which allows us to determine the nodes missing from a complete binary tree using the binary representation of the number of missing nodes. The simplicity of our technique allows for fast hierarchy construction achieving over 6× speedup over the state-of-the-art. Making use of these characteristics, we show that not only it is feasible to rebuild the BVH at every frame, but that using our technique, it is actually faster than refitting and more memory efficient.     

A Coherence-based Collision Detection Method for Dressed Human Simulation

In this paper, paper we present a coherence-based method to detect collisions between the garment and human model for dressed human simulations. Based on the property of coherence, collisions can be rapidly detected by tracking the movement of the most likely geometric elements to collide. The voxel technique is employed to quickly identify the potential collision region. Experimental results show that our method is very efficient.     

虚拟场景中碰撞检测实用算法研究

碰撞检测是虚拟系统中的一项关键技术,也是提高虚拟系统现实感的一个重要因素。许多算法对碰撞检测的精度进行了研究,但对一个大型的虚拟场景,碰撞检测的范围则是影响仿真速度的主要因素。该文在包围盒检测技术研究的基础上,根据大型虚拟场景的特点,提出了碰撞发生的局部性、主动性、相邻性的观点,由此给出了虚拟游览系统中碰撞检测的DS算法,通过在本单位虚拟战场仿真系统的应用及分析表明,该算法对提高虚拟系统的运算效率是非常有效的。     

一种快速的基于球体混合重建的碰撞检测算法

为了解决虚拟特征和虚拟环境中虚拟物体的相交问题,必须对实时的虚拟应用环境实施快速的碰撞检测.提出了基于球体混合重建的碰撞检测算法,对球体混合表面提出了一个子线性时间复杂性的重建过程;利用四元组构造变换范围,扩展了从线性到球形混合的构造变换方法;采用循环划分的方法完成了由球体混合到线性混合的分解过程.尽管这个方法的实现过程较线性的方法更难些,但算法的执行过程所需时间却与线性方法相差无几,其复杂性也与线性结构的相同.     

USSCD：一个基于均匀空间分割的快速碰撞检测算法

对于存在大量运动物体的虚拟环境，碰撞检测往往成为影响系统计算效率的瓶颈，为提高多体碰撞检测的效率，提出了一个基于均匀空间分割的快速多体碰撞检测算法——USSCD，该算法首先将物体空间均匀分割成一系列单元格，然后在每个单元格，通过基于AVL排序的扫描排除法进行碰撞检测，同时依据物体的分布密度，提出了一个计算单元格尺寸的优化方法，通过一系列实验，测试了USSCD算法的性能，并与I-COLLIDE算法进行比较，实验结果表明，在均匀分布条件下，当物体数量较大时，USSCD的效率高于I-COLLIDE算法，而且，USSCD算法的效率基本不受物体运动相关性的影响。     

虚拟环境中的快速碰撞检测算法

该文在Lin-Canny算法的基础上,提出一种虚拟环境下三维实体的动态、实时碰撞检测算法,并应用于柔性制造仿真系统中以检查工作环境中物体间的干涉状况,应用结果表明该算法在物体结构较复杂或运动的连贯性不好的情况下仍有较好的性能。     

虚拟坦克装甲车运动仿真中的碰撞检测算法研究

提出了一种新的虚拟坦克装甲车运动仿真的混合碰撞检测算法，该算法是先用帧与帧之间的画面连贯性进行判断，若帧与帧之间的物体不一致，则用方向包围盒来进行碰撞检测，为了避免两帧之间发生穿透，则有线段与包围盒的重叠测试进行穿透测试。此算法可以很好解决坦克装甲车的运动仿真中的碰撞检测。满足实时性要求。     

基于DDA的碰撞检测及碰撞仿真

碰撞检测是基于物理的动画,计算机辅助没计,计算机辅助制造,计算几何,虚拟现实,机器人等领域必须解决的关键问题,目前仍是研究热点.非连续变形分析方法是一种较新的土木工程领域的数值模拟技术,可以分析不连续块体的运动.将非连续变形分析方法引入到基于物理动厕领域.在计算辅助设计软件设计的虚拟物理场景下,仿真了汽车撞墙和车辆相撞.仿真结果显示:应用非连续变形分析方法可以成功的实现精确的碰撞检测和模拟真实的碰撞响应,在不连续变形、多块体碰撞仿真方面有较大优势.     

织物仿真中的冲突检测和处理

冲突检测以及冲突处理一直是织物仿真的“瓶颈”问题。该文论述了对柔性物体如织物与刚体的冲突检测问题。通过正冲突物体表面周围建立一个很狭小的相当于防护屏的力场来避开冲突。将这个力场分割成一些连续不重迭的完全围绕着表面的小单元，一旦某个点要进入某个单元，就产生一个排斥力，这个力的大小和方向由速度、法向、点与表面的距离决定。     

一个计算凸多面体间碰撞点的快速算法

计算两个物体之间的碰撞点是碰撞响应的基础,也是一项系统开销很大的任务.因此,研究碰撞点快速求解算法对碰撞响应的实时性具有重要意义.该文提出了一个算法,当在虚拟环境中检测到碰撞时,应用此算法可以在碰撞响应之前快速计算出两个物体之间的准确碰撞时间,并能计算出此时两个物体之间的碰撞点.     

作物可视化中的碰撞检测及响应研究

将碰撞检测与响应技术引入作物可视化生长模拟,针对以NUR13S曲面表示的作物叶片,提出了一种基于曲 面分割技术及混合层次包围盒实现作物叶片间碰撞检测的方法。首先采用节点插入技术分割叶片曲面,然后为分割 后的叶片曲面建立轴向包围盒(AAI313)与固定方向凸包(FDH)的混合层次包围盒树:根节点采用AA1313包围盒,以快 速排除不可能相交的叶片;其它层节点采用FDH包围盒,以保证精确地判定距离较近的叶片间碰撞状态。在此基础 上,根据作物叶片形态变化规律,提出了较合理、有效的冲突响应机制。实例分析表明,所建立的算法可有效地应用于 作物叶片碰撞的模拟实现。     

碰撞检测技术在空间飞行器视景仿真中的应用

视景仿真技术是空间飞行器系统仿真中的关键技术之一。该文阐述了碰撞检测技术在视景仿真中的应用,旨在提高飞行器视景仿真的逼真度。文中列述了视景驱动软件Vega的8种碰撞检测方法,分析了各种方法的特点,并展示了各种碰撞检测方法应用于空间飞行器视景仿真中的结果,包括卫星星下点轨迹绘制、卫星照相效果显示等,从而证实了将碰撞检测技术应用于空间飞行器视景仿真能取得良好的仿真效果。该文为空间飞行器视景仿真以及碰撞检测技术应用者提供了应用范例,具有一定借鉴价值。     

Kinetic Collision Detection for Convex Fat Objects

We design compact and responsive kinetic data structures for detecting collisions between n convex fat objects in 3-dimensional space that can have arbitrary sizes. Our main results are:

碰撞检测在虚拟仿真系统中的应用

碰撞检测对于增强虚拟仿真系统的拟真度和沉浸感有着重要的作用。通过对现有碰撞检测程序库的整合与改进,设计并实现了虚拟仿真系统的碰撞检测模块,实验证明,该模块能够较好地满足虚拟仿真系统对碰撞检测的要求。     

实时碰撞检测算法的探讨与研究

本文对碰撞检测算法的分类进行了阐述,并比较了按层次包围盒法分类的包围盒AABB、包围球、方向包围盒OBB、固定方向凸包的包围盒FDH、时空包围盒检测算法（STBB）的构造难度高低,存储量大小和相交测试复杂度高低等方面。同时,也对空间分割法下的各类算法进行了分析。最后介绍了两种新趋势下的混合碰撞检测法进行了归纳研究,并总结了算法的优劣和新的方向。     

基于Z_buffer值的碰撞检测算法研究

碰撞检测算法是增强虚拟环境的逼真感和沉浸感的一个重要手段。原有的碰撞检测算法计算复杂，在复杂大范围三维场景绘制时会占用系统大量计算资源。针对传统碰撞检测算法的缺点，提出了一种基于缓冲区Z_buffer值的快速碰撞检测算法。该算法充分利用场景绘制时的变换矩阵和深度信息，实现了用户以第一人称在虚拟场景中漫游时进行快速碰撞检测与响应。实验证明该算法计算简单、速度快且与场景复杂度无关。     

虚拟漫游中的碰撞检测问题的解决方法

碰撞检测是虚拟漫游中的关键技术。在进行虚拟漫游时,为了避免观察者飞人地下或穿墙而过等不真实情况的发生,就需要进行碰撞检测。解决虚拟漫游中碰撞检测问题的一种方法是：将场景中运动的观察者转化为一个视点,场景中的物体表面剖分成三角形,运动的观察者与静态的虚拟场景之间的碰撞检测问题,就转化为点与三角形之问的碰撞检测问题;此方法的优化方法是对场景中的三角形进行过滤,以减少不必要的计算。文中给出了此方法的具体算法及其优化方法。     

Broadmark: A Testing Framework for Broad-Phase Collision Detection Algorithms

Research in the area of collision detection permeates most of the literature on simulations, interaction and agents planning, being commonly regarded as one of the main bottlenecks for large-scale systems. To this day, despite its importance, most subareas of collision detection lack a common ground to test and validate solutions, reference implementations and widely accepted benchmark suites. In this paper, we delve into the broad-phase of collision detection systems, providing both an open-source framework, named Broadmark, to test, compare and validate algorithms, and an in-deep analysis of the main techniques used so far to tackle the broad-phase problem. The technical challenges of building this framework from the software and hardware perspectives are also described. Within our framework, several original and state-of-the-art implementations of CPU and GPU algorithms are bundled, alongside three benchmark scenes to stress algorithms under several conditions. Furthermore, the system is designed to be easily extensible. We use our framework to bring out an extensive performance comparison among assembled solutions, detailing the current CPU and GPU state-of-the-art on a common ground. We believe that Broadmark encompasses the principal insights and tools to derive and evaluate novel algorithms, thus greatly facilitating discussion about successful broad-phase collision detection solutions.     

Efficient Collision Detection among Moving Spheres with Unknown Trajectories

Collision detection is critical for applications that demand a great deal of spatial interaction among objects. In such applications the trajectory of an object is often not known in advance either since a user is allowed to move an object at his/her will, or since an object moves under the rules that are hard to describe by exact mathematical formulas. In this paper we present a new algorithm that efficiently detects the collisions among moving spheres with unknown trajectories. We assume that the current position and velocity of every sphere can be probed at any time although its trajectory is unknown. We also assume that the magnitude of the acceleration of each sphere is bounded. Under these assumptions, we represent the bounding volume of the sphere as a moving sphere of variable radius, called a time-varying bound. Whenever the time-varying bounds of two spheres collide with each other, they are checked for actual collision. Exploiting these bounds, the previous event-driven approach for detecting the collisions among multiple moving spheres with ballistic trajectories is generalized for those with unknown trajectories. The proposed algorithm shows an interactive performance for thousands of moving spheres with unknown trajectories without any hardware help.