3D Collision Detection: A Survey
---
paper_title: Evaluating signs of determinants using single-precision arithmetic

paper_content:

We propose a method of evaluating signs of 2×2 and 3×3 determinants withb-bit integer entries using onlyb and (b+1)-bit arithmetic, respectively. This algorithm has numerous applications in geometric computation and provides a general and practical approach to robustness. The algorithm has been implemented and compared with other exact computation methods.
---
paper_title: A collision detection algorithm based on velocity and distance bounds

paper_content:

The collision detection problem is encountered whenever objects are to be manipulated in the real world. Efficient solutions to this problem must intelligently decide when in time and where in space to check for interference among the objects. Complete solutions must guarantee that no collision can be overlooked. Useful solutions should also report the precise space/time points at which colliding objects begin and end contact. An algorithm based on velocity and distance bounds is described which is both useful and complete. Experiments are presented which measure the efficiency of the algorithm on a variety of test cases. The algorithm is contrasted with existing collision detection methods.
---
paper_title: Convex decomposition of polyhedra and robustness

paper_content:

This paper presents a simple algorithm to compute a convex decomposition of a nonconvex polyhedron of arbitrary genus (handles) and shells (internal voids). For such a polyhedron S with n edges and rnotches (features causing nonconvexity in polyhedra), the algorithm produces a worst-case optimal $O(r^2 )$ number of convex polyhedra $S_i $, with $U_{i = 1}^k S_i = S$, in $O(nr^2 + r^{7/2} )$ time and $O(nr + r^{5/2} )$ space. Recently, Chazelle and Palios have given a fast $O((n + r^2 )\log r$) time and $O(n + r^2 )$ space algorithm to tetrahedralize a nonconvex polyhedron. Their algorithm, however, works for a simple polyhedron of genus zero and with no shells (internal voids). The algorithm, presented here, is based on the simple cut and split paradigm of Chazelle. With the help of zone theorems on arrangements, it is shown that this cut and split method is quite efficient. The algorithm is extended to work for a certain class of nonmanifold polyhedra. Also presented is an algorithm for the same problem ...
---
paper_title: Strategies for polyhedral surface decomposition: an experimental study

paper_content:

Abstract This paper addresses the problem of decomposing a complex polyhedral surface into a small number of “convex” patches (i.e., boundary parts of convex polyhedra). The corresponding optimization problem is shown to be NP-complete and an experimental search for good heuristics is undertaken.
---
paper_title: Decomposition Algorithms in Geometry

paper_content:

Decomposing complex shapes into simpler components has always been a focus of attention in computational geometry. The reason is obvious: most geometric algorithms perform more efficiently and are easier to implement and debug if the objects have simple shapes. For example, mesh-generation is a standard staple of the finite-element method; partitioning polygons or polyhedra into convex pieces or simplices is a typical preprocessing step in automated design, robotics, and pattern recognition. In computer graphics, decompositions of two-dimensional scenes are used in contour filling, hit detection, clipping and windowing; polyhedra are decomposed into smaller parts to perform hidden surface removal and ray-tracing.
---
paper_title: Fast contact determination in dynamic environments

paper_content:

We present an efficient contact determination algorithm for objects undergoing rigid motion. The environment consists of polytopes and models described by algebraic sets. We extend an expected constant time collision detection algorithm between convex polytopes to concave polytopes and curved models. The algorithm makes use of hierarchical representations for concave polytopes and local, global methods for solving polynomial equations to determine possible contact points. We also propose techniques to reduce O(n/sup 2/) pairwise intersection tests for a large environment of n objects. These algorithms work well in practice and give real time performance for most environments. >
---
paper_title: Incremental algorithms for collision detection between polygonal models

paper_content:

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.
---
paper_title: I-COLLIDE: an interactive and exact collision detection system for large-scale environments

paper_content:

we present an exact and interactive collision detection system, I-COLLIDE, for large-scale environments. Such environments are characterized by the number of objects undergoing rigid motion and the complexity of the models. The algorithm does not assume the objects' motions can be expressed as a closed form function of time. The collision detection system is general and can be easily interfaced with a variety of applications. The algorithm uses a two-level approach based on pruning multiple-object pairs using bounding boxes and performing exact collision detection between selected pairs of polyhedral models. We demonstrate the performance of the system in walkthrough and simulation environments consisting of a large number of moving objects. In particular, the system takes less than 1/20 of a second to determine all the collisions and contacts in an environment consisting of more than 1000 moving polytopes, each consisting of more than 50 faces on an HP-9000/750.
---
paper_title: A new representation for collision avoidance and detection

paper_content:

By combining the simplicity of the sphere and the power of the motion of hierarchy of detail, a novel model is proposed with applications to collision avoidance and detection in 3D. The model is based on a double spherical representation for solid bodies. First, each element making up the robot and the obstacles is approximated by a set of exterior spheres which are automatically defined. Second, another set composed of interior spheres is generated. These representations define a hierarchy, since they can be redefined as many times as necessary; starting with two spheres per element, the approximation may be improved until it contains hundreds of spheres. Moreover, they converge to a zero-error representation. The proposed models leads to a simple treatment for the problem of collision detection, and it is further applied to collision-free path planning for manipulators in 3D. >
---
paper_title: Collision Detection for Animation using Sphere‐Trees

paper_content:

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 five times over traditional polyhedral intersection tests.
---
paper_title: Very fast collision detection for practical motion planning. I. The spatial representation

paper_content:

Practical robot motion planning for multiple moving objects in complex scenarios requires very fast collision detection. The efficiency of the algorithms is critically dependent on the representation that is used to model the objects. We present a hierarchical spatial representation based on spheres that is very adequate for speeding up collision detection. The objects can be non-convex and curved and they are not partitioned into convex ones. We present results that show some of its main features: spatial balance, stability and convergence. Comparative results in terms of quality and time are provided.
---
paper_title: Rapid and Accurate Contact Determination between Spline Models using ShellTrees

paper_content:

In this paper, we present an efficient algorithm for contact determination between spline models. We make use of a new hierarchy, called ShellTree, that comprises of spherical shells and oriented bounding boxes. Each spherical shell corresponds to a portion of the volume between two concentric spheres. Given large spline models, our algorithm decomposes each surface into Bezier patches as part of pre-processing. At runtime it dynamically computes a tight fitting axis-aligned bounding box across each Bezier patch and efficiently checks all such boxes for overlap. Using off-line and on-line techniques for tree construction, our algorithm computes ShellTrees for Bezier patches and performs fast overlap tests between them to detect collisions. The overall approach can trade off runtime performance for reduced memory requirements. We have implemented the algorithm and tested it on large models, each composed of hundred of patches. Its performance varies with the configurations of the objects. For many complex models composed of hundreds of patches, it can accurately compute the contacts in a few milliseconds.
---
paper_title: Speeding up interference detection between polyhedra

paper_content:

A classical paradigm for interference detection between polyhedra consists in testing all edges of one polyhedron against all faces of the other one for intersection. If the relative orientation of the polyhedra is fixed, only certain edge-face pairs can intersect first, when the polyhedra come into contact. These candidate pairs are efficiently determined using a representation which the authors call spherical face orientation graph. By applying the interference test to candidates only, the computational effort is significantly reduced, as shown by experimental results with convex polyhedra. In the non-convex case, the strategy is conservative, but it still leads to savings.
---
paper_title: Incremental algorithms for collision detection between solid models

paper_content:

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. We 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. We highlight its performance on different applications. Index Terms—Collision detection, contacts, interference, dynamic simulation, physically based modeling, convex hulls, hierarchical representation. —————————— ✦ —————————— 1I NTRODUCTION realistic visual simulation system, which couples geometric modeling and physical prototyping, can provide a useful toolset for applications in robotics, CAD/CAM design, molecular modeling, manufacturing design simulations, etc. Such systems create electronic rep- resentations of mechanical parts, tools, and machines, which need to be tested for interconnectivity, functionality, and reliability. The goal of these virtual and electronic simula- tion systems is to save processing time and manufacturing costs by avoiding the production of actual physical proto- types (1), (2). This is similar to the goal of CAD tools for VLSI. It requires a complete test environment for simulat- ing hundreds of parts interacting.
---
paper_title: Fast contact determination in dynamic environments

paper_content:

We present an efficient contact determination algorithm for objects undergoing rigid motion. The environment consists of polytopes and models described by algebraic sets. We extend an expected constant time collision detection algorithm between convex polytopes to concave polytopes and curved models. The algorithm makes use of hierarchical representations for concave polytopes and local, global methods for solving polynomial equations to determine possible contact points. We also propose techniques to reduce O(n/sup 2/) pairwise intersection tests for a large environment of n objects. These algorithms work well in practice and give real time performance for most environments. >
---
paper_title: I-COLLIDE: an interactive and exact collision detection system for large-scale environments

paper_content:

we present an exact and interactive collision detection system, I-COLLIDE, for large-scale environments. Such environments are characterized by the number of objects undergoing rigid motion and the complexity of the models. The algorithm does not assume the objects' motions can be expressed as a closed form function of time. The collision detection system is general and can be easily interfaced with a variety of applications. The algorithm uses a two-level approach based on pruning multiple-object pairs using bounding boxes and performing exact collision detection between selected pairs of polyhedral models. We demonstrate the performance of the system in walkthrough and simulation environments consisting of a large number of moving objects. In particular, the system takes less than 1/20 of a second to determine all the collisions and contacts in an environment consisting of more than 1000 moving polytopes, each consisting of more than 50 faces on an HP-9000/750.
---

Title: 3D Collision Detection: A Survey

Section 1: Introduction
Description 1: This section introduces the topic of 3D collision detection, highlighting its importance in various fields such as Computational Geometry, Robotics, and Computer Graphics. It provides an overview of the different approaches and aims of collision detection algorithms.

Section 2: Approaches to Collision Detection
Description 2: This section describes the various formulations of the collision detection problem based on different types of outputs and constraints. It categorizes the main approach used in handling the collision detection problem.

Section 3: Spatio-temporal intersection
Description 3: Discusses the most general representation of collision detection problems through the extrusion operation and the challenges associated with implementing this approach.

Section 4: Swept Volume Interference
Description 4: This section explains the concept of swept volume used in detecting collisions and the computational costs involved. It also covers different strategies to simplify this approach.

Section 5: Multiple Interference Detection
Description 5: Describes the method of collision detection by repeatedly applying a static interference test at sampled intervals, highlighting the importance of adaptive sampling techniques.

Section 6: Trajectory Parameterization
Description 6: In this section, the collision detection is performed by parameterizing object trajectories, explaining the mathematical and computational complexities involved.

Section 7: Static Interference Detection
Description 7: Reviews efficient strategies for static interference detection, including methods specific to convex and non-convex polyhedra, and discusses ways to handle various polyhedral configurations.

Section 8: Strategies for Time and Space Bounding
Description 8: Focuses on reducing the computational expense of collision detection by restricting the application of the interference test using strategies like distance computation, bounding collision areas, and prioritizing collision pairs.

Section 9: Conclusions
Description 9: Summarizes the findings of the survey, comparing different collision detection algorithms and their practical applications in the fields of Computational Geometry, Robotics, and Computer Graphics. Discusses future research directions.