Fact-checked by Grok 2 weeks ago

Collision detection

Collision detection is the computational process of determining whether two or more objects in a digital simulation intersect or come into contact, often including the identification of contact points, penetration depths, and intersection times to enable realistic interactions.^[1] It serves as a foundational element in simulating physical phenomena, ensuring that objects do not unrealistically pass through one another in dynamic environments.^[2] In computer graphics and animation, collision detection is essential for applications such as video games, virtual reality, and film production, where it supports rigid-body dynamics, deformable object simulations, and crowd behaviors involving thousands of entities.^[1] Beyond graphics, it plays a critical role in robotics for path planning and obstacle avoidance, in computer-aided design (CAD) for assembly verification, and in physically-based modeling for accurate force computations in engineering simulations.^[3] The challenge lies in achieving real-time performance, as naive pairwise checks scale quadratically with the number of objects, necessitating efficient algorithms that balance accuracy and speed.^[4] Key techniques in collision detection are typically organized into phases: the broad phase uses bounding volume hierarchies (BVHs) like axis-aligned bounding boxes (AABBs) or oriented bounding boxes (OBBs) to quickly cull non-intersecting object pairs, often employing sweep-and-prune or spatial partitioning like grids for O(n + k) complexity where k is the number of potential collisions.^[1] The mid phase refines these candidates with more precise hierarchical tests, such as OBB-trees, while the narrow phase computes exact intersections using methods like the Gilbert-Johnson-Keerthi (GJK) algorithm for convex shapes or separating axis theorem (SAT) for polyhedra.^[2] For dynamic scenarios, continuous collision detection (CCD) predicts future intersections to handle high-speed motions, and specialized approaches address deformable or articulated models.^[1] Ongoing research focuses on GPU acceleration, multi-core parallelism, and robust handling of complex geometries with millions of primitives.^[3]

Introduction

Definition and Fundamentals

Collision detection is the computational process of determining whether, where, and when two or more objects in a simulated environment intersect or are likely to intersect in space and time.^[5] This involves analyzing the geometric representations of objects under motion or transformation to identify overlaps or potential contacts.^[6] It serves as a foundational step in simulating physical interactions, assuming a basic understanding of 3D geometry such as points, vectors, and transformations.^[3] The importance of collision detection lies in its role within physics engines, where it enables realistic interactions by preventing unintended overlaps in simulations and providing data for subsequent processing.^[3] In real-time systems, it supports decision-making by identifying intersections that could affect object trajectories, ensuring stability and fidelity in dynamic environments like games and robotics.^[7] Without accurate detection, simulations may exhibit artifacts such as objects passing through each other, compromising the integrity of the modeled world.^[8] Key terminology in collision detection includes objects, which can be rigid—maintaining fixed shape and volume during interactions—or deformable, allowing changes in geometry due to forces.^[9] Contact points refer to the specific locations where intersecting objects touch, often forming a contact manifold that describes the full set of such points across the intersection surface.^[10] Penetration depth measures the extent of overlap between objects, quantifying how deeply one has entered the other.^[11] Normal vectors at these contact points indicate the perpendicular direction to the surface, aiding in determining separation axes. Collision response, which follows detection, typically involves computing forces or displacements to separate objects and resolve the interaction, though details of resolution vary by system.^[8] Bounding volumes, such as spheres or boxes, provide simple enclosures for approximating object geometry during initial checks.^[11]

Historical Development

The origins of collision detection trace back to the emerging field of computational geometry in the 1970s, where foundational work on proximity queries and distance computations between geometric objects laid the groundwork for later algorithms. Pioneering efforts, such as Michael Shamos' 1978 PhD thesis on computational geometry, including work on nearest-neighbor searching and the closest-pair problem (building on his 1975 paper with Daniel Hoey), introduced efficient methods for determining minimal distances in sets of points, which served as precursors to more advanced techniques like the Gilbert-Johnson-Keerthi (GJK) distance algorithm developed in 1988. These early developments focused on static geometric problems in two and three dimensions, driven by applications in pattern recognition and database queries, rather than real-time dynamics.^[12] In the 1980s, advancements in computer graphics spurred the integration of hierarchical structures for efficient spatial queries, with bounding volume hierarchies (BVH) introduced by Steven M. Rubin and Turner Whitted in 1980 to accelerate ray-object intersections in rendering complex scenes.^[13] This hierarchical approach, using bounding volumes to prune unnecessary tests, was soon adapted for collision detection, enabling faster proximity checks in simulated environments. The decade also saw the formalization of convex optimization techniques, culminating in the GJK algorithm by Elmer G. Gilbert, Daniel W. Johnson, and S. S. Keerthi, which iteratively computes the minimum distance between convex polyhedra using support functions and the Minkowski difference. The 1990s marked a boom in real-time collision detection, propelled by the demands of interactive computer games and simulations. The sweep-and-prune (SAP) algorithm, first introduced by Cohen et al. in 1995, was adapted and popularized by Gino van den Bergen in his 1997 publication, a broad-phase method that sorts object bounding intervals along axes to efficiently identify potential colliding pairs, exploiting temporal coherence for performance in dynamic scenes. Concurrently, the separating axis theorem (SAT), rooted in earlier convex separation principles but popularized for narrow-phase tests, enabled robust intersection detection for convex polygons and polyhedra by projecting onto candidate axes.^[14] David Baraff's contributions during this period, including his 1992 PhD thesis on non-penetrating rigid body simulation, integrated collision response with dynamics, using impulse-based methods to handle contacts without penetration. The 2000s and 2010s shifted focus toward continuous collision detection (CCD) to prevent tunneling artifacts in high-speed simulations, with Erwin Coumans' Bullet Physics engine incorporating CCD features starting in 2005, building on van den Bergen's earlier convex collision libraries like SOLID. This era also saw growing integration with graphics processing units (GPUs) for parallel broad-phase culling, as demonstrated in early GPU-based BVH traversal methods from 2006 onward, which accelerated queries in large-scale virtual environments. Key contributors like van den Bergen and Baraff influenced open-source libraries and industry standards, emphasizing robustness and scalability. In the 2020s, collision detection has evolved with AI-assisted methods and advanced representations for deformable and robotic systems. Machine learning models, such as neural networks approximating distance-to-collision fields, have emerged to accelerate self-collision checks in articulated robots, reducing computational overhead while maintaining accuracy. Signed distance field (SDF)-based approaches have gained prominence for real-time detection in robotics, as reviewed in recent literature, enabling efficient collision-free motion planning for complex morphologies via implicit surface queries. These developments, highlighted in 2024 surveys on dynamic environment navigation, underscore a trend toward hybrid geometric-AI pipelines for enhanced precision in autonomous systems. In 2025, further advances include NeuralSVCD for efficient swept volume collision detection in dynamic scenes and improved probabilistic methods using superquadrics for accurate shape approximation in robotic motion planning.^[16]^[17]^[18]

Core Concepts

Discrete versus Continuous Detection

Collision detection algorithms are broadly classified into two paradigms: discrete and continuous, distinguished by how they handle the temporal aspect of object motion in simulations. Discrete collision detection, also known as a posteriori detection, evaluates potential overlaps between objects at fixed time intervals, typically corresponding to simulation frames or steps. This approach checks the positions of objects at the beginning and end of each time step to determine if interpenetration has occurred, making it computationally efficient with a typical complexity of O(n²) for n objects in naive implementations, though optimizations reduce this in practice. However, it is susceptible to the tunneling problem, where fast-moving objects can pass through each other without detection if their relative speed exceeds the distance covered in a single time step relative to their size.^[19] In contrast, continuous collision detection, or a priori detection, predicts collisions by analyzing the continuous trajectories of objects over time intervals, ensuring no tunneling occurs.^[19] It models motion using swept volumes—the spatial regions traced by moving objects—or ray casting along velocity vectors to find exact contact times.^[20] This method computes the time of impact (TOI), the earliest time t within [0, 1] (normalized to the time step) at which objects intersect, allowing the simulation to advance precisely to that moment.^[20] For linear motion, the TOI is the scalar parameter t solving the parametric equation \mathbf{position}(t) = \mathbf{b} + t \mathbf{d} (with $0 \leq t \leq 1) for intersection with the separating geometry, often using projected distances along relevant axes or normals.^[21] A representative example is the sphere-line sweep, where a sphere of radius R moves linearly from center \mathbf{B} along direction \mathbf{D} (with \|\mathbf{D}\| as the distance traveled). To detect intersection with a static plane defined by normal \mathbf{N} and constant C_p, the distance from the moving center \mathbf{C}(t) = \mathbf{B} + t \mathbf{D} to the plane is |\mathbf{N} \cdot \mathbf{C}(t) + C_p|. Setting this equal to R yields the quadratic equation |\mathbf{N} \cdot (\mathbf{B} + t \mathbf{D}) + C_p| = R, solved for t as:

t = \frac{ \pm R - (\mathbf{N} \cdot \mathbf{B} + C_p) }{ \mathbf{N} \cdot \mathbf{D} },

producing two roots clamped to [0, 1]; intersection exists if the interval overlaps.^[21] This derivation extends to more complex primitives via Minkowski difference, but solving often involves quadratic equations, increasing computational cost.^[20] The trade-offs between these paradigms are significant: discrete methods are faster and simpler, suitable for low-speed scenarios or when sub-frame accuracy is unnecessary, but they fail at high velocities where tunneling risks simulation instability.^[19] Continuous methods provide exactness and robustness, essential for applications like robotics or high-fidelity physics, yet they are more expensive due to root-finding operations and trajectory integrations, often scaling poorly for many objects.^[19] Hybrid approaches mitigate these issues by combining both paradigms. Conservative advancement, for instance, iteratively advances the simulation to the earliest TOI by estimating relative motion bounds, using discrete checks for coarse filtering and continuous refinement for precision, thus balancing efficiency and accuracy.^[22]

Bounding Volumes and Primitives

Bounding volumes are simplified geometric shapes that enclose complex objects to approximate their spatial extent, thereby reducing the computational cost of collision detection by allowing quick rejection of non-intersecting pairs before performing more expensive exact tests.^[23] Common types include axis-aligned bounding boxes (AABBs), oriented bounding boxes (OBBs), spheres, capsules, and cylinders, each offering trade-offs in tightness of fit and intersection test efficiency.^[23] AABBs align their edges with the world coordinate axes and are defined by minimum and maximum coordinates along each axis, making them the fastest for intersection checks due to simple min-max comparisons.^[23] OBBs align with the object's local coordinate system for a tighter enclosure but require more complex tests involving projections onto separating axes.^[23] Spheres are defined by a center and radius, ideal for roughly spherical objects, while capsules combine a cylinder with hemispherical caps for better approximation of elongated shapes like limbs, and cylinders suit rotational symmetry.^[23] The intersection test for two AABBs determines no overlap if, on any axis i (where i \in \{x, y, z\}), the maximum extent of one box is less than the minimum extent of the other:

\max(\mathbf{A}_i) < \min(\mathbf{B}_i) \quad \text{or} \quad \max(\mathbf{B}_i) < \min(\mathbf{A}_i)

This separability theorem enables rapid culling with minimal arithmetic operations.^[23] Tighter volumes like OBBs improve accuracy by reducing false positives but increase test complexity, often involving dot products of edge vectors and cross products for axis alignment.^[23] Sphere intersections simply compare the distance between centers against the sum of radii, providing constant-time performance.^[23] Capsule and cylinder tests compute distances between their defining line segments, adjusted by radii, balancing enclosure quality and speed.^[23] Collision primitives serve as the fundamental building blocks for exact narrow-phase tests in mesh-based representations, where complex surfaces are decomposed into simpler elements such as points (vertices), edges (line segments), and faces (typically triangles).^[24] In polygonal meshes, these primitives enable precise intersection queries by reducing full mesh tests to combinations of vertex-face, edge-edge, and edge-face checks, which are essential for handling deformable or detailed geometries.^[24] Triangles, as the most common face primitive, approximate curved surfaces while allowing efficient barycentric coordinate computations for contact points.^[24] Selection of bounding volumes depends on balancing enclosure tightness, which minimizes overestimation and false intersections, against computational speed for updates and tests; for instance, spheres are preferred for rounded objects due to their simplicity and rotational invariance, while AABBs suit axis-aligned scenarios despite potential looseness.^[25] For dynamic objects undergoing motion or deformation, bounding volumes must be updated frequently, often through refitting processes that recompute extents based on current vertex positions to maintain validity without full reconstruction.^[26] These primitives and volumes are applicable in both discrete and continuous detection paradigms to approximate and refine spatial overlaps over time.^[23]

Broad-Phase Algorithms

Spatial Partitioning

Spatial partitioning is a broad-phase collision detection technique that divides the three-dimensional space into discrete cells or regions to group objects efficiently, enabling rapid elimination of non-interacting object pairs by limiting intersection tests to objects within the same or adjacent cells. This approach leverages the spatial locality of objects, assigning them to cells based on the positions of their bounding volumes, such as axis-aligned bounding boxes (AABBs), and typically reduces the computational complexity from the brute-force O(n²) pairwise checks to near-linear O(n + k) time, where n is the number of objects and k is the number of potential colliding pairs.^[27] Uniform grids represent one of the simplest forms of spatial partitioning, overlaying the scene with a regular lattice of equal-sized cubic cells whose dimensions are chosen to approximate the average object size. Objects are inserted into cells via hashing their bounding volume centers or extents, and potential collisions are queried only among objects sharing a cell or its 26 immediate neighbors in 3D, making it particularly effective for static scenes or environments with uniformly distributed small objects. This method's simplicity allows for constant-time insertions and queries in the average case, though it requires careful cell sizing to avoid excessive overlaps.^[28] For scenes with uneven object distributions, adaptive spatial structures like octrees and k-d trees provide more efficient partitioning by recursively subdividing space based on object density or geometric features. Octrees, which divide space into eight equal octants at each level, adaptively refine denser regions, achieving a construction time of O(n log n) for n objects and enabling logarithmic query times for collision candidate retrieval. Similarly, k-d trees perform binary partitioning along alternating coordinate axes, balancing the tree to handle clustered data while supporting efficient nearest-neighbor and overlap queries essential for broad-phase culling. These structures excel in scenarios with varying scales, such as complex environments in interactive simulations, but incur higher preprocessing costs compared to uniform grids.^[28]^[29] The primary advantages of spatial partitioning include its scalability for large numbers of small objects, where it drastically prunes unnecessary tests, and its straightforward parallelization potential on modern hardware. However, it struggles with large objects that span multiple cells, leading to redundant checks across many cells, and performs poorly in highly dynamic scenes without frequent rebuilding, which can be costly. To address these limitations in dynamic contexts, modern variants like optimized hash grids have emerged, employing perfect hashing and lazy updates to handle moving objects efficiently; these are widely adopted in game engines such as Unity for particle simulations and crowd systems, offering near-constant update times even in the 2020s.^[30]^[29]

Sweep and Prune

The sweep and prune (SAP) algorithm, also known as sort and sweep, is a broad-phase collision detection technique designed to efficiently identify potential colliding pairs among multiple objects by exploiting spatial separation along coordinate axes. It projects the bounding volumes, typically axis-aligned bounding boxes (AABBs), of objects onto one or more axes (x, y, z in 3D), representing each as an interval defined by its min and max endpoints. These endpoints are collected and sorted into separate lists for each axis, allowing the algorithm to "sweep" a virtual line through the sorted order to detect overlapping intervals. Pairs of objects whose projections overlap on all axes are reported as potential colliders, pruning away non-overlapping pairs without full geometric tests. This approach significantly reduces the computational cost from exhaustive O(n²) pairwise checks to a more manageable set, making it suitable for dynamic simulations with hundreds or thousands of objects.^[31] In implementation, the algorithm maintains sorted endpoint lists using data structures like arrays or linked lists to facilitate efficient updates. For each axis, min and max endpoints are tagged and sorted; during the sweep, an active list tracks objects whose intervals currently overlap the sweep position, with enter/exit events triggered at each endpoint to add or remove objects from the active set. Potential collision pairs are accumulated by intersecting active lists across all axes (e.g., via bitwise operations or set intersections for efficiency). To handle dynamic scenes, temporal coherence is exploited: between simulation steps, only moved objects have their endpoints removed and reinserted via insertion sort, minimizing resorting costs. This incremental update keeps the process lightweight, often using flags to toggle pair activity during endpoint swaps in the sorted lists. The algorithm extends naturally to 2D by using only two axes, reducing overhead for planar scenarios.^[31] The time complexity is O(n log n + k) in the worst case, where n is the number of objects and k is the number of output potential pairs, dominated by initial sorting; however, with temporal coherence in animated scenes where objects move incrementally, it achieves expected O(n + k) performance per frame, as few insertions occur. Empirical results from early implementations demonstrate processing over 1,000 complex polytopes in under 1/20 second on mid-1990s hardware, highlighting its scalability for interactive applications when motion is coherent.^[31] Variants of SAP address specific challenges, such as projecting intervals onto rotated axes aligned with the principal axes of object bounding volumes (e.g., oriented bounding boxes or OBBs) to improve pruning accuracy and reduce false positives from axis-aligned biases. These rotated projections adapt to object orientation, offering tighter separation for non-axis-aligned motions at the cost of additional computation for axis transformation. Other extensions include bi-dimensional SAP, which simplifies to two axes for approximate culling in large 3D datasets, or kinetic variants that handle continuous motion by prioritizing events in time-parameterized projections.^[32]^[33] Despite its efficiency, SAP has limitations, including sensitivity to axis alignment, where objects moving parallel to projection axes may produce overlapping intervals even if spatially separated, leading to excess pairs. Degenerate cases, such as clusters of objects with synchronized motions or high rotational velocities, increase endpoint swaps and degrade the benefits of temporal coherence, potentially reverting to near-quadratic behavior in dense scenes. The algorithm performs best with small inter-frame displacements and may require hybrid use with other methods for highly rotational or sparse environments.^[31]

Bounding Volume Hierarchies

Bounding volume hierarchies (BVHs) are tree structures that organize a set of geometric objects for efficient broad-phase collision detection by enclosing groups of objects in progressively larger bounding volumes, enabling rapid culling of non-intersecting pairs. Each node in the tree represents a bounding volume—such as an axis-aligned bounding box (AABB), oriented bounding box (OBB), or sphere—that approximates the spatial extent of its descendants, with leaf nodes typically containing single primitives or tight bounds around individual objects like triangles or vertices. This hierarchical representation, often binary for simplicity, allows for scalable querying in complex scenes with thousands of objects, as originally adapted from ray tracing techniques to collision detection in the mid-1990s.^[34]^[35] BVHs are constructed either top-down or bottom-up to balance tree depth and tightness of enclosures. Top-down construction begins at the root with all primitives, recursively partitioning them using heuristics like longest axis splits or surface area minimization to create child subsets, ensuring a balanced tree with O(n log n) build time for n objects. Bottom-up construction starts from leaf nodes with individual primitive bounds and iteratively clusters pairs of nearby objects into parent volumes, often guided by proximity metrics to minimize volume overlap. In dynamic scenes, such as those involving deformable models, refitting updates existing hierarchies by recomputing bounding volumes bottom-up along affected paths without full reconstruction, preserving the tree topology for real-time performance.^[25]^[36] Traversal for detecting collisions between two BVHs employs a recursive descent algorithm that prunes unnecessary computations. Beginning at the roots, the process tests for intersection between the current pair of node volumes using separating axis tests or similar checks; if no overlap exists, entire subtrees are culled. Intersecting nodes recurse to their children, terminating at leaves where primitive intersection tests occur only if required. This approach, known as a separating intersection volume check, exploits the hierarchy to avoid exhaustive pairwise evaluations.^[34]^[36] The logarithmic depth of a well-constructed BVH reduces collision queries to O(log n) average time complexity, dramatically lowering the number of tests—from O(n^2) in naive methods to a fraction involving only potential candidates—making it suitable for interactive applications. Originating in 1980s ray tracing with hierarchical bounding slabs, BVHs were extended to collision detection through early systems like OBB-tree-based RAPID, achieving sub-millisecond detection for rigid models with hundreds of thousands of triangles.^[37]^[34]^[36] Advanced dynamic BVH variants support efficient updates for moving or deforming objects via techniques like tree rotations to maintain balance or targeted insertion/deletion along paths from root to leaf, each costing O(log n) time by adjusting only ancestor volumes. Refitting in AABB trees, for instance, enables collision detection on deformable meshes by propagating changes upward, often completing in linear time relative to the deformed subset while keeping overall query costs low.^[35]^[38]

Narrow-Phase Algorithms

Primitive Intersection Tests

Primitive intersection tests form a core component of narrow-phase collision detection, where the focus is on determining exact overlaps between basic geometric shapes such as spheres, axis-aligned bounding boxes (AABBs), rays, triangles, capsules, and edges. These tests are essential for verifying contacts after broad-phase culling has identified potential pairs, enabling efficient and precise simulations in real-time applications. Bounding volumes like spheres and AABBs serve as enclosures for more complex primitives, simplifying initial checks before delving into detailed intersections.^[39] The sphere-sphere intersection test is one of the simplest and most computationally efficient methods, checking whether two spheres overlap by comparing the Euclidean distance between their centers to the sum of their radii. Specifically, two spheres with centers C_1 and C_2 and radii r_1 and r_2 intersect if \|C_1 - C_2\| \leq r_1 + r_2, where \|\cdot\| denotes the L2 norm; this can be computed using the squared distance to avoid expensive square roots, yielding \|C_1 - C_2\|^2 \leq (r_1 + r_2)^2. For dynamic scenarios involving moving spheres, the test extends to solving a quadratic equation at^2 + 2bt + c = 0, where a = \|v_1 - v_2\|^2, b = (C_1 - C_2) \cdot (v_1 - v_2), c = \|C_1 - C_2\|^2 - (r_1 + r_2)^2, and v_1, v_2 are velocities, to find the earliest collision time t \geq 0. This approach requires minimal instructions, often 11 in SIMD-optimized implementations, making it suitable for high-frequency queries.^[39] Axis-aligned bounding box (AABB) intersection tests determine overlap between two boxes by performing independent checks along each principal axis (x, y, z). For AABBs defined by min-max intervals [A_{\min}, A_{\max}] and [B_{\min}, B_{\max}], no overlap exists if A_{\max_i} < B_{\min_i} or A_{\min_i} > B_{\max_i} for any axis i; intersection occurs only if overlap is confirmed on all axes. In dynamic cases with relative velocity v, the test uses the slab method: for each axis i with v_i \neq 0, compute t_1 = \frac{A_{\min_i} - B_{\max_i}}{v_i}, t_2 = \frac{A_{\max_i} - B_{\min_i}}{v_i}; then per-axis t_{\text{enter},i} = \min(t_1, t_2), t_{\text{exit},i} = \max(t_1, t_2). Overall, t_{\text{enter}} = \max(0, \max_i t_{\text{enter},i}), t_{\text{exit}} = \min(1, \min_i t_{\text{exit},i}), reporting collision if t_{\text{enter}} \leq t_{\text{exit}}. For v_i = 0, check static overlap on that axis; if no overlap for any axis, no collision. This method leverages the orthogonality of axes for rapid evaluation, typically completing in 16-19 CPU cycles with SIMD, while handling division-by-zero via separate static checks.^[39] Ray-triangle intersection is a fundamental test for ray tracing and raycast queries, with the Möller-Trumbore algorithm providing a fast, storage-efficient solution using barycentric coordinates. Given a ray \mathbf{P}(t) = \mathbf{O} + t\mathbf{D} (origin \mathbf{O}, direction \mathbf{D}) and triangle vertices \mathbf{V_0}, \mathbf{V_1}, \mathbf{V_2}, the algorithm solves for intersection parameter t and coordinates u, v such that \mathbf{P}(t) = (1 - u - v)\mathbf{V_0} + u\mathbf{V_1} + v\mathbf{V_2}, with t \geq 0, u \geq 0, v \geq 0, and u + v \leq 1. This is achieved by forming edges \mathbf{E_1} = \mathbf{V_1} - \mathbf{V_0}, \mathbf{E_2} = \mathbf{V_2} - \mathbf{V_0}, computing determinant \det = \mathbf{D} \cdot (\mathbf{E_1} \times \mathbf{E_2}), and using Cramer's rule for t = [(\mathbf{O} - \mathbf{V_0}) \times \mathbf{E_1}] \cdot \mathbf{E_2} / \det, u = [\mathbf{D} \times \mathbf{E_2}] \cdot \mathbf{E_1} / \det, v = [\mathbf{D} \cdot ((\mathbf{O} - \mathbf{V_0}) \times \mathbf{E_1})] / \det; backface culling can skip if \det < 0. The method avoids explicit plane equations, reducing preprocessing and enabling real-time performance in rendering pipelines.^[40]^[39] Capsule-edge intersection approximates a capsule as a line segment with hemispherical endcaps (or a finite cylinder with radius r) and tests against an edge (line segment). The process first finds the closest points between the capsule's axis segment and the edge, then checks if their distance is at most r; if the closest points lie outside segments, endpoint sphere tests are performed. For static cases, this reduces to distance queries between segments, while dynamic versions solve quadratics for the earliest intersection along the capsule's cylindrical surface or endcaps, akin to ray-cylinder tests. This method is particularly useful for character limbs or ropes, balancing simplicity and accuracy in skeletal animations.^[39] Handling edge cases is crucial for robustness in primitive tests, particularly degenerate primitives like zero-length edges or zero-area triangles, which can arise from modeling errors or numerical drift. For zero-length edges in capsule-edge tests, the intersection simplifies to a sphere-point check at the endpoint, while for degenerate triangles in ray-triangle tests, the algorithm may report invalid barycentrics, requiring fallback to edge-ray tests or mesh preprocessing to ensure non-zero areas. Numerical stability is maintained through epsilon tolerances (e.g., \epsilon = 10^{-6}) in comparisons to absorb floating-point errors, such as adding \epsilon to zero checks for near-parallel rays (|\mathbf{N} \cdot \mathbf{D}| < \epsilon) or using squared distances to avoid roots. Additional techniques include vector normalization before cross products to prevent precision loss and interval arithmetic for bounding errors in critical determinants, ensuring reliable results across varying scales and orientations.^[39]

Convex Object Collision Detection

Collision detection for convex objects leverages the geometric properties of convexity to efficiently determine intersections or separations between shapes such as polyhedra, capsules, or spheres, which are common in rigid body simulations. Unlike primitive tests that focus on basic geometric elements like edges or faces, methods for convex objects exploit global properties, such as the existence of separating hyperplanes or support mappings, to avoid exhaustive pairwise checks. These techniques are particularly effective because convex sets guarantee that any line segment connecting two points within the set lies entirely inside it, enabling robust algorithms for both discrete and penetrating contacts.^[11] The Separating Axis Theorem (SAT) provides a foundational approach for detecting collisions between convex polyhedra by identifying potential separating axes where the projections of the two objects do not overlap. According to SAT, two convex objects do not intersect if there exists at least one axis—typically derived from the face normals or edge cross-products of the objects—onto which their orthogonal projections are disjoint; otherwise, they intersect. For oriented bounding boxes (OBBs), this involves testing up to 15 axes: the three face normals from each box (six total) and the nine pairwise cross-products of those normals. Projections onto these axes can be computed efficiently using dot products with the vertices or by leveraging primitive intersection tests for bounding boxes. This method is widely used due to its simplicity and exactness for convex shapes, though its efficiency depends on the number of axes tested.^[11] The Gilbert-Johnson-Keerthi (GJK) algorithm offers an iterative, feature-based method for computing the minimum distance between two convex sets or detecting penetration, relying on the support function to query extreme points without enumerating all vertices. The support function for a convex object A in direction v is defined as h_A(v) = \max_{x \in A} \langle x, v \rangle, where \langle \cdot, \cdot \rangle denotes the dot product, allowing the algorithm to build a simplex (a point, line segment, triangle, or tetrahedron in 3D) that approximates the closest features. GJK operates on the Minkowski difference A - B = \{a - b \mid a \in A, b \in B\}, treating relative motion as a translation of one object relative to the other; if the origin lies inside the simplex of this difference set, the objects intersect, and the algorithm terminates early for detection. The process iterates by selecting new support points to expand or shrink the simplex until convergence, typically requiring few iterations for practical shapes. Introduced in 1988, GJK is valued for its sublinear complexity in the number of features and applicability to any convex representation supporting the support function, such as polyhedra or implicit surfaces.^[41] To resolve penetration depth and contact normals beyond mere intersection, the Expanding Polytope Algorithm (EPA) extends GJK by growing the initial simplex from GJK into a polytope that envelopes the Minkowski difference, yielding the deepest penetration vector. Starting from the intersecting simplex, EPA repeatedly adds support points in the direction toward the origin, forming new boundary facets until the origin lies on the polytope's surface; the vector from the origin to the nearest facet then provides the penetration depth and normal. This algorithm maintains the efficiency of support function queries, with worst-case complexity linear in the number of features but practical performance often constant for simple convexes. EPA is particularly useful for resolving overlaps in dynamic simulations, as it directly computes the minimal translation to separate objects.^[11] These methods underpin rigid body dynamics in real-time applications, such as the NVIDIA PhysX engine, which employs GJK for proximity queries and EPA for penetration resolution among convex shapes like capsules and boxes to ensure stable, high-performance simulations in games and animations.^[42]

Non-Convex and Deformable Object Handling

Handling non-convex objects in collision detection often involves decomposing complex static meshes into simpler convex components, such as through tetrahedralization, which partitions the volume into tetrahedra whose convex hulls can then be tested using established convex intersection methods.^[43] This approximate convex decomposition (ACD) iteratively removes non-convex features like notches to generate a set of convex hulls that approximate the original shape, enabling efficient broad- and narrow-phase queries while minimizing the number of primitives.^[44] For feature-based tests on triangle meshes, algorithms perform edge-face and vertex-face intersection checks to detect penetrations between non-convex surfaces, with methods such as the fast triangle-triangle intersection test by Möller (1997) providing robust pair evaluations by separating intersecting and non-intersecting cases through signed distances and separating axes.^[45] Voxel-based approaches represent non-convex volumes as discrete grids, where occupancy queries allow rapid detection of potential overlaps by checking voxel intersections before refining to surface geometry.^[46] In deformable models like cloth or soft bodies, continuous collision detection (CCD) is essential to capture inter-frame penetrations, often using distance fields to compute the minimum separation between deforming elements or proxy volumes such as hierarchical bounding spheres to approximate dynamic shapes for culling.^[9] Self-collision in these models is managed through cage structures, where nested or hierarchical cages enclose the deforming mesh to detect intra-object contacts by testing cage intersections and propagating to the underlying geometry.^[47] Recent advances leverage signed distance fields (SDFs) for implicit surface representations, enabling real-time collision queries between general deformable solids in robotics by computing exact distances without explicit meshing, as demonstrated in 2024 frameworks that integrate SDFs with trajectory optimization for safe manipulation.^[48] GPU-accelerated voxel hashing further enhances scalability for large-scale deformable scenes, using spatial hash tables to dynamically allocate voxels only where needed, supporting multi-scale representations for efficient volume queries in simulations.^[49] Key challenges include the high computational cost of updating decompositions or fields during frequent deformations, which can degrade real-time performance, and managing topology changes like tearing in cloth that invalidate precomputed structures and require adaptive rebuilding.^[9]^[50]

Advanced Techniques

Exploiting Temporal Coherence

In animated scenes, collision detection algorithms can exploit temporal coherence—the observation that object motions are typically smooth and continuous between consecutive frames—to reuse computational results from prior time steps, thereby reducing the workload for subsequent detections. This approach caches intersecting object pairs and incrementally updates them based on small velocity changes, avoiding full recomputation of spatial relationships. For instance, in bounding volume hierarchies (BVHs), persistent data structures like the Bounding Volume Test Tree maintain a "front" of potentially colliding nodes from the previous frame, sprouting or pruning branches only where motion warrants it, leading to significant speedups for oriented bounding boxes (OBBs) in cases of small displacements.^[51] Specific methods leverage this coherence through incremental maintenance of data structures. In sweep and prune algorithms, sorted lists of axis-aligned bounding boxes (AABBs) from the prior frame are rotated or adjusted via local swaps rather than fully resorting, exploiting the fact that relative object orders change minimally with smooth motion; this reduces the average complexity from O(n log n) to near O(n in highly coherent scenarios. Motion bounds provide conservative tests by enclosing an object's swept volume over a time interval within a simple shape, such as a sphere or capsule, allowing quick rejection of non-colliding pairs without exact trajectory integration; the controlled conservative advancement technique advances simulation time by the minimum safe interval bounded by these volumes, ensuring no collisions are missed while minimizing tests.^[31]^[52] To further localize updates, islanding groups objects into connected components based on prior contacts or joints, treating isolated "islands" as independent sub-simulations that only require broad-phase checks within their boundaries, thus scaling efficiency with scene sparsity. These techniques yield significant gains in real-time applications, such as rigid body simulations, where coherent motions dominate, but their effectiveness diminishes with abrupt changes like explosions or teleportations, necessitating hybrid strategies that trigger full rebuilds when coherence thresholds are exceeded.^[53]

GPU and Parallel Acceleration

Collision detection in large-scale scenes benefits significantly from GPU acceleration, which exploits the single instruction, multiple data (SIMD) architecture to parallelize computations across thousands of cores. In the broad phase, GPUs enable efficient parallel traversal of bounding volume hierarchies (BVHs), where multiple rays or queries can be processed simultaneously using frameworks like CUDA or OpenCL. This approach distributes the workload by assigning independent traversal tasks to GPU threads, achieving speedups of up to 10x over CPU implementations for scenes with millions of primitives.^[54]^[55] General-purpose computing on GPUs (GPGPU) extends to narrow-phase primitive tests, such as batch ray-triangle intersections, where kernels perform vectorized computations on groups of triangles to detect overlaps. For instance, optimized ray-triangle algorithms on GPUs can process billions of tests per second by leveraging shared memory and warp-level primitives, reducing latency in real-time applications.^[56]^[57] In handling deformable objects, signed distance field (SDF) volumes computed in shaders provide a continuous representation for collision queries, allowing efficient distance computations between deforming meshes without explicit triangle tests. This technique integrates seamlessly with GPU pipelines, enabling real-time detection for cloth or soft bodies by sampling SDFs in fragment shaders.^[58]^[59] Prominent frameworks like NVIDIA's PhysX have incorporated GPU solvers since the 2010s, offloading rigid body collision detection to CUDA for scenes with thousands of objects, yielding performance gains of 5-20x in broad- and narrow-phase culling.^[60]^[61] On the CPU side, parallelization complements GPU efforts through multi-threading techniques, such as sorting sweep-and-prune (SAP) structures using parallel radix sort algorithms that distribute axis-aligned bounding box (AABB) endpoints across cores. Temporal coherence aids in load balancing for irregular workloads, ensuring scalable broad-phase performance for scenes with millions of objects on multi-core processors.^[62] Recent advances as of 2025 include machine learning approaches for robot self-collision detection, integrating positional encoding with neural networks to improve accuracy in cluttered environments.^[63] Despite these advantages, GPU acceleration faces trade-offs, including memory bandwidth limitations that bottleneck irregular data access patterns during BVH traversal or primitive fetches in non-uniform scenes. Additionally, narrow-phase bottlenecks persist for complex contacts, as GPU efficiency drops for sequential dependency-heavy tasks, often requiring hybrid CPU-GPU pipelines to maintain overall throughput.^[64]^[55]

Pruning and Optimization Strategies

Pairwise pruning techniques refine the set of candidate object pairs generated by broad-phase algorithms, eliminating those unlikely to collide through additional spatial or distance-based checks. These methods often employ distance thresholds to skip pairs separated by more than a predefined margin, such as the sum of object radii plus a safety buffer, thereby avoiding expensive narrow-phase tests. For instance, in sphere-based representations, a pair is pruned if the distance between centers exceeds the combined radii, a test that can be performed in constant time. Voronoi regions further enhance this by defining boundaries around object features (e.g., vertices, edges, faces) where the closest points on colliding objects must lie, allowing early rejection of pairs whose Voronoi diagrams do not overlap. These approaches are particularly effective in dense scenes, reducing the number of full intersection tests by orders of magnitude.^[39] A priori pruning predicts non-collisions before detailed geometric tests by analyzing object motions, such as relative velocity vectors between pairs. By projecting the relative velocity onto face normals, faces with negative dot products—indicating motion away from the surface—can be culled, effectively pruning up to 50% of potential checks in polyhedral scenes. For translational motions between convex polyhedra, applicability constraints limit valid contact types (e.g., vertex-face or edge-edge) based on velocity directions, achieving near-linear complexity with a small constant factor. These predictive culls are especially useful in dynamic simulations where objects exhibit coherent trajectories, minimizing redundant computations without sacrificing accuracy.^[65] Further optimizations include level-of-detail (LOD) representations, which use simplified geometries for distant or low-priority objects to reduce collision complexity while maintaining accuracy for nearby interactions. Dynamic LOD adjusts hierarchy density based on object proximity or importance, integrating with bounding volume trees to prune subtrees of low-detail models efficiently. Batching groups similar tests (e.g., via SIMD instructions) to exploit cache locality and parallelism, processing multiple pairwise checks in vectorized operations for up to 4x speedup on sphere tests. These techniques ensure cache-efficient traversal in hierarchical structures, minimizing memory accesses during pruning.^[66]^[39] Effective pruning strategies typically reduce candidate pairs to less than 1% of the naive O(n²) total, with benchmarks showing broad-phase outputs dropping from 55 potential pairs to 10 for 11 objects, and overall detection times of 2-5 ms per frame in interactive applications. Oriented bounding box trees, for example, outperform axis-aligned variants by processing O(m) tests instead of O(m²) for m primitives, while discrete oriented polytopes (DOPs) with 18 facets yield optimal balance in pruning efficiency.^[39]^[67]

Applications

In Computer Graphics and Simulations

In computer graphics, collision detection plays a crucial role in rendering pipelines, particularly through ray-object intersections that enable accurate computation of shadows and reflections. Rays are traced from the camera or light sources to determine intersections with scene geometry, ensuring realistic light transport effects such as hard and soft shadows or specular reflections on surfaces.^[1] Bounding volume hierarchies (BVHs) accelerate these intersections by organizing scene primitives into a spatial tree structure, reducing the number of ray-primitive tests from linear to logarithmic complexity.^[1] In offline rendering engines like Blender's Cycles, BVHs are built per frame or scene to support path tracing, where millions of rays per pixel intersect complex models for photorealistic outputs.^[68] In physics-based simulations, collision detection integrates with rigid and soft body dynamics to prevent interpenetrations and compute realistic responses. For rigid bodies, discrete collision detection checks overlaps at simulation timesteps, while continuous collision detection (CCD) predicts exact contact times during motion, avoiding tunneling artifacts in high-speed scenarios.^[69] Soft body simulations, often using finite element methods (FEM), rely on CCD to handle deformable materials like rubber or tissue, where element-wise intersection tests ensure stability across deformation steps.^[70] Cloth simulations address self-collisions by detecting and resolving intersections between adjacent or distant triangles in the mesh, using techniques like predictive contacts to maintain fabric integrity without excessive stretching or folding.^[71] Narrow-phase algorithms, such as triangle-triangle tests, are employed within these simulation loops to verify contacts after broad-phase culling.^[1] Open-source physics engines like Bullet and ODE facilitate collision detection in graphics simulations, supporting rigid body stacks, constraints, and deformable extensions for animation workflows. Bullet provides robust broad- and narrow-phase detection with CCD support, enabling stable stacking of thousands of objects in visual effects scenes.^[72] ODE offers modular collision geometries and friction models, integrated into tools for simulating jointed mechanisms or particle systems.^[73] Commercial software like Houdini employs advanced collision detection in its DOP networks for VFX production, using volume or surface-based methods to handle particle-fluid or rigid-fracture interactions in films.^[74] Key challenges in these applications include balancing detection accuracy with performance constraints, such as maintaining 60 frames per second (FPS) in interactive previews while processing scenes with millions of primitives. High-fidelity CCD can increase computational cost by orders of magnitude, necessitating hybrid acceleration via spatial partitioning or GPU offloading to prune unnecessary tests.^[69] Recent 2025 reviews of deformable model collision detection highlight hybrid discrete-continuous approaches, combining timestep-based checks with motion prediction to improve efficiency in FEM-based soft body simulations without sacrificing robustness.^[75]

In Video Games

In video games, collision detection is often implemented using hitboxes, which are simplified geometric shapes such as rectangles in 2D or capsules and boxes in 3D that approximate the visual model of an object for rapid intersection testing. These hitboxes enable fast input handling and response mechanics, like character movement or projectile impacts, by decoupling precise visual rendering from computational geometry; for instance, a character's capsule hitbox detects ground contact without testing every polygon of the mesh.^[76] Bounding volumes form the foundation of these hitboxes, providing an efficient proxy for more complex shapes.^[77] Major game engines integrate collision detection through dedicated physics systems, such as Unity's integration with NVIDIA PhysX, which employs a sweep-and-prune (SAP) algorithm for broad-phase culling of potential collisions and the Gilbert-Johnson-Keerthi (GJK) algorithm for narrow-phase testing of convex shapes. Similarly, Unreal Engine's Chaos Physics uses GJK for distance calculations between convex geometries in the narrow phase, combined with spatial partitioning for broad-phase efficiency to handle dynamic scenes with thousands of objects. These implementations support layered queries, where collision checks are filtered by object categories—such as triggers for non-physical events versus full physics simulations—reducing unnecessary computations via layer collision matrices that ignore predefined layer pairs.^[78]^[79]^[80] Optimizations extend to multiplayer networking, where synchronization ensures consistent collision outcomes across clients; typically, server-side collision detection resolves disputes to prevent cheating, while client-side prediction simulates immediate responses for low-latency feel, reconciling with server authoritative results. Common issues include tunneling, where fast-moving objects like projectiles pass through thin barriers between frames, mitigated by continuous collision detection (CCD) modes that compute exact time-of-impact along motion paths rather than discrete frame checks. In mobile games, hardware constraints necessitate reduced precision, such as using simpler axis-aligned bounding boxes (AABB) over oriented ones and limiting collision checks via spatial partitioning to maintain frame rates on lower-powered devices.^[81]^[82]^[83] The evolution of collision detection in video games traces from 1980s 2D arcade titles using basic AABB for pixel-perfect or rectangular overlaps in platformers, to modern 3D open-world environments leveraging bounding volume hierarchies (BVH) for scalable detection amid vast numbers of dynamic elements, as seen in large-scale simulations requiring real-time performance.^[84]^[76]

In Robotics and Autonomous Systems

In robotics, proximity sensing plays a crucial role in collision detection, enabling robots to perceive and avoid obstacles in dynamic environments. Light Detection and Ranging (LIDAR) sensors provide high-resolution 3D point clouds for accurate distance measurement, while ultrasonic sensors complement them by detecting soft or low-reflectivity objects that LIDAR might miss, such as those on the ground or at varying heights. For manipulator path planning, octree-based algorithms efficiently represent complex environments by hierarchically partitioning 3D space into voxels, facilitating rapid collision checks during motion planning. The MoveIt! framework, integrated with the Robot Operating System (ROS), leverages these octrees to generate collision-free trajectories for robotic arms, optimizing for real-time performance in tasks like assembly and manipulation.^[85]^[86] In autonomous vehicles, real-time obstacle detection relies on processing LIDAR-generated point clouds to identify and track dynamic objects, such as pedestrians or other vehicles, with algorithms clustering points and estimating velocities for immediate response. Vehicle-to-Everything (V2X) communication enhances predictive avoidance by sharing intent and position data between vehicles and infrastructure, allowing preemptive maneuvers to prevent collisions beyond line-of-sight. Signed Distance Fields (SDFs) serve as a key method for environment mapping in robotics, representing surfaces implicitly to enable efficient collision queries and navigation; recent frameworks, such as online learning of continuous SDFs from depth images, support dynamic updates for mobile robots. Reviews of human-robot collaboration highlight integrated sensor fusion for collision avoidance, emphasizing power- and force-limiting strategies to ensure safe coexistence in shared workspaces.^[87]^[88] Safety standards like ISO/TS 15066 guide collaborative robot design by specifying limits on force, pressure, and speed during human interactions, mandating collision detection mechanisms to halt operations upon impact. Handling uncertainty in sensor data is essential, with probabilistic models accounting for noise in LIDAR or ultrasonic readings to maintain robust detection, often using Bayesian filtering to predict potential collisions under partial observability. Advances include machine learning approaches for anomaly detection in collisions, such as unsupervised algorithms that identify deviations in joint torques or vibrations, enabling proactive safety responses in manipulators. In fusion robotics applications, novel collision detection algorithms estimate fast ion losses in tokamak devices by simulating particle trajectories against wall geometries, improving predictive maintenance for high-energy environments.^[89]^[90]^[91]^[92]^[93]

References

[1]
[PDF] Real-Time_Rendering_4th-Collision_Detection.pdf
Collision detection (CD) is a fundamental and important ingredient in many computer graphics applications. Areas where CD plays a vital role include virtual ...
[2]
[PDF] Collision Detection: Algorithms and Applications - GAMMA
Collision detection is a fundamental problem in robotics, computer animation, physically-based mod- eling, molecular modeling and computer simulated en-.
[3]
Collision Detection and Proximity Queries - GAMMA UNC
Collision detection has been a fundamental problem in computer animation, physically-based modeling, geometric modeling, and robotics. In these applications, ...
[4]
[PDF] Collision Detection for Interactive Graphics Applications - Brown CS
To work in these applications, a collision-detection algorithm must run at real-time rates, even when many objects can collide, and it must tolerate objects ...
[5]
Real-Time Triangle-SDF Continuous Collision Detection
Aug 8, 2025 · This paper introduces a novel triangle-SDF collision detection algorithm using spatio-temporal optimization, solving for the first time of ...
[6]
https://ieeexplore.ieee.org/document/4414258
[7]
Introduction | SpringerLink
Collision detection is a fundamental technique in each situation where we interact with virtual objects, including computer graphics, robotics and haptics.
[8]
Collision Detection and Response for Computer Animation
This paper discusses collision detection and response in general, presents two collision detection algorithms, describes modeling collisions of arbitrary bodies ...Missing: definition | Show results with:definition
[9]
[PDF] Collision Detection for Deformable Objects - Hal-Inria
Nov 25, 2010 · If compared to collision detection approaches for rigid bodies, there are various aspects that complicate the prob- lem for deformable objects.Missing: terminology | Show results with:terminology
[10]
Interval Methods for Multi-Point Collisions between Time-Dependent ...
Second, our method can solve the difficult problem of detecting collision points on a contact manifold. We have found the methods described here to be ...
[11]
[PDF] Proximity Queries and Penetration Depth Computation on 3D Game ...
In this paper, we focus on methods for performing collision detection, distance computation, and penetration depth computation on convex objects. Several.
[12]
The IMA Volumes in Mathematics and its Applications
Basic Engineering, pages 35-45, March 1960. [7] S.S. KEERTHI AND E.G. GILBERT. Optimal infinite-horizon feedback laws for a gen- eral class of constrained ...
[13]
A 3-dimensional representation for fast rendering of complex scenes
This paper describes a method whereby the object space is represented entirely by a hierarchical data structure consisting of bounding volumes, with no other ...
[14]
[PDF] An Introduction to Physically Based Modeling: Rigid Body ...
1Collision detection (i.e. determining the points of contact between bodies) runs a close second though! D1. Page 3. Part I. Unconstrained Rigid Body Dynamics.
[15]
[PDF] Physically Based Modeling Rigid Body Simulation
In rigid body dynamics then, we consider collisions as occurring instantaneously. This means we have two types of contact we need to deal with. When two ...
[16]
Review on Motion Planning of Robotic Manipulator in Dynamic ...
Nov 21, 2024 · This paper provides a detailed review of motion planning algorithms designed for robotic manipulators working in dynamic environments.<|control11|><|separator|>
[17]
[PDF] Fast Continuous Collision Detection between Rigid Bodies - Hal-Inria
Jun 2, 2009 · This paper introduces a fast continuous collision detection technique for polyhedral rigid bodies. As opposed to most collision detection ...Missing: seminal | Show results with:seminal
[18]
[PDF] Continuous Collision Detection and Physics | GameDevs.org
Instead of using ballistic motion, we use constant linear and angular velocity to describe D. Similar to van den Bergen [2], we use the Minkowski Sum of both.
[19]
[PDF] Collision Detection with Swept Spheres and Ellipsoids - Jorrit Rouwé
May 28, 2003 · After that we will derive the intersection between a static polygon and a swept sphere and that of a static polygon with a swept ellipsoid.
[20]
[PDF] Continuous Collision - Box2D
Conservative advancement works by considering the distance between two moving shapes. ... • Gino van den Bergen, Ray Casting against General Convex Objects with ...
[21]
[PDF] Geometric Primitives & Proximity Detection | GameDevs.org
Sphere-Sphere Collision. » Compute distance d between centers. » If d < r ... » Key: swept sphere axis is line segment with surrounding radius. » Compute ...
[22]
[PDF] Fast Collision Detection for Deformable Models using ...
Each triangle consists of three types of features: vertices, edges and faces. For discrete CD, the exact tests can be reduced to six elementary tests between ...
[23]
[PDF] Bounding Volume Hierarchies for Collision Detection - IntechOpen
Mar 30, 2012 · Simple bounding-volume seems to perform faster intersection test while tight bounding-volume goes for the accuracy but slow intersection test.<|control11|><|separator|>
[24]
[PDF] Fast Collision Detection for Skeletally Deformable Models
The main problem with this approach is the update of bounding volumes – they must follow the current deformation of the model. We introduce a new fast ...
[25]
[PDF] Collision detection between geometric models: a survey - GAMMA
Abstract. In this paper, we survey the state of the art in collision detec- tion between general geometric models. The set of models include.
[26]
[PDF] Collision Detection in Interactive 3D Environments
Gino van den Bergen. ELSEVIER. AMSTERDAM • BOSTON • HEIDELBERG • LONDON. NEW ... 5.4.1 Sweep and Prune. 210. 5.4.2 Implementing the Sweep-and-Prune ...Missing: 1997 | Show results with:1997
[27]
[PDF] Collision Detection: A Survey - Rose-Hulman
Jun 1, 2014 · Abstract—A process of determining whether two or more bodies are making contact at one or more points is called collision detection or ...
[28]
[PDF] Optimized Spatial Hashing for Collision Detection of Deformable ...
This paper describes a new algorithm for the detection of collisions and self–collisions of de- formable objects based on spatial hashing. The al- gorithm ...
[29]
[PDF] An Interactive and Exact Collision Detection System for Large-Scale ...
1 INTRODUCTION. Collision detection is a fundamental problem in computer animation, physically-based modeling, computer simu- lated environments and robotics.
[30]
[PDF] Collision Detection for Continuously Deforming Bodies
... sweep and prune sorting technique suggested by Cohen et al.4 Initially, all ex- tents of the objects along the three principal axes are sorted into three lists.
[31]
Efficient collision culling by a succinct bi-dimensional sweep and ...
We present an improved variant of the broad phase collision-detection algorithm called Sweep and Prune (SaP) for large datasets in three-dimensional ...Missing: original paper
[32]
[PDF] OBB-Tree: A Hierarchical Structure for Rapid Interference Detection
We present a data structure and an algorithm for efficient and exact interference detection amongst complex models undergoing rigid motion.
[33]
Efficient Collision Detection of Complex Deformable Models using ...
Recent work has shown that AABB trees are slower than oriented bounding box (OBB) trees for performing overlap tests. In this paper, we describe a way to speed ...
[34]
[PDF] Efficient Collision Detection Using Bounding Volume Hierarchies of ...
... collision queries per second. In this paper, we develop and analyze a method, based on bounding-volume hierarchies, for efficient collision detection for.Missing: seminal | Show results with:seminal
[35]
None
Nothing is retrieved...<|control11|><|separator|>
[36]
[PDF] Dynamic Bounding Volume Hierarchies - Box2D
The tree consists of internal nodes and leaf nodes. The leaf nodes are the collision objects and the internal nodes only exist to accelerate collision queries.
[37]
[PDF] Real-Time Collision Detection
Real-time collision detection is a difficult but fundamental topic in computer games, involving algorithms, implementation, and geometric robustness.
[38]
None
### Summary of Möller-Trumbore Algorithm for Ray-Triangle Intersection
[39]
[PDF] A fast procedure for computing the distance between complex ...
21-30, 1985. [16] E. G. Gilbert, D. W. Johnson, and S. S. Keerthi, "A fast procedure for computing the distance between complex objects in three space ...Missing: original | Show results with:original
[40]
Advanced Collision Detection — NVIDIA PhysX SDK 3.4.0 ...
Collision detection is able to generate contact points between two shapes when they are still a distance apart, when they are exactly touching, or when they ...
[41]
[PDF] COMPUTATIONAL GEOMETRY
Tetrahedralization is an important process of convex decomposition. NOTE: Held, Klosowski and Mitechell. (1995) uses a tetrahedral mesh for checking.
[42]
[PDF] Approximate Convex Decomposition and Its Applications
ACD can help improve the efficiently of point location for non-convex models by replacing each ACD component with its convex hull and then performing the point ...Missing: tetrahedralization | Show results with:tetrahedralization
[43]
[PDF] A Fast Triangle-Triangle Intersection Test 1 Introduction 2 ...
This paper presents a method, along with some optimizations, for comput- ing whether or not two triangles intersect. The code, which is shown to be fast, can be ...
[44]
A voxel-based parallel collision detection algorithm
This work presents a simple voxel-based collision detection algorithm, an efficient parallel implementation of the algorithm, and performance results.
[45]
[PDF] Nested Cages - CS@Columbia
We demonstrate the effectiveness of our nested cages not only for multigrid solvers, but also for conservative collision detection, domain discretization for.
[46]
Real-time collision detection between general SDFs
Jun 1, 2024 · Signed Distance Fields (SDFs) have found widespread utility in collision detection applications due to their superior query efficiency and ...
[47]
[PDF] Real-time 3D Reconstruction at Scale using Voxel Hashing
The system uses a spatial hashing scheme for real-time 3D reconstruction, enabling fine-quality, large-scale reconstructions without a voxel grid.
[48]
[PDF] A-Fast-Culling-Scheme-For-Deformable-Object-Collision-Detection ...
Culling process for deformable objects is especially challenging due to the frequent changes of object shape and topology. There are mainly four different ...
[49]
https://niessnerlab.org/papers/2013/4hashing/niessner2013hashing.pdf
[50]
[PDF] C A: Controlled Conservative Advancement for Continuous Collision ...
In this section, we give a brief survey of prior work on continuous collision detection and motion bound computa- tions. A. Continuous Collision Detection.<|control11|><|separator|>
[51]
Simulation Islands - Box2D
Oct 8, 2023 · ... Collision Detection in Interactive 3D Environments. Spatial ... islands without understanding how a physics engine is put together.
[52]
Bulk-synchronous parallel simultaneous BVH traversal for collision ...
Gino van den Bergen. 1997. Efficient collision detection of complex deformable models using AABB trees. Journal of Graphics Tools 2, 4 (1997), 1--13.
[53]
[PDF] Fast GPU-based Collision Detection for Deformable Models - GAMMA
Our algorithm builds a BVH for the entire scene and performs top-down traversal to check for both inter-object and intra-object collisions. We make no assump-.
[54]
[PDF] GPU-Based Ray-Triangle Intersection Testing 1 Introduction
A quite common and fundamental problem in computer graphics is how to per- form stable intersection tests of rays with geometric primitives in minimal time.
[55]
[PDF] Performance Analysis for GPU-based Ray-triangle Algorithms
Ray-triangle and segment-triangle intersection tests are basic algorithms used for solving many prob- lems in Computer Graphics. This includes applica- tions ...
[56]
[PDF] Neural Collision Detection for Deformable Objects - arXiv
Feb 4, 2022 · We propose a neural network-based approach for collision detection with deformable objects. Unlike previous approaches based on bounding ...Missing: self- | Show results with:self-
[57]
[PDF] Real-time Collision Detection between General SDFs
Signed Distance Fields (SDFs) have found widespread utility in collision detection applications due to their superior query efficiency and ability to ...
[58]
GPU Simulation — physx 5.4.1 documentation
Jul 23, 2024 · Signed Distance Field (SDF) in PhysX is a powerful tool enhancing rigid bodies collision detection. SDFs represent the distance from any ...
[59]
Particles — NVIDIA PhysX SDK 3.3.4 Documentation
PhysX 3 takes care of collision detection and particle dynamics, while auxiliary facilities such as emitters, lifetime maintenance etc. need to be provided ...Particles · Particle Management · Gpu/cuda Acceleration
[60]
(PDF) Virtual Assembly Collision Detection Algorithm Using ...
Oct 15, 2024 · The optimized HBVT architecture not only accelerates the speed of collision detection but also significantly diminishes error rates, presenting ...<|separator|>
[61]
[PDF] Adaptive Collision Culling for Large-Scale Simulations by a Parallel ...
We propose a parallel Sweep and Prune algorithm that solves the dynamic box intersection problem in three di- mensions. It scales up to very large datasets, ...
[62]
How can I exploit multithreading in collision resolution?
Oct 12, 2015 · Multithreading can be achieved by solving islands of bodies separately, or by batching narrow phase pair-wise collision detection in separate ...
[63]
[PDF] Practical Collision Detection on the GPU
We have implemented and examined CInDeR, which is an algorithm for collision detection on the. GPU. CInDeR is an image-space algorithm and the results from the ...Missing: integration | Show results with:integration
[64]
[PDF] Collision Detection Algorithms for Motion Planning
In the context of collision detection, non-convex objects are usually approximated by simpler convex shapes, and a conservative lower bound on the distance is ...
[65]
Improvement of Collision Detection Performance of Hierarchies by ...
By using this algorithm, an LOD (level-of-detail) algorithm can be applied to 3D space to improve collision detection of 3D objects in a 3D space.
[66]
[PDF] Collision Detection and Proximity Queries SIGGRAPH 2004 Course
This course will primarily cover widely accepted and proved methodologies in collision detection. In addition more advanced or recent topics such as.<|control11|><|separator|>
[67]
BVH - Blender Developer Documentation
Cycles supports multiple ray-tracing acceleration structures, depending on the device. When rendering with multiple devices, a different BVH may be built for ...
[68]
[PDF] Interactive Simulation of Rigid Body Dynamics in Computer Graphics
Collision Detection for Rigid Body Dynamics. Collision detection provides important information used by rigid body dynamics. We briefly discuss the most ...<|control11|><|separator|>
[69]
[PDF] Efficient Geometrically Exact Continuous Collision Detection
This paper provides (1) the first CCD algorithm to guarantee safety and accuracy despite using rounded floating-point arithmetic, under the paradigm of Ex- act ...
[70]
[PDF] Chapter 9 Collision Detection in Cloth Modeling
Collision and self-collision detection are often the most time consuming part of the simulation algorithm. The collision algorithm described above provides ...
[71]
bulletphysics/bullet3: Bullet Physics SDK - GitHub
Bullet Physics SDK: real-time collision detection and multi-physics simulation for VR, games, visual effects, robotics, machine learning etc.
[72]
Manual - ODE - Open Dynamics Engine
May 14, 2019 · Before you start, you should know that there are two parts to ODE. There is "ODE", which is the physics and collision detection library.Introduction · Install and Use · Concepts · Joint Types and Functions
[73]
POP Collision Detect dynamics node - SideFX
The POP Collision Detect node finds collisions between particles and geometry. It stores the resulting collision information in a set of hit attributes.Overview · Parameters · Collision · BehaviorMissing: VFX | Show results with:VFX
[74]
(PDF) Collision Detection Algorithms for Deformable Models
Aug 8, 2025 · Collision Detection Algorithms for Deformable Models: A Literature Review. February 2025; Applied and Computational Engineering 134(1):146-154.Missing: hybrid | Show results with:hybrid
[75]
Hitboxes: A Survey About Collision Detection in Video Games
This paper surveys recent research and practice in Collision detection in computer gaming that is the detection when two or more objects collide with each ...
[76]
3D collision detection - Game development - MDN Web Docs
Jul 11, 2025 · This article provides an introduction to the different bounding volume techniques used to implement collision detection in 3D environments.Missing: capsules | Show results with:capsules
[77]
Unity - Manual: Choose a collision detection mode
### Summary of Unity Collision Detection Modes
[78]
Chaos::GJKDistance | Unreal Engine 5.6 Documentation
Chaos::GJKDistance. Find the distance and nearest points on two convex geometries A and B, if they do not overlap. On ...Missing: SAP | Show results with:SAP
[79]
Use the layer collision matrix to reduce overlaps - Unity - Manual
The Layer Collision Matrix controls how layers interact, reducing overlap checks by telling the physics system which layers to ignore during collision checks.
[80]
how to do client side prediction with server side collision detection?
Feb 28, 2018 · It is worth to mention what a client side prediction is. It is technique to perform a prediction of what an authoritative server will compute and respond with.Should collision detection be done server-side or cooperatively ...Collision detection in pong style multiplayer network gameMore results from gamedev.stackexchange.com
[81]
Continuous Collision Detection (Background Information)
Collision detection in 3d games detects whether objects are intersecting. The normal discrete collision detection does so by checking the objects at their ...Missing: 2005 | Show results with:2005
[82]
10 Strategies to Optimize Physics in Mobile Games - Daily.dev
May 27, 2024 · Reduced physics calculations lead to faster gameplay. Precise Collision Detection, Layer masks allow control over which objects collide.Missing: batching | Show results with:batching
[83]
Collision Detection in 2D and 3D: Concepts and Techniques
Efficient collision detection ensures smooth movement and prevents characters from sinking into the floor or passing through walls. Many 2D engines use tile- ...
[84]
[PDF] Near-Optimal Path Planning Using Octree Leafs for Industrial ...
Path Planning with Octrees. • Robot-independent path planning framework. • ROS or standalone solution for industrial robot controllers via position interface.Missing: manipulator | Show results with:manipulator
[85]
MoveIt Motion Planning Framework
Moving robots into the future. A motion planning, manipulation, and kinematics framework for ROS, ideal for students and university researchers.FAQs · Concepts · MoveIt 1 Binary Install · Planners Available in MoveIt
[86]
3D LiDAR-based obstacle detection and tracking for autonomous ...
Nov 14, 2023 · This paper proposes a 3D LiDAR-based obstacle detection and tracking method using u-depth and restricted v-depth representations from point ...
[87]
Collision Avoidance System at Urban Intersections Using V2X ...
Mar 31, 2025 · The system leverages V2X map data to identify warning zones and uses vehicle-to-vehicle (V2V) communication to estimate the maneuver types and ...
[88]
ISO/TS 15066:2016 - Robots and robotic devices
In stockISO/TS 15066:2016 specifies safety requirements for collaborative industrial robot systems and the work environment.
[89]
A review of the ISO 15066 standard for collaborative robot systems
This article reviews requirements for safety assurance of collaborative robot systems discussed in the recent ISO 15066 standard for collaborative robots.
[90]
Human-robot collision detection under modeling uncertainty using ...
Jan 22, 2015 · This paper presents the development and experimental evaluation of a collision detection method for robotic manipulators sharing a workspace ...
[91]
Collision Detection for Robot Manipulators Using Unsupervised ...
Nov 4, 2021 · In this article, we present two collision detection methods using unsupervised anomaly detection algorithms—a one-class support vector machine, ...
[92]
Development of novel collision detection algorithms for the ...
Aug 4, 2025 · Development of novel collision detection algorithms for the estimation of fast ion losses in tokamak fusion device. December 2024; Computer ...