Interactive continuous collision detection for non-convex polyhedra

We present a highly interactive, continuous collision detection algorithm for rigid, general polyhedra. Given initial and final configurations of a moving polyhedral model, our algorithm creates a continuous motion with constant translational and angular velocities, thereby interpolating the initial and final configurations of the model. Then, our algorithm reports whether the model under the interpolated motion collides with other rigid polyhedral models in environments, and if it does, the algorithm reports its first time of contact (TOC) with the environment as well as its associated contact features at TOC. Our algorithm is a generalization of conservative advancement [19] to general polyhedra. In this approach, we calculate the motion bound of a moving polyhedral model and estimate the TOC based on this bound, and advance the model by the current TOC estimate. We iterate this process until the inter-distance between the moving model and the other objects in the environments is below a user-defined distance threshold. We pose the problem of calculating the motion bound as a linear programming problem and provide an efficient, novel solution based on the simplex method. Moreover, we also provide a hierarchical advancement technique based on a bounding volume traversal tree to generalize the conservative advancement for non-convex models. Our algorithm is relatively simple to implement and has very small computational overhead of merely performing discrete collision detection multiple times. We extensively benchmarked our algorithm in different scenarios, and in comparison to other known continuous collision detection algorithms, the performance improvement ranges by a factor of 1.4～45.5 depending on benchmarking scenarios. Moreover, our algorithm can perform CCD at 120～15460 frames per second on a 3.6 GHz Pentium 4 PC for complex models consisting of 10K～70K triangles.     

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.     

High Performance GPU‐based Proximity Queries using Distance Fields

Proximity queries such as closest point computation and collision detection have many applications in computer graphics, including computer animation, physics‐based modelling, augmented and virtual reality. We present efficient algorithms for proximity queries between a closed rigid object and an arbitrary, possibly deformable, polygonal mesh. Using graphics hardware to densely sample the distance field of the rigid object over the arbitrary mesh, we compute minimal proximity and collision response information on the graphics processing unit (GPU) using blending and depth buffering, as well as parallel reduction techniques, thus minimizing the readback bottleneck. Although limited to image‐space resolution, our algorithm provides high and steady performance when compared with other similar algorithms. Proximity queries between arbitrary meshes with hundreds of thousands of triangles and detailed distance fields of rigid objects are computed in a few milliseconds at high‐sampling resolution, even in situations with large overlap.     

TightCCD: Efficient and Robust Continuous Collision Detection using Tight Error Bounds

http://gamma.cs.unc.edu/BSC/ We present a realtime and reliable continuous collision detection (CCD) algorithm between triangulated models that exploits the floating point hardware capability of current CPUs and GPUs. Our formulation is based on Bernstein Sign Classification that takes advantage of the geometry properties of Bernstein basis and Bézier curves to perform Boolean collision queries. We derive tight numerical error bounds on the computations and employ those bounds to design an accurate algorithm using finite‐precision arithmetic. Compared with prior floatingpoint CCD algorithms, our approach eliminates all the false negatives and 90–95% of the false positives. We integrated our algorithm (TightCCD) with physically‐based simulation system and observe speedups in collision queries of 5–15X compared with prior reliable CCD algorithms. Furthermore, we demonstrate its benefits in terms of improving the performance or robustness of cloth simulation systems.     

gProximity: Hierarchical GPU‐based Operations for Collision and Distance Queries

We present novel parallel algorithms for collision detection and separation distance computation for rigid and deformable models that exploit the computational capabilities of many‐core GPUs. Our approach uses thread and data parallelism to perform fast hierarchy construction, updating, and traversal using tight‐fitting bounding volumes such as oriented bounding boxes (OBB) and rectangular swept spheres (RSS). We also describe efficient algorithms to compute a linear bounding volume hierarchy (LBVH) and update them using refitting methods. Moreover, we show that tight‐fitting bounding volume hierarchies offer improved performance on GPU‐like throughput architectures. We use our algorithms to perform discrete and continuous collision detection including self‐collisions, as well as separation distance computation between non‐overlapping models. In practice, our approach (gProximity) can perform these queries in a few milliseconds on a PC with NVIDIA GTX 285 card on models composed of tens or hundreds of thousands of triangles used in cloth simulation, surgical simulation, virtual prototyping and N‐body simulation. Moreover, we observe more than an order of magnitude performance improvement over prior GPU‐based algorithms.     

Collision Detection between Robot Arms and People

As the result of an increasing number of robots performing tasks in a range of human life activites, human–robot interaction has become a very active research field. Safety of people around robots is a major concern. This paper presents some research in this context: our aim is to avoid mechanical injure of people interacting with robots. We approach the collision detection problem in a scene with people and several moving robot arms. Fast collision detection for practical motion planning depends on an adequate spatial representation for the objects involved in the scene. The authors have previosly proposed a system that automatically generates a hierarchy of approximations for general objects. The spatial model has interesting properties and has been used in efficient collision detection algorithms between moving robots [8]. In spatial representations, there is a trade-off between generality and efficiency. Some existing approaches claim to be general but they are less efficient. In this paper, we present two extensions to the spatial model. First, the system can deal with a general class of objects, those that are composed of nonhomogeneous generalized cylinders. Secondly, a simple method for automatic converting from a polyhedral representation to such a generalized cylinder is presented. Therefore, we enhance the generality of the system but without compromising the efficiency. With these extensions virtually any object can be dealt with, and particularly those composing the human body.     

Computation of a penetration measure between 3D convex polyhedral objects for collision detection

Measures to characterize the penetration between a pair of intersecting objects are given, based on translating one object to separate from the other. Algorithms to compute a measure between convex polyhedral objects in ?³ are presented for two different input representations. These algorithms have linear expected running time. Details of experiments in collision detection for 3D objects using the penetration measure are also presented. © 2001 John Wiley & Sons, Inc.     

Control of cooperative manipulator-endowed systems under high-level tasks and uncertain dynamics

This paper considers the problem of distributed motion- and task-planning of multi-agent and multi-agent-object systems under temporal-logic-based tasks and uncertain dynamics. We focus on manipulator-endowed robotic agents that can interact with their surroundings. We present first continuous control algorithms for multi-agent navigation and cooperative object manipulation that exhibit the following properties. First, they are distributed in the sense that each agent calculates its own control signal from local interaction with the other agents and the environment. Second, they guarantee safety properties in terms of inter-agent collision avoidance and obstacle avoidance. Third, they adapt on-the-fly to dynamic uncertainties and are robust to exogenous disturbances. The aforementioned algorithms allow the abstraction of the underlying system to a finite-state representation. Inspired by formal-verification techniques, we use such a representation to derive plans for the agents that satisfy the given temporal-logic tasks. Various simulation results and hardware experiments verify the efficiency of the proposed algorithms.     

Octree-based hierarchical distance maps for collision detection

Discretized distance maps have been used in robotics for path planning and efficient collision detection applications in static environments.¹ However, they have been used at the finest level of resolution, thereby making them memory intensive. In this article, we propose an octree-based hierarchical representation for discretized distance maps, called Octree Distance Maps (ODM), and show its use in efficient collision detection. To the best of our knowledge, ours is the first work to consider the use of hierarchical distance maps for collision detection. ODM representation achieves an advantageous compromise between array-based distance maps and ordinary octrees. Compared to the former, ODM requires a fraction of the memory at the expense of somewhat slower collision detection. Compared to the latter, ODM requires slightly more memory but provides a significant improvement in collision detection. ODM is similar to the quadtree distance transforms used in image representation² but differs significantly in various aspects of distance representation and its use in collision detection since the main motivation behind ODM is efficient collision detection instead of image representation. We then present algorithms for (1) creating an ODM from an octree, and (2) for efficient collision detection based on an ODM. Extensive experiments are then presented and compared with octree-based collision detection. Our experimental results quantify the advantageous compromise achieved by ODM representation. © 1997 John Wiley & Sons, Inc.     

Optimal virtual cluster-based multiprocessor scheduling

Scheduling of constrained deadline sporadic task systems on multiprocessor platforms is an area which has received much attention in the recent past. It is widely believed that finding an optimal scheduler is hard, and therefore most studies have focused on developing algorithms with good processor utilization bounds. These algorithms can be broadly classified into two categories: partitioned scheduling in which tasks are statically assigned to individual processors, and global scheduling in which each task is allowed to execute on any processor in the platform. In this paper we consider a third, more general, approach called cluster-based scheduling. In this approach each task is statically assigned to a processor cluster, tasks in each cluster are globally scheduled among themselves, and clusters in turn are scheduled on the multiprocessor platform. We develop techniques to support such cluster-based scheduling algorithms, and also consider properties that minimize total processor utilization of individual clusters. In the last part of this paper, we develop new virtual cluster-based scheduling algorithms. For implicit deadline sporadic task systems, we develop an optimal scheduling algorithm that is neither Pfair nor ERfair. We also show that the processor utilization bound of us-edf{m/(2m−1)} can be improved by using virtual clustering. Since neither partitioned nor global strategies dominate over the other, cluster-based scheduling is a natural direction for research towards achieving improved processor utilization bounds.

A Visibility Sphere Marching algorithm of constructing polyhedral models for haptic sculpting and product prototyping

This paper presents a Visibility Sphere Marching algorithm of constructing polyhedral models from Dexel volume models for haptic virtual sculpting. Dexel volume models are used as the in-process models representation during interactive modification in a haptic virtual sculpting system. The stock material represented in a Dexel volume model is sculpted into a designed model using a developed haptic sculpting system. The sculpted Dexel volume models are converted to polyhedral surface models in STL format by the proposed visibility sphere marching algorithm. The conversion turns out to be an interesting and challenging problem. The proposed visibility sphere marching algorithm consists of three sub-algorithms: (i) roof and floor covering, (ii) wall-building, and (iii) hole-filling algorithms. The polyhedral surface models converted from the Dexel volume models can then be input to and processed by available computer-aided manufacturing (CAM) or rapid prototyping systems. The presented technique can be used in virtual sculpting, CAD/CAM, numerically controlled machining verification and rapid prototyping.     

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.     

虚拟装配环境中碰撞检测算法的研究综述与展望

虚拟装配系统可对机电产品进行装配仿真,生成装配顺序与装配轨迹,而碰撞检测技术正是对装配顺序与装配轨迹的正确性进行验证。把虚拟装配环境的碰撞检测算法归类为:基于时间域的碰撞检测算法、基于几何空间的碰撞检测算法、基于图像空间的碰撞检测算法。对这几类算法的研究现状进行了综述,根据研究现状分析了碰撞检测算法中存在的问题及研究难点,并对碰撞检测算法的研究趋势进行了展望。     

Deterministic Broadcast and Gossiping Algorithms for Ad hoc Networks

We present in this paper three deterministic broadcast and a gossiping algorithm suitable for ad hoc networks where topology changes range from infrequent to very frequent. The proposed algorithms are designed to work in networks where the mobile nodes possessing collision detection capabilities. Our first broadcast algorithm accomplishes broadcast in O(nlog n) for networks where topology changes are infrequent. We also present an O(nlog n) worst case time broadcast algorithms that is resilient to mobility. For networks where topology changes are frequent, we present a third algorithm that accomplishes broadcast in O(Δ·nlog n + n·|M|) in the worst case scenario, where |M| is the length of the message to be broadcasted and Δ the maximum node degree. We then extend one of our broadcast algorithms to develop an O(Dn log n + D²) algorithm for gossiping in the same network model.     

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

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

Collision Detection for Animation using Sphere-Trees

The detection of collisions between moving polyhedral objects is one of the most computationally intensive tasks in the computer animation process. The use of object-oriented techniques to encapsulate data within the objects' structures compounds this problem through the requirement for inter-object message passing in order to obtain geometric information for collision detection. The REALISM system decreases the time for collision detection by using a three stage process. The first stage identifies objects in the same locality using a global bounding volume table. The second stage locates regions of possible collision using a sphere-tree data structure (a hierarchical tree of spheres based on octree-type spatial subdivision). The final stage finds intersections between polygonal faces of the objects that are contained within the intersecting pairs of leaf nodes. Hence the algorithm uses a spherical geometry approximation rapidly to locate regions of potential collisions and then uses a local intersection test with actual object geometry information. The system is therefore fast and accurate. Tests for various geometric objects support this and show performance improvements of jive times over traditional polyhedral intersection tests.     

Adjacency-based culling for continuous collision detection

We present an efficient approach to reduce the number of elementary tests for continuous collision detection between rigid and deformable models. Our algorithm exploits connectivity information and uses the adjacency relationships between triangles to perform hierarchical culling. This can be combined with table-based lookups to eliminate duplicate elementary tests. In practice, our approach can reduce the number of elementary tests by two orders of magnitude. We demonstrate the performance of our algorithm on various challenging rigid body and deformable simulations.