贵州大学计算机图形学实验报告直线生成算法.docx

贵州大学计算机图形学实验报告直线生成算法.docx

《贵州大学计算机图形学实验报告直线生成算法.docx》由会员分享，可在线阅读，更多相关《贵州大学计算机图形学实验报告直线生成算法.docx（14页珍藏版）》请在冰点文库上搜索。

贵州大学计算机图形学实验报告直线生成算法

贵州大学计算机图形学实验报告

学院：

计算机科学与信息学院专业：

软件工程班级：

102班

姓名

学号

实验组

实验时间

指导教师

成绩

实验项目名称

实验一直线生成算法

实验目的

通过本实验，了解并掌握在光栅显示系统中直线的生成和显示算法，熟悉相关开发平台。

为后继实验打下基础。

实验要求

1、能够使用DDA数值微分法绘制直线。

2、能够使用中点画线算法绘制直线。

3、能够使用Bresenham画线算法绘制直线。

实验原理

一、DDA数值微分法画直线

已知直线段L的起点为P0（x0,y0）,终点为P1（x1,y1）

直线的斜率K则为：

K=（y1-y0）/（x1-x0）.直线的方程为：

y=kx+b.则对于|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

假设已确定当前象素点P（Xp,Yp）,然后确定下一个象素点，即T或B之一。

M为T，B中点，Q为理想直线与栅格线的交点。

若M在Q的下方，选T，否则选B。

使用直线的正负划分性来判断M和Q的位置关系.构造判别式:

d=F（M）=F（xp+1,yp+0.5）=a（xp+1）+b（yp+0.5）+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+0.5,yp+1）=a（xp+0.5）+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+0.5b，当d>=0，M在L上方，增量d1为a；当d<0，M在L下方，增量d2为a+b。

对于|k|>1的情况d的初值为0.5a+b，当d>=0，M在L下方，增量d1为b；当d<0，M在L上方，增量d2为a+b。

三、Bresenham划线算法

该算法是计算机图形学领域中使用最为广泛的直线扫描转换算法，该划线算法类似与中点划线算法，也是由误差项符号决定下一个像素右边点还是右上点。

基本原理：

过各行各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。

该算法的优点在于增量计算，使得对于每一列只要检查一个误差项的符号，就可以确定该列所求的像素。

根据直线的斜率来确定变量在x或y方向递增一个单位。

另一个方向y或x的增量为0或1，它取决于实际直线与最接近网格点位置的距离。

这一距离称为误差。

由以上原理，为方便计算，令e=d-0.5,e的初值为-0.5，增量为k。

当e>=0时，取当前像素（xi,yi）的右上方像素（xi+1,yi+1），e减小1，而当e<0时，更接近于右方像素（xi+1,yi）。

Bresenham算法的分析：

优点：

高效，巧妙地采用了e=d-0.5,e的初值为-0.5来简化运算，把e和0.5的比较转化成了e和0的比较，使得每次画点只需考虑误差项增量的符号即可。

实验环境

硬件平台：

PC机

软件：

Windows平台，eclipse

编程语言：

java

实验步骤

1.掌握三种划线算法的基本原理；

2.依据划线算法，在eclipse下编写源程序并进行调试；

3.对运行过程中的错误进行修改；

4.对运行结果进行分析与总结；

5.书写实验报告。

实验内容

在java中没有画点的函数，可以借用划线的函数来完成，java中的划线函数需要传线段的起点和终点两个点做参数来画线，我们可以传给它相同的两个点，就达到了画点的目的。

在本次实验中通过选取六条特殊的直线来检验三种划线算法，这六条直线分别取点为：

（x0,y0,x1,y1）

（100,300,500,300）;（400,90,400,500）;（100,100,500,400）;（100,400,500,100）;

（10,100,210,510）;（210,10,10,510）;

一、DDA算法的核心代码为：

publicvoiddrawLineDDA（intx0,inty0,intx1,inty1,Graphicsg）{

//变量的定义

floatdx,dy,k;

dx=x1-x0;

dy=y1-y0;

k=dy/dx;

if（k>=-1&&k<=1）{//|k|<=0

intx;

floaty;

y=y0;

for（x=x0;x<=x1;x++）{

g.drawLine（x,（int）（y+0.5）,x,（int）（y+0.5））;

y=y+k;

}

}else{//|k|>0

inty;

floatx;

x=x0;

for（y=y0;y<=y1;y++）{

g.drawLine（（int）（x+0.5）,y,（int）（x+0.5）,y）;

x=x+1/k;

}

}

System.out.println（"DDA算法k="+k）;

}

二、中点划线算法的核心代码：

publicvoiddrawLineMidPoint（intx0,inty0,intx1,inty1,Graphicsg）{

inta,b,d1,d2,d,x,y;

floatdx,dy,k;

dx=x1-x0;

dy=y1-y0;

k=dy/dx;

a=y0-y1;

b=x1-x0;

x=x0;

y=y0;

g.drawLine（x,y,x,y）;

if（k>=-1&&k<=1）{

if（k>=0）{

d=2*a+b;

d1=2*a;

d2=2*（a+b）;

while（x

if（d<0）{

x++;

y++;

d+=d2;

}else{

x++;

d+=d1;

}

g.drawLine（x,y,x,y）;

}

}else{

d=2*a-b;

d1=2*a;

d2=2*（a-b）;

while（x

if（d<0）{

x++;

d+=d1;

}else{

x++;

y--;

d+=d2;

}

g.drawLine（x,y,x,y）;

}

}

}else{

if（k>=0）{

d=a+2*b;

d1=2*b;

d2=2*（a+b）;

while（y

if（d<0）{

y++;

d+=d1;

}else{

x++;

y++;

d+=d2;

}

g.drawLine（x,y,x,y）;

}

}else{

d=-a+2*b;

d1=2*b;

d2=2*（-a+b）;

while（y

if（d<0）{

x--;

y++;

d+=d2;

}else{

y++;

d+=d1;

}

g.drawLine（x,y,x,y）;

}

}

}

System.out.println（"中点划线算法k="+k）;

}

三、Bresenham算法的核心代码：

publicvoiddrawLineBresenham（intx0,inty0,intx1,inty1,Graphicsg）{

intx,y;

floatk,e,dx,dy;

dx=x1-x0;

dy=y1-y0;

k=dy/dx;

e=-0.5f;

x=x0;

y=y0;

if（k>=-1&&k<=1）{

if（k>=0）{

for（inti=0;i<=dx;i++）{

g.drawLine（x,y,x,y）;

x++;

e=e+k;

if（e>=0）{

y++;

e=e-1;

}

}

}else{

for（inti=0;i<=dx;i++）{

g.drawLine（x,y,x,y）;

x++;

e=e-k;

if（e>=0）{

y--;

e=e-1;

}

}

}

}else{

if（k>=0）{

for（inti=0;i<=dy;i++）{

g.drawLine（x,y,x,y）;

y++;

e=e+1/k;

if（e>=0）{

x++;

e=e-1;

}

}

}else{

for（inti=0;i<=dy;i++）{

g.drawLine（x,y,x,y）;

y++;

e=e-1/k;

if（e>=0）{

x--;

e=e-1;

}

}

}

}

System.out.println（"Bresenham划线算法k="+k）;

}

实验结果

在java中原点位于左上点，水平向右为X轴正方向，垂直向下为Y轴正方向。

用三种算法划线的过程中采用了不同的颜色加以区分：

DDA算法（黄色），中点划线算法（绿色），Bresenham算法（蓝色）。

运行程序后，分别显示如下：

DDA算法：

斜率显示：

中点划线算法

斜率显示：

Bresenham算法

斜率显示：

实验总结

本次试验我收获很大，掌握了三种划线算法的基本原理，并成功编出了测试程序，我觉得试验是将书本知识与实践结合的最佳途径，编写程序的过程也不是很顺利，过程中存在很多BUG，通过调试得到了解决，但是还遗留一些问题没有解决，在我的代码中，要运行算法画直线，必须先将其他的两种算法的代码注释，才能显示，否则后一中算法的颜色就会覆盖前一种算法的颜色，因为我画的六条直线在三种算法中都是相同的斜率。

此次试验中存在的不足我会查阅相关资料并改正，争取得到更好的完善。

指导教师意见

签名：

年月日

注：

可根据教学需要对以上栏目进行增减。

表格内容可根据内容扩充。