A tight inclusion function for continuous collision detection

Related tags

Deep Learningcollision-detectionccd
Overview

Tight-Inclusion Continuous Collision Detection

Build

A conservative Continuous Collision Detection (CCD) method with support for minimum separation.

You can read more about this work in our ACM Transactions on Graphics paper:

"A Large Scale Benchmark and an Inclusion-Based Algorithm forContinuous Collision Detection"

@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,
    journal = {ACM Transactions on Graphics}
}

Compiling Instruction

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

Then you can run a CCD example:

./Tight_Inclusion_bin

We also provide you an example to run the Sample Queries using our CCD method. You may need to install gmp before compiling the code. Then set the CMake option TIGHT_INCLUSION_WITH_TESTS as ON when compiling:

cmake ../ -DCMAKE_BUILD_TYPE=Release -DTIGHT_INCLUSION_WITH_TESTS=ON
make

Then you can run ./Tight_Inclusion_bin to test the handcrafted queries in the Sample Queries.

Usage

Include #include <tight_inclusion/inclusion_ccd.hpp>

To check edge-edge ccd, use bool inclusion_ccd::edgeEdgeCCD_double();

To check vertex-face ccd, use bool inclusion_ccd::vertexFaceCCD_double();

💡 If collision is detected, the ccd function will return true, otherwise, the ccd function will return false. Since our method is CONSERVATIVE, if the returned result is false, we guarantee that there is no collision happens. If the result is true, it is possible that there is no collision but we falsely report a collision, but 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. We wil explain these parameters below.

For both edge-edge ccd and vertex-face ccd, the input CCD query is presented by 8 vertices which are in the format of Eigen::Vector3d. Please read our code in tight_inclusion/inclusion_ccd.hpp for the correct input order of the vertices.

Beside the input vertices, there are some input and output parameters for users to tune the performace or to get more CCD information. Here is a list of the explanations of the parameters:

input:
    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                  Minimum separation distance no less than 0. It guarantees that collision will be reported if the distance between the two primitives is less than ms.
    tolerance           User-specific solving precision. It is the target maximal x, y, and z length of the inclusion function. We suggest the user to set it as 1e-6.
    t_max               The time range [0, t_max] where we detect collisions. Since the input query implies the motion in time range [0, 1], t_max should no larger than 1.
    max_itr             The parameter to enable early termination of the algorithm. If you set max_itr < 0, early termination will be disabled, but this may cause longer runtime. We suggest to set max_itr = 1e6.
    CCD_TYPE            The parameter to choose collision detection algorithms. By default CCD_TYPE = 1. If set CCD_TYPE = 0, the code will switch to a naive conservative CCD algorithm, but lack of our advanced features. 
    
output:
    toi                 Time of impact. If multiple collisions happen in this time step, it will return the earlist collision time. If there is no collision, the returned toi value will be std::numeric_limits<double>::infinity().
    output_tolerance    The real solving precision. If early termination is enabled, the solving precision may not reach the target precision. This parameter will return the real solving precision when the code is terminated.

Tips

💡 The input parameter err is crucial to guarantee our algorithm to be a conservative method not affected by floating point rounding errors. To run a single query, you can set err = {{-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 std::array<double, 3> err_vf = inclusion_ccd::get_numerical_error() and std::array<double, 3> err_ee = inclusion_ccd::get_numerical_error()
  • Use the parameter err_ee each time you call bool inclusion_ccd::edgeEdgeCCD_double() and err_vf when you call bool inclusion_ccd::vertexFaceCCD_double().

The parameters for function inclusion_ccd::get_numerical_error() is explained below:

input:
    vertices            Vertices of the Axies-Aligned-Bounding-Box of the simulation scene. Before you run the simulation, you need to conservatively estimate the Axies-Aligned-Bounding-Box in which the meshes will located during the whole simulation process, and the vertices should be the corners of the AABB.
    check_vf            A boolean instruction showing if you are checking vertex-face or edge-edge CCD.
    using_minimum_separation    A boolean instruction. If you are using minimum-separation CCD (the input parameter ms > 0), please set it as true.

💡 For some simulators which use non-zero minimum separation distance (ms > 0) to make sure intersection-free for each time-step, we have a CMake option TIGHT_INCLUSION_WITH_NO_ZERO_TOI to avoid the returned collision time toi is 0. You need to set TIGHT_INCLUSION_WITH_NO_ZERO_TOI as ON when compiling by: cmake ../ -DCMAKE_BUILD_TYPE=Release -DTIGHT_INCLUSION_WITH_NO_ZERO_TOI=ON. Then when you use the CCD functions, the code will continue the refinement in higher precision if the output toi is 0 under the given tolerance. So, the eventually toi will not be 0.

To have a better understand, or to get more details of our Tight-Inclusion CCD algorithm, please refer to our paper.

You might also like...
Continuous Query Decomposition for Complex Query Answering in Incomplete Knowledge Graphs

Continuous Query Decomposition This repository contains the official implementation for our ICLR 2021 (Oral) paper, Complex Query Answering with Neura

UCL Natural Language Processing 71 Dec 29, 2022
On the model-based stochastic value gradient for continuous reinforcement learning

On the model-based stochastic value gradient for continuous reinforcement learning This repository is by Brandon Amos, Samuel Stanton, Denis Yarats, a

Facebook Research 46 Dec 15, 2022
Continuous Diffusion Graph Neural Network

We present Graph Neural Diffusion (GRAND) that approaches deep learning on graphs as a continuous diffusion process and treats Graph Neural Networks (GNNs) as discretisations of an underlying PDE.

Twitter Research 227 Jan 5, 2023
PyTorch implementation for MINE: Continuous-Depth MPI with Neural Radiance Fields
PyTorch implementation for MINE: Continuous-Depth MPI with Neural Radiance Fields

MINE: Continuous-Depth MPI with Neural Radiance Fields Project Page | Video PyTorch implementation for our ICCV 2021 paper. MINE: Towards Continuous D

Zijian Feng 325 Dec 29, 2022
This repository contains the source code and data for reproducing results of Deep Continuous Clustering paper
This repository contains the source code and data for reproducing results of Deep Continuous Clustering paper

Deep Continuous Clustering Introduction This is a Pytorch implementation of the DCC algorithms presented in the following paper (paper): Sohil Atul Sh

Sohil Shah 197 Nov 29, 2022
This is the codebase for the ICLR 2021 paper Trajectory Prediction using Equivariant Continuous Convolution
This is the codebase for the ICLR 2021 paper Trajectory Prediction using Equivariant Continuous Convolution

Trajectory Prediction using Equivariant Continuous Convolution (ECCO) This is the codebase for the ICLR 2021 paper Trajectory Prediction using Equivar

Spatiotemporal Machine Learning 45 Jul 22, 2022
PyTorch implementation for Stochastic Fine-grained Labeling of Multi-state Sign Glosses for Continuous Sign Language Recognition.

Stochastic CSLR This is the PyTorch implementation for the ECCV 2020 paper: Stochastic Fine-grained Labeling of Multi-state Sign Glosses for Continuou

Zhe Niu 28 Dec 19, 2022
Code for the ICASSP-2021 paper: Continuous Speech Separation with Conformer.

Continuous Speech Separation with Conformer Introduction We examine the use of the Conformer architecture for continuous speech separation. Conformer

Sanyuan Chen (陈三元) 81 Nov 28, 2022
A clean and robust Pytorch implementation of PPO on continuous action space.
A clean and robust Pytorch implementation of PPO on continuous action space.

PPO-Continuous-Pytorch I found the current implementation of PPO on continuous action space is whether somewhat complicated or not stable. And this is

XinJingHao 56 Dec 16, 2022
Comments
  • Improved No Zero ToI

    Improved No Zero ToI

    • I changed the options for avoiding a zero time of impact by making the option a parameter to the CCD functions.
    • I also changed from a recursive algorithm to an iterative one with a maximum number of iterations.
    opened by zfergus 2
  • a case returned 0 TOI

    a case returned 0 TOI

    For the PT CCD case below, TICCD returned 0 TOI.

    3.5000000000e-01 0.0000000000e+00 3.5000000000e-01
3.4604643638e-01 2.7847887896e-03 3.4658121160e-01
3.5000819263e-01 -1.5763377304e-06 3.5001214242e-01
3.4903882032e-01 -1.5866575093e-03 3.4560164356e-01
0.0000000000e+00 0.0000000000e+00 0.0000000000e+00
1.0120300789e-07 -1.4009994248e-04 -8.5653091896e-05
-9.2976239634e-07 1.4361165221e-06 5.5168830145e-07
1.1649271683e-04 -3.6172565398e-05 -4.7128237917e-05

    The format is

    node_x node_y node_z
traingle_node0_x traingle_node0_y traingle_node0_z
traingle_node1_x traingle_node1_y traingle_node1_z
traingle_node2_x traingle_node2_y traingle_node2_z
node_displacement_x node_displacement_y node_displacement_z
traingle_node0_displacement_x traingle_node0_displacement_y traingle_node0_displacement_z
traingle_node1_displacement_x traingle_node1_displacement_y traingle_node1_displacement_z
traingle_node2_displacement_x traingle_node2_displacement_y traingle_node2_displacement_z

    I used the TICCD from the CCDWrapper repo (latest commit), and I called it like

    template <class T>
bool Point_Triangle_CCD_TI(
    const Eigen::Matrix<T, 3, 1>& p, 
    const Eigen::Matrix<T, 3, 1>& t0, 
    const Eigen::Matrix<T, 3, 1>& t1,
    const Eigen::Matrix<T, 3, 1>& t2,
    const Eigen::Matrix<T, 3, 1>& dp, 
    const Eigen::Matrix<T, 3, 1>& dt0, 
    const Eigen::Matrix<T, 3, 1>& dt1,
    const Eigen::Matrix<T, 3, 1>& dt2,
    T eta, T thickness, T& toc)
{
    T toc_prev = toc;
    T output_tolerance;

    T dist2_cur;
    Point_Triangle_Distance_Unclassified(p, t0, t1, t2, dist2_cur);
    T dist_cur = std::sqrt(dist2_cur);
    if (inclusion_ccd::vertexFaceCCD_double(p, t0, t1, t2,
        p + dp, t0 + dt0, t1 + dt1, t2 + dt2, { { -1, 0, 0 } },
        eta * (dist2_cur - thickness * thickness) / (dist_cur + thickness) + thickness,
        toc, 1e-6, toc_prev, 1e6, output_tolerance, 1))
    {
        if (toc < 1.0e-6) {
            std::cout << "PT CCD tiny!" << std::endl;
            if (inclusion_ccd::vertexFaceCCD_double(p, t0, t1, t2,
                p + dp, t0 + dt0, t1 + dt1, t2 + dt2, { { -1, 0, 0 } },
                thickness, toc, 1e-6, toc_prev, 1e6, output_tolerance, 1))
            {
                toc *= (1.0 - eta);
                return true;
            }
            else {
                return false;
            }
        }
        return true;
    }
    return false;
}

printf("TICCD:\n");
largestAlpha = 1;
tstart = clock();
if (Point_Triangle_CCD_TI(x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7], 0.1, 0.0, largestAlpha)) {
    printf("%le\n", largestAlpha);
}
else {
    printf("no collision\n");
}
printf("%.1lems\n", double(clock() - tstart) / CLOCKS_PER_SEC * 1000);

    The output is

    TICCD:
PT CCD tiny!
0.000000e+00
1.9e+00ms

    However I implemented a simpler version of TICCD according to the paper as

    template <class T>
void Point_Triangle_Distance_Vector_Unclassified(
    const Eigen::Matrix<T, 3, 1>& p, 
    const Eigen::Matrix<T, 3, 1>& t0, 
    const Eigen::Matrix<T, 3, 1>& t1,
    const Eigen::Matrix<T, 3, 1>& t2,
    const Eigen::Matrix<T, 3, 1>& dp, 
    const Eigen::Matrix<T, 3, 1>& dt0, 
    const Eigen::Matrix<T, 3, 1>& dt1,
    const Eigen::Matrix<T, 3, 1>& dt2,
    T t, T lambda, T beta,
    Eigen::Matrix<T, 3, 1>& distVec)
{
    const Eigen::Matrix<T, 3, 1> tp = (1 - lambda - beta) * t0 + lambda * t1 + beta * t2;
    const Eigen::Matrix<T, 3, 1> dtp = (1 - lambda - beta) * dt0 + lambda * dt1 + beta * dt2;
    distVec = p + t * dp - (tp + t * dtp);
}

template <class T>
bool Point_Triangle_CheckInterval_Unclassified(
    const Eigen::Matrix<T, 3, 1>& p, 
    const Eigen::Matrix<T, 3, 1>& t0, 
    const Eigen::Matrix<T, 3, 1>& t1,
    const Eigen::Matrix<T, 3, 1>& t2,
    const Eigen::Matrix<T, 3, 1>& dp, 
    const Eigen::Matrix<T, 3, 1>& dt0, 
    const Eigen::Matrix<T, 3, 1>& dt1,
    const Eigen::Matrix<T, 3, 1>& dt2,
    const std::array<T, 6>& interval,
    T gap)
{
    Eigen::Matrix<T, 3, 1> distVecMax, distVecMin;
    distVecMax.setConstant(-2 * gap - 1);
    distVecMin.setConstant(2 * gap + 1);
    for (int t = 0; t < 2; ++t) {
        for (int lambda = 0; lambda < 2; ++lambda) {
            for (int beta = 0; beta < 2; ++beta) {
                if (lambda == 1 && beta == 1) {
                    continue;
                }
                Eigen::Matrix<T, 3, 1> distVec;
                Point_Triangle_Distance_Vector_Unclassified(p, t0, t1, t2, dp, dt0, dt1, dt2, 
                    interval[t], interval[2 + lambda], interval[4 + beta], distVec);
                distVecMax = distVecMax.array().max(distVec.array());
                distVecMin = distVecMin.array().min(distVec.array());
            }
        }
    }
    return (distVecMax.array() >= -gap).all() && (distVecMin.array() <= gap).all();
}
template <class T>
bool Point_Triangle_TICCD(
    const Eigen::Matrix<T, 3, 1>& p, 
    const Eigen::Matrix<T, 3, 1>& t0, 
    const Eigen::Matrix<T, 3, 1>& t1,
    const Eigen::Matrix<T, 3, 1>& t2,
    Eigen::Matrix<T, 3, 1> dp, 
    Eigen::Matrix<T, 3, 1> dt0, 
    Eigen::Matrix<T, 3, 1> dt1,
    Eigen::Matrix<T, 3, 1> dt2,
    T eta, T thickness, T& toc)
{
    T dist2_cur;
    Point_Triangle_Distance_Unclassified(p, t0, t1, t2, dist2_cur);
    T dist_cur = std::sqrt(dist2_cur);
    T gap = eta * (dist2_cur - thickness * thickness) / (dist_cur + thickness);

    T tTol = 1e-3;

    std::vector<std::array<T, 6>> roots;
    std::deque<std::array<T, 6>> intervals;
    intervals.push_back({0, toc, 0, 1, 0, 1});
    int iterAmt = 0;
    while (!intervals.empty()) {
        ++iterAmt;

        std::array<T, 6> curIV = intervals.front();
        intervals.pop_front();

        // check
        if (Point_Triangle_CheckInterval_Unclassified(p, t0, t1, t2, dp, dt0, dt1, dt2, curIV, gap)) {
            if (curIV[0] && curIV[1] - curIV[0] < tTol) {
                // root found within tTol
                roots.emplace_back(curIV);
            }
            else {
                // split interval and push back
                std::vector<T> intervalLen({curIV[1] - curIV[0], curIV[3] - curIV[2], curIV[5] - curIV[4]});
                switch (std::max_element(intervalLen.begin(), intervalLen.end()) - intervalLen.begin()) {
                case 0:
                    intervals.push_back({curIV[0], (curIV[1] + curIV[0]) / 2, curIV[2], curIV[3], curIV[4], curIV[5]});
                    intervals.push_back({(curIV[1] + curIV[0]) / 2, curIV[1], curIV[2], curIV[3], curIV[4], curIV[5]});
                    break;

                case 1:
                    intervals.push_back({curIV[0], curIV[1], curIV[2], (curIV[2] + curIV[3]) / 2, curIV[4], curIV[5]});
                    intervals.push_back({curIV[0], curIV[1], (curIV[2] + curIV[3]) / 2, curIV[3], curIV[4], curIV[5]});
                    break;

                case 2:
                    intervals.push_back({curIV[0], curIV[1], curIV[2], curIV[3], curIV[4], (curIV[4] + curIV[5]) / 2});
                    intervals.push_back({curIV[0], curIV[1], curIV[2], curIV[3], (curIV[4] + curIV[5]) / 2, curIV[5]});
                    break;
                }
            }
        }
    }
    
    if (roots.empty()) {
        printf("TICCD PT converged with %d iters\n", iterAmt);
        return false;
    }
    else {
        for (const auto& rI : roots) {
            if (toc > rI[0]) {
                toc = rI[0];
            }
        }
        printf("TICCD PT converged with %d iters\n", iterAmt);
        return true;
    }
}

    and it kinds of worked on this case and output

    TICCD PT converged with 6143 iters
4.882812e-04
5.3e-01ms

    which with tighter convergence tolerance might be able to reach the ground truth solution -- no collision.

    In my implementation, I didn't include the epsilons in formula (5) in the paper. Is it the main cause here?

    opened by liminchen 2
  • Refactored and cleaned up code

    Refactored and cleaned up code

    I tested and timed it on the entire dataset. I get 0 FN, a couple of fewer FP on the handcrafted data, and the timing is a little faster on the simulation and faster on handcrafted.

    opened by zfergus 0
Releases(v1.0.2)
Owner
Continuous Collision Detection
Code for continuous collision detection methods bechmarked in "A Large Scale Benchmark and an Inclusion-Based Algorithm for Continuous Collision Detection"
Continuous Collision Detection
GitHub Repository
Learning Energy-Based Models by Diffusion Recovery Likelihood

Learning Energy-Based Models by Diffusion Recovery Likelihood Ruiqi Gao, Yang Song, Ben Poole, Ying Nian Wu, Diederik P. Kingma Paper: https://arxiv.o

Ruiqi Gao 41 Nov 22, 2022
Code for DisCo: Remedy Self-supervised Learning on Lightweight Models with Distilled Contrastive Learning

DisCo: Remedy Self-supervised Learning on Lightweight Models with Distilled Contrastive Learning Pytorch Implementation for DisCo: Remedy Self-supervi

79 Jan 06, 2023
Contrastive Learning for Many-to-many Multilingual Neural Machine Translation(mCOLT/mRASP2), ACL2021

Contrastive Learning for Many-to-many Multilingual Neural Machine Translation(mCOLT/mRASP2), ACL2021 The code for training mCOLT/mRASP2, a multilingua

104 Jan 01, 2023
BraTs-VNet - BraTS(Brain Tumour Segmentation) using V-Net

BraTS(Brain Tumour Segmentation) using V-Net This project is an approach to dete

Rituraj Dutta 7 Nov 27, 2022
A script depending on VASP output for calculating Fermi-Softness.

Fermi softness calculation for Vienna Ab initio Simulation Package (VASP) Update 1.1.0: Big update: Rewrote the code. Use Bader atomic division instea

qslin 11 Nov 08, 2022
Stroke-predictions-ml-model - Machine learning model to predict individuals chances of having a stroke

stroke-predictions-ml-model machine learning model to predict individuals chance

Alex Volchek 1 Jan 03, 2022
House3D: A Rich and Realistic 3D Environment

House3D: A Rich and Realistic 3D Environment Yi Wu, Yuxin Wu, Georgia Gkioxari and Yuandong Tian House3D is a virtual 3D environment which consists of

Meta Research 1.1k Dec 14, 2022
ESGD-M - A stochastic non-convex second order optimizer, suitable for training deep learning models, for PyTorch

ESGD-M - A stochastic non-convex second order optimizer, suitable for training deep learning models, for PyTorch

Katherine Crowson 53 Dec 29, 2022
Official code for MPG2: Multi-attribute Pizza Generator: Cross-domain Attribute Control with Conditional StyleGAN

This is the official code for Multi-attribute Pizza Generator (MPG2): Cross-domain Attribute Control with Conditional StyleGAN. Paper Demo Setup Envir

Fangda Han 5 Sep 01, 2022
Use CLIP to represent video for Retrieval Task

A Straightforward Framework For Video Retrieval Using CLIP This repository contains the basic code for feature extraction and replication of results.

Jesus Andres Portillo Quintero 54 Dec 22, 2022
DeepDiffusion: Unsupervised Learning of Retrieval-adapted Representations via Diffusion-based Ranking on Latent Feature Manifold

DeepDiffusion Introduction This repository provides the code of the DeepDiffusion algorithm for unsupervised learning of retrieval-adapted representat

4 Nov 15, 2022
Asymmetric Bilateral Motion Estimation for Video Frame Interpolation, ICCV2021

ABME (ICCV2021) Junheum Park, Chul Lee, and Chang-Su Kim Official PyTorch Code for "Asymmetric Bilateral Motion Estimation for Video Frame Interpolati

Junheum Park 86 Dec 28, 2022
A big endian Gentoo port developed on a Pine64.org RockPro64

Gentoo-aarch64_be A big endian Gentoo port developed on a Pine64.org RockPro64 The endian wars are over... little endian won. As a result, it is incre

Rory Bolt 6 Dec 07, 2022
OpenFed: A Comprehensive and Versatile Open-Source Federated Learning Framework

OpenFed: A Comprehensive and Versatile Open-Source Federated Learning Framework Introduction OpenFed is a foundational library for federated learning

25 Dec 12, 2022
The source code and dataset for the RecGURU paper (WSDM 2022)

RecGURU About The Project Source code and baselines for the RecGURU paper "RecGURU: Adversarial Learning of Generalized User Representations for Cross

Chenglin Li 17 Jan 07, 2023
An Open-Source Package for Information Retrieval.

OpenMatch An Open-Source Package for Information Retrieval. 😃 What's New Top Spot on TREC-COVID Challenge (May 2020, Round2) The twin goals of the ch

THUNLP 439 Dec 27, 2022
Detectron2 is FAIR's next-generation platform for object detection and segmentation.

Detectron2 is Facebook AI Research's next generation software system that implements state-of-the-art object detection algorithms. It is a ground-up r

Facebook Research 23.3k Jan 08, 2023
Weighing Counts: Sequential Crowd Counting by Reinforcement Learning

LibraNet This repository includes the official implementation of LibraNet for crowd counting, presented in our paper: Weighing Counts: Sequential Crow

Hao Lu 18 Nov 05, 2022
The official implementation of the research paper "DAG Amendment for Inverse Control of Parametric Shapes"

DAG Amendment for Inverse Control of Parametric Shapes This repository is the official Blender implementation of the paper "DAG Amendment for Inverse

Elie Michel 157 Dec 26, 2022
Joint project of the duo Hacker Ninjas

Project Smoothie Společný projekt dua Hacker Ninjas. První pokus o hříčku po třech týdnech učení se programování. Jakub Kolář e:\

Jakub Kolář 2 Jan 07, 2022