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

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

Rhadamés Carmona (Universidad Central de Venezuela, Venezuela) and Héctor Navarro (Universidad Central de Venezuela, Venezuela)
DOI: 10.4018/jcicg.2012010102
OnDemand PDF Download:
List Price: $37.50


Collision detection has been studied for scenes containing only polygonal objects (surfaces) or only volumes. With the evolution of the graphics hardware, surfaces and volumes can be rendered together, demanding new challenges for the area of collision detection. In this order of ideas, the authors propose the first approach for volume-surface collision detection, with GPU support. A mapping from surface space to texture space is established, such as each mesh fragment has a 3D texture coordinate. The volume-surface collision is tested in the fragment shader, verifying if a surface fragment is texturized with an opaque voxel. OpenGL® occlusion query extension is used to count the number of mesh fragments colliding with the volume. Since one surface can be texturized with multiple volume textures, the authors’ approach is naturally extended to discard collision between one surface and several volumes in a single pass, with a minimum impact in the rendering time. The authors’ tests reveal that collision between thousands of volume-mesh pairs can be evaluated in one second, showing that our solution is ideal for real-time applications.
Article Preview

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.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 8: 2 Issues (2017): Forthcoming, Available for Pre-Order
Volume 7: 2 Issues (2016)
Volume 6: 2 Issues (2015)
Volume 5: 2 Issues (2014)
Volume 4: 2 Issues (2013)
Volume 3: 2 Issues (2012)
Volume 2: 2 Issues (2011)
Volume 1: 2 Issues (2010)
View Complete Journal Contents Listing