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

• Guilherme Amadio
• Andrei Gheata

Links

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

• VecGeom

Participating Organizations

• CERN

---