bool FindNextVertex( vector3 *verts, int *indices, int numvertices, vector3 &v0, vector3 &v1, int &nextvertex )
{
vector3 e0 = v1-v0;
e0.Normalise();
int bestvertex = 0xffffffff;
float bestdev = -1e7f;
for ( int i=0; i < numvertices; i++ )
{
vector3 e1 = verts[indices[i]]-v1;
e1.Normalise();
vector3 cross = e0.CrossProduct(e1);
if ( cross.z < 0.0f )
{
float dev = e0.DotProduct(e1);
if ( dev > bestdev )
{
bestvertex = i;
bestdev = dev;
}
}
}
if ( bestvertex == 0xffffffff ) return false;
nextvertex = bestvertex;
return true;
}
// indices is an output buffer, allocated by caller
bool FindPolygon( vector3 *verts, int numvertices, int *indices )
{
int *idxs = new int[numvertices];
for ( int i=0; i < numvertices; i++ ) idxs[i] = i;
// randomise the order of the vertices
for ( int i=numvertices-1; i > 0; i-- )
{
int j = rand() % (i+1);
if ( i != j )
{
int tmp = idxs[i];
idxs[i] = idxs[j];
idxs[j] = tmp;
}
}
int nextvertex;
if ( !FindNextVertex( verts, &idxs[1], numvertices-2, verts[idxs[numvertices-1]], verts[idxs[0]], nextvertex ) )
return false;
indices[0] = idxs[0];
indices[1] = idxs[nextvertex+1];
for ( int j=nextvertex+1; j < numvertices-1; j++ )
idxs[j] = idxs[j+1];
for ( int i=2; i < numvertices; i++ )
{
if ( !FindNextVertex( verts, &idxs[1], numvertices-i, verts[indices[i-2]], verts[indices[i-1]], nextvertex ) )
return false;
indices[i] = idxs[nextvertex+1];
for ( int j=nextvertex+1; j < numvertices-1; j++ )
idxs[j] = idxs[j+1];
}
return true;
}