Skip to content
Snippets Groups Projects
Code owners
Assign users and groups as approvers for specific file changes. Learn more.

kDet Tetrahedron Animation Benchmarks

This repository contains different animations of colliding tetrahedron meshes in varying resolutions. Each benchmark contains the tetrahedron data for each model once (since the topologies do not change) and the vertex data for each frame. The benchmarks were used to test the runtime of kDet for tetrahedral meshes.

Table of Contents

Animations

This repository contains the following animations:

Description Topology Changes? Recording Provided?
Bunny & Planck a stiff model of Max Planck's head falling onto a deformable Stanford bunny
Buddha & Armadillo a deformarble armadillo falling onto a non-deforming buddha model
Armadillos two deformable armadillo models moving towards and colliding with each other
Giraffes same as buddha & armadillo, but with two lower resolution giraffes; great for debugging & testing
Pass Through Armadillos an armadillo passing through another stationary armadillo along the x-axis (both armadillos are model resolution 2); great for debugging & testing

The animations were created with SOFA framework, using their FEM solver (for the scene files s. Scene Files).

Most animations are provided in varying resolutions, which are all included in the .zip-archives under animations/. After unzipping, the resolution is indicated with the final digit of the directory names (s. Model Resolutions). Furthermore, same-titled animations use the same scene configuration (s. Scene Files), but always turn out (slightly) different due to the solving process & different parameters for the FEM models.

The following chart shows the number of frames per animation as well as the selected young modulus (YM) & poisson ratio (PR) for each model:

#frames Model A Model B
YM PR YM PR
Bunny & Planck - 1 140 100,000 0.2 5,000 0.3
Bunny & Planck - 2 130 100,000 0.2 5,000 0.3
Bunny & Planck - 3 140 100,000 0.2 12,000 0.3
Bunny & Planck - 4 120 100,000 0.2 24,000 0.3
Buddha & Armadillo - 1 160 - - 10,000 0.3
Buddha & Armadillo - 2 160 - - 10,000 0.3
Buddha & Armadillo - 3 160 - - 10,000 0.3
Buddha & Armadillo - 4 160 - - 10,000 0.3
Armadillos - 1 130 300,000 0.2 300,000 0.2
Armadillos - 2 140 350,000 0.2 300,000 0.2
Armadillos - 3 210 400,000 0.2 400,000 0.2
Armadillos - 4 260 450,000 0.2 450,000 0.2
Giraffes 170 - - 20,000 0.4
Pass Through Armadillos 160 - - - -

Also .mp4 screen recordings of the animations are provided, though only in one model resolution (usually 3 or 4). Each scene is provided once with solid surface rendering and once with vertex only rendering. Check the media directory for the mp4-files.

Solid Surface Rendering Vertex Only Rendering

Models

The 3d models used for the animations can be found in models. The files are provided in tetgen-format (.node\.ele) and sometimes also in PLY-format (.ply), though only the former were used for the animations.

Most triangle models were taken from https://github.com/alecjacobson/common-3d-test-models which itself sourced the models from various sites. The following models were used in the animations:

Most models were rescaled, retriangulated, and finally meshed with tetgen with the p and q options (see p. 33 tetgen manual):

-p Tetrahedralizes a piecewise linear complex (PLC)
-q Refines mesh (to improve mesh quality)

Model Resolutions

Most models are provided in 4 resolutions, indicated by the final digit of the file name. The resolutions are as follows:

digit in filename #tetrahedra
1 ~10k
2 ~20-30k
3 ~44-57k
4 ~85-100k

Exact #tetrahedra

filename \ resolution 1 2 3 4
Armadillo 10,121 20,052 49,218 83,804
Happy Buddha 10,433 28,584 49,616 87,158
Max Planck 10,093 21,240 43,648 92,387
Stanford Bunny 10,308 29,274 56,924 99,201
filename resolution
Giraffe 1,904

Exact #vertices

filename \ resolution 1 2 3 4
Armadillo 3,051 5,912 15,233 25,159
Happy Buddha 3,380 8,647 15,046 26,450
Max Planck 3,079 6,290 12,673 26,507
Stanford Bunny 3,272 8,969 17,205 29,536
filename resolution
Giraffe 693

Scene Files

Animations featuring deformable objects were made with SOFA framework. Scene files for the animations can be found in sofa-scenes. If you like to run the animations, make sure the referenced model files are in a location that can be accessed and set the path in the scene files accordingly.

Notable Issue

Due to choice of parameters and scenes not checking for self collisions of the models (we could not get it to work) some of the frames turned out undesirable. For example, frame 109 of Armadillos-4.scn has the snout of the armadillos overly deform and penetrate through their own ear, before correcting back the next frame.

We tried to adjust parameters to minimize such occurences, but they still exist here and there.

kDet Benchmark Data

The benchmarks for tetrahedral kDet were run on a 64-Bit Windows 10 system with an Intel(R) Core(TM) i7-7800X with six cores and 3.50 GHz, 64 GB of RAM, and an NVIDIA GForce RTX 3080 with 10 GB of GPU memory. Frame times & further data can be found in kdet-benchmark-data/ in .csv-format (s. Included Data for each Method). The folder structure looks something like this:

kdet-benchmark-data
├── ...
├── <animation folder>
│   ├── ...
│   └── <benchmarking configuration>
│       ├── averaged.csv
│       └── raw
│           ├── 1.csv
│           ├── ...
│           └── 10.csv
└── ...

Each benchmarked animation has its own folder, e.g. armadillos-3, which then contains folders for each benchmarking configuration. Those contain the data for each run and as well as the averaged data for each frame.

The directory name for benchmarking configurations is built the following way:

<cd method>_<block size>_<overlap test>_<hash method>_<self cols?>_<#runs>.csv

The parameters and their possible values:

  • cd method: collision detection method
    • kdet-thrust: new kDet; finds all collision pairs
    • kdet-no-pairs: old kDet; does not find all collision pairs, only total set of colliding tetrahedra
    • gpu-loop: GPU brute-force method; launches a thread for each tetrahedron of the first object and checks against all tetrahedra of the second object in a loop; finds all collision pairs
    • gpu-no-loop: GPU brute-force method; launches a thread for each possible pair of tetrahedra to be checked; finds all collision pairs
  • block size: CUDA GPU block size
    • 16
    • 32
    • 64
    • 128
    • 256
  • overlap test: simplex overlap test
    • sat: Separating Axis Theorem
    • sat-no-edges: Separating Axis Theorem w/o Edge Tests
    • sat-mtv: Separating Axis Theorem w/ Minimum Translation Vector
    • gjk: Gilbert-Johnson-Keerthi
  • hash method: hashing algorithm
    • none (GPU brute-force only)
    • djb2
    • fnv-1a
    • morton-layered (reference)
    • simple-hash
  • self cols?: checked self collisions?
    • self-cols: checked for self collisions
    • no-self-cols: did not check for self collisions
  • #runs: number of runs
    • 10

Note: We did not benchmark every possible combination of parameters, only those relevant to our research.

CSV Headers

The .csv files all have a few header lines which include information about the benchmark. Example:

scene name, Buddha & Armadillo - 4
algorithm, kdet-no-pairs
cuda block size, 256
overlap test, sat
self collisions, no
hashing algorithm, djb2
compute global data time, 21.1566   // only included for kDet methods
#frames, 160
total runs for benchmark, 10
#tetsA, 26450
#tetsB, 25159
#verticesA, 87158
#verticesB, 83804

Included Data for each Method

The following data is provided per frame for each of the methods respectively:

  • kdet-thrust

    • frame: frame counter
    • host time: measured time on the host
    • device time: measured time on the device (GPU); is the sum of bbox time, grid populate time, self collision time, find all pairs time, sort pairs time and collision time
    • bbox time: time for calculating the bounding boxes of the objects
    • grid populate time: time for populating the grid
    • self collision time: time for calculating self collisions (only if self collisions were turned on)
    • find all pairs time: time for calculating all potential collision pairs
    • sort pairs time: time for sorting potential collision pairs & removing duplicates
    • collision time: time for calculating collisions between the objects
    • col tets A to B: #tetrahedra from A that collide with B
    • col tets B to A: #tetrahedra from B that collide with A
    • potential pairs w. dup: #potential pairs with duplicates, found by find all pairs
    • potential pairs: #potential pairs without duplicates, sorted and filtered by sort all pairs
    • collision pairs: number of collision pairs detected
    • self collision pairs A: number of self collision pairs detected for model A (only if self collisions were turned on)
    • self collision pairs B: number of self collision pairs detected for model B (only if self collisions were turned on)
  • kdet-no-pairs

    • frame: frame counter
    • host time: measured time on the host
    • device time: measured time on the device (GPU); is the sum of bbox time, grid populate time, self collision time, and collision time
    • bbox time: time for calculating the bounding boxes of the objects
    • grid populate time: time for populating the grid
    • self collision time: time for calculating self collisions (only if self collisions were turned on)
    • collision time: time for calculating collisions between the objects
    • col tets A to B: #tetrahedra from A that collide with B
    • col tets B to A: #tetrahedra from B that collide with A
    • collision pairs: [not used, since this method does not find collision pairs]
    • self collision pairs A: number of self collision pairs detected for model A (only if self collisions were turned on)
    • self collision pairs B: number of self collision pairs detected for model B (only if self collisions were turned on)
  • gpu-loop & gpu-no-loop

    • frame: frame counter
    • host time: measured time on the host
    • device time: measured time on the device (GPU); is the sum of bbox time, self collision time, and collision time
    • bbox time: time for calculating the bounding boxes of the objects
    • self collision time: time for calculating self collisions (only if self collisions were turned on)
    • collision time: time for calculating collisions between the objects
    • col tets A to B: #tetrahedra from A that collide with B
    • col tets B to A: #tetrahedra from B that collide with A
    • collision pairs: number of collision pairs detected
    • self collision pairs A: number of self collision pairs detected for model A (only if self collisions were turned on)
    • self collision pairs B: number of self collision pairs detected for model B (only if self collisions were turned on)

Additionally for the Pass Through Armadillos the bounding box overlap of the two objects in x-direction during each frame is provided.

Notes for Benchmarking

Because the collision detection in SOFA already corrects with penetration penalties, the final animations usually do not have colliding tetrahedron pairs. If desired, this can be accounted for by slightly translating the position data for benchmarking, if possible in the benchmarking software.

We recommend the following translations for the respective animations:

Animation Model Translation
Bunny & Planck B (0, 0.1, 0)
Buddha & Armadillo B (0, -0.1, 0)
Armadillos B (-0.1, 0, 0)
Giraffes B (0, -0.1, 0)

Furthermore, some animations might naturally have colliding tetrahedra pairs, be it inter object collisions or self collisions, due to choice of parameters in the scene or errors during computation (s. Notable Issue).

How to Contribute

Additions to this repository are greatly appreciated. Currently we are looking for the following kind of animations:

  • cloth simulations
  • animations where the topology of the models changes, e.g. explosions
  • recalculations of the provided animations with adjusted parameters, to correct some of the errors (s. Notable Issue)
  • one object animations which only check for self collisions
  • particle simulations

Current animations always have two objects, but this was only due to a technical limitation of the benchmarking software in the original study (which will hopefully be improved upon in the future). Therefore feel free to create scenes with multiple objects.

Additionally, scenes where the input models have varying sizes of tetrahedra in their meshes might be interesting.

Steps for Contributing

Please follow these steps when contributing:

  • create the animation in different resolutions (ideally in the ones we suggested in model resolutions, but higher resolutions are also welcome)
    • export each frame of the animation in tetgen format
    • if the topology of the objects does not change, providing one .ele-file per object is enough
  • add models to the repository
  • adjust the README and add sources for the models & software that were used for the created animation (check their licenses beforehand)
  • submit the additions via pull request

Despite using git LFS, due to filesize limits it might be necessary to add / commit certain files (like the .zip-archives of the animations) via the web interface.