Archived

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

Basiror

Vertex Sorting not working properly

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 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]      
[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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites