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;
}    

Share this post


Link to post
Share on other sites
Cross-post in the Maths-Physics forum. You should delete one of your threads before the moderators choose for you.

Regarding your specific question, try to reduce the code samples to a minimum. It''s quite long to get to the meat of the problem.

Cédric

Share this post


Link to post
Share on other sites