The Gilbert-Johnson-Keerthi (GJK) algorithm, a descent method for computing the clos-est point pairs between convex objects, has been widely adopted in robotics, rigid-body dynamics, and computer graphics due to its generality and implementation simplicity. However, GJK exhibits numerical instability when handling degenerate geometries, leading to reduced convergence rates and erroneous judgments—primarily caused by the limited precision of Johnson’s distance subalgorithm. Although several methods have been proposed to address these issues, challenges remain in achieving both high efficiency and accuracy for performance-critical applications.
This thesis aims to implement an improved GJK algorithm to enable robust and efficient collision detection between convex objects in multibody dynamics simulations. The research begins with a comprehensive literature review to identify optimal enhancements for GJK, focusing on stabilizing degenerate cases and accelerating convergence. Subsequently, a C++-based implementation will be developed, integrating convex object modeling and hierarchical management within a multibody dynamics framework. Finally, the proposed method will be rigorously evaluated through benchmark tests and practical case studies, quantifying its performance gains in computational speed and precision compared to classical GJK.
Keywords: Computer Graphics, Collision Detection Algorithm, Convex Object, Dynamics Simulation
Requirements:
-
You are studying Electrical Engineering, Automation, or Robotics Systems Engineering.
-
You are interested in robot simulation or game physics engines; ideally, you have studied multibody dynamics or robotics dynamics.
- Ideally, you have programming skills in C++
Betreuer: Shao, Email:
