CHOI, Yoo-Joo, KIM, Young J., KIM, Myoung-Hee
yjchoi@smit.ac.kr, kimy@ewha.ac.kr, mhkim@ewha.ac.kr

Overview

We present an efficient collision detection algorithm using GPUs that is capable of reporting all pairs of intersecting triangles between two triangular mesh models. In particular, our proposed algorithm can be plugged into the narrow phase of any existing collision detection algorithms, where one must actually check for interferences between the triangles surviving different types of broad phased culling steps such as bounding volume hierarchies. Moreover, the algorithm itself without relying on any broad-phased culling scheme is still fast enough to check for a collision between moderately complex mesh models (e.g., 60 FPS for 1K triangles on NV40). The overall pipeline of our algorithm is shown as follows:

1. For each mesh, the position of each triangle is stored at three 1D textures, respectively. Then, a quadrilateral is texture mapped using the 1D triangle textures while the textures are periodically duplicated across the quadrilateral in the horizontal direction for one mesh and in the vertical direction for the other mesh. This step enables a pairwise checking between triangles.
2. A pair of triangles is symmetrically represented on the textured quadrilateral; i.e., the (i , j) and (j , i) triangle pairs represent the same triangle pairs. We avoid examining these duplicate triangle pairs by using the stencil test.
3. The triangle pairs that survive the stencil test are examined for collisions using the separating axis test (SAT). The SAT is fairly simple and thus well mapped to GPUs using the pixel shader. In particular, we first perform three SATs based on the AABBs of triangles, followed by eleven SATs based on the vertex/face and edge/edge combinations of a pair of triangles.
4. In order to effectively read collision results back from GPU, we render the collision results onto off-screen buffers (i.e., P-buffers) using a multi-pass rendering technique, where each pass hierarchically encodes lower-level collisions results, and then we read backwards from the highest level buffer to the lowest level buffer.

Related Publication

self-CD: Interactive Self-Collision Detection for Deformable Body Simulation Using GPUs, Yoo-Joo Choi, Young J. Kim, Myoung-Hee Kim,  Asian Simulation Conference, 2004 (to appear).

Note: This paper focuses on checking for a self-collision between deformable bodies; however, the main idea is almost identical.

Videos

Self-collision areas are colored cyan and  blue in cloth models.

Cloth model with 512 triangles. AVI (15.2MB)

Cloth model with 2048 triangles. AVI (25.1MB)

Examples

Results of Inter- and Self- Collision Detection (proposed in this article)

Collision detection between two mesh models.
Self- and inter- collision areas are colored red and green, respectively.

Complexity of Benchmarking Models for Inter-Object and Self Collisions

Algorithm Performance. Our algorithm can detect inter-object and self collisions for the benchmarking models at 16 FPS

Results of Self- Collision Detection Only (proposed in the self-CD paper)

Deformed Models with Self-Collisions. Self-colliding areas are colored red

Complexity of Benchmarking Models for Self-Collisions

Algorithm Performance. Our algorithm can detect self-collisions for the benchmarking models at 16-67 FPS

Comparison of Readback Performance. Notice that, using the hierarchical
readback scheme, the readback performance is improved by about 73.6%

Maintained by yjchoi@kgit.ac.kr