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 triangle-mesh objects that runs on the GPU. With this thesis, we extend kDet to 3D-objects 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 ~1-4ms for "realistic" collisions of two 100k tetrahedra models, and ~20-30ms when also calculating self-collisions.

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.

The blue tetrahedron has 3 larger tetrahedra (green) intersect its neighborhood area

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).

Tetrahedra are inserted into intersecting grid cells on the layer that corresponds to their "size".

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:

1. insert the tetrahedra into the hierarchical grid
2. traverse the grid and find all potential collision pairs
3. filter out duplicate pairs from the previous step
4. 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:

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 ~1-4ms 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 self-collisions of each object, the new version of kDet performs increasingly better for higher scene resolutions. For resolution 4 scenes, the old kDet needs ~30-45ms per frame, while in comparison, the new kDet method only needs ~20-30ms per frame.

In general, the frame times seem to scale "accordingly" with the scene resolution and self-collisions 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 self-collisions turn out very costly in comparison.

Files

• Full version of the master thesis (English only)
• Tetrahedron-mesh 3D-models 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 eur-lex.europa.eu.
The Thesis provided above (as PDF file) is licensed under Attribution-NonCommercial-NoDerivatives 4.0 International.
Any other assets (3D models, movies, documents, etc.) are covered by the Creative Commons Attribution-NonCommercial-ShareAlike 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.uni-bremen dot de.