バリコードに基づくGJKアルゴリズム
Barycode-based GJK Algorithm
2D衝突検出と距離計算のためのGJKアルゴリズムをバリコードで改良し、最小単体判定の統一条件と高速な衝突判定サブルーチンを提案、主要ライブラリを上回る性能を示した。
著者: Yu Zhang, Yangming Wu, Xigui Wang, Xiaocheng Zhou
分類: cs.RO, cs.CG
原文アブストラクト
In this paper, we present a more efficient GJK algorithm to solve the collision detection and distance query problems in 2D. We contribute in two aspects: First, we propose a new barycode-based sub-distance algorithm that does not only provide a simple and unified condition to determine the minimum simplex but also improve the efficiency in distant, touching, and overlap cases in distance query. Second, we provide a highly efficient implementation subroutine for collision detection by optimizing the exit conditions of our GJK distance algorithm, which shows dramatic improvements in run-time for applications that only need binary results. We benchmark our methods along with that of the well-known open-source collision detection libraries, such as Bullet, FCL, OpenGJK, Box2D, and Apollo over a range of random datasets. The results indicate that our methods and implementations outperform the state-of-the-art in both collision detection and distance query.
