a case returned 0 TOI

[liminchen]

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?

[zfergus]

It looks like this line if (curIV[0] && curIV[1] - curIV[0] < tTol) { is avoiding finding a root if the start of the interval equals 0, right?

By default, our CCD will converge to any solution as long as the interval width is less than the tolerance (even if it contains 0). There is a CMake option TIGHT_INCLUSION_WITH_NO_ZERO_TOI which will continue refining if the time of impact is zero. Can you try with that ON?

[liminchen]

Thanks! It worked and output

TICCD:
2.379254e-02
1.0e+00ms

It would be great if it can report the ground truth "no collision", as this could still limit the step size taken about 1/50 smaller. Maybe figuring out a way to set more adaptive tolerance can help? Anyway this is just my curiosity.