#### Archived

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

# Vertex Sorting not working properly

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

## Recommended Posts

this might be a bit advanced topic but i can t get it working although i can t find any mistake in my theory you are my last hope this code is for a .map file compiler which i want to make opensource once it is done so when help me,you support the community ok lets switch to the topic underneath i have posted the code to sorting the vertices see i get the center and one point from the polygon vertices then i check which vertex has the smallest angle in the trianle vertex0<-center->vertex1++ once i have found a point i add him back to the polygon and exclude him from the current search the last vertex added to the list of sorted vertices is used as comparsion vertex for the rest of the unsorted vertices ... but somehow screws it up the theory should be fine the dir1 and dir2 vectors get normalized so i don t have to used the length but only the dotproduct to get the cosinus cos 1==0° cos -1==180° so i only have to check for the smallest "cos" and then add the vertex with the smallest cos to the sorted list so far so good

void CMapParser::SortVertices(struct polygon_s *p)
{
vec3_t center={0,0,0};
vec3_t online={0,0,0};
vec3_t dir1={0,0,0};
vec3_t dir2={0,0,0};
float cos=0;
float lowestcos=-2;

vertex_t *copy=NULL;
vertex_t *browse=NULL;
copy=(vertex_t*)malloc(sizeof(struct vertex_s)*p->m_iVertices);
browse=p->v;
int i=0,a=0;
while( browse)
{
VectorCopy(browse->p,copy[i].p);
i++;
browse=browse->next;
}
free(p->v);
p->v=NULL;
for(i=0;i<p->m_iVertices;i++)
{
center[0]+=copy[i].p[0];
center[1]+=copy[i].p[1];
center[2]+=copy[i].p[2];
}
center[0]/=p->m_iVertices;
center[1]/=p->m_iVertices;
center[2]/=p->m_iVertices;
int iSortedIdx=-1;
int iCount=0;
int c=0;
int iReplace=-1;
vec3_t compare={0,0,0};
vec3_t b={0,0,0};
//VectorCopy(copy[0].p,compare);

VectorCopy(copy[0].p,b);

int icount=p->m_iVertices;
p->m_iVertices=0;
for(i=0;i<icount;i++)
{

if(GetLastVertexFromPolygon(p))
{
VectorCopy(GetLastVertexFromPolygon(p)->p,compare);
}
else
{
iSortedIdx=0;
}
copy[iSortedIdx].p[0]=-1;
copy[iSortedIdx].p[1]=-1;
copy[iSortedIdx].p[2]=-1;
VectorSubtract(compare,center,dir1);
VectorNormalize(dir1);
for(a=0;a<icount;a++)
{
if(copy[a].p[0]!=-1 && copy[a].p[1]!=-1 && copy[a].p[2]!=-1)
{

VectorSubtract(copy[a].p,center,dir2);

VectorNormalize(dir2);
cos=DotProduct(dir1,dir2);

if(cos>lowestcos)
{
//printf("Angle: %f\n",cos);

//VectorCopy(copy[a].p,compare);

iSortedIdx=a;
}
}
}
lowestcos=-2;
cos=-2;

if(copy[iSortedIdx].p[0]!=-1 && copy[iSortedIdx].p[1]!=-1 && copy[iSortedIdx].p[2]!=-1)
//printf("%f %f %f \n",compare[0],compare[1],compare[2]);

}

printf("%d\n",p->m_iVertices);
}

{
if(!p )
{
printf("ok\n");
return NULL;
}
vertex_t *browse=NULL;
browse=p->v;
int i=0;
if(p->v!=NULL)
{
while(browse)
{
if(VectorEqual(point,browse->p))
{
//printf("%f %f %f \n",point[0],point[1],point[2]);

return NULL;

}
browse=browse->next;
}
}
if(p->v==NULL)
{
p->v=(vertex_t*)malloc(sizeof(struct vertex_s));
p->v->next=NULL;
VectorCopy(point,p->v->p);
printf("%f %f %f \n",point[0],point[1],point[2]);
p->m_iVertices++;
return p->v;
}
else
{
browse=p->v;
while(browse)
{
{	browse->next= (vertex_t*)malloc(sizeof(struct vertex_s));
browse->next->next=NULL;
VectorCopy(point,browse->next->p);
printf("%f %f %f \n",point[0],point[1],point[2]);
p->m_iVertices++;
return browse->next;
}
browse=browse->next;
}

}
return NULL;
}

vertex_t *CMapParser::GetLastVertexFromPolygon(struct polygon_s *p)
{
vertex_t *browse=NULL;
if(p->v==NULL)
return NULL;
browse=p->v;
while(browse)
{
if(browse->next==NULL)
return browse;
browse=browse->next;
}
return browse;
}  [/i]  [/a]      
[edited by - Basiror on September 30, 2002 11:29:40 AM] [edited by - Basiror on September 30, 2002 11:37:24 AM] [edited by - Basiror on September 30, 2002 11:43:27 AM]

##### Share on other sites
So basically, you are trying to sort vertices counter-clockwise, starting from the vertex with the smallest angle. At least I think that''s what you want.

I would create a simple helper structure that contains a vertex structure (pointer if you wish) and a floating point number identifying the angle.

typedef struct vert_ang_s{   vertex_t *vert;   float angle;} vert_ang_t;

For each vertex, figure out its angle. This is as simple as an arc-cosine or arc-sine plus simple quadrant checks. Then use something like qsort to sort the vertices by angle. In the end, you have an order list of vertices, and you can just iterate the list, and that will be the correct order.

Hopefully I understood you correctly

##### Share on other sites
well the order has to be checked after you have sorted them by the smalled angle
you can do this by comparing the given normal with the normal that results by sorting them by the smalled angle to the next vertex
but this helper structure could be helpful
i gonna try this but thats very memory consuming

##### Share on other sites
It appears to be a lot less memory-intensive and computational expensive than the algorithm you wanted to use It really only uses 8 bytes for each instance of the helper structure, and qsort is fast for what it does.

1. 1
2. 2
3. 3
4. 4
Rutin
18
5. 5

• 11
• 22
• 12
• 12
• 11
• ### Forum Statistics

• Total Topics
631406
• Total Posts
2999903
×