移动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（和其他物理对象）都可能试图将球推向接近相反的方向。（下图）

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

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

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

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