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