-
Navid Mirzayousef Jadid authoredNavid Mirzayousef Jadid authored
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:
- Armadillo, from the Stanford Scan repository
- Happy Buddha, from the Stanford Scan repository
- Max Planck, from the Princeton Model Repository
- Stanford Bunny, from the Stanford Scan repository
- Giraffe, modeled by Hermann Meißenhelter (CGVR, Uni Bremen)
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
andcollision 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
, andcollision 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
, andcollision 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
- export each frame of the animation in
- 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.