计算机图形学-算法总结

2、中点法

假设，最大位移方向为x方向，直线方程如下图所示。

假设，红色点是我们现在位置，那么我们下一步，只能是走到蓝色点或者紫色点。紫色点(x+1,y)(x+1,y)(x+1,y)，蓝色点(x+1,y+1)(x+1,y+1)(x+1,y+1)。把紫色与蓝色中间的坐标(x+1,y+0.5)(x+1,y+0.5)(x+1,y+0.5)带入，再得解ym，判断ym的大小，ym>=0,下一个点为紫色点，否则为蓝色点。就这样算下去，直到结束。
ym>=0时，ymi+1=ymi+1−kym<0时，ymi+1=ymi−kym0=0.5−k用2Δxymi替换ymiym>=0,ym=ym+2Δx−2Δyym<0,ym=ym−2Δyym>=0时，ym_{i+1}=ym_i+1-k\\ ym<0时，ym_{i+1}=ym_i-k\\ ym_0=0.5-k\\ 用2\Delta x ym_i 替换ym_i\\ ym>=0, ym=ym+2\Delta x-2\Delta y\\ ym<0,ym=ym-2\Delta y ym>=0时，ymi+1​=ymi​+1−kym<0时，ymi+1​=ymi​−kym0​=0.5−k用2Δxymi​替换ymi​ym>=0,ym=ym+2Δx−2Δyym<0,ym=ym−2Δy

int dx,dy,d,up,dow,x,y;
if(x0>xn){ //说明是第三象限//交换一下x0与xn即可，x=xn;xn=x0;x0=xn;y=yn;yn=y0;y0=y;  
}
dx=xn-x0;
dy=yn-y0;
x=x0;
y=y0;d=dx-2*dy;
up=2*dx-2*dy;
dow=-2*dy;//进行打印点
while(x<=xn){cout<  //说明是蓝色点++y;d+=up;}else{  //说明是紫色点d+=dow;}
}

3、Bresenhan算法

这个算法是对中点法的优化。令e=ymi−0.5ym_i-0.5ymi​−0.5,如果e>0e>0e>0说明下一个坐标是(x+1,y+1)(x+1,y+1)(x+1,y+1)否则就是(x+1,y)(x+1,y)(x+1,y)。为了除去小数(0.5)，用2eΔx\Delta xΔx来替换e。
ei+1={ei+2Δy−2Δxei>0ei+2Δyei≤0e的初始值为−Δxe_{i+1}=\begin{cases} e_i +2\Delta y -2\Delta x & e_i>0\\ e_i + 2\Delta y& e_i\leq 0 \end{cases}\\ e的初始值为-\Delta x ei+1​={ei​+2Δy−2Δxei​+2Δy​ei​>0ei​≤0​e的初始值为−Δx

int x,y,dx,dy,e;
dx=xn-x0;
dy=yn-y0;
e=-dx;
x=x0;y=y0;
while(x<=xn){cout<0){y++;e-=2*dx;}
}

二、圆

1、中点Bresenham画圆算法

对于圆心不在原点的圆，可以通过平移，让它圆心变成原点。

由图可知，圆有4条对称轴，把圆分成了完全相同的8个圆，我们只需要画出1/8，就能画出完整的圆。

假设圆的方程
x2+y2=R2x^2+y^2=R^2\\ x2+y2=R2
构造函数F(x,y)=x2+y2−R2F(x,y)=x^2+y^2-R^2F(x,y)=x2+y2−R2,

1. 对于圆上的点F(x,y)=0F(x,y)=0F(x,y)=0
2. 圆外的点F(x,y)>0F(x,y)>0F(x,y)>0
3. 圆内的点F(x,y)<0F(x,y)<0F(x,y)<0

对于下一个点，在(x+1，y),(x+1,y−1)(x+1，y),(x+1,y-1)(x+1，y),(x+1,y−1)里面选一个，通过中点(x+1,y+0.5)(x+1,y+0.5)(x+1,y+0.5)的符合判断选择哪一个。
di=F(x+1,y+0.5)>0,选择(x+1,y−1);di=F(x+1,y+0.5)≤0,选择(x+1,y);d_i=F(x+1,y+0.5)>0,选择(x+1,y-1);\\ d_i=F(x+1,y+0.5)\leq0,选择(x+1,y);\\ di​=F(x+1,y+0.5)>0,选择(x+1,y−1);di​=F(x+1,y+0.5)≤0,选择(x+1,y);

di+1={di+2xi+3,d<0di+2(xi−yi)+5,d≥0d初始值为1−Rd_{i+1}= \begin{cases} d_i+2x_i+3,&d<0\\ d_i+2(x_i-y_i)+5, &d \geq 0\\ \end{cases}\\ d初始值为1-R di+1​={di​+2xi​+3,di​+2(xi​−yi​)+5,​d<0d≥0​d初始值为1−R

int x,y,d;
x=0;
y=r;
d=1-r;
while(x<=r){cout<d+=2*x+3;}else{--y;d+=2(x-y)+5;}++x;
}

2、椭圆的中点Bresenham算法

椭圆方程
F(x,y)=b2x2+a2y2−a2b2=0F(x,y)=b^2x^2+a^2y^2-a^2b^2=0 F(x,y)=b2x2+a2y2−a2b2=0

由图可知，椭圆关于y=0,x=0对称，把椭圆分成了4个完全相等的部分。我们只需要画出1/4个即可,再利用对称性，就可画出全部。

把第一象限的椭圆分成2部分，如绿色和翠绿色，绿色最大位移方向为x方向，翠绿色最大位移方向为y方向。采用中点来判断下一个点在哪。

上部分（绿色），下一个点是(x+1,y)或者(x+1,y−1)(x+1,y)或者(x+1,y-1)(x+1,y)或者(x+1,y−1).

下部分（翠绿色),下一个点是(x,y−1)或者(x+1,y−1)(x,y-1)或者(x+1,y-1)(x,y−1)或者(x+1,y−1)
构造判别式di=F(x+1,y+0.5)构造判别式 d_i=F(x+1,y+0.5) 构造判别式di​=F(x+1,y+0.5)
上部分

di+1={di+b2(2xi+3),d<0di+b2(2xi+3)+a2(−2yi+2),d≥0d_{i+1}= \begin{cases} d_i+b^2(2x_i+3),&d<0\\ d_i+b^2(2x_i+3)+a^2(-2y_i+2), &d \geq 0 \end{cases}\\ di+1​={di​+b2(2xi​+3),di​+b2(2xi​+3)+a2(−2yi​+2),​d<0d≥0​
d初始值为b2+a2(−b+0.25)d初始值为b^2+a^2(-b+0.25)d初始值为b2+a2(−b+0.25)
下部分
di+1={di+b2(2xi+2)+a2(−2yi+3),d<0di+a2(−2yi+3),d≥0d_{i+1}= \begin{cases} d_i+b^2(2x_i+2)+a^2(-2y_i+3),&d<0 \\ d_i+a^2(-2y_i+3), &d \geq 0\\ \end{cases} di+1​={di​+b2(2xi​+2)+a2(−2yi​+3),di​+a2(−2yi​+3),​d<0d≥0​
d初始值为b2(x+0.5)2+a2(y−1)2−a2b2d初始值为b^2 (x+0.5 )^2+a ^2 (y-1) ^2 - a ^2 b^2 d初始值为b2(x+0.5)2+a2(y−1)2−a2b2

int x,y;
double d1,d2;
x=0;
y=b;
d1=b*b+a*a*(-b+0.25);
cout<if(d1<=0){d1+=b*b*(2*x+3);++x;}else{d1+=b*b*(2*x+3)+a*a*(-2*y+2);++x;--y;}
cout<if(d2<=0){d2+=b*b*(2*x+2)+a*a*(-2*y+3);++y;--y;}else{d2+=a*a*(-2*y+3);--y;}
cout<