Collision Detection - yszheda/wiki GitHub Wiki

References

BVH

split

AABB

AABB and ray

OBB

SIMD for OBB intersection checking

Separating Axis Theorem (SAT)

Morton code

Broad Phase

Dynamic AABB Tree

Sweep and Prune

Narrow Phase

Expanding Polytope Algorithm (EPA)

concave

Continuous Collision Detection

multi-thread

GPU

occlusion query

Collision Detection Algorithms for Motion Planning

1 Introduction

    1. to find a lower time bound for the first collision
    1. to reduce the pairs of primitives within objects susceptible of interfering
    1. to cut down the number of object pairs to be considered for interference.

2 Interference detection

  • Constructive Solid Geometry (CSG)

  • Hierarchical volume representations

  • Object partition hierarchies: “S-bounds”

  • Space partition hierarchies

    • octree
    • binary space partition tree

2.2 Basic interference tests

  • Convex polyhedra
  • One convex and one one non-convex
  • Non-convex polyhedra: Decomposition into convex parts
  • Non-convex polyhedra: Direct approach

First, check if the edge endpoints are on opposite sides of the face plane. If so, check if the intersection point between the edge and the face plane is located inside the face by simply casting a ray from this point and determining how many times the ray intersects the polygon. Then, if this number is odd, the intersection does exists (odd-parity rule).

3 Collision detection

3.1 Four main approaches

Multiple interference detection

The simplest way to tackle collision detection consists in sampling the trajectories followed by the objects and repeatedly applying a static interference test.

  • adaptive sampling

Since the closest points between two objects lie always in their boundaries, it is usual practice to resort to boundary representations (B-rep) when following a multiple interference detection approach.

Swept volume interference

sufficient, but not a necessary condition

Extrusion in 4D space

  • extruded volume

The intersection of two extruded volumes is a necessary and sufficient condition for the occurrence of a collision between the corresponding objects as they move along their respective trajectories.

Trajectory parameterization

3.2 Strategies for space and time bounding

Distance computation for collision time bounding

  • spherical cones
  • spherical planes
The geometric approach
  • incremental distance algorithm
The optimization approach
Orientation-based pruning
Prioritizing collision pairs

4 Collision detection in motion planning

4.1 Global planners

4.2 Incremental planners

4.3 Local planners

Libraries

fcl

Bullet3

PhysX

Flex

HPCCD

https://sglab.kaist.ac.kr/HPCCD/

octomap

visualization

Trouble-shooting

PluginlibFactory: The plugin for class 'octomap_rviz_plugin/OccupancyGrid' failed to load.  Error: According to the loaded plugin descriptions the class octomap_rviz_plugin/OccupancyGrid with base class type rviz::Display does not exist.
  • source the setup script.