Efficient triangle–triangle intersection test for OBB-based collision detection

We present an efficient algorithm for triangle–triangle intersection test in oriented bounding box (OBB)-based collision detection. In testing two OBB leaf nodes (i.e., rectangles), many intermediate computation results can be reused for the intersection test of two triangles they contain. It is considerably easier to detect redundant operations when we work in the local coordinate of the bounding rectangle rather than in the global coordinate of the object. The performance improvement of our algorithm is based on this observation that eliminates redundant computations. Compared with conventional algorithms, we have observed 15–79% improvement in computing time. We demonstrate the effectiveness of our approach using several experimental results.     

三角形对的快速相交测试

为提高碰撞检测的响应速度,提出了一种基于Ayellet算法的改进算法.该算法从代数的角度出发,首先快速排除掉三角形对不相交或共面的两种情况,然后分别计算一个三角形与另一个三角形所在平面的相交线段,最后检测这两条线段是否有公共点.如果有公共点则三角形对相交,反之则不相交.该算法也可以应用于类似的问题,如矩形对的相交测试,多边形对的相交测试.实验结果表明,该算法的速度优于改进前的算法.     

A faster triangle‐to‐triangle intersection test algorithm

The triangle‐to‐triangle intersection test is the most basic component of collision detection. And our algorithm, which firstly computes the line segment between triangle A and the plane of triangle B and uses a new method to detect the intersection between this line and triangle B, can reduce about 10% of time on average, compared with the previous fastest algorithm. Our new method divides the plane of triangle B into four quarter planes by two edges of B, and detects intersection depending on the location of the two endpoints of the segment. After using some techniques like avoiding division and projecting the segment and triangle B on XY, YZ, or ZX plane, the total number of arithmetic operations is reduced to at most 87, which is less than any existing algorithms. Copyright © 2013 John Wiley & Sons, Ltd.     

基于一类分类的三角形和三角形相交测试

三角形和三角形相交测试是碰撞检测数据结构和算法的基本组成部分,基于支持向量机的一类分类方法对三维空间中三角形和三角形相交测试提出了一种新的算法,首先用核函数把其中一个三角形（记为T_a）训练成球心为a半径为R的超球体,然后依据另一个三角形（记为T_b上的某些点到超球体的球心a的距离d_i（i=1,2,…,n）与R的关系,判断这些点是否在超球体内。如果T_b有点在超球体内,则断定两个三角形发生相交,反之则没有。理论分析和实验结果都表明,该算法速度很快,效率较高,能够满足动画中运动物体的实时交互碰撞检测。     

Countermeasures to prevent detection failure of a vehicle approaching on collision course

Objective

This study investigated causal factor of perceptual failure and possible countermeasure of crossing path crashes at clear-sighted unsignalised intersections.

Background

Crossing path crashes involving two vehicles at intersections are a common and serious problem, and perceptual failure has been identified as a predominant causal factor. Previous studies have showed that late detection of a crossing vehicle frequently occurs even when there are no visual obstructions, at such as rural intersections.

Method

With using a fixed-based driving simulator, three experiments were performed to investigate a driver’s ability to detect a periphery presented cross traffic while approaching an intersection. In Experiment 1, drivers’ ability to detect crossing vehicles in their peripheral field of view was studied, both in conditions of vehicles following a collision and a non-collision trajectory. In Experiment 2, we examined whether abrupt appearance of a vehicle on collision course would improve detection performance. In Experiment 3, we tested potential of collision warning, if it affects voluntary visual scanning, improving the detection performance regarding hazards cross traffic.

Results

The results of Experiment 1 showed that vehicles on collision course vehicles were detected late. This suggested that the late detection could be related to the lack of motion visible in the peripheral view. In Experiment 2, it was found that abrupt appearance effect (“pop-up” from road side occluding furniture) improves detection performance of a crossing vehicle. The results of Experiment 3 demonstrated that cross traffic collision warnings were beneficial for preventing late detection responses by means of encouraging voluntary visual scanning.

Conclusion

Less attention attractive visual properties of hazardous cross traffic attributed to mutual approaching course can cause recognition failure. Drivers’ gaze shift to potential conflicting direction, either reflective or voluntary manner, is crucially important for preventing crossing path crashes at such as rural intersections.     

A collision resolution algorithm for clump-free fast moving cloth

Cloth animation is an important area of computer graphics due to its numerous applications. However, so far a fast moving cloth with multiple wrinkles has been difficult to animate because of the cloth clump problem. Cloth clumps are the frozen areas where cloth pieces are clustered unnaturally — an obstacle in making a realistic cloth animation. Hence we present a novel cloth collision resolution algorithm that prevents clump formation during fast cloth motions. The goal of our resolution algorithm is to make cloth move swiftly without having any unnatural frozen cloth clumps, while preventing any cloth-cloth and rigid-cloth penetrations at any moment of a simulation. The non-penetration status of cloth is maintained without the formation of cloth clumps regardless of the speed of cloth motion. Our algorithm is based on a particular order that we found in the resolution of cloth collisions, and can be used with any structural modeling approaches such as spring-masses or finite elements. This paper includes several realistic simulation examples involving fast motions that are clump-free.     

Kinetic collision detection with fast flight plan changes

We show how to augment a kinetic data structure for collision detection between translating polygons with the ability to make fast flight plan changes. This allows us to update the KDS after a moving polygon changes its motion in O(logn) time, instead of the Ω(n) worst-case time needed by previous kinetic data structures. The key to our approach is replacing the KDS priority queue by a dynamic convex hull that represents the certificates of the KDS.     

A force-sensorless approach to collision detection based on virtual powers

A collision detection approach for torque-controlled manipulators is proposed to detect and isolate a collision in an unknown environment without using external sensors. A set of artificial indexes physically representing instantaneous powers are introduced. A contact link can be detected and isolated by finding the smallest power index based on full knowledge of the link parameters. However, it is difficult to precisely obtain the link parameters. Therefore, we propose a robust way in which the collision detection and isolation processes are separated. A collision can be detected by comparing a power-based index with a unique threshold, and a contact link can be isolated by comparing power indexes without any additional threshold. The statistical simulation results using a 6 degree of freedom (DOF) spatial manipulator show the performance of the proposed approach in an ideal situation. Furthermore, the statistical experimental results using the 2- and 3-DOF planar manipulators validate the robustness of the proposed approach.     

Extended linked voxel structure for point-to-mesh distance computation and its application to NC collision detection

When working with milling or polishing robots and large workpieces it is necessary to check not only the milling or polishing tool for collision, but it is also necessary to check the remaining arms of the robot for collision. In most of the cases the arms of the robot do not collide with the workpiece and so applying an existing collision detection algorithm to the arms of the robot slows the process down. In this paper, we present an algorithm for quickly assuring non-collisions, which is especially targeted at collisions of the arms of the robot with a workpiece. The algorithm is based on an extended voxel structure. More precisely, we extend a voxel structure by adding distance values to the corner of the voxels and by linking empty voxels to non-empty voxels to accelerate finding the desired voxel. This ensures that we only need to consider a small subset of the triangles describing the workpiece’s surface, namely those triangles that are close to the possible collision area. The triangles within each non-empty voxel are stored in a bsp-tree. For empty voxels, we save information about the distances to the mesh. This setup speeds up the point-to-mesh distance calculation, especially for points close to the mesh. The extra distance information in empty voxels enables a fast distance estimation and hence a fast early collision check.     

空间三角形快速相交检测算法

综述了典型的快速稳定的三角形相交检测算法的原理及实现方法 ,并根据算法原理将其分为标量判别型和矢量判别型算法。从计算量角度对各种算法的适用场合和性能进行了分析比较及验证 ,结果显示矢量判别型算法中的 Olivier Devillers & Philippe Guigue算法整体性能最优 ,而标量判别型算法中的 Oren Tropp算法最适合于三角形相交率较高的场合。     

Back-face culling applied to collision detection of polyhedra

Back-face culling is a preprocessing technique used in computer graphics to speed up the rendering of polyhedra. In this paper we show how this technique can be modified to reduce unnecessary checking of boundary elements in collison detection for a physical-based simulation and animation systems. At each time step, we determine a priori which faces cannot be part of the contact between two polyhedra and thus can be culled. In the computer graphics technique, the normal vector of a polygon is compared with the view direction. Here, the normal is compared to one or possibly several relative-velocity vectors, and the face is culled when its motion is in the opposite direction of the normal vector. We also give an algorithm that takes linear time in terms of the number of faces, and on the average eliminates half of the polygons. Owing to its low computational overhead, when it is used as a front end to a collision detection system, a noticeable improvement in performance can be achieved.     

无人驾驶车辆的路口防撞机制研究

防撞协议是提高无人驾驶车辆安全性的重要组成部分,大部分防撞协议已经为路口外的车辆提供了躲避机制.交叉路口因其流量大、方向多而成为事故易发地,但对已在路口内部的车辆的防撞协议的研究比较少.自治路口协议AIM作为目前较流行的路口管理协议之一,也未给出已在路口的车辆的防撞协议.给出了两类基于路口空间的防撞协议:当路口空间较小时,改进的AIM根据三种情况,即同向、逆向、垂直同向,给出了基于刹车的躲避机制;当路口空间较大时,改进的AIM除可以采用基于刹车的躲避机制外,还可以通过转弯为车辆重新规划路线使其通过路口.通过实验证明了改进的AIM的有效性.     

基于混合包围盒与三角形相交的碰撞检测优化算法

碰撞检测的速度与准确性是众多计算机应用程序的关键难题之一。为了提高检测速度同时兼顾准确性,将检测分为两个阶段：预处理检测阶段首先均匀剖分待测空间以确定相邻对象,然后对相邻的对象构造AABB-OBB混合层次包围盒,改进包围盒的构造方式,同时改善任务结构加速遍历过程;详细检测阶段在M?ller算法基础上加以改进,构造新的计算坐标系,对空间几何三角形进行投影降维,在二维平面上解决空间问题,从而减少算法总的计算量。实验结果表明,在保证碰撞检测准确性的前提下其检测速度大幅提高。     

VoxColliDe: Voxel collision detection for virtual environments

Collision detection is fundamental in achievingnatural dynamics in virtual environments, but current algorithms are too slow, causing a major bottleneck in processing and hindering the building of interactive simulation environments. This paper provides an overview of the collision detection problem and current attempted solutions. A voxel-based approach to rigid-body collision detection is presented, with its potential high performance explained.Voxel collision detection takes place on a pair-wise basis, involving two additional representations of a polygonal object, a Voxmap and a Point Shell. These are constructed in a pre-processing step and allow fast collision detection through a simple look-up reference of points into voxels. Collision performance depends upon the number of points in the shell, and can trade accuracy for speed. A range ofpruning techniques, needed to cut down the number of objects undergoing collision testing, are reviewed and implemented. These allow most effective use of the voxel collision detection algorithm in multi-body simulations, such as virtual environments.Performance evaluations demonstrate the voxel collision detection algorithm's ability to achieve interactive rates (above 20 Hz) for both high precision pair-wise collision tests, and for large numbers of objects in multi-body environments. The voxel collision detection algorithm is suitable for parallel, hardware implementation. This provides the potential for great enhancements to already extremely high performance, rendering the voxel-based approach to collision detection all the more promising.     

A fast algebraic non-penetration filter for continuous collision detection

Continuous collision detection is a key technique to meet non-penetration requirements in many applications. Even though it is possible to perform efficient culling operations in the broad stage of a continuous collision detection algorithm, such as bounding volume hierarchies, a huge number of potentially colliding triangles still survive and go to the succeeding narrow stage. This heavily burdens the elementary collision tests in a collision detection algorithm and affects the performance of the entire pipeline, especially for fast moving or deforming objects. This paper presents a low-cost filtering algorithm using algebraic analysis techniques. It can significantly reduce the number of elementary collision tests that occur in the narrow stage. We analyze the root existence during the time interval [0, 1] for a standard cubic equation defining an elementary collision test. We demonstrate the efficiency of the algebraic filter in our experiments. Cubic-solvers augmented by our filtering algorithm are able to achieve up to 99% filtering ratios and more than 10 ×  performance improvement against the standard cubic-solver without any filters.     

Facility layout by collision detection and force exertion heuristics

Facility layout problem (FLP) considers the optimization of layout costs, primarily on the account of material handling costs. FLP can be solved via mathematical modelling, heuristic or metaheuristic approaches. This paper presents a novel heuristic approach for solving the unequal area FLP. Here, facilities are randomly generated points that exert forces on each other based on a relation matrix. In this setup, every point is a centroid of the respective facility shape and two heuristic methods are used to detect and consequently remove the collisions where the heuristic parameters influence the speed and quality of the final results. Furthermore, a graphic user interface (GUI) is designed to monitor performance of the proposed heuristic algorithm and modify its parameters while running if required. Finally, layout in higher dimensional space, facility rotation and future possible extensions are discussed.     

Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection

Summary This paper presents an efficient randomized emulation ofsingle-hop radio networkwith collision detection onmulti-hop radio networkwithout collision detection. Each step of the single-hop network is emulated by rounds of the multi-hop network and succeeds with probability 1–. (n is the number of processors,D the diameter and the maximum degree). It is shown how to emulate any polynomial algorithm such that the probability of failure remains . A consequence of the emulation is an efficient randomized algorithm for choosing a leader in a multi-hop network. Reuven Bar-Yehuda was born in Iran, on July 17th 1951. Received B.A., M.Sc., and D.Sc. in Computer Science from the Technion — Israel Institute of Technology, Haifa, Israel, in 1978, 1980, and 1983, respectively. He is currently a Senior Lecturer of Computer Science at the Technion. From 1984 to 1986, he was a visiting assistant professor in the Computer Science Dept. at the Duke Univesity His research interests include computational geometry, VLSI, graph algorithms and distributed algorithms. Oded Goldreich was born in Tel-Aviv, Israel, on February 4th 1957. Received B.A., M.Sc., and D.Sc. in Computer Science from the Technion — Israel Institute of Technology, Haifa, Israel, in 1980, 1982, and 1983, respectively. He is currently an Associate Professor of Computer Science at the Technion. From 1983 to 1986, he was a postdoctoral fellow at MIT's Laboratory for Computer Science. His research interests include cryptography and related areas, relation between randomness and algorithms, and distributed computation. Alon Itai was born in Scotland, on December 12th 1946. Received B.Sc. in Mathematics from the Hebrew University in Jerusalem in 1969. M.Sc., and Ph.D. in Computer Science from the Weizmann Institute of Science, Rehovot, Israel in 1971 and 1976. He is currently an Associate Professor of Computer Science at the Technion. His research interests include randomized and distributed algorithms, computational learning theory and performance evaluation.The second author was partially supported by grant No. 86-00301 from the United States—Israel Bi-national Science Foundation BSF), Jerusalem, Israel.     

三角形和三角形相交测试技术研究

高效率的“三角形和三角形相交测试”对于提高碰撞检测算法效率,增强虚拟场景的真实感和沉浸感起着至关重要的作用。该文深入研究了“三角形和三角形相交测试”的基本原理和典型算法,根据算法思想提出两个概念：标量判别法和矢量判别法,并对两种算法进行验证,对仿真计算结果进行分析、比较得出：矢量判别算法是对标量判别算法的改进和优化,条件相同时检测效率提高约7％,算法更加简单快捷,具有较高的理论意义和实际工程应用价值。     

A modelling system for complex deformable bodies suited to animation and collision processing

We propose an integrated set of methods for designing and animating bodies whose deformable flesh coats an articulated skeleton. The proposed methods provide good automatic positioning of the ‘skin’ after movements, and automatic deformation after collisions with rigid or deformable objects (dynamic or static). The response to collisions includes a feedback from the flesh to the skeleton, whose movement is adequately modified. Moreover, coating the skeleton gives an easy solution to closed loop collisions and angle constraints control. Our model is modular and gives some high level control to the user.