自相交2D多边形（软体/网格、绳环）的碰撞检测与响应算法问询

A) 寻找最接近原形状的非相交精确算法 #

这类算法适合离线处理或对精度要求高的场景，核心是先定位相交再修复拓扑：

• 步骤1：自相交检测：遍历多边形所有边对，用线段相交叉积判定法找出所有相交点。该方法通过计算两条线段端点的叉积符号，快速判断是否存在交点及交点位置。
• 步骤2：拓扑修复与形状优化：
  • 对于自相交的闭合多边形，可将其在相交点处分割为多个非相交子多边形，再根据“顶点总位移最小”的目标，选择保留主体区域或合并合理子部分，重构为单一闭合非相交多边形。
  • 若追求严格的“最接近”，可将问题转化为带约束的二次优化问题：以原顶点坐标为初始值，最小化所有顶点位移的平方和，约束条件为所有边段无相交。通过拉格朗日乘数法或梯度下降法求解，能得到理论上的最优解，但计算成本较高。

B) 小时间步下的防相交算法（微移/力约束） #

这类方法适合实时模拟，通过提前干预避免相交：

• 连续碰撞检测（CCD）：不再仅检测当前帧的状态，而是预测边段在整个时间步内的运动轨迹（如线性插值顶点位置），判断是否会发生相交。若预测到相交，提前调整顶点位置或施加反向力，将相交消除在萌芽状态。
• 排斥力约束：当两条边段的距离小于设定阈值时，沿边段法线方向施加排斥力，力的大小与距离成反比。这种类似弹簧的约束能在小时间步下有效阻止边段靠近至相交，适合可变形网格的实时模拟。
• 顶点微移修正：若刚发生轻微自相交，将相交边的顶点沿各自边的切线方向做极小幅度移动，直到边段分离。微移幅度需控制在不破坏模拟真实性的范围内。

可变形网格的适配方案 #

针对你提到的弯折折叠网格，可采用两种思路：

• 分环处理：将网格拆解为独立的闭合环，对每个环单独执行上述自相交检测与修复逻辑，再整合回整体网格。
• 全局边段碰撞处理：放弃按网格单元划分，直接将所有边段纳入碰撞检测系统。对每对边段进行距离检测和相交判断，一旦触发阈值就执行排斥力或微移修正。这种方法无需依赖闭合多边形结构，能处理任意移动绳索/网格的碰撞。

替代point-in-polygon的优化方案 #

你当前使用的point-in-polygon算法仅适用于简单刚体多边形，面对自相交的网格单元会失效，推荐替换为：

• 线段相交检测：直接检测网格单元的边与其他所有边（包括自身单元的边）是否相交，不依赖多边形的封闭性和简单性，更适配可变形体的动态变化。
• 基于距离的提前预警：计算边段间的最小距离，当距离小于安全阈值时就触发响应，而非等到相交发生后再处理，能大幅提升模拟稳定性。

内容的提问来源于stack exchange，提问作者Tony Zhang