基于包围盒与空间分解的碰撞检测算法

本文提出了一种基于包围盒方法与空间分解方法相结合的碰撞检测算法,用于解决变形体的碰撞检测问题。该算法首先用包围盒来快速判断物体之间是否相交,如果相交则进一步用空间分解法来定位相交的区域,在此阶段用哈希表的数据结构来保存物体的几何信息。与其他碰撞检测算法相比较,本算法不仅能够较大地节省空间,而且时间复杂度也比较低。除此之外,本算法不仅能够找出发生碰撞的基本几何元素对,而且还能够精确地找出碰撞点。     

Incremental algorithms for collision detection between polygonalmodels

Fast and accurate collision detection between general polygonal models is a fundamental problem in physically based and geometric modeling, robotics, animation, and computer-simulated environments. Most earlier collision detection algorithms are either restricted to a class of models (such as convex polytopes) or are not fast enough for practical applications. The authors present an incremental algorithm for collision detection between general polygonal models in dynamic environments. The algorithm combines a hierarchical representation with incremental computation to rapidly detect collisions. It makes use of coherence between successive instances to efficiently determine the number of object features interacting. For each pair of objects, it tracks the closest features between them on their respective convex hulls. It detects the objects' penetration using pseudo internal Voronoi cells and constructs the penetration region, thus identifying the regions of contact on the convex hulls. The features associated with these regions are represented in a precomputed hierarchy. The algorithm uses a coherence based approach to quickly traverse the precomputed hierarchy and check for possible collisions between the features. They highlight its performance on different applications     

基于线性规划的碰撞检测算法研究

介绍了虚拟环境中一种基于凸多面体面信息对偶线性规划模型(DualModel)的快速旋转和移动物体之间干涉碰撞实时检测方法。该文详细介绍了建模过程和求解步骤,物体由构成凸多面体的三角形面信息表示,而物体的运动由一组虚拟现实环境中的全局移动和旋转矩阵表示。这种数学编程方法具有数据结构简单、算法可靠和速度快等优点,同时能够很好地解决高速(运动帧)碰撞的问题。这一方法通过使用主-对偶(primal-dual)内点方法来解线性规划方程,具有很好的效果,能够检测多物体对之间的碰撞。实验结果表明,基于数学编程的方法相对两种著名的工具包I-COLLIDE和SOLID,具有速度快和稳定可靠的优点,而I-COLLIDE和SOLID工具包基于两种著名的算法:LinCanny(LC)最近特征算法和GJK算法(EnhancedGilbertJohnsonandKeethialgorithm)。     

An Algorithm for Geometric Set Operations Using Cellular Subdivision Techniques

Geometric set operations play an integral role in systems for CAD/CAM, for robot planning, and for modeling objects such as underground formations from empirical data. Two major issues in the implementation of geometric set operations are efficiency in the search for geometric intersections and effectiveness in the treatment of singular intersection cases. This article presents an algorithm for geometric set operations on planar polyhedral nonmanifold objects that addresses both these issues. First, an efficient search for geometric intersections is obtained by localizing the search to small regions of object space through a cellular subdivision scheme using the polytree data structure. Second, an effective treatment of singular intersection cases is obtained by mapping each singular intersection occurring in a region into one of a small set of cases.     

Fast Collision Detection Algorithms with Applications to Particle Flow

In this paper, we present efficient algorithms for collision detection of arbitrarily shaped rigid moving objects in a variety of interactive as well as non-interactive environments. The algorithms primarily consist of two stages. The first stage involves finding candidate objects for possible collisions. The second stage involves detecting exact (within a prespecified tolerance) collision between these candidates. The primary data structure used in the algorithms is an octree. In the first stage, we build an octree for the enclosure containing the objects, which is used to detect possible collisions. Assuming spatial/temporal coherence i.e., that the particles move slowly or that the time sampling is fast enough, the average time complexity of this stage can be shown to be O(n) (excluding the time complexity for a one time octree construction), where n is the number of particles. In the second stage, we build a surface-octree for each object. If the objects are convex and assuming coherence, the expected time complexity to detect precise (within a prespecified tolerance) collision for each pair is a constant (excluding the time complexity for a one time surface-octree construction). Therefore, the overall expected time complexity for convex object collision detection is linear with respect to n. For the concave objects, complexity analysis is nontrivial to perform and instead we provide a very practical (almost linear time) algorithm. We apply our algorithms to particle flow simulations by simulating flow density conditions often arising in granular flows.     

基于角色几何碰撞体估计的实时服装仿真

提出了一种快速处理三维服装仿真中角色与服装碰撞的方法.该方法能够满足交互式实时仿真环境的需求.在预处理阶段,根据蒙皮动画的特点,将角色的几何形状以球和简化凸包等简单碰撞体进行估计.在实时模拟阶段,这些碰撞体跟随骨架运动并代替角色模型网格完成与虚拟服装之间的碰撞处理.此外,为了能够快速计算碰撞响应信息,该方法还利用外围映射机制进一步开发了相交测试的空间局部性.实验结果表明,应用该方法可以有效避免衣片与角色模型之间的相互穿透,同时大幅度地减少碰撞处理计算量.实时仿真系统对于复杂服装网格仍然保持了较高的模拟帧速率.     

Fast Penetration Volume for Rigid Bodies

Handling collisions among a large number of bodies can be a performance bottleneck in video games and many other real‐time applications. We present a new framework for detecting and resolving collisions using the penetration volume as an interpenetration measure. Given two non‐convex polyhedral bodies, a new sampling paradigm locates their near‐contact configurations in advance, and stores associated contact information in a compact database. At runtime, we retrieve a given configuration's nearest neighbors. By taking advantage of the penetration volume's continuity, cheap geometric methods can use the neighbors to estimate contact information as well as a translational gradient. This results in an extremely fast, geometry‐independent, and trivially parallelizable computation, which constitutes the first global volume‐based collision resolution. When processing multiple collisions simultaneously on a 4‐core processor, the average running cost is as low as 5 μs. Furthermore, no additional proximity or contact‐regions queries are required. These results are orders of magnitude faster than previous penetration volume approaches.     

Comparative investigation of GPU-accelerated triangle-triangle intersection algorithms for collision detection

Efficient collision detection is critical in 3D geometric modeling. In this paper, we first implement three parallel triangle-triangle intersection algorithms on a GPU and then compare the computational efficiency of these three GPU-accelerated parallel triangle-triangle intersection algorithms in an application that detects collisions between triangulated models. The presented GPU-based parallel collision detection method for triangulated models has two stages: first, we propose a straightforward and efficient parallel approach to reduce the number of potentially intersecting triangle pairs based on AABBs, and second, we conduct intersection tests with the remaining triangle pairs in parallel based on three triangle-triangle intersection algorithms, i.e., the Möller’s algorithm, Devillers’ and Guigue’s algorithm, and Shen’s algorithm. To evaluate the performance of the presented GPU-based parallel collision detection method for triangulated models, we conduct four groups of benchmarks. The experimental results show the following: (1) the time required to detect collisions for the triangulated model consisting of approximately 1.5 billion triangle pairs is less than 0.5 s; (2) the GPU-based parallel collision detection method speedup over the corresponding serial version is 50x - 60x, and (3) Devillers’ and Guigue’s algorithm is comparatively and comprehensively the best of the three GPU-based parallel triangle-triangle intersection algorithms. The presented GPU-accelerated method is capable of efficiently detecting the potential collisions of triangulated models. Overall, the GPU-accelerated parallel Devillers’ and Guigue’s triangle-triangle intersection algorithm is recommended when performing practical collision detections between large triangulated models.

     

结合轴对齐包围盒和空间划分的碰撞检测算法

目的 碰撞检测是虚拟现实,特别是虚拟装配中的关键技术。针对基于包围盒的碰撞检测算法的准确性和检测效率不足的问题,提出一种结合AABB轴对齐包围盒和空间划分的碰撞检测算法。方法 本文算法采用分步检测的方法,利用AABB算法来确定两包围盒的相交区域后,结合模型移动方向和运动趋势进行空间划分,利用碰撞检测的时空相关性,对时空相关的部分进行相交测试,通过将包围盒还原成三角面以及点的方式来保证检测的准确性。结果 本文算法与AABB层次包围盒二叉树算法、k-Dops包围盒算法以及BPS空间分割树算法进行对比实验分析。在碰撞的几何精度上,本文算法在大部分情况下与AABB算法和k-Dops算法的距离差超过阈值0.02,证明本文算法在碰撞几何精度上有明显的提高。在碰撞检测时耗上,随着碰撞检测难度的不断增加,本文算法在平移自由度下比AABB算法和BSP算法、在旋转自由度下比AABB算法和k-Dops算法的检测时间均降低了50%以上。在三角面数对算法碰撞检测时耗的影响上,当运动模型的三角面数较多时,本文算法表现出更高的稳定性。结论 结合AABB包围盒和空间划分方法的碰撞检测算法,在减少碰撞检测所需时间的同时提高了碰撞检测的准确性,可以满足虚拟装配技术中对碰撞检测算法准确性的要求,同时也能满足使用者实时性的交互习惯。     

A collisions evaluation method in virtual environment for collaborativeassembly

Collision detection is critical for collaborative assembly simulation to assist design processing. However, collisions between polygonal models may not reflect collisions between real objects in reality because of polygonal approximation and designed tolerance. This problem reduces the reliability of simulation in collaborative assembly and sometimes even results in wrong conclusions. To solve the problem, we propose a novel collision evaluation algorithm based on generalized penetration depth, approximation information, and tolerance information. Given two interfered polygonal models, generalized penetration depth is calculated using relative motion information. Then two thresholds, which are based on approximation information and tolerance information, are integrated to evaluate collisions between polygonal models. In order to distinguish the status of collisions for further analysis, the collisions between polygonal models are categorized into three types by evaluation algorithm, namely real collision, potential collision, and fake collision. Computational efficiency and accuracy of the evaluation algorithm are verified in a virtual collaborative assembly environment.     

复杂场景中基于拓扑空间网格的碰撞检测算法

为了提高复杂场景的碰撞检测效率,提出一种基于拓扑空间网格的碰撞检测算法. 由于场景中存在众多形状复杂、尺寸不一且运动状态不同的物体,首先采取场景预处理对空间进行均匀八叉树网格划分,建立物体方向包围盒层次树与空间网格拓扑结构,利用静态大尺寸物体分割策略提升定位精确性,然后在实时检测中利用拓扑空间网格及投影相交测试排除大量不相交物体对,利用层次包围盒算法对潜在碰撞对进行精确检测并计算出碰撞点. 实验结果表明,本算法有效地提高了实时检测的效率,适用于复杂虚拟场景中的碰撞检测.     

Partitioning and Handling Massive Models for Interactive Collision Detection

We describe an approach for interactive collision detection and proximity computations on massive models composed of millions of geometric primitives. We address issues related to interactive data access and processing in a large geometric database, which may not fit into main memory of typical desktop workstations or computers. We present a new algorithm using overlap graphs for localizing the "regions of interest" within a massive model, thereby reducing runtime memory requirements. The overlap graph is computed off-line, pre-processed using graph partitioning algorithms, and modified on the fly as needed. At run time, we traverse localized sub-graphs to check the corresponding geometry for proximity and pre-fetch geometry and auxiliary data structures. To perform interactive proximity queries, we use bounding-volume hierarchies and take advantage of spatial and temporal coherence. Based on the proposed algorithms, we have developed a system called IMMPACT and used it for interaction with a CAD model of a power plant consisting of over 15 million triangles. We are able to perform a number of proximity queries in real-time on such a model. In terms of model complexity and application to large models, we have improved the performance of interactive collision detection and proximity computation algorithms by an order of magnitude.     

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

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

Real-time Velocity Alteration Strategy for Collision-free Trajectory Planning of Two Articulated Robot Manipulators

Two articulated robots working in a shared workspace can be programmed by planning the tip trajectory of each robot independently. To account for collision avoidance between links, a real-time velocity alteration strategy based on fast and accurate collision detection is proposed in this paper to determine the step of next motion of slave (low priority) robot for collision-free trajectory planning of two robots with priorities. The effectiveness of the method depends largely on a newly developed method of accurate estimate of distance between links. By using the enclosing and enclosed ellipsoids representations of polyhedral models of links of robots, the minimum distance estimate and collision detection between the links can be performed more efficiently and accurately. The proposed strategy is implemented in an environment where the geometric paths of robots are pre-planned and the preprogrammed velocities are piecewise constant but adjustable. Under the control of the proposed strategy, the master robot always moves at a constant speed. The slave robot moves at the selected velocity, selected by a tradeoff between collision trend index and velocity reduction in one collision checking time, to keep moving as far as possible and as fast as possible while avoid possible collisions along the path. The collision trend index is a fusion of distance and relative velocity between links of two robots to reflect the possibility of collision at present and in the future. Graphic simulations of two PUMA560 robot arms working in common workspace but with independent goals are conducted. Simulations demonstrate the collision avoidance capability of the proposed approach as compared to the approach based on bounding volumes. It shows that advantage of our approach is less number of speed alterations required to react to potential collisions.     

A Unified Cloth Untangling Framework Through Discrete Collision Detection

We present an efficient and stable framework, called Unified Intersection Resolver (UIR), for cloth simulation systems where not only impending collisions but also pre‐existing penetrations often arise. These two types of collisions are handled in a unified manner, by detecting edge‐face intersections first and then forming penetration stencils to be resolved iteratively. A stencil is a quadruple of vertices and it reveals either a vertex‐face or an edge‐edge collision event happened. Each quadruple also implicitly defines a collision normal, through which the four stencil vertices can be relocated, so that the corresponding edge‐face intersection disappear. We deduce three different ways, i.e., from predefined surface orientation, from history data and from global intersection analysis, to determine the collision normals of these stencils robustly. Multiple stencils that constitute a penetration region are processed simultaneously to eliminate penetrations. Cloth trapped in pinched environmental objects can be handled easily within our framework. We highlight its robustness by a number of challenging experiments involving collisions.     

基于空间分割与椭球包围盒的碰撞检测算法

为提高复杂环境下多物体碰撞检测的效率,提出了一种基于均匀网格分割与椭球包围盒的并行碰撞检测算法。该算法首先用均匀网格分割法来确定相邻物体,然后用紧密性较好的椭球包围盒层次树依次把它们包围,并利用基于线程池的多任务并行处理技术实现了并行化。为降低椭球相交测试的复杂度,先预测了椭球间的相交情况,再将三维椭球降维成二维椭圆,从而整体提高了算法的效率。通过实验数据表明,相对于其他算法,该算法具有较好的性能。     

Collision detection with relative screw motion

We introduce a framework for collision detection between a pair of rigid polyhedra. Given the initial and final positions and orientations of two objects, the algorithm determines whether they collide, and if so, when and where. All collisions, including collisions at different times, are computed at once along with properness values that measure the extent to which the collisions are between parts of the objects that properly face each other. This is useful for handling multiple (nearly) concurrent collisions and contact points.The relative motions of the rigid bodies are limited to screw motions. This limitation is not always completely accurate, but we can estimate the error introduced by the assumption.Our implementation uses rasterization to approximate the position and time of the collisions. This allows level-of-detail techniques that provide a tradeoff between accuracy and computational expense.The collision detection algorithms are only approximate, both because of the screw motion assumption and because of the rasterization. However, they can be made robust so as to give consistent information about collisions and to avoid sensitivity to roundoff errors.