文章目录

• 计算机图形学-算法总结
• • 一、直线转换
  • • 1、DDA算法
    • 2、中点法
    • 3、Bresenhan算法
  • 二、圆
  • • 1、中点Bresenham画圆算法
    • 2、椭圆的中点Bresenham算法

计算机图形学-算法总结

一、直线转换

1、DDA算法

Δ y = y n − y 0 Δ x = x n − x 0 ε = 1 m a x ( ∣ Δ x ∣ , ∣ Δ y ∣ ) \Delta y=y_n-y_0 \\ \Delta x=x_n-x_0\\ \varepsilon=\frac{1}{max(|\Delta x|,|\Delta y|)} Δy=yn​−y0​Δx=xn​−x0​ε=max(∣Δx∣,∣Δy∣)1​
把区间分成$Max(|\Delta x|,|\Delta y|)$个，需要循环这么多次。

每次算出的x，y都需要+0.5，进行向下取整运算。（因为在显示屏上，都是整数，没有小数）。

int x0,y0,xn,yn;
cin>>x0>>y0>>xn>>yn;double k,x=x0,y=y0;
int dx=xn-x0;
int dy=yn-y0;
k=max(dx,dy);for(int i=0;i<k;i++){
cout<<x<<" "<<y<<" ";x+=(dx/k);y+=(dy/k);//进行取整运算x=int(x+0.5);y=int(y+0.5);
}

2、中点法

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

假设，红色点是我们现在位置，那么我们下一步，只能是走到蓝色点或者紫色点。紫色点$(x+1,y)$，蓝色点$(x+1,y+1)$。把紫色与蓝色中间的坐标$(x+1,y+0.5)$带入，再得解ym，判断ym的大小，ym>=0,下一个点为紫色点，否则为蓝色点。就这样算下去，直到结束。
y m > = 0 时 ， y m i + 1 = y m i + 1 − k y m < 0 时 ， y m i + 1 = y m i − k y m 0 = 0.5 − k 用 2 Δ x y m i 替 换 y m i y m > = 0 , y m = y m + 2 Δ x − 2 Δ y y m < 0 , y m = y m − 2 Δ y ym>=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<<x<<y<<" ";++x;if(d<0){  //说明是蓝色点++y;d+=up;}else{  //说明是紫色点d+=dow;}
}

3、Bresenhan算法

这个算法是对中点法的优化。令e= y m i − 0.5 ym_i-0.5 ymi​−0.5,如果$e>0$说明下一个坐标是$(x+1,y+1)$否则就是$(x+1,y)$。为了除去小数(0.5)，用2e$\Delta x$来替换e。
e i + 1 = { e i + 2 Δ y − 2 Δ x e i > 0 e i + 2 Δ y e i ≤ 0 e 的 初 始 值 为 − Δ x e_{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<<x<<" "<<y<<" ";x++;e+=2*dy;if(e>0){y++;e-=2*dx;}
}

二、圆

1、中点Bresenham画圆算法

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

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

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

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

对于下一个点，在$(x+1，y),(x+1,y-1)$里面选一个，通过中点$(x+1,y+0.5)$的符合判断选择哪一个。
d i = F ( x + 1 , y + 0.5 ) > 0 , 选 择 ( x + 1 , y − 1 ) ; d i = 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);

d i + 1 = { d i + 2 x i + 3 , d < 0 d i + 2 ( x i − y i ) + 5 , d ≥ 0 d 初 始 值 为 1 − R d_{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<<x<<y<<" ";if(d<0){d+=2*x+3;}else{--y;d+=2(x-y)+5;}++x;
}

2、椭圆的中点Bresenham算法

椭圆方程
F ( x , y ) = b 2 x 2 + a 2 y 2 − a 2 b 2 = 0 F(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,y-1)或者(x+1,y-1)$
构 造 判 别 式 d i = F ( x + 1 , y + 0.5 ) 构造判别式 d_i=F(x+1,y+0.5) 构造判别式di​=F(x+1,y+0.5)
上部分

d i + 1 = { d i + b 2 ( 2 x i + 3 ) , d < 0 d i + b 2 ( 2 x i + 3 ) + a 2 ( − 2 y i + 2 ) , d ≥ 0 d_{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 初 始 值 为 b 2 + a 2 ( − b + 0.25 ) d初始值为b^2+a^2(-b+0.25) d初始值为b2+a2(−b+0.25)
下部分
d i + 1 = { d i + b 2 ( 2 x i + 2 ) + a 2 ( − 2 y i + 3 ) , d < 0 d i + a 2 ( − 2 y i + 3 ) , d ≥ 0 d_{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 初 始 值 为 b 2 ( x + 0.5 ) 2 + a 2 ( y − 1 ) 2 − a 2 b 2 d初始值为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<<x<<y<<" ";
cout<<-x<<-y<<" ";
cout<<-x<<y<<" ";
cout<<x<<-y<<" ";//上半部分
while(b*b*(x+1)<a*a*(y-0.5)){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<<x<<y<<" ";
cout<<-x<<-y<<" ";
cout<<-x<<y<<" ";
cout<<x<<-y<<" ";  
}//下半部
d2=b*b*(x+0.5)*(x+0.5)+a*a*(y-1)*(y-1)-a*a*b*b;
while(y<0){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<<x<<y<<" ";
cout<<-x<<-y<<" ";
cout<<-x<<y<<" ";
cout<<x<<-y<<" ";    
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！