Curse this forum. I typed this up once, hit submit, and the board gave an internal server error and my words of wisdom were lost forever.

Oh well, it gave me a chance to think “hmm, that’ll come in handy in the next day or so”, so I wrote it. Provided the vertices describe a convex polygon you can do the following. (It’s in C++ (obviously), it uses my vector3 class, it’s probably terrible coding style, the FindPolygon function is a bit of a mess. It’s free, what do you expect? )

Before calling into FindPolygon, set all your vertices z values to zero, and create an array of int[numvertices] for the results to get put into.

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;

}

Wow, I’m glad I typed this up in VC, typing into this little box is a nightmare.

Oh, the usual disclaimers apply. If your nuclear power station blows up as a result of using this code, don’t blame me, it’s all at your own risk

[edited for nicer formatting]

[This message has been edited by SmutMonkey (edited 03-13-2004).]