Rapid pairwise intersection tests using programmable GPUs

Yoo Joo Choi, Young J. Kim, Myoung Hee Kim

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


Detecting self-intersections within a triangular mesh model is fundamentally a quadratic problem in terms of its computational complexity, since in principle all triangles must be compared with all others. We reflect the 2D nature of this process by storing the triangles as multiple 1D textures in texture memory, and then exploit the massive parallelism of graphics processing units (GPUs) to perform pairwise comparisons, using a pixel shader. This approach avoids the creation and maintenance of auxiliary geometric structures, such as a bounding volume hierarchy (BVH); but nevertheless we can plug in auxiliary culling schemes, and use stencils to indicate triangle pairs that do not need to be compared. To overcome the readback bottleneck between GPU and CPU, we use a hierarchical encoding scheme. We have applied our technique to detecting self-intersections in extensively deformed models, and we achieve an order of magnitude increase in performance over CPU-based techniques such as [17].

Original languageEnglish
Pages (from-to)80-89
Number of pages10
JournalVisual Computer
Issue number2
StatePublished - Feb 2006


  • Collision detection
  • Computer animation
  • Deformable body simulation
  • Geometric modeling
  • Programmable shaders


Dive into the research topics of 'Rapid pairwise intersection tests using programmable GPUs'. Together they form a unique fingerprint.

Cite this