计算机图形学算法.ppt

计算机图形学算法基础作业
DDA直线生成法
中点画直线法
Bresenham生成直线
Bresenham画圆
DDA直线生成法
DDA算法基本原理
DDA是数字微分分析式(Digital Differential Analyzer)的缩写。设直线之起点为,终点为,则斜率为:
直线中的每一点坐标都可以由前一点坐标变化一个增量而得到,即表示为递归式:
并有关系:
DDA直线生成法
递归式的初值为直线的起点,这样,就可以用加法来生成一条直线。
DDA算法实现步骤
具体方法是:
按照直线从到的方向不同,分为8个象限(见图1)。对于方向在第1a象限内的直线而言,。对于方向在第1b象限内的直线而言,取值各不相同。
算法流程
初始化
判断dx与dy中哪个较大当|dx|>|dy|时x1=x+1。.y1=y+1/m
重复操作
DDA算法程序
#include<>
#include<>
#include<>
#include<>
#include<>
void dda_line(int xa,int ya,int xb,int yb,int c)
{
float delta_x,delta_y,x,y;
int dx,dy,steps,k;
dx=xb-xa;
dy=yb-ya;
DDA算法程序
if(abs(dx)>abs(dy))
steps=abs(dx);
else steps=abs(dy);
delta_x=(float)dx/(float)steps;
delta_y=(float)dy/(float)steps;
x=xa;
y=ya;
putpixel(x,y,c);
for(k=1;k<=steps;k++)
{
x+=delta_x;
y+=delta_y;
DDA算法程序
putpixel(x,y,c);
}
}
void main()
{
int a,b,c,d,e;
int gdriver=DETECT,gmode,errorcode;
char msg[80];
initgraph(&gdriver,&gmode,"");
errorcode=graphresult();
if (errorcode != gr0k)
{
DDA算法程序
printf("Graphics error:%s\n",grapherrormsg(errorcode));
printf("press any key to halt:");
getch();
exit(1);
}
printf("print two point and color\n");
scanf("%d,%d,%d,%d,%d",&a,&b,&c,&d,&e);
dda_line(a,b,c,d,e);
getch();
}
中点画直线法
下面讨论中点画线法的实现。过点、的直线段L的方程式为,其中,,要判断中点M在Q点的上方还是下方,只要把M代入,并判断它的符号即可。为此,我们构造判别式:
    当时,M在L(Q点)下方,取为下一个象素;
    当时,M在L(Q点)上方,取为下一个象素;
    当时,选或均可,约定取为下一个象素。
中点画直线法
注意到是的线性函数,可采用增量计算,提高运算效率。
若当前象素处于情况,则取正右方象素,要判下一个象素位置,应计算,增量为a。
    若时,则取右上方象素。要判断再下一象素,则要计算,增量为。画线从开始,的初值,因,所以。
    由于我们使用的只是的符号,而且的增量都是整数,只是初始值包含小数。因此,我们可以用代替来摆脱小数,写出仅包含整数运算的算法程序。