the title does say it all. Is there an easy way to retrieve triangle data from the support map function (convex objects) ?
I saw some engines just randomly collecting points from the support map and giving that points into a convex hull generator. I also stumbled across some code which I don't fully understand. I implemented the code from here (http://www.xbdev.net/physics/MinkowskiD ... /index.php) and it works for all my test cases, but I don't understand why or why it should always return a closed triangle surface
My understanding so far:
1) Go to the left, right, up, down, forward, backward and build a octrahedron (consisting of triangles) from it.
2) foreach triangle: support in the 3 directions defined by the triangle vertices. If the 3 resulting points are not the same subdivide the triangle
into 4 subtriangles. If the generation threshold is reached and we have a triangle with 3 different support points, add it to the final list.
Why does this work? What do you use for algorithms?
Code: Select all
public HullMaker(Shape shape, int generationThreshold)
{
float distanceThreshold = 0.0f;
if (generationThreshold < 0) generationThreshold = 4;
Stack activeTriList = new Stack();
Vector3[] v = new Vector3[] // 6 Array
{
new Vector3( -1, 0, 0 ),
new Vector3( 1, 0, 0 ),
new Vector3( 0, -1, 0 ),
new Vector3( 0, 1, 0 ),
new Vector3( 0, 0, -1 ),
new Vector3( 0, 0, 1 ),
};
int[,] kTriangleVerts = new int[8,3] // 8 x 3 Array
{
{ 5, 1, 3 },
{ 4, 3, 1 },
{ 3, 4, 0 },
{ 0, 5, 3 },
{ 5, 2, 1 },
{ 4, 1, 2 },
{ 2, 0, 4 },
{ 0, 2, 5 }
};
for (int i=0; i < 8; i++)
{
ClipTri tri = new ClipTri();
tri.n1 = v[ kTriangleVerts[i,0] ];
tri.n2 = v[ kTriangleVerts[i,1] ];
tri.n3 = v[ kTriangleVerts[i,2] ];
tri.generation = 0;
activeTriList.Push(tri);
}
List<Vector3> pointSet = new List<Vector3>();
// surfaceTriList
while (activeTriList.Count > 0)
{
ClipTri tri = (ClipTri)activeTriList.Pop();
Vector3 p1 = shape.GetSupportPoint( tri.n1 );
Vector3 p2 = shape.GetSupportPoint( tri.n2 );
Vector3 p3 = shape.GetSupportPoint( tri.n3 );
//tri.n1 = p1;
//tri.n2 = p2;
//tri.n3 = p3;
float d1 = (p2 - p1).LengthSquared();
float d2 = (p3 - p2).LengthSquared();
float d3 = (p1 - p3).LengthSquared();
if ( Math.Max( Math.Max(d1, d2), d3 ) > distanceThreshold && tri.generation < generationThreshold )
{
ClipTri tri1 = new ClipTri();
ClipTri tri2 = new ClipTri();
ClipTri tri3 = new ClipTri();
ClipTri tri4 = new ClipTri();
tri1.generation = tri.generation+1;
tri2.generation = tri.generation+1;
tri3.generation = tri.generation+1;
tri4.generation = tri.generation+1;
tri1.n1 = tri.n1;
tri2.n2 = tri.n2;
tri3.n3 = tri.n3;
Vector3 n = 0.5f * (tri.n1 + tri.n2);
n.Normalize();
tri1.n2 = n;
tri2.n1 = n;
tri4.n3 = n;
n = 0.5f * (tri.n2 + tri.n3);
n.Normalize();
tri2.n3 = n;
tri3.n2 = n;
tri4.n1 = n;
n = 0.5f * (tri.n3 + tri.n1);
n.Normalize();
tri1.n3 = n;
tri3.n1 = n;
tri4.n2 = n;
activeTriList.Push(tri1);
activeTriList.Push(tri2);
activeTriList.Push(tri3);
activeTriList.Push(tri4);
}
else
{
ClipTri triKeep = new ClipTri();
triKeep.n1 = p1;
triKeep.n2 = p2;
triKeep.n3 = p3;
surfaceTriList.Add( triKeep );
//m_points.Add(p1);
//m_points.Add(p2);
//m_points.Add(p3);
}
}