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 algoritm 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:

Technology

Desirable Skills

Expected results

Mentors

  1. VecGeom Gitlab Repository
  2. Gilbert-Johnson-Keerthi Distance Algorithm (Wikipedia)
  3. Improving the GJK Algorithm for Faster and More Reliable Distance Queries Between Convex Objects
  4. Real-Time Collision Detection by Christer Ericson (Morgan Kaufmann, 2005)

Corresponding Project

Participating Organizations