Simple and parallel proximity algorithms for general polygonal models

Youngeun Lee, Young J. Kim

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


We present simple and fast parallel proximity algorithms for rigid polygonal models. Given two polygon-soup models in space, if they overlap, our algorithm can find all the intersected primitives between them; otherwise, it reports their Euclidean minimum distance. Our algorithm is performed in a parallel fashion and shows scalable performance in terms of the number of available computing cores. The key ingredient of our algorithm is a simple load-balancing metric based on the penetration depth (PD) (for collision detection) and approximate Euclidean distance (for Euclidean distance computation) between bounding volumes. To compute the PD between oriented bounding boxes (OBBs), we present a novel algorithm based on the well-known separating axis theorem (SAT) and also shows that the PD can be trivially obtained as a byproduct of SAT. We have implemented these algorithms on a commodity PC with eight cores and benchmarked their performance on complicated geometric models. In practice, the performance of our algorithm shows up to 5 and 9.7 times improvement for collision and distance queries, respectively, compared to single core computation.

Original languageEnglish
Pages (from-to)365-374
Number of pages10
JournalComputer Animation and Virtual Worlds
Issue number3-4
StatePublished - May 2010


  • Collision detection
  • Distance calculation
  • Parallel algorithm
  • Penetration depth


Dive into the research topics of 'Simple and parallel proximity algorithms for general polygonal models'. Together they form a unique fingerprint.

Cite this