Implementation of Gilbert-Johnson-Keerthi Algorithm for Convex Shapes in VecGeom
Description
The VecGeom project aims at developing a high-performance library for geometry modelling, describing geometry in terms of 3D solid primitives. Fast geometry queries are crucial in high energy physics (HEP) detector simulations. The VecGeom library provides vectorized implementations of ray-solid intersection algorithms and other functionality that make use of fine-grained SIMD and SIMT parallelism.
The Gilbert-Johnson-Keerthi algorithm is a fast algorithm for general convex shapes. The goal of this project is to implement the GJK algorithm in VecGeom/Geant4 to allow for the simplification and potentially speedup of several geometry primitives by sharing the same algorithm for their implementation. Using a common implementation is also helpful to run simulations on the GPU in the future.
Task ideas
We propose the following steps:
- Implementation of the GJK distance and ray-casting algorithms
- Implementation of validation and performance tests
- Performance comparison with current algorithms
Technology
- C++11, template programming
Desirable Skills
- Advanced C++ programming skills
- Experience with numerical algorithms
Expected results
- Development and validation of the GJK algorithm in Geant4/VecGeom
Mentors
Links
- VecGeom Gitlab Repository
- Gilbert-Johnson-Keerthi Distance Algorithm (Wikipedia)
- Improving the GJK Algorithm for Faster and More Reliable Distance Queries Between Convex Objects
- Real-Time Collision Detection by Christer Ericson (Morgan Kaufmann, 2005)