3D 凸多面体的 Minkowski 差分

Question

我不太了解碰撞检测，我正在尝试准确解决 3D 碰撞。为此，我使用了闵可夫斯基差分。问题是，我在计算两个形状之间的差异时遇到了问题。

我尝试做的事情：在 2D 中，您可以计算 M. 2 个多边形（A 和 B）的差异，方法是在 A 的边中循环，使用 A 的反向边法线找到 B 的正确支撑顶点，然后用支撑顶点代替 A 的边B的。然后通过循环B的边缘来做类似的事情。

所以基本上，在 3D 中，我尝试通过使用三角形而不是边缘来做同样的事情。它似乎有点工作，有点失败（这里是 M. 一个立方体与同一立方体旋转 45 度的差异）： Click to view image.

如图所示，中间有一个奇怪的洞。我不认为这是正常的，因为我们应该以封闭的形状结束。

下面是我的代码（请注意，代码没有优化，因为我不确定如何选择支撑顶点，所以我不选择，我全部拿走了）。

这里是处理 Minkowski 问题的 class（如果该方法有 //OK，我很确定它有效）：

#include "TransformedPolyhedron.h"
#include "Array.h"
#include "graphics/MeshLoader.h"
#include <iostream>

using namespace graphics;

namespace math
{
  TransformedPolyhedron::TransformedPolyhedron(Polyhedron& polyhedron)
  {
    this->polyhedron = &polyhedron;
  }

  //OK
  ArrayList<int>& TransformedPolyhedron::getIndices() const
  {
    return polyhedron->getIndices();
  }

  //OK
  ArrayList<Vector3> TransformedPolyhedron::getTransformedPositions() const
  {
    ArrayList<Vector3>& positions = polyhedron->getPositions();
    ArrayList<Vector3> result(positions.size());

    for(int i=0;i<result.size();i++)
    {
      result[i] = transformation.transform(positions[i]);
    }
    return result;
  }

  //OK(?)
  ArrayList<TriangleFace> TransformedPolyhedron::getTriangleFaces(const ArrayList<Vector3>& positions) const
  {
    ArrayList<int>& indices = getIndices();
    ArrayList<TriangleFace> result;
    for(int i=0;i<indices.size();i+=3)
    {
      Vector3& v1 = positions[indices[i]];
      Vector3& v2 = positions[indices[i + 1]];
      Vector3& v3 = positions[indices[i + 2]];
      result.add(TriangleFace(v1, v2, v3));
    }
    return result;
  }

  ArrayList<Vector3> TransformedPolyhedron::getSupportingVertex(const Vector3& normal, const ArrayList<Vector3>& positions) const
  {
    double maxDot = normal.dot(positions[0]);
    for(int i=0;i<positions.size();i++)
    {
      double dot = normal.dot(positions[i]);
      if(dot > maxDot)
      {
        maxDot = dot;
      }
    }
    ArrayList<Vector3> result;
    for(int i=0;i<positions.size();i++)
    {
      Vector3& position = positions[i];
      double dot = normal.dot(position);
      if(dot >= maxDot)
      {
        result.add(position);
      }
    }
    return result;
  }

  Polyhedron TransformedPolyhedron::minkowskiDifference(const TransformedPolyhedron& poly) const
  {
    ArrayList<int> resultIndices;
    ArrayList<Vector3> resultPositions;

    ArrayList<Vector3> thisPositions = getTransformedPositions();
    ArrayList<TriangleFace> thisTriangleFaces = getTriangleFaces(thisPositions);

    ArrayList<Vector3> polyPositions = poly.getTransformedPositions();
    ArrayList<TriangleFace> polyTriangleFaces = poly.getTriangleFaces(polyPositions);
    //this
    for(int i=0;i<thisTriangleFaces.size();i++)
    {
      TriangleFace& triangle = thisTriangleFaces[i];
      Vector3 normal = triangle.getNormal();
      normal*=(-1);
      ArrayList<Vector3> supportingVectors = poly.getSupportingVertex(normal, polyPositions);
      for(int k=0;k<supportingVectors.size();k++)
      {
        Vector3& supportingVector = supportingVectors[k];
        for(int j=0;j<3;j++)
        {
          Vector3 toAdd = triangle[j] - supportingVector;

          resultIndices.add(resultPositions.size());
          resultPositions.add(toAdd);
        }
      }
    }
    //poly
    for(int i=0;i<polyTriangleFaces.size();i++)
    {
      TriangleFace& triangle = polyTriangleFaces[i];
      Vector3 normal = triangle.getNormal();
      normal*=(-1);
      ArrayList<Vector3> supportingVectors = getSupportingVertex(normal, thisPositions);
      for(int k=0;k<supportingVectors.size();k++)
      {
        Vector3& supportingVector = supportingVectors[k];
        for(int j=0;j<3;j++)
        {
          Vector3 toAdd = triangle[j] - supportingVector;

          resultIndices.add(resultPositions.size());
          resultPositions.add(toAdd);
        }
      }
    }

    return Polyhedron(resultPositions, resultIndices);
  }

  //OK
  void TransformedPolyhedron::transform(const Matrix4& transformation)
  {
    this->transformation = transformation;
  }

  //ok
  GLuint TransformedPolyhedron::loadToGPU(int* amount) const
  {
    ArrayList<int>& indices = getIndices();
    ArrayList<Vector3> positions = getTransformedPositions();
    ArrayList<float> textures(positions.size()*2);
    ArrayList<float> positionsArray(positions.size()*3);
    for(int i=0;i<positions.size();i++)
    {
      positionsArray[3*i] = positions[i].getX();
      positionsArray[3*i + 1] = positions[i].getY();
      positionsArray[3*i + 2] = positions[i].getZ();
    }
    Array<float> apos(positionsArray.toArray(), positionsArray.size());
    Array<int> aind(indices.toArray(), indices.size());
    Array<float> atex(textures.toArray(), textures.size());
    *amount = indices.size();
    return MeshLoader::loadIndexedVertices(apos, atex, aind);
  }
}

感谢您的帮助！

Answer 1

好的，我发现算法出了什么问题，基本上我只计算了 "translated faces" 而不是通过扫边计算完成的部分，这里有一篇论文讨论了 minkowski 和以及如何计算计算它：liris.cnrs.fr/Documents/Liris-3813.pdf（查看关于 CVMS 算法的部分）

最后，对于碰撞检测，这在性能方面非常糟糕，所以正如有人在评论中指出的那样，我实现了碰撞检测的 GJK 算法和碰撞响应的 EPA 算法，效果不佳。

GJK + EPA：http://hacktank.net/blog/?p=93

3D 凸多面体的 Minkowski 差分

Minkowski Difference with 3D convex Polyhedrons

c++

collision-detection