文档介绍：信科0301班
一、实验目的:
通过<<计算机图形学>>的实验课程,使学生能熟练地掌握各种图形的生成原理,理解各种图形的基本算法,并能将算法用程序实现,最终运用c语言编写绘图程序,得到所需结果。
二、实验内容:
本实验报告综合了计算机图形学的多项知识,详细讲述了二维线画图元的生成(包括二维直线、圆、椭圆、抛物线的生成)、二维填充图元的生成(图形的填充、字符的输出)、二维裁剪、图形变换(平移、旋转、放缩三种变换)、投影(透视投影)和曲线生成(Hermite曲线和Bezier曲线的生成)的算法思想以及程序实现。并且,为了使画面更加美观,我们特地制作了一张菜单界面,通过从菜单项的选择就可方便地得到我们想要的图形。
三、算法思想:
1. 二维线画图元的生成
A. 生成直线段的DDA算法
基本原理
扫描转换直线段
所谓扫描转换直线段就是计算出落在直线段上或充分靠近它的一串像素,并以此像素集近似替代原连续直线段在屏幕上显示的过程。
生成直线段的DDA算法
求表示直线段的像素集的最简单方法是利用直线方程直接计算。设直线方程为y=m·x+B
DDA算法描述:
对给定端点的直线段以一个单位像素为分割区间
根据直线方程得到直线段上对应于横坐标的点的纵坐标,于是得到一系列点列
计算出的纵坐标可能是浮点数,并其四舍五入取整
描点画图
其中,用公式
我们就从直接得到,而不是由通过直线方程来计算,由此便消除了算法中的乘法。递推公式的初值为:。
扫描转换直线段的DDA算法的程序实现(见附录)
遇到的问题
此方法用到了浮点数的乘法、加法和取整运算。影响DDA算法效率的有两点,其一是采用了浮点加法,其二是浮点数在显示输出时需要取整。为了解决这个问题,我们引入了直线的中点算法。
改进的方法
采用生成直线段的中点算法
B. 生成直线段的中点算法
基本原理
假定直线段的斜率m∈[0,1],并且左下方的端点为,,右上方的端点为。直线段的方程为:y=mx+B……y-x-B=0
这里用到了直线的正负划分性,直线F(x,y)=0将整个二维空间分割成三个部分,直线上方的为正,下方的为负,直线上当然为零。现在假定已经求得像素,由四舍五入的取整原则可知
由假设的斜率范围可知,和的交点的纵坐标在直线上,区间内存在两个像素NE和E。如图
NE
M
E
根据整原则,当在中点上方时,取像素NE,否则取像素E,即
而“在M上方”等价于“F(M)〈=0”。
若取判别式,
则式变为,
以上两式即为中点判别式。
计算判别式的递推公式如下:
算法的初始条件为
直线段中点算法描述如下:
初始化中点判别式
确定取像素E和NE时判别式的增量
以x为自变量循环自增判断判别式的增量,即确定下一个是取E和NE中的哪个点
并将其描出
直线段中点算法的程序实现(见附录)
遇到的问题
以上算法只适合假定的条件
解决问题的方法:
(1)对于斜率在其他范围内直线段,我们有不同的判别式和初始条件,需要对算法作出一些改动,如下表格所示
斜率
0<=m<=1
m>1
-1<=m<0
m<-1
d(判别式)
dx-2*dy
dy-2*dx
-dx-2*dy
2*dx-dy
d>0(增量)
-2*dy
2*(dx-dy)
-2*(dx+dy)
-2*dx
d<0(增量)
2*(dx-dy)
2*dx
-2*dy
-2*(dx+dy)
(2)对于|m|>1时,我们是以y为自变量,x为因变量
此时的算法只要稍做修改即可。
(3)为了避开繁杂的讨论(直线共有8种情况),我们先假定x0<x1而得到四种情况的算法,至于x0<x1的情况,我们只需将两端点互换即可。
C. 生成圆和椭圆的中点算法
基本原理
首先,圆具有八对称性,所以,我们只要画出第一象限内x∈——的八分之一圆弧段,再对称的画出其他七个点,就可以得到整圆了。而对于椭圆,他没有八对称性,我们可以先画出他在第一像限内的四分之一椭圆弧,然后对称的画出其他三个像限内的椭圆弧。
其中生成圆弧和椭圆弧的中点算法和直线的中点算法类似,只是初始化条件和判别式的递推公式不同,并且在确定判别式的时候要消去浮点运算和尽量减少乘法的次数,对于椭圆,还要注意,在第一像限内斜率大于1的情况与直线|m|>1时相同,要以y为自变量,在此不再详细叙述。
对于圆:在所考虑的弧段,此段的斜率,由像素递推出后继的像素。根据条件得到
初始条件为
对于椭圆:考虑分界点的上部的弧段,此段的斜率,由像素递推出后继的像素。根据条件得到
初始条件为,对于分界点下方的弧段,可类似求得。
出现的问题,
如果求分界点的时候只是将其转化为整型,那么表示的椭圆轴长只能在