Hi I have loaded the .MAP worldcraft vertices into an array using the intersection of three planes equation. I now need to sort the vertacies but am unable to get the code below to function correctly. It's suppose to take in an unsorted array of vertacies and put it into a clockwise winding order. It then draws the sorted array to a display list (For testing purposes). The data thats placed into the sorted array is not been sorted and as a result the geomotry is messed up when rendering as a polygon. I cannot understand what is wrong with the code. I have already calculated the centre of the polygon. This code is suppose to calcuate vectors from the centre of the poly to the vertacies on the outside. The vectors are placed in the dot product equation and the vertacie with the smallest angle from the current vector is placed into an array. This is repeated to sort the array. void SortVerts() { Vector3 poly; Poly SortedPoly; // Calculate the average of the vertices to find the centre point of the polygon for (int n=0; n SmallestAngle) { SmallestAngle = Angle; Smallest = m; } } SortedPoly.AddVertex(&Polys.Vertices[Smallest]); } level = glGenLists(1); // Generate room for one list and returns a pointer to the first and only list glNewList(level,GL_COMPILE); // Create the list int the space allocated by box and prebuild the list glBegin(GL_POLYGON); glPointSize(5.0f); glColor3ub(255,0,0); for (n=0; n<Polys.verts; n++) { glVertex3f(SortedPoly.Vertices[n].Vert[0], SortedPoly.Vertices[n].Vert[1], SortedPoly.Vertices[n].Vert[2]); } glEnd(); glEndList(); } Hope you undertsand what i'm on about Tell me what u think is wrong Thanks Alot ~Steve~ Edited by - steveharper101 on July 18, 2001 7:40:45 PM

Hey Steve, could you post that code I sent you here so anyone who looks this up will have an answer Post either my source or your adaptation of it, doesn''t matter.

Thanks man,

FatalXC

Yes the code that does it is below. It was wrote and sent to me by FatalXC. Sorry FatalXC it''s 03:37 am in the morning here in the United Kingdom and I haven''t had time to adapt it. Besides your comments and code style is good

//
// FUNCTION: cCompilerPolygon::SortVerticesCW
//
// PURPOSE: Sorts all the vertices in this polygon in clockwise order
// so that the renderer can use back face culling.
//
// FIXME: This is not perfect, and sometimes fails when polygons span an
axis
//
void cCompilerPolygon::SortVerticesCW(void)
{
cVector vCenter; // Calculate center of polygon

// Add all the vertices together
for (int i = 0; i < GetVertexCount(); i++)
{
// Add this vertex on
vCenter = vCenter + Vertices.p;
}

// Take the average of the vertices to get the center
vCenter = vCenter / (double)GetVertexCount();

// Sort vertices
for (i = 0; i < GetVertexCount() - 2; i++)
{
// Temporary vectors
cVector Vec1;
cVector Vec2;

double dSmallestAngle; // Holds the smallest angle from the centre
int iSmallest; // Which vertex had the angle above

// Compute first vertex
Vec1 = Vertices.p - vCenter;<br> Vec1.Normalize();<br><br> // Compute second vertex<br> Vec2 = Vertices.p - vCenter;<br> Vec2.Normalize();<br><br> // Set the starting smallest angle and vertex index<br> dSmallestAngle = Vec1.DotProduct(Vec2);<br> iSmallest = i + 1;<br><br> // Loop through all the vertices after this one<br> for (int j = i + 2; j < GetVertexCount(); j++)<br> {<br> // Temporary angle<br> double dAngle;<br><br> // Compute new value for vertex j<br> Vec2 = Vertices[j].p - Center;<br> Vec2.Normalize();<br><br> // Get angle of this vertex<br> dAngle = Vec1.DotProduct(Vec2);<br><br> // Set new angle if smaller<br> if (dAngle > dSmallestAngle)<br> {<br> dSmallestAngle = dAngle;<br> iSmallest = j;<br> }<br> }<br><br> // Swap vertices<br> cVertex Vertex;<br> Vertex = Vertices;<br> Vertices = Vertices[iSmallest];<br> Vertices[iSmallest] = Vertex;<br> }<br><br> // Check if vertex order needs to be reversed for back-facing polygon<br> cPlane OldPlane = Plane;<br><br> // Calculate plane of polygon<br> CalculatePlane();<br><br> // If the old planes normal is behind the new plane then the order needs<br> // to be reversed so that the winding is CW<br> if (Plane.n.DotProduct(OldPlane.n) < 0)<br> {<br> // Store vertex count<br> int iVertexCount = GetVertexCount();<br><br> // Loop through and reverse vertex ordering<br> for (int i = 0; i < iVertexCount / 2; i++)<br> {<br> cVertex v = Vertices;<br> Vertices = Vertices[iVertexCount - i - 1];<br> Vertices[iVertexCount - i - 1] = v;<br> }<br><br> // Recalculate plane normal<br> CalculatePlane();<br> }<br>}<br><br><br>FatalXC is publishing the source code for his own engine soon which parses .MAP files with textures using the intersection of three planes equation. It also loads light maps and performs the various CSG actions required.<br><br>Be sure to check it out if your interested in loading your own files from Quake 3 Radient.<br><br><br>~Steve~ </i>

Oi. I had a fun time dealing with this little bastard problem too, and I only found this forum post after I came up with a solution myself. My solution is a little more elegant than yours... it's a bit faster, it will always work and the only parameter you need to give it is the normal of the plane you need to sort to clockwise order for rendering.

for (int v=0;v < MyBrushFace->num_vertices;v++)
{
D3DXVECTOR3 c,i,j,t;

int v1 = (v+1) % MyBrushFace->num_vertices;
int v2 = (v+2) % MyBrushFace->num_vertices;

i = MyBrushFace->vertices[v2] - MyBrushFace->vertices[v];
j = MyBrushFace->vertices[v1] - MyBrushFace->vertices[v];

D3DXVec3Cross(&c,&i,&j);
D3DXVec3Normalize(&c,&c);

if (D3DXVec3Dot(&c,&MyBrushFace->plane.n)<0.0f)
{
t = MyBrushFace->vertices[v2];

MyBrushFace->vertices[v2] = MyBrushFace->vertices[v1];
MyBrushFace->vertices[v1] = t;
}
}

Hope this somehow helps someone somewhere so they don't have to go through what I did. :|

[edited by - parlance on April 19, 2004 9:34:51 PM]

[edited by - parlance on April 19, 2004 9:35:33 PM]

Sorry, after posting I noticed a few fatal flaws in my previous algorithm, but this one is definately fool-proof.

bool DoneSorting;

for (int i=0;i < MyBrushFace->num_vertices;i++)
{
DoneSorting = true;

for (int v=0;v < MyBrushFace->num_vertices-2;v++)
{
D3DXVECTOR3 c,i,j,t;

i = MyBrushFace->vertices[v+2] - MyBrushFace->vertices[0];
j = MyBrushFace->vertices[v+1] - MyBrushFace->vertices[0];

D3DXVec3Cross(&c,&i,&j);
D3DXVec3Normalize(&c,&c);

if (D3DXVec3Dot(&c,&MyBrushFace->plane.n)<0.0f)
{
DoneSorting = false;

t = MyBrushFace->vertices[v+2];

MyBrushFace->vertices[v+2] = MyBrushFace->vertices[v+1];
MyBrushFace->vertices[v+1] = t;
}
}

if (DoneSorting)
{
break;
}
}


[edited by - parlance on April 20, 2004 8:52:23 PM]