图形学初步------圆生成Bresenham算法

上一篇讲完了直线最简单的生成算法，这篇我们讲圆的生成算法，这些都是比较basic&easy的思路和code，并且一定能实现，因为博主我也在学习中~

除了直线的光栅化研究，还有很多曲线光栅化研究，比如说：圆、椭圆、抛物线、双曲线等圆锥曲线的光栅化。其中，Bresenham算法是一种最简单最有效的方法。我们先看下图：

怎么画圆呢？如果是一个像素一个像素的去算，是不是太不符合工科生的思维了。我们要的是，用尽量小的脑力劳动去完成一个比较大的工作量~只要算法写得好，放心交给计算机跑。

首先，我们只需要画出一个八分圆(逆时针0°-45°)，也就是①的那段圆弧；然后②这段圆弧就可以通过y=x对称变换得到，这时候我们把①②合并起来就得到了一个四分圆(逆时针0°-90°)；四分圆对x=0对称变换，得到了③④，把①②③④合并起来通过y=0对称变换，就得到了下半部分的半圆，上半圆和下边圆合并起来就是整个圆啦！

那三个 二阶对称变换矩阵怎么理解，这里需要读者有线性代数的基础。比如说我们有点A(2,1)在圆上，那么通过y=x这个直线得到的对称点是：

不知道哪位小主有更好的数学描述工具啊，一眼看上去就很拙劣的图都是鄙人用mspaint画出来的，委屈·····

好了，下面我们开始推导Bresenham算法啦，这里我们让坐标原点是圆心，那么第一个四分圆应该是顺时针画还是逆时针画呢，我们看到，如果起始点是(0,R),然后顺时针画圆的话，y是x的递减函数；如果起始点是(R,0)，然后逆时针画圆的话，x是y的递减函数。顺时针比较符合人的理解方式，所以我们选择顺时针方向画圆~

那么从起点开始，下一个像素该选择哪个像素呢？我们有三个方向的像素可以选择-----右方像素、右下角像素、下方像素，分别记为mH，mD，mV。如下图所示：

我们要在这三个像素中，选择一个像素点。选择的依据就是这个点应该是最逼近真正的圆的。我们用差值来表达逼近的程度，也就是---这个点离圆心的距离平方-圆半径平方：

圆这条线呢，肯定不会乖乖的经过这三个点，它可能会在点与点之间裸奔。于是我们用人脑穷举，发现圆与点(xi,yi)附近光栅网格的相交关系只有5种可能，也就是上面的那幅图。下面我们开始思考这5种情况了：

如果∆i < 0 ，说明右下角像素点(xi + 1,yi - 1) 在圆内，对应情形①②，这时候取像素(xi + 1,yi),也就是mH；或者取像素(xi + 1,yi - 1)，也就是mD，因为这时候只有mH或者mD最逼近圆弧了，反正看情况二选一。

        情形①，到底圆弧离mH近还是mD近，用这个方程来衡量：

               下面我们来简化这个判断语句，对于情形①来讲，mH肯定是在圆外，mD肯定是在圆内，也就是说

               因此     

               去括号以后，得到

        情形②，只能选择mH，这时候mH和mD都位于圆内，因此

               这时候，

               我们就可以把情形②跟情形 ①中的其中一个分支合并啦，合并结果就是：

if delt_i < 0:
	if Q <=0 then
		select mH
	if Q > 0 then
		select mD
		

如果∆i > 0, 也就是右下角(xi + 1,yi -1)位于圆外，对应图中的情形③④，显然只能取mD，或者mV，下面就分情况讨论。

        情形③，判断mV和mD哪个点更逼近真正的圆

       同理，我们把公式简化

        情形④，只能取下方像素mV

        因此，我们可以把情形④和情形③中的一个分支合并啦，合并结果就是：

if delt_i > 0:
	if Q_ <= 0 then
		select mD
	if Q_ > 0 then
		select mV

如果∆i=0，

        情形⑤，圆恰巧乖乖的经过了mD，这时候，我们要看是否可以归并到上述的两大情况的其中一种：

         也就是：

          随便归类到哪一个都行。

最后，判别准则就简化如下：

if delt_i < 0:
	if Q <=0 then
		select mH
	if Q > 0 then
		select mD
		
		
if delt_i > 0:
	if Q_ <= 0 then
		select mD
	if Q_ > 0 then
		select mV
if delt_i = 0:
	select mD

也可以这么写：

if delt_i <= 0:
	if Q <=0 then
		select mH
	if Q > 0 then
		select mD
		
		
if delt_i > 0:
	if Q_ <= 0 then
		select mD
	if Q_ > 0 then
		select mV

因此我们的Bresenham的伪代码就出来了：

#all variables are assumed integer
start
	#initialize the variables
	xi = 0
	yi = R
	delt_i = 2*(1-R)
	Limit = 0

	while yi >= Limit
		call setpixel(xi,yi)
		#determin if case 1 or 2, 3 or 4, or 5
		if delt_i < 0 then
			Q = 2*delt_i + 2*yi - 1
			#determin whether case 1 or 2
			if Q <=0 then
				call mh(xi,yi,delt_i)
			else
				call md(xi,yi,delt_i)
			end if
		else if delt_i > 0 then
			Q_ = 2*delt_i - 2*xi -1
			#determin whether case 3 or 4
			if Q_ <= 0 then
				call md(xi,yi,delt_i)
			else call mv(xi,yi,delt_i)
			end if
			
		else if delt_i = 0
                        #case 5
			call md(xi,yi,delt_i)
		end if
	end while
finish

#move horizontally
subroutine mh(xi,yi,delt_i):
	xi = xi + 1
	delt_i = delt_i + 2*xi + 1
#end sub

#move diagonally
subroutine md(xi,yi,delt_i):
	xi = xi + 1
	yi = yi -1
	delt_i = delt_i + 2*xi - 2*yi + 2
#end sub

#move vertically
subroutine mv(xi,yi,delt_i):
	yi = yi - i 
	delt_i = delt_i - 2*yi + 1 
#end sub

不知道读者有没有看懂，delt_i之所以在三个函数里都改变了，是因为我们的基准点移动啦~意思就是，当我从(xi,yi)水平移动到(xi + 1, yi)之后，我们的基准点(xi,yi)就变成了(xi + 1 ,yi)了。下面举个例子来帮助读者更加详细的认知这个过程：

例：以坐标原点为圆心，半径为8的圆在第一象限部分为例

#初始值
xi = 0,yi=8
delt_i = 2(1-8) = -14
Limit = 0
#开始loop

	#Step 1
	yi > Limit:
		setpixel(0,8)
		delt_i < 0:
			Q = 2*(-14) + 2*8 - 1 = -13 < 0
			call mh(0,8,-14):
				x = 0 + 1 = 1
				delt_i = -14 + 2*(1) + 1 = -11
	#Step2
	yi > Limit:
		setpixel(1,8)
		delt_i < 0:
			Q = 2*(-11) + 2*(8) -1 = -7
			Q < 0
			call mh(1,8,-11):
				x = 1 + 1 = 2
				delt_i = -11 + 2*(2) + 1 = -6
	#Step3
	....

#跳出loop

最后的画图结果应该是这样的：

好了，一个四分圆搞定了，那么我们怎么通过整个四分圆得到整个圆呢?

思路就是在循环中，每次都把选中的像素散播在其他象限对应的位置。

于是我的c++代码是这样的：

void CCGPainterView::DrawCircle(CDC *pDC, CPoint ptOrigin, int iRadius, COLORREF cLineColor)
{
	//CPoint ptLeftTop(ptOrigin.x - iRadius, ptOrigin.y - iRadius);
	//CPoint ptRightBottom(ptOrigin.x + iRadius, ptOrigin.y + iRadius);
	//CRect circleRect(ptLeftTop, ptRightBottom);
	//pDC->Ellipse(circleRect);

/*************************************************************
write the circle algorithm for drawing the circle
use function: pDC->SetPixelV(point, cLineColor); to drawing a pixel
编码圆弧生成算法，调用函数pDC->SetPixelV(point, cLineColor)画像素。
*************************************************************/
	
	POINT point;
	int xi = 0; 
	int yi = iRadius;
	int delt_i = (xi+1)*(xi+1)+(yi-1)*(yi-1)-iRadius*iRadius;
	int alpha;
	int Limit = 0;

	while (yi >= Limit){
		point.x = ptOrigin.x + xi;
		point.y = ptOrigin.y + yi;
		pDC->SetPixelV(point, cLineColor);
		point.x = ptOrigin.x + xi;
		point.y = ptOrigin.y - yi;
		pDC->SetPixelV(point, cLineColor);
		point.x = ptOrigin.x - xi;
		point.y = ptOrigin.y + yi;
		pDC->SetPixelV(point, cLineColor);
		point.x = ptOrigin.x - xi;
		point.y = ptOrigin.y - yi;
		pDC->SetPixelV(point, cLineColor);
		if (delt_i < 0){
			alpha = 2 * delt_i + 2 * yi - 1;
			if (alpha <= 0){
				//mh(xi, yi, delt_i);
				xi = xi + 1;
				delt_i = delt_i + 2 * xi + 1;
			}
			else{
				//md(xi, yi, delt_i);
				xi = xi + 1;
				yi = yi - 1;
				delt_i = delt_i + 2 * xi - 2 * yi + 2;
			}
				
		}
		else if(delt_i>0){
			alpha = 2 * delt_i - 2 * xi - 1;
			if (alpha <= 0){
				//md(xi, yi, delt_i);
				xi = xi + 1;
				yi = yi - 1;
				delt_i = delt_i + 2 * xi - 2 * yi + 2;
			}
			else{
				//mv(xi, yi, delt_i);
				yi = yi - 1;
				delt_i = delt_i - 2 * yi + 1;
			}
				
		}
		else{
			//md(xi, yi, delt_i);
			xi = xi + 1;
			yi = yi - 1;
			delt_i = delt_i + 2 * xi - 2 * yi + 2;
		}
	}
}

我们的运行结果如下：

另外我要注释一下：

如果只保留其中一个象限点的描点，你会发现，画出来的四分圆并不是数学上的第一象限，但是是计算机的第一象限。

point.x = ptOrigin.x + xi;
point.y = ptOrigin.y + yi;
pDC->SetPixelV(point, cLineColor);
/*
point.x = ptOrigin.x + xi;
point.y = ptOrigin.y - yi;
pDC->SetPixelV(point, cLineColor);
point.x = ptOrigin.x - xi;
point.y = ptOrigin.y + yi;
pDC->SetPixelV(point, cLineColor);
point.x = ptOrigin.x - xi;
point.y = ptOrigin.y - yi;
pDC->SetPixelV(point, cLineColor);
*/

 

因为计算机的原点是从屏幕左上角开始的，往右是x轴正向，往下是y轴正向~

其实这个算法并不难，就是要计算的公式太多。。。。。没有耐心和数学功底的人是干不下去的。。。

若有理解不到之处，还请大佬指正~