Tetrahedral kDet: Linear Time Collision Detection for Tetrahedral Meshes
In 2017, Weller et. al. [1] first presented kDet, a linear time collision detection algorithm for trianglemesh objects that runs on the GPU. With this thesis, we extend kDet to 3Dobjects with tetrahedral meshes and show that it retains its linear runtime property, while computing additional information compared to the original algorithm. The demo application is written in C++ and CUDA and boasts frame times between ~14ms for "realistic" collisions of two 100k tetrahedra models, and ~2030ms when also calculating selfcollisions.
Description
The algorithm is based on the premise that for objects that are modelled after the real world, the number of larger primitives intersecting a certain neighborhood of a single primitive would be limited. Following that assumption, it is possible to prove that the maximum number of intersections between two sets that fulfill this property has a linear upper bound.
Following from said premise, the basic idea of the algorithm is to only check collisions against a primitives close neighbors that are "of the same" size or "larger" than itself. In order to achieve that, the tetrahedra are first inserted into a hierarchical grid, which assign each tetrahedra a layer depending on their "size" and grid cells on said layer. The grid is then traversed upwards when looking for collisions. The hierarchical grid itself is implemented as a hash table (such a construct is also known as a spatially hashed grid).
During traversal, we check which grid cells on higher layers are intersected by the primitive and check for collision against all primitives in those cells.
While the original algorithm only computes the total set of intersecting tetrahedra, the version we implemented finds all unique pairs of colliding tetrahedra.
The algorithm basically follows these four steps:
 insert the tetrahedra into the hierarchical grid
 traverse the grid and find all potential collision pairs
 filter out duplicate pairs from the previous step
 run intersection tests on the remaining, unique pairs
Results
For benchmarking, several animated scenes were created using a physical simulation solver. Every scene is provided in 4 different model resolutions each, which are described in the following table:
model resolution  #tetrahedra 

1  ~10k 
2  ~2030k 
3  ~4457k 
4  ~85100k 
Benchmarks were run with the old version of kDet (kDet  No Pairs) and our new version (kDet  Thrust) on each each scene and resolution. For evaluation, frame times between the different methods were compared.
When only computing collisions between objects, the two algorithms perform about the same and require roughly ~14ms per frame. However, it should once again be mentioned that the new algorithm finds all the individual collision pairs while the old one does not. We observe that the frame times do not differ much between the varying scene resolutions.
When also considering selfcollisions of each object, the new version of kDet performs increasingly better for higher scene resolutions. For resolution 4 scenes, the old kDet needs ~3045ms per frame, while in comparison, the new kDet method only needs ~2030ms per frame.
In general, the frame times seem to scale "accordingly" with the scene resolution and selfcollisions seem to add a lot of computation time.
Overall, we conclude that the new version of kDet performs just as good or better than the previous version. While interactive frame times are possible for collision detection between object, computing selfcollisions turn out very costly in comparison.
Files
 Full version of the master thesis (English only)
 Tetrahedronmesh 3Dmodels and animation benchmarks
 kDet Demo

Screenshot of the demo application:
References
[1] R. Weller, N. Debowski, G. Zachmann "kDet: Parallel Constant Time Collision Detection for Polygonal Objects", 04 2017.
License
This original work is copyright by University of Bremen.
Any software of this work is covered by the European Union Public Licence v1.2.
To view a copy of this license, visit
eurlex.europa.eu.
The Thesis provided above (as PDF file) is licensed under AttributionNonCommercialNoDerivatives 4.0 International.
Any other assets (3D models, movies, documents, etc.) are covered by the
Creative Commons AttributionNonCommercialShareAlike 4.0 International License.
To view a copy of this license, visit
creativecommons.org.
If you use any of the assets or software to produce a publication,
then you must give credit and put a reference in your publication.
If you would like to use our software in proprietary software,
you can obtain an exception from the above license (aka. dual licensing).
Please contact zach at cs.unibremen dot de.