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 iAdded=0;
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);
//AddSortedVertex(p,copy[0].p);
int icount=p->m_iVertices;
p->m_iVertices=0;
for(i=0;i<icount;i++)
{
if(GetLastVertexFromPolygon(p))
{
VectorCopy(GetLastVertexFromPolygon(p)->p,compare);
}
else
{
AddSortedVertex(p,copy[0].p);
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)
AddSortedVertex(p,copy[iSortedIdx].p);
//printf("%f %f %f \n",compare[0],compare[1],compare[2]);
}
//AddSortedVertex(p,b);
printf("%d\n",p->m_iVertices);
}
vertex_t *CMapParser::AddSortedVertex(struct polygon_s *p,vec3_t point)
{
if(!p )
{
printf("ok\n");
return NULL;
}
vertex_t *browse=NULL;
bool bAddPoint=true;
browse=p->v;
int i=0;
if(p->v!=NULL)
{
while(browse)
{
if(VectorEqual(point,browse->p))
{
bAddPoint=false;
//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)
{
if(browse->next==NULL /*&& bAddPoint==true*/)
{ 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]
Vertex Sorting not working properly
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
[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]
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.
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
Hopefully I understood you correctly
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
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
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
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement