DDA算法.ppt

1、教材,计算机图形学教程（第二版） 王汝传主编，人民邮电出版社2009年8月出版,第一章 概述 第二章 计算机图形系统 第三章 C语言图形程序设计基础 第四章 二维图形生成和变换技术 第五章 三维图形生成和变换技术 第六章 真实感图形生成技术 第七章 几何造型简介 第八章 计算机动画技术 第九章 计算机动画实践 第十章 虚拟现实技术及VRML语言,基础部分,应用技术,核心部分,第四章 二维图形生成和变换技术,教学目的与要求： 目的：使学生掌握基本二维图形的生成技术及二维图形的相关操作，并了解几种常用的反走样技术。 要求：1、掌握直线的几种生成算法； 2、掌握几种曲线的生成算法； 3、理解区域填充

2、的概念，并掌握几种填充方法； 4、理解二维图形变换的基本原理，掌握二维图形 齐次坐标变换； 5、理解二维图形裁剪的原理和方法； 6、了解几种常用的反走样技术；,教学重点：1、基本二维图形的生成算法； 2、区域填充的方法； 3、二维几何变换及其齐次坐标表示 4、二维图形裁剪 教学难点：1、直线生成算法及其比较 2、二维图形变换的齐次坐标表示 授课方法：课堂讲授+上机实习,第四章 二维图形生成和变换技术,4.1基本绘图元素 4.2直线段的生成 4.3曲线的生成 4.4区域填充 4.5二维图形变换 4.6二维图形裁剪 4.7反走样技术,第四章 二维图形生成和变换技术,本节内容：4.1节及4.2节的前

3、两种算法。 教学目的：掌握逐点比较法和DDA算法的思想及推导 教学要求：掌握算法的推导过程并能上机实现 教学重点：两种算法的基本原理及推导； 教学难点：理解光栅化的过程； 程序设计时以计算机的思维考虑问题。 授课方法：PPT+板书 使用课时：2节,第四章 二维图形生成和变换技术,4.1 基本绘图元素,基本图形元素：指的是点、直线、圆、多边形、字符等基本图形，是生成一副图像的基础。 扫描转换：把图像中的点、线、面等图形基本指令组成的显示文件转换成显示缓冲区中图像的位映像图的过程。位映像图是屏幕每点一一对应的图像矩阵。 光栅显示器可看作是一个像素的矩阵，要显示一种图形，其实是一种或多种颜色的像素集

4、合，确定最佳逼近像素集合的过程叫图形的扫描转换。,了解几个概念：,一、点的生成,点用一个像素表示，是显示器显示图形的最小单位，是最基本的图形元素。 特点：只有位置，没有大小。注意区分这里点的定义和点状物体的概念。 像素点的大小决定了显示器的分辨率。 点的生成其实是将单个坐标位置转换成显示、输出设备的相应操作。,4.1 基本绘图元素,二、直线,几何中：定义为两点间的最短距离。 直线是一维的：具有长度，没有维数； 在CG中：直线实际是指直线段（主要受显示范围的限制）； 生成时，水平和竖直方向上都能准确绘出，但斜线却不好表达，因此有不同算法。,4.1 基本绘图元素,三、曲线,包括：圆、椭圆及其他类型

5、的曲线； 曲线是图形学的基础，满足人们各种设计的需要，如汽车设计；,4.1 基本绘图元素,四、区域填充,一般指用颜色、图案等填充一个封闭区域的内部； 主要涉及的难点是点在区域内部还是外部的判断上。,4.2 直线段的生成,一、计算机生成直线的要求,理论上直线没有宽度，其宽度就是一个像素的宽度。对直线进行光栅化（扫描转换）时，只能在显示器给定的有限像素组成的矩阵中，选出最佳逼近的一系列像素，并按顺序进行写操作，这个过程称为直线的扫描转换。,由于光栅网格是由离散像素组成，除了斜率为0或1的直线，否则会不可避免地出现台阶现象。因此直线的生成有一定的要求：,画的线应是直的 线的浓度应均匀,保证端点位置准

6、确 生成速度要快,4.2 直线段的生成,二、逐点比较法,1、原理：绘图仪中常用的方法，绘图过程中，画笔每画一步就与规定图形进行比较，以决定下一步的走向。 2、算法推导：,如左图：规定直线是OA，画笔当前位置是M，用OM与OA得斜率之差来计算偏差，以寻找规律。,4.2 直线段的生成,有如下推论： 当上式小于0时，说明当前M在OA的下方，为了精确地去画，下一步应该向+y的方向走； 当上式大于0时，说明当前M在OA的上方，下一步该向+x方向走； 当上式等于0，说明M就在规定的直线上。 因为：分母 0(第一象限) 所以：只需判断分子 的正负即可 设：直线的起点为原点（0，0），终点为 现构造判别式：,

7、4.2 直线段的生成,设笔当前位置为 M1(X1，Y1)，此时 F1Y1XA YAX10，应走+Y一步到M2 即X2X1，Y2=Y11，1表示走一步 M2处的偏差为：F2=Y2XAYAX2=F1XA（用X2X1，Y2=Y11代入得到）,若F20，应走X一步到M3， 则X3=X21，Y3=Y2， M3处的偏差为： F3=Y3XAYAX3=Y2XAYAX2YA=F2YA,4.2 直线段的生成,终点判断循环设计： 采用减法计数器原理，即当绘图仪的步距为1个像素时，取循环初始值为X、Y方向上增量之和，然后每走一步计数减去1，当计数器的循环因子值为0时，终止循环，程序完成。 3、程序设计实现 算法流程：

8、教材P88页图4.12； 程序实现： void cb_line(int x1,int y1,int x2,int y2) int dx,dy,n,k,i,f; int x,y;,这样依次进行下去，就得到第i步的递推公式 ： 当Fi0时，向+X方向走一步，此时偏差Fi1FiYA （i=1，2，n）。 当Fi0时，向+Y方向走一步，此时偏差Fi1FiXA （i=1，2，n）。 偏差Fi的推算，只用到终点坐标值XA ，YA而与中间点的坐标值无关，且只需进行加减运算。,4.2 直线段的生成,dx=abs(x2-x1); dy=abs(y2-y1); n=dx+dy; if(x2=x1) k=y2=y1

9、?1:4;x=x1;y=y1; /判断所在的象限 else k=y2=y1?2:3;x=x1;y=y1; putpixel(x,y,1); /在屏幕上画点 for(i=0,f=0;i=0) switch(k) case 1:putpixel(x+,y,1);f-=dy; break; case 1:putpixel(x,y+,1);f-=dx; break; case 1:putpixel(x-,y,1);f-=dy; break; case 1:putpixel(x,y-,1);f-=dx; break; ,4.2 直线段的生成,4.2 直线段的生成,else switch(k) case

10、1:putpixel(x,y+,1);f-=dy;break; case 1:putpixel(x-,y,1);f-=dy;break; case 1:putpixel(x,y-,1);f-=dy;break; case 1:putpixel(x+,y,1);f-=dy;break; ,4.2 直线段的生成,三、数值微分法（DDA）,1、原理：Digital Differential Analyzer,基于直线的微分方程来生成直线，典型的光栅显示器生成算法。 2、算法推导：,设（x1，y1）和（x2，y2）分别为所求直线的端点坐标，由直线的微分方程得,直线的斜率,4.2 直线段的生成,可通过计算由x方向的增量x引起y的改变来生成直线，由yi1=yiy（yi为直线上某步的初值）则,可通过计算由y方向的增量引起x的改变来生成直线,若设Xi1Xix 则：,三、数值微分法（DDA）,4.2 直线段的生成,3、程序实现： dda_line(x1,y1,x2,y2) int x1,y1,x2,y2; float increx,increy,x,y,length; int i; if(abs(x2-x1)abs(y2-y1) length=abs(x2-x1); else