Collision detection and response for self intersecting 2d polygons (e.g. soft bodies/meshes, loops of "string")

Question

I am looking for an algorithm to resolve collisions in 2d meshes.

Picture a free floating loop of string represented by a polygon (vertex connected by edges). Nodes and edges can move depending on other forces or objects.

This is an extreme example, but in one frame it is possible for such a loop to move from non-intersecting to intersecting. Is there either A) an exact algorithm that finds the closest non-intersecting shape, or B) applies a "nudge" or a force that prevents these intersections given a small enough timestep?

The question above is a simplified version of the problem I wish to solve, my simulation more closely resembles a deformable mesh.

While this doesn't appear to be about self intersections, my reasoning is that I can compute self collisions each individual loop within the mesh, which will in turn resolve intersections for the whole mesh. An alternative approach can be an algorithm that handles collision for any line segments or a general solution that doesn't need closed polygons (such as solving collision for a pile of moving string).

My current solution uses a standard point in polygon algorithm that detects collision between two separate "grids" of the mesh, however this seems to be typically used for rigid bodies and causes unstable behavior when the mesh is twisted in a way such that each individual grid intersects itself.

Answer 1

- Check that initial arrangement has no line intersections.
- Divide the deformation into smallest reasonable steps
- Identify the lines that are moving
- Loop over deformation steps
   - Loop over moving lines
       - IF moving line intersects any other line
                  - Back up deformation one step
                  - BREAK OUT of loop over deformation steps

I have committed C++ code for a demo application that implements this algorithm to the github repository at https://github.com/JamesBremner/so78862498

Code ( code documentation at https://github.com/JamesBremner/so78862498/blob/main/src/main.cpp ):

#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <vector>
#include <algorithm>

#include <cxy.h>

struct sdeform
{
    int node;  // index of moving node
    double xv; // x direction
    double yv; // y direction
    double v;  // velocity

    sdeform(int n, double x, double y, double vel)
        : node(n), xv(x), yv(y), v(vel)
    {
    }
};
struct spile
{
    std::vector<cxy> vnode;    // initial node locations
    std::vector<cxy> vcurrent; // current node locations
    std::vector<std::pair<int, int>> vedge;
    std::vector<sdeform> vdeform;

    void clear()
    {
        vnode.clear();
        vcurrent.clear();
        vedge.clear();
        vdeform.clear();
    }
    void deform()
    {
        if (!vcurrent.size())
        {
            vcurrent = vnode;
            return;
        }
        vcurrent[vdeform[0].node].x += vdeform[0].xv;
        vcurrent[vdeform[0].node].y += vdeform[0].yv;
    }
    void deformReverse()
    {
        if (!vcurrent.size())
        {
            vcurrent = vnode;
            return;
        }
        vcurrent[vdeform[0].node].x -= vdeform[0].xv;
        vcurrent[vdeform[0].node].y -= vdeform[0].yv;
    }
    std::vector<int>
    moving()
    {
        std::vector<int> ret;
        for (int iedge = 0; iedge < vedge.size(); iedge++)
        {
            if (vedge[iedge].first == vdeform[0].node ||
                vedge[iedge].second == vdeform[0].node)
                ret.push_back(iedge);
        }
        return ret;
    }
    bool isIntersection()
    {
        const double delta = 0.01;

        cxy p;
        for (int iedgemoving : moving())
        {
            auto n1me = vcurrent[vedge[iedgemoving].first];
            auto n2me = vcurrent[vedge[iedgemoving].second];
            for (int iedgefixed = 0; iedgefixed < vedge.size(); iedgefixed++)
            {
                if (iedgefixed == iedgemoving)
                    continue;
                auto n1fe = vcurrent[vedge[iedgefixed].first];
                auto n2fe = vcurrent[vedge[iedgefixed].second];
                if (cxy::isIntersection( p,
                        n1me, n2me,
                        n1fe,n2fe))
                {
                    if( ! ( n1me.dist2(p) < delta || n2me.dist2(p) < delta ) )
                        return true;
                }
            }
        }
        return false;
    }

    void text()
    {
        std::cout << "starting position\n";
        for( auto& n : vnode )
            std::cout << n.x <<" "<< n.y << "\n";
        std::cout << "final position\n";
        for( auto& n : vcurrent )
         std::cout << n.x <<" "<< n.y << "\n";
    }
};

spile thePile; // the pile of string

std::vector<std::string>
ParseSpaceDelimited(
    const std::string &l)
{
    std::vector<std::string> token;
    std::stringstream sst(l);
    std::string a;
    while (getline(sst, a, ' '))
        token.push_back(a);

    // remove empty tokens
    token.erase(
        remove_if(
            token.begin(),
            token.end(),
            [](std::string t)
            {
                return (t.empty());
            }),
        token.end());

    return token;
}

void read(const std::string fname)
{
    thePile.clear();
    std::ifstream ifs(fname);
    if (!ifs.is_open())
        throw std::runtime_error("Cannot open input file");
    std::string line;
    while (getline(ifs, line))
    {
        auto vtoken = ParseSpaceDelimited(line);
        switch (line[0])
        {
        case 'n':
            thePile.vnode.emplace_back(atof(vtoken[1].c_str()), atof(vtoken[2].c_str()));
            break;
        case 'e':
            thePile.vedge.emplace_back(atoi(vtoken[1].c_str()), atoi(vtoken[2].c_str()));
            break;
        case 'd':
            thePile.vdeform.emplace_back(
                atoi(vtoken[1].c_str()),
                atof(vtoken[2].c_str()),
                atof(vtoken[3].c_str()),
                atof(vtoken[4].c_str()));
            break;
        }
    }
}

main()
{

    read( "../dat/data1.txt");
    for( ; ; ) {
        thePile.deform();
        if( thePile.isIntersection() ) {
            thePile.deformReverse();
            break;
        }
    }
    thePile.text();
    return 0;
}

Sample input

// define node locations
n -1, 1
n 1 1
n 1 -1
n -1 -1
n -1 0
// define edges between nodes
e 0 1
e 1 2
e 2 3
e 3 4
e 4 0

// define deformation ( node 4 moves along the +ve x direction )
d 4 0.1 0 1

Generates the output

starting position
-1 1
1 1
1 -1
-1 -1
-1 0
final position
-1 1
1 1
1 -1
-1 -1
1 0