Enhancing Bounding Volumes using Support Plane Mappings for Collision Detection

In this paper we present a new method for improving the performance of the widely used Bounding Volume Hierarchies for collision detection. The major contribution of our work is a culling algorithm that serves as a generalization of the Separating Axis Theorem for non parallel axes, based on the well‐known concept of support planes. We also provide a rigorous definition of support plane mappings and implementation details regarding the application of the proposed method to commonly used bounding volumes. The paper describes the theoretical foundation and an overall evaluation of the proposed algorithm. It demonstrates its high culling efficiency and in its application, significant improvement of timing performance with different types of bounding volumes and support plane mappings for rigid body simulations.     

Continuous Collision Detection for Ellipsoids

We present an accurate and efficient algorithm for continuous collision detection between two moving ellipsoids. We start with a highly optimized implementation of interference testing between two stationary ellipsoids based on an algebraic condition described in terms of the signs of roots of the characteristic equation of two ellipsoids. Then we derive a time-dependent characteristic equation for two moving ellipsoids, which enables us to develop a real-time algorithm for computing the time intervals in which two moving ellipsoids collide. The effectiveness of our approach is demonstrated with several practical examples.     

Collision Detection for Deformable Objects

Interactive environments for dynamically deforming objects play an important role in surgery simulation and entertainment technology. These environments require fast deformable models and very efficient collision handling techniques. While collision detection for rigid bodies is well investigated, collision detection for deformable objects introduces additional challenging problems. This paper focuses on these aspects and summarizes recent research in the area of deformable collision detection. Various approaches based on bounding volume hierarchies, distance fields and spatial partitioning are discussed. In addition, image‐space techniques and stochastic methods are considered. Applications in cloth modeling and surgical simulation are presented.     

Particle Oriented Collision Detection using Simplicial Coverings and Tetra-Trees

Collision detection (CD) among complex objects in motion is an open question because of its algorithmic complexity. In this paper, we present a CD algorithm between a particle and a complex rigid solid. In order to represent solids, we use a simplicial covering scheme by means of 3‐simplices. With this representation system, complex polyhedra and closed triangle meshes can be represented and used in CD with a particle. A particle can be represented by a point, where the real dimensions of the particle are not important. This CD algorithm has been extended for a particle represented by a sphere which in turn represents an approximation to the particle dimensions. In order to efficiently classify the particles and the simplices of the polyhedra covering, we use a new hierarchical data structure named tetra‐tree that decomposes the space into tetra‐cones. These algorithms also use bounding volumes and temporal and geometric coherence, as well as incremental calculations in order to determine the collision in an efficient and exact way. Because of the use of sign operations with signed volumes and barycentric coordinates, we conclude that operations carried out using this method are more robust and efficient than those used in classic algorithms.     

一种快速的基于并行的碰撞检测算法

提出一种基于并行的碰撞检测算法。该算法主要采用并行算法中的分治策略建立环境中每个物体的平衡包围盒树,通过遍历每两棵包围盒树形成对一任务树的遍历,采用并行算法中的流水线技术,利用划分进程遍历任务树从而加速碰撞检测算法。该算法在进程中也应用了多线程技术,因而能运行于单处理机和多处理机上。     

虚拟环境中的碰撞检测方法

忆速精确的碰撞检测对提高虚拟环境的真实性和增强虚拟环境的沉浸感有着至关重要的作用,而虚拟环境的复杂性和实时性又对碰撞检测提出了更高的要求。本文详细介绍了两种碰撞检测方法,一是著名的基于方向包围盒的方法,二是我们提出的基于固定方向凸包的方法,并对它们进行了分析与比较,实验证明,我们的方法不仅在性能上有所提
提高,而且能较好地适应复杂环境的要求。     

车辆碰撞事件与碰撞损伤的检测方法

提出了一种针对车辆碰撞事件的远程检测方法. 该方法利用机器学习技术分析车辆的速度和加速度信号, 从而对车辆的行驶状态进行在线监测. 车载的前端设备实时的采集速度和加速度信号, 初步识别出可能的碰撞信号并通过无线网络发送给后台服务器. 后台服务器对碰撞信号进行准确识别, 并判断车辆的损伤程度. 论文给出了碰撞事件和碰撞损伤的检测方法, 并进行了实验测试, 结果表明该方法是有效的.     

Graceful Degradation of Collision Handling in Physically Based Animation

Interactive simulation is made possible in many applications by simplifying or culling the finer details that would make real-time performance impossible. This paper examines detail simplification in the specific problem of collision handling for rigid body animation. We present an automated method for calculating consistent collision response at different levels of detail. The mechanism works closely with a system which uses a pre-computed hierarchical volume model for collision detection.     

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:

适用于移动设备的实时碰撞检测算法

针对移动设备性能低、屏幕小等缺陷,提出一种快速有效的碰撞检测和响应算法。该算法使用多层次碰撞检测和动态多分辨率网格划分的方法来减少碰撞检测的计算次数,提高了算法性能。在碰撞响应中,为了精确计算碰撞的交点以符合物体运动的物理规律,采用时间间隔二分查找算法来保证碰撞的计算精度和系统效率。为某公司设计的移动台球游戏的运行结果表明该算法具有较高的性能和良好的实时交互性,满足用户的需求。     

适用于复杂场景的碰撞检测算法研究

创建虚拟场景不仅要进行静态建模,更重要的是进行动态建模。而且物体之间的实时碰撞检测是关键。首先对常用检测算法的检测效率进行了分析和比较。然后重点针对复杂虚拟场景中吉有大量物体的特点,提出了混合包围盒碰撞检测算法。该算法利用帧与帧之间的时间和几何相关性,把对（cn^2＋m）个对象的动态跟踪转化为它们在三个坐标轴上的投影的排序问题,把时间复杂度由O（n^2）降低为O（n）。并引入树的深度的概念,根据不同的应用场合合理控制检测深度以加快检测速度。理论分析和仿真计算都表明,该算法能够满足多达几百个运动物体的实时交互碰撞检测。     

机器人碰撞检测方法形式化

为应对更为复杂的任务需求,现代机器人产业发展愈发迅猛.出于协调工作的灵活性、柔顺性以及智能性等多项考虑因素,多臂/多机器人充分发挥了机器人的强大作用,成为现代机器人产业的重要研究热点.在机器人双臂协调运行当中,机械臂之间以及机械臂与外部障碍物之间容易发生碰撞,可能会造成财产损失甚至人员伤亡.对机器人碰撞检测方法进行形式化验证,以球体和胶囊体形式化模型为基础,构建基本几何体单元之间最短距离和机器人碰撞的高阶逻辑模型,证明其相关属性及碰撞条件,建立机器人碰撞检测方法基础定理库,为多机系统碰撞检测算法可靠性与稳定性的验证提供技术支撑和验证框架.     

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.     

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

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

一种优化的机器人碰撞检测算法研究

提出了一种基于Vclip的优化碰撞检测算法,利用Vclip算法对AABB包围盒进行底层碰撞检测计算,用GPU的遮挡查询等特性进行三角形相交测试,以提高对虚拟物体进行碰撞检测的精确性与实时性。算法已成功应用于课题组自行研制的6自由度小型工业机器人的仿真控制系统中,实验结果表明,其算法具有高效、精确、实时性高等特点,能使控制系统对工业机器人的控制更为流畅。     

基于骨骼的3D角色的碰撞检测

基于骨骼的角色实现快速碰撞检测。该算法以层次包围盒（OBB）为基础,通过为每个骨骼模型建立包围盒,运用分离轴理论计算包围盒的相交测试。该方法能有效地用于3D游戏引擎中碰撞检测的实现。     

Reliable Collision Detection for Time-Dependent Parametric Surfaces

We improve on an algorithm by Von Herzen, Barr, and Zatz (HBZ) to detect geometric collisions between pairs of time-dependent parametric surfaces. The HBZ algorithm uses upper bounds on the parametric derivatives to guarantee detection of collisions and near misses, thus avoiding the defects of algorithms which sample the surfaces, possibly missing sharp spikes. Unfortunately, the user of the HBZ algorithm must supply not only routines computing the surface functions, but also routines bounding every component in the Jacobian of these surface functions over an arbitrary parametric range. Although they give helpful analyses for several types of surfaces, HBZ admit the need to provide Jacobian bounding routines as a disadvantage.We propose using interval arithmetic to bound functional values over a parametric input range, thus eliminating the need for the Jacobian entirely. Our interval version of the collision detection algorithm assumes neither bounded differentiability nor satisfaction of the Lipschitz criterion. Therefore, our code can detect geometric collisions for the much larger class of surface functions for which bounds on the function values can be computed using interval arithmetic. We contrast our code to that of HBZ and give timing comparisons.