Tukukkk

I do not know much about collision detection and I am trying to resolve 3D collisions exactly. To do so, I am using the Minkowski difference. The thing is, I am having problems calculating the difference between two shapes.

What I tried doing:
In 2D you can calculate the M. difference of 2 polygons (A and B) by looping in the edges of A finding the correct support vertex of B by using the reversed edge normal of A and then substrating the edge of A by the supporting vertex of B. And then do something similar by looping through the edges of B.

So basically, in 3D I tried doing the same thing by using triangles instead of edges. It seems to kinda work and kinda fail (here is M. difference of a cube with the same cube turned 45 degrees):
Click to view image.

As seen in the image, there is a weird hole in the middle. I don't think this is normal because we are supposed to end up with a closed shape.

Here below is my code (note that the code is very unoptimised because I'm not sure about how to choose the supporting vertices, so I don't choose, I take all of them).

Here is the class which takes care of the Minkowski stuff (if there is an //OK over the method, I'm pretty sure that it works):

#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);

  }

}

Thanks for helping!

Ok i found what was wrong with the algorithm, basicly i was only calculating the "translated faces" and wasn't calculating the part done by sweeping the edges, here is a paper talking about the minkowski sum and how to compute it: liris.cnrs.fr/Documents/Liris-3813.pdf (look at the part about the CVMS algorithm)

In the end for collision detection this is very bad performence-wise, so as someone pointed out in the comments, i implemented the GJK algorithm for collision detection and the EPA algorithm for collision response, works petty well.

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