trianglecreator.cpp

三角网的计算与绘制

				{

					iPointIndex=j;
					iBorderIndex=ii;
					dAngle=cosc;
				}
			}
			if(iPointIndex>=0 && pPointArray[iPointIndex].flag!=0)
				iPointIndex=-1;
			
			if(iPointIndex>=0 && dAngle>-dLimit)
			{//边界处的细长的三角形略去,只是内部向边界扩充时起作用,对于内部的钝角三角形可能受影响,但不影响结果
				double dxa=pPointArray[iPointIndex].x-fp1.x;
				double dya=pPointArray[iPointIndex].y-fp1.y;
				double aa=dxa*dxa+dya*dya;
				double a=sqrt(aa);

				double dxb=pPointArray[iPointIndex].x-fp0.x;
				double dyb=pPointArray[iPointIndex].y-fp0.y;
				double bb=dxb*dxb+dyb*dyb;
				double b=sqrt(bb);

				double cosb=(aa+cc-bb)/a/c/2.0;

				double cosa=(bb+cc-aa)/b/c/2.0;

				if(cosa<dLimit || cosb<dLimit )
				{
					iPointIndex=-1;
				}
			}
			if(iPointIndex<0)//没有扩充成功
			{
				pBorderArray[ii].SetFlag(0xff);
				continue;
			}

			break;
		}
		if(i>=iBorderCount)
		{
			break;
		}

		if(iBorderCount==2)
		{//初始三角形需特殊处理
			ASSERT(pBorderArray[iBorderIndex].m_byteBorderIndex==0 || pBorderArray[iBorderIndex].m_byteBorderIndex==1);

			if(pBorderArray[iBorderIndex].m_byteBorderIndex==0)
			{
				pTriangleArray[iTriangleCount-1].SetPointIndex(2,pTriangleArray[iTriangleCount-1].GetPointIndex((BYTE)0));
				pTriangleArray[iTriangleCount-1].SetPointIndex(0,iPointIndex);

				BorderIndexArray[0].m_iPointIndex0=iPointIndex;

				border.m_iTriangleIndex=iTriangleCount-1;
				border.m_byteBorderIndex=2;
				border.m_iPointIndex0=iPointIndex0;
				border.m_iPointIndex1=iPointIndex;

				BorderIndexArray.Add(border);
			}
			else
			{
				pTriangleArray[iTriangleCount-1].SetPointIndex(2,iPointIndex);

				BorderIndexArray[1].m_iPointIndex1=iPointIndex;

				border.m_iTriangleIndex=iTriangleCount-1;
				border.m_byteBorderIndex=2;
				border.m_iPointIndex0=iPointIndex;
				border.m_iPointIndex1=iPointIndex1;

				BorderIndexArray.Add(border);
			}

			continue;
		}
		iStartSearchIndex=iBorderIndex+1;

		//设置原来的三角形的公共边
		int iTriangleIndex=pBorderArray[iBorderIndex].m_iTriangleIndex;

		pTriangleArray[iTriangleIndex].SetNeighbor(pBorderArray[iBorderIndex].m_byteBorderIndex,iTriangleCount,0);

		//增加新的三角形
		triangle.SetPointIndex(0,iPointIndex1);
		triangle.SetPointIndex(1,iPointIndex0);
		triangle.SetPointIndex(2,iPointIndex);

		triangle.SetNeighbor(0,iTriangleIndex,pBorderArray[iBorderIndex].m_byteBorderIndex);

		m_TriangleArray.Add(triangle);

		//调整边界,将原来的一段边替换为新三角形的两段边
		pBorderArray[iBorderIndex].m_iTriangleIndex=iTriangleCount;
		pBorderArray[iBorderIndex].m_byteBorderIndex=2;
		pBorderArray[iBorderIndex].m_iPointIndex0=iPointIndex;

		border.m_iTriangleIndex=iTriangleCount;
		border.m_byteBorderIndex=1;
		border.m_iPointIndex0=iPointIndex0;
		border.m_iPointIndex1=iPointIndex;

		BorderIndexArray.InsertAt(iBorderIndex,border);

		int iNewTriangleIndex=iTriangleCount;

		int iNewBorderIndex0=iBorderIndex;//新加入的两条边
		int iNewBorderIndex1=iBorderIndex+1;//新加入的两条边
		//边检查是否有两对边重合
		iTriangleCount=(int)m_TriangleArray.GetSize();
		pTriangleArray=m_TriangleArray.GetData();
		iBorderCount=(int)BorderIndexArray.GetSize();
		pBorderArray=BorderIndexArray.GetData();
		for(i=0;i<iBorderCount;i++)
		{
			if(i==iNewBorderIndex0 || i==iNewBorderIndex1) continue;

			if(pTriangleArray[iNewTriangleIndex].IsSameBorder(1,pTriangleArray[pBorderArray[i].m_iTriangleIndex],pBorderArray[i].m_byteBorderIndex))
			{
				pTriangleArray[iNewTriangleIndex].SetNeighbor(1,pBorderArray[i].m_iTriangleIndex,pBorderArray[i].m_byteBorderIndex);
				pTriangleArray[pBorderArray[i].m_iTriangleIndex].SetNeighbor(pBorderArray[i].m_byteBorderIndex,iNewTriangleIndex,1);

				pBorderArray[iNewBorderIndex0].m_byteFlag=1;
				pBorderArray[i].m_byteFlag=1;
				break;
			}
		}
		for(i=0;i<iBorderCount;i++)
		{
			if(i==iNewBorderIndex0 || i==iNewBorderIndex1) continue;

			if(pTriangleArray[iNewTriangleIndex].IsSameBorder(2,pTriangleArray[pBorderArray[i].m_iTriangleIndex],pBorderArray[i].m_byteBorderIndex))
			{
				pTriangleArray[iNewTriangleIndex].SetNeighbor(2,pBorderArray[i].m_iTriangleIndex,pBorderArray[i].m_byteBorderIndex);
				pTriangleArray[pBorderArray[i].m_iTriangleIndex].SetNeighbor(pBorderArray[i].m_byteBorderIndex,iNewTriangleIndex,2);

				pBorderArray[iNewBorderIndex1].m_byteFlag=1;
				pBorderArray[i].m_byteFlag=1;
				break;
			}

		}

		//检查是否有相邻边重合
		int startindex=-1;
		int ii0=iNewBorderIndex0-1;
		int ii1=iNewBorderIndex1+1;
		if(ii0<0) ii0+=iBorderCount;
		if(ii1>=iBorderCount) ii1-=iBorderCount;

		BOOL b0=pTriangleArray[pBorderArray[ii0].m_iTriangleIndex].IsSameBorder(pBorderArray[ii0].m_byteBorderIndex,pTriangleArray[iNewTriangleIndex],1);
		BOOL b1=pTriangleArray[pBorderArray[ii1].m_iTriangleIndex].IsSameBorder(pBorderArray[ii1].m_byteBorderIndex,pTriangleArray[iNewTriangleIndex],2);


		if(b0)
		{
			pTriangleArray[pBorderArray[ii0].m_iTriangleIndex].SetNeighbor(pBorderArray[ii0].m_byteBorderIndex,iNewTriangleIndex,1);
			pTriangleArray[iNewTriangleIndex].SetNeighbor(1,pBorderArray[ii0].m_iTriangleIndex,pBorderArray[ii0].m_byteBorderIndex);
		}

		if(b1)
		{
			pTriangleArray[pBorderArray[ii1].m_iTriangleIndex].SetNeighbor(pBorderArray[ii1].m_byteBorderIndex,iNewTriangleIndex,2);
			pTriangleArray[iNewTriangleIndex].SetNeighbor(2,pBorderArray[ii1].m_iTriangleIndex,pBorderArray[ii1].m_byteBorderIndex);
		}

		if(b0 && b1)
		{
			ASSERT(pBorderArray[iNewBorderIndex0].m_byteBorderIndex==1);
			pTriangleArray[pBorderArray[ii0].m_iTriangleIndex].SetNeighbor(pBorderArray[ii0].m_byteBorderIndex,iNewTriangleIndex,1);
			pTriangleArray[iNewTriangleIndex].SetNeighbor(1,pBorderArray[ii0].m_iTriangleIndex,pBorderArray[ii0].m_byteBorderIndex);

			if(iNewBorderIndex1>ii0) iNewBorderIndex1--;
			iNewBorderIndex1--;
			startindex=iNewBorderIndex1;

			int ii=BorderIndexArray[ii0].m_iPointIndex1;
			pPointArray[ii].flag=1;

			if(ii0>iNewBorderIndex0)
			{

				BorderIndexArray.RemoveAt(ii0);
				BorderIndexArray.RemoveAt(iNewBorderIndex0);

			}
			else
			{
				BorderIndexArray.RemoveAt(iNewBorderIndex0);
				BorderIndexArray.RemoveAt(ii0);
			}
		}
		else if(b0)
		{
			startindex=ii0;
		}
		else if(b1)
		{
			startindex=iNewBorderIndex1;
		}
		if(startindex>=0)
		{
			while(TRUE)
			{
				iBorderCount=(int)BorderIndexArray.GetSize();
				pBorderArray=BorderIndexArray.GetData();

				if(startindex<0) 
					startindex+=iBorderCount;

				ii0=startindex;
				ii1=startindex+1;
				if(ii1>=iBorderCount) ii1-=iBorderCount;

				if(pTriangleArray[pBorderArray[ii0].m_iTriangleIndex].IsSameBorder(pBorderArray[ii0].m_byteBorderIndex,pTriangleArray[pBorderArray[ii1].m_iTriangleIndex],pBorderArray[ii1].m_byteBorderIndex))
				{
					pTriangleArray[pBorderArray[ii0].m_iTriangleIndex].SetNeighbor(pBorderArray[ii0].m_byteBorderIndex,pBorderArray[ii1].m_iTriangleIndex,pBorderArray[ii1].m_byteBorderIndex);
					pTriangleArray[pBorderArray[ii1].m_iTriangleIndex].SetNeighbor(pBorderArray[ii1].m_byteBorderIndex,pBorderArray[ii0].m_iTriangleIndex,pBorderArray[ii0].m_byteBorderIndex);

					int ii=BorderIndexArray[ii0].m_iPointIndex1;
					pPointArray[ii].flag=1;

					if(ii0<ii1)
					{
						startindex=ii0-1;
						BorderIndexArray.RemoveAt(ii0,2);
					}
					else
					{
						startindex=ii0-2;
						BorderIndexArray.RemoveAt(ii0);
						BorderIndexArray.RemoveAt(ii1);
					}
				}
				else
					break;
			}
		}
	}


	if(BorderIndexArray.GetSize()<3)
	{//没有扩充成功
		BorderIndexArray.RemoveAll();
		m_TriangleArray.RemoveAll();
		return;
	}
	//建立三角形间的邻接关系
	int iTriangleCount=(int)m_TriangleArray.GetSize();
	CTriangle* pTriangleArray=m_TriangleArray.GetData();
	int iPointIndex0[3];
	int iPointIndex1[3];
	for(int i=0;i<(iTriangleCount-1);i++)
	{
		pTriangleArray[i].GetPointIndex(iPointIndex0);

		int j; for(j=0;j<3;j++)
		{
			if(pTriangleArray[i].m_Border[j].m_iTriangleIndex>=0) continue;

			int j1=j+1;
			if(j1>=3) j1=0;

			int k; for(k=i+1;k<iTriangleCount;k++)
			{
				pTriangleArray[k].GetPointIndex(iPointIndex1);

				int l; for(l=0;l<3;l++)
				{
					if(pTriangleArray[k].m_Border[l].m_iTriangleIndex>=0) continue;

					int l1=l+1;
					if(l1>=3) l1=0;

					if(iPointIndex0[j]==iPointIndex1[l1] && iPointIndex0[j1]==iPointIndex1[l])
					{
						pTriangleArray[i].SetNeighbor(j,k,l);
						pTriangleArray[k].SetNeighbor(l,i,j);
						break;
					}
				}
				if(l<3) break;
			}
		}
	}

}
int CTriangleCreator::GetTriangleCount()
{
	return (int)m_TriangleArray.GetSize();
}
CTriangle* CTriangleCreator::GetTriangleArray()
{
	return m_TriangleArray.GetData();
}