c++ - 移动 Physics 对象以进行穿透的最小尺寸 Vec3 = 0

Question

这是一个例子(见图片):-

• 2 个红色矩形是静态对象(即它不能移动)。
• 蓝色的球是动态物体。

到目前为止，我设法获得了所有深入的信息。让我们将其视为我们的输入:-

• 为了解决 A 和球之间的渗透问题，我可以通过 Vec3(1,0,0) OR 移动球Vec3(0,2,0)。
• 为了解决 B 和球之间的穿透问题，我可以将球移动 Vec3(0,1,0)。

^ 我将其存储为 2D Vec3 数组 problem = {{Vec3{1,0,0},Vec3{0,2,0}},{Vec3{0,1,0} }}.

如何找到物理对象(例如示例中的球)的最佳运动(最小尺寸)以尽可能减少穿透力？

此示例中的最佳解决方案是“通过 Vec3(1,1,0) 移动球:size=1.414”。

在实际情况中，情况可能更加复杂和丑陋，
例如A&B(和其他物理对象)都可能试图将球推向几乎相反的方向。 (下图)

^ 在某些场景中，二维数组问题可能缺少一些细节，但为了简单起见，我们假设它准确地解释了所有信息。

C++代码

这是我的 MCVE (coliru) :-

#include<iostream>
#include <utility>
#include <vector>
#include <array>
#include <math.h>

using Vec3=std::array<float, 3>;
float dotProduct(Vec3 vec1,Vec3 vec2){
    return vec1[0]*vec2[0]+vec1[1]*vec2[1]+vec1[2]*vec2[2];
}
float size2(Vec3 vec1){
    return vec1[0]*vec1[0]+vec1[1]*vec1[1]+vec1[2]*vec1[2];
}
Vec3 mulFloat(Vec3 vec1,float m){
    return Vec3{vec1[0]*m,vec1[1]*m,vec1[2]*m};
}
Vec3 normalize(Vec3 vec1){
    return mulFloat(vec1,1/sqrt(size2(vec1)));
}

这是main():-

int main() {
    std::vector<std::vector<Vec3>> problem;
    std::vector<Vec3> location1;
    location1.push_back(Vec3{0,2,0});
    location1.push_back(Vec3{1,0,0});
    problem.push_back(location1);
    std::vector<Vec3> location2;
    location2.push_back(Vec3{0,1,0});
    problem.push_back(location2);
    //^ INPUT
    //----- insert YOUR ALGORITHM here  ------
    Vec3 solution=Vec3{0,2,0};

    float totalResidual=0;
    for(auto& location : problem){
        float residualRemainMin=1000000;//numerical limit
        for(auto& orgResidual : location){
            Vec3 orgResidualNormalize=normalize(orgResidual);
            float orgResidualSize=sqrt(size2(orgResidual));
            float residualModifyBy=-dotProduct(orgResidualNormalize,solution);//#1
            //"residualModifyBy" is usually negative
            float remainResidual=std::max(0.0f,orgResidualSize+residualModifyBy);
            //^ "max" because it has no advantage to reduce residual to < 0
            residualRemainMin=std::min(residualRemainMin,remainResidual);
            //^ "min" because the "OR" word
        }
        totalResidual+=residualRemainMin;
    }
    std::cout<<"totalResidual="<<totalResidual;
    return 0;
}

注意代码中的(#1):残差被dotProduct(solution,normalize(orgResidual) )减少。
我对这个公式的推导来自这张图片:-

边注

我觉得排列每个组合太慢(我不确定如何排列)。
我还认为一般的迭代方法收敛速度太慢。

我只是想要一些指南；我不介意仅描述而没有代码的答案。

编辑(2019 年 6 月 29 日)

更多测试用例:-

{{(0,3,0)},{(2,2,0)}}            ===> (1,3,0)       
{{(0,1,1),(10,0,0)},{(0,2,3)}}   ===> (0,2,3)  
{{(99,1,0),(99,-1,0),(100,0,0)}} ===> (99,1,0) OR (99,-1,0)    (equally good)

Answer 1

我认为在一步中为您提供正确/最佳答案的实现将非常复杂。

我的方法是:

1. 如果与任何物体都没有交点，则将球朝物体的方向移动(而不是物体已经接触的方向)转到 0;
2. 检测所有与物体的非法交叉点
3. 对于每个交叉点计算您需要球移动的方向以消除交叉点(最简单的情况是垂直于物体表面移动交叉点深度的量)
4. 按照 2 中计算的方向移动球。
5. 转到0

如果球的位置不再改变(或在有限的迭代次数之后)，则终止循环

在第一个示例中，这将在一次迭代中找到最佳解决方案。
在第二个例子中，球会在每次迭代中缓慢向上移动，直到不再存在交叉点)