#### Archived

This topic is now archived and is closed to further replies.

# Sorting a list of vertacies

This topic is 5327 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites
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

##### Share on other sites
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++)
{
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[i].p - vCenter;
Vec1.Normalize();

// Compute second vertex
Vec2 = Vertices[i + 1].p - vCenter;
Vec2.Normalize();

// Set the starting smallest angle and vertex index
dSmallestAngle = Vec1.DotProduct(Vec2);
iSmallest = i + 1;

// Loop through all the vertices after this one
for (int j = i + 2; j < GetVertexCount(); j++)
{
// Temporary angle
double dAngle;

// Compute new value for vertex j
Vec2 = Vertices[j].p - Center;
Vec2.Normalize();

// Get angle of this vertex
dAngle = Vec1.DotProduct(Vec2);

// Set new angle if smaller
if (dAngle > dSmallestAngle)
{
dSmallestAngle = dAngle;
iSmallest = j;
}
}

// Swap vertices
cVertex Vertex;
Vertex = Vertices[i + 1];
Vertices[i + 1] = Vertices[iSmallest];
Vertices[iSmallest] = Vertex;
}

// Check if vertex order needs to be reversed for back-facing polygon
cPlane OldPlane = Plane;

// Calculate plane of polygon
CalculatePlane();

// If the old planes normal is behind the new plane then the order needs
// to be reversed so that the winding is CW
if (Plane.n.DotProduct(OldPlane.n) < 0)
{
// Store vertex count
int iVertexCount = GetVertexCount();

// Loop through and reverse vertex ordering
for (int i = 0; i < iVertexCount / 2; i++)
{
cVertex v = Vertices[i];
Vertices[i] = Vertices[iVertexCount - i - 1];
Vertices[iVertexCount - i - 1] = v;
}

// Recalculate plane normal
CalculatePlane();
}
}

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.

~Steve~

##### Share on other sites
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]

##### Share on other sites
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]

1. 1
Rutin
44
2. 2
3. 3
4. 4
5. 5

• 10
• 28
• 20
• 9
• 20
• ### Forum Statistics

• Total Topics
633409
• Total Posts
3011706
• ### Who's Online (See full list)

There are no registered users currently online

×