An Image-Space Approach for Collision Detection Between Multiple Volumes and a Surface

Prior Works

Hierarchical decomposition of the scene and objects has been widely used to reduce the number of pairs for intersection testing. Space subdivision and hierarchical bounding volumes are used to create a hierarchical representation of the scene. The goal of such hierarchies is to approximate the mesh topology on different levels of detail, usually by using simple polyhedra, leading to faster intersection tests. BSPs and octrees are common examples of techniques based on space subdivision. BSP trees (Fuchs et al., 1980) are mostly used for partitioning the static part of the scene. Each node of the BSP tree contains a single plane which divides the scene in two: one part located below the plane, and the other one located above it. Each half-space can be divided recursively in two, using the same principle. Different criterion can be used for selecting each plane; a basic approach chooses the plane which splits the largest axis of the axis aligned bounding box of the remaining scene. A more accurate approach may consider the difference in number of triangles of both sides and the number of polygons (or objects) intersected with the plane (Carmona, Kienholz, & Navarro, 2002). On the other hand, octrees (Wilhelms & Van Gelder, 1992) divide the scene in eight equal boxes. Each of those boxes are then recursively subdivided until all the data inside of the box is uniform, and no more subdivisions are required.