OpenGL研究2.0 圆计算方法

DionysosLai2014-06-18

         在游戏中，经常有些地方涉及到一些圆的轨迹计算，比方一些转轴类的游戏，人物一般在角色转轴上面运动。这时，我们就要时刻计算角色的位置。分析一下，圆位置的一般算法。

         首先，如下图的一个圆：

图1

         根据对称性原理，我们只需要计算黑色区域的点集合即可。同时，由于黑色区域的圆的切线斜率明显在-1到0，这点就可以和前面一节线段的计算方法相结合了。

         圆的点计算方法：

1.      直接计算方法

          1). 离散点计算法

          利用隐函数公式方法：；

          2). 三角函数方法

          这两个方法，明显都涉及到了三角函数、开根号等一些比较复杂的计算方法，运算量比较大。

2.      中点运算方法

         思想：圆的正负性划分：,将点(x,y)带入F(x,y)中，则：

          F(x,y)>0---->圆外面的点，F(x,y)=0---->圆上的点，F(x,y)<0---->圆里面的点。

          运算：

          在图1中，黑色区域的x值变化率大于y，切线斜率在-1到0之间，取x递增1。则

           和的关系如下图所示：

        对于点，要么在点E或者在点SE。

        基本原理：

        对于点的下一个点间的线段中点M=(xi+1,yi-0.5),将点M带入F(x,y)方程中，如果F(M)<=0, 说明点M在圆内，则点取点E，反之取点SE。    

        数学计算：

       假设di=F(M)，那么下一个点的d值如下所示：

      1）  如果di<=0,则取E点，即，因此

      2）  如果di>0,则取SE点，即，因此

      3）   那么对于d0，值为多少呢？有计算式可知：

      4）  综上，我们有如下关系：

      代码如下：

void midCircle(int x0, int y0, int R)
{
	/*只画1/8圆*/
	int d0, d1, d2,x,y,xEnd;
	d0 = 1.25-R;
	x = x0;
	y = y0-R;
	xEnd = x0+sqrt(2)/2.f*R;
	SetPixel(x,y);
	while(x<xEnd)
	{
		if(d0<=0)
		{
			d0 = d0+x+x+3;
		}
		else
		{
			y = y -1;
			d0 = d0+x+x-y-y+5;
		}
		x = x+1;
	}
}

3.      正内多边形迫近法

         基本原理：通过内接多边形不断的逼近一个圆：

         计算公式：

           一般，只要你内接多边形边数越大，就越接近圆了。曾经试过100正多边形，基本符合圆的需求了。