README.md

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
• Models
  • Model Resolutions
• Scene Files
  • Notable Issue
• kDet Benchmark Data
  • CSV Headers
  • Included Data for each Method
• Notes for Benchmarking
• How to Contribute
  • Steps for Contributing

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