文档介绍：贵州大学计算机图形学实验报告
学院:计算机科学与信息学院专业:软件工程班级:102班
姓名
学号
实验组
实验时间
指导教师
成绩
实验项目名称
实验一直线生成算法
实验目的
通过本实验,了解并掌握在光栅显示系统中直线的生成和显示算法,熟悉相关开发平台。为后继实验打下基础。
实验要求
能够使用DDA数值微分法绘制直线。
能够使用中点画线算法绘制直线。
能够使用Bresenham画线算法绘制直线。
实验原理
一、DDA数值微分法画直线
已知直线段L的起点为P0(x0,y0),终点为P1(x1,y1)
yi
xi
yi+1
xi+1
直线的斜率K则为:K=(y1-y0)/(x1-x0).直线的方程为:y = kx+|k|<=1来说,x每增加1个步长,y增加 k(直线的斜率)。对于|k|>1来说,y每增加1个步长,x增加1/k。
分析如下所示:
|k|<=1的推导过程
yi+1 = kxi+1 + b = k(xi+Δx)+b = kxi+b+kΔx
yi+1 = yi+ kΔx
Δx = 1
yi+1 = yi+ k
|k|>1的推导过程
Xi+1 = yi+1/k – b/k = yi/k - b/k +Δy/k
Δy = 1
Xi+1 = Xi+1/k
DDA算法的分析:
复杂度:加法+取整
优点:避免了y=kx+b 方程中的浮点乘法,比直接用点斜式画线快。
缺点:需浮点数加法及取整运算,不利于硬件实现。
二、中点划线法
假设直线的起点、终点分别为:(X0,Y0),(X1,Y1),直线方程: F(x,y)=ax+by+c=0,其中: a=y0-y1,b=(x1-x0),c=x0y1-x1y0。
如F(x,y)=0, 则(x,y) 在直线上
如F(x,y)<0, 则(x,y)在直线下方
如F(x,y)>0, 则(x,y)在直线上方
对于|k|<=1
x
Pi=(xi, yi)
M
Q
P1
p2
y
假设已确定当前象素点P(Xp ,Yp ),然后确定下一个象素点,即T 或B之一。M为T,B中点,Q为理想直线与栅格线的交点。若M在Q的下方,选T,否则选B。:
d=F(M)=F(xp+1,yp+)=a(xp+1)+b(yp+)+c
当d<0,M在L(Q点)下方,取右上方T为下一个象素;
当d>=0,M在L(Q点)上方,取右方B为下一个象素;
当d=0,选T或B均可,约定取B为下一个象素
判断了M的位置之后则可以依次的画出各个点,从而得到一条直线。
对于|k|>1
d=F(M)=F(xp+,yp+1)=a(xp+)+b(yp+1)+c
当d>=0,M在L(Q点)下方,取右上方T为下一个象素;
当d<0,M在L(Q点)上方,取右方B为下一个象素;
当d=0,选T或B均可,约定取B为下一个象素
中点划线算法的分析:
优点:用整数加法代替了DDA数值微分法中的浮点数加法及取整运算,大大提高了算法的效率。
缺点:在计算d的符号时,需要做4个加法和2个乘法
改进:因为d是x和y的线性函数,因此可采用增量计算。通过计算可得对于|k|<=1的情况d的初值为a+,当d>=0,M在L上方,增量d1为a;当d<0,M在L下方,增量d2为a+b。对于|k|>+b,当d>=0,M在L下方,增量d1为b;当d<0,M在L上方,增量d2为a+b。
三、Bresenham划线算法
该算法是计算机图形学领域中使用最为广泛的直线扫描转换算法,该划线算法类似与中点划线算法,也是由误差项符号决定下一个像素右边点还是右上点。
基本原理:过各行各列像素中心构造一组虚拟网格线,按直线从起点到终点的顺序计算直线与各垂直网格线的交点,然后确定该列像素中与此交点最近的像素。该算法的优点在于增量计算,使得对于每一列只要检查一个误差项的符号,就可以确定该列所求的像素。根据直线的斜率来确定变量在x或y方向递增一个单位。另一个方向y或x的增量为0或1,它取决于实际直线与最接近网格点位置的距离。这一距离称为误差。
由以上原理,为方便计算,令e = d-,e的初值为-,增量为k。当 e>=0时,取当前像素(xi,yi)的右上方像素(xi+1,yi+1),e减小1,而当e<0时,更接近于右方像素(xi+1,yi)。
Bresenham算法的分析:
优点:高效,巧妙地采用了e = d-,e的初值为-,,使得每次画点只需考虑误差项增量的符号即可。
实验环境
硬