A conservative continuous collision detection (CCD) method with support for minimum separation.
To know more about this work, please read our ACM Transactions on Graphics paper:
"A Large Scale Benchmark and an Inclusion-Based Algorithm for Continuous Collision Detection" and watch our SIGGRAPH 2022 presentation.
To compile the code, first, make sure CMake is installed.
To build the library on Linux or macOS:
mkdir build
cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
make -j4Then you can run a CCD example:
./app/Tight_Inclusion_binWe also provide an example that tests sample queries using our CCD method. This requires installing gmp on your system before compiling the code. Set the CMake option TIGHT_INCLUSION_WITH_SAMPLE_QUERIES to ON when compiling:
cmake .. -DCMAKE_BUILD_TYPE=Release -DTIGHT_INCLUSION_WITH_SAMPLE_QUERIES=ON
make -j4Then you can run ./app/Tight_Inclusion_bin to test the handcrafted and simulation queries in the Sample Queries.
- Include:
#include <tight_inclusion/ccd.hpp> - Check vertex-face CCD:
bool ticcd::vertexFaceCCD(...) - Check edge-edge CCD:
bool ticcd::edgeEdgeCCD(...)
💡 Each CCD function returns a boolean result corresponding to if a collision is detected. Because our method is conservative, we guarantee a result of false implies no collision occurs. If the result is true, there may not be a collision but we falsely report a collision. However, we can guarantee that this happens only if the minimal distance between the two primitives in this time step is no larger than tolerance + ms + err (see below for a description of these parameters).
For both vertex-face and edge-edge CCD, the input query is given by eight vertices which are in the format of Eigen::Vector3d. Please read our code in tight_inclusion/ccd.hpp for the correct input order of the vertices.
Besides the input vertices, there are some input and output parameters for users to tune the performance or to get more information from the CCD.
Here is a list of the explanations of the parameters:
-
err: The numerical filters of the$x$ ,$y$ and$z$ coordinates. It measures the errors introduced by floating-point calculation when solving inclusion functions. -
ms: A minimum separation distance (no less than 0). We guarantee a collision will be reported if the distance between the two primitives is less thanms. -
tolerance: User-specific solving precision. It is the target maximal$x$ ,$y$ , and$z$ length of the inclusion function. We suggest the to use1e-6. -
t_max: The time range$[0, t_{\max}]$ where we detect collisions. Since the input query implies the motion is in time interval$[0, 1]$ ,t_maxshould not be larger than 1. -
max_itr: The maximum number of iterations our inclusion-based root-finding algorithm can take. This enables early termination of the algorithm. If you setmax_itr < 0, early termination will be disabled, but this may cause longer running times. We suggest settingmax_itr = 1e6. -
no_zero_toi: For simulators which use non-zero minimum separation distance (ms > 0) to make sure intersection-free for each time-step, we have the optionno_zero_toito avoid returning a collision timetoiof 0. The code will continue the refinement in higher precision if the outputtoiis 0 under the giventolerance, so the eventualtoiwill not be 0. -
CCD_TYPE: Enumeration of possible CCD schemes. The default and recommended type isBREADTH_FIRST_SEARCH. If setDEPTH_FIRST_SEARCH, the code will switch to a naive conservative CCD algorithm but lacks our advanced features.
toi: The time of impact. If multiple collisions happen in this time step, it will return the earliest collision time. If there is no collision, the returnedtoivalue will bestd::numeric_limits<double>::infinity().output_tolerance: The resulting solve's precision. If early termination is enabled, the solving precision may not reach the target precision. This parameter will return the resulting solving precision when the code is terminated.
💡 The input parameter err is crucial to guarantee our algorithm is a conservative method not affected by floating-point rounding errors. To run a single query, you can set err = Eigen::Array3d(-1, -1, -1) to enable a sub-function to calculate the real numerical filters when solving CCD. If you are integrating our CCD in simulators, you need to:
- Include the headler:
#include <tight_inclusion/interval_root_finder.hpp>. - Call
and
std::array<double, 3> err_vf = ticcd::get_numerical_error()std::array<double, 3> err_ee = ticcd::get_numerical_error() - Use the parameter
err_eeeach time you callbool ticcd::edgeEdgeCCD()anderr_vfwhen you callbool ticcd::vertexFaceCCD().
The parameters for function ticcd::get_numerical_error() are:
vertices: Vertices of the axis-aligned bounding box of the simulation scene. Before you run the simulation, you need to conservatively estimate the axis-aligned bounding box in which the meshes will be located during the whole simulation process, and the vertices should be the corners of the AABB.is_vertex_face: A boolean flag corresponding to if you are checking vertex-face or edge-edge CCD.using_minimum_separation: A boolean flag corresponding to if you are using minimum-separation CCD (the input parameterms > 0).
To better understand or to get more details of our Tight-Inclusion CCD algorithm, please refer to our paper.
If you use this work in your project, please consider citing the original paper:
@article{Wang:2021:Benchmark,
title = {A Large Scale Benchmark and an Inclusion-Based Algorithm for Continuous Collision Detection},
author = {Bolun Wang and Zachary Ferguson and Teseo Schneider and Xin Jiang and Marco Attene and Daniele Panozzo},
year = 2021,
month = oct,
journal = {ACM Transactions on Graphics},
volume = 40,
number = 5,
articleno = 188,
numpages = 16
}
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent