DDA算法

教材《计算机图形学教程》（第二版）王汝传主编，人民邮电出版社2009年8月出版第一章概述第二章计算机图形系统第三章C语言图形程序设计基础第四章二维图形生成和变换技术第五章三维图形生成和变换技术第六章真实感图形生成技术第七章几何造型简介第八章计算机动画技术第九章计算机动画实践第十章虚拟现实技术及VRML语言基础部分应用技术核心部分第四章二维图形生成和变换技术教学目的与要求：目的：使学生掌握基本二维图形的生成技术及二维图形的相关操作，并了解几种常用的反走样技术。要求：1、掌握直线的几种生成算法；2、掌握几种曲线的生成算法；3、理解区域填充的概念，并掌握几种填充方法；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节的前两种算法。教学目的：掌握逐点比较法和DDA算法的思想及推导教学要求：掌握算法的推导过程并能上机实现教学重点：两种算法的基本原理及推导；教学难点：理解光栅化的过程；程序设计时以计算机的思维考虑问题。授课方法：PPT+板书使用课时：2节第四章二维图形生成和变换技术4.1基本绘图元素基本图形元素：指的是点、直线、圆、多边形、字符等基本图形，是生成一副图像的基础。扫描转换：把图像中的点、线、面等图形基本指令组成的显示文件转换成显示缓冲区中图像的位映像图的过程。位映像图是屏幕每点一一对应的图像矩阵。光栅显示器可看作是一个像素的矩阵，要显示一种图形，其实是一种或多种颜色的像素集合，确定最佳逼近像素集合的过程叫图形的扫描转换。了解几个概念：一、点的生成点用一个像素表示，是显示器显示图形的最小单位，是最基本的图形元素。特点：只有位置，没有大小。注意区分这里点的定义和点状物体的概念。像素点的大小决定了显示器的分辨率。点的生成其实是将单个坐标位置转换成显示、输出设备的相应操作。4.1基本绘图元素二、直线几何中：定义为两点间的最短距离。直线是一维的：具有长度，没有维数；在CG中：直线实际是指直线段（主要受显示范围的限制）；生成时，水平和竖直方向上都能准确绘出，但斜线却不好表达，因此有不同算法。4.1基本绘图元素A(x1,y1)、B(x2,y2)、三、曲线包括：圆、椭圆及其他类型的曲线；曲线是图形学的基础，满足人们各种设计的需要，如汽车设计；4.1基本绘图元素四、区域填充一般指用颜色、图案等填充一个封闭区域的内部；主要涉及的难点是点在区域内部还是外部的判断上。4.2直线段的生成一、计算机生成直线的要求理论上直线没有宽度，其宽度就是一个像素的宽度。对直线进行光栅化（扫描转换）时，只能在显示器给定的有限像素组成的矩阵中，选出最佳逼近的一系列像素，并按顺序进行写操作，这个过程称为直线的扫描转换。由于光栅网格是由离散像素组成，除了斜率为0或1的直线，否则会不可避免地出现台阶现象。因此直线的生成有一定的要求：①画的线应是直的③线的浓度应均匀②保证端点位置准确④生成速度要快4.2直线段的生成二、逐点比较法1、原理：绘图仪中常用的方法，绘图过程中，画笔每画一步就与规定图形进行比较，以决定下一步的走向。2、算法推导：如左图：规定直线是OA，画笔当前位置是M，用OM与OA得斜率之差来计算偏差，以寻找规律。),(AAYXA),(MMYXMaOyxAMMAAMAAMMXXXYXYXYXYtantan4.2直线段的生成有如下推论：①当上式小于0时，说明当前M在OA的下方，为了精确地去画，下一步应该向+y的方向走；②当上式大于0时，说明当前M在OA的上方，下一步该向+x方向走；③当上式等于0，说明M就在规定的直线上。因为：分母0(第一象限)所以：只需判断分子的正负即可设：直线的起点为原点（0，0），终点为现构造判别式：AMXXMAAMXYXY),(AAYXAiAiAiXYYXF4.2直线段的生成设笔当前位置为M1(X1，Y1)，此时F1＝Y1XA－YAX1＜0，应走+Y一步到M2即X2＝X1，Y2=Y1＋1，＋1表示走一步M2处的偏差为：F2=Y2XA－YAX2=F1＋XA（用X2＝X1，Y2=Y1＋1代入得到）若F2≥0，应走＋X一步到M3，则X3=X2＋1，Y3=Y2，M3处的偏差为：F3=Y3XA－YAX3=Y2XA－YAX2－YA=F2－YA4.2直线段的生成终点判断循环设计：采用减法计数器原理，即当绘图仪的步距为1个像素时，取循环初始值为X、Y方向上增量之和，然后每走一步计数减去1，当计数器的循环因子值为0时，终止循环，程序完成。3、程序设计实现①算法流程：教材P88页图4.12；②程序实现：voidcb_line(intx1,inty1,intx2,inty2){intdx,dy,n,k,i,f;intx,y;这样依次进行下去，就得到第i步的递推公式：当Fi≥0时，向+X方向走一步，此时偏差Fi＋1＝Fi－YA（i=1，2，……n）。当Fi≤0时，向+Y方向走一步，此时偏差Fi＋1＝Fi＋XA（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?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;in;i++)if(f=0)switch(k){case1:putpixel(x++,y,1);f-=dy;break;case1:putpixel(x,y++,1);f-=dx;break;case1:putpixel(x--,y,1);f-=dy;break;case1:putpixel(x,y--,1);f-=dx;break;}4.2直线段的生成4.2直线段的生成elseswitch(k){case1:putpixel(x,y++,1);f-=dy;break;case1:putpixel(x--,y,1);f-=dy;break;case1:putpixel(x,y--,1);f-=dy;break;case1:putpixel(x++,y,1);f-=dy;break;}4.2直线段的生成三、数值微分法（DDA）1、原理：DigitalDifferentialAnalyzer,基于直线的微分方程来生成直线，典型的光栅显示器生成算法。2、算法推导：设（x1，y1）和（x2，y2）分别为所求直线的端点坐标，由直线的微分方程得直线的斜率4.2直线段的生成可通过计算由x方向的增量Δx引起y的改变来生成直线，由yi＋1=yi＋Δy（yi为直线上某步的初值）则xxxyyyyii12121可通过计算由y方向的增量引起x的改变来生成直线,若设Xi＋1＝Xi＋Δx则：yyyxxxxii12121三、数值微分法（DDA）4.2直线段的生成3、程序实现：dda_line(x1,y1,x2,y2)intx1,y1,x2,y2;{floatincrex,increy,x,y,length;inti;if(abs(x2-x1)abs(y2-y1))length=abs(x2-x1);elselength=abs(y2-y1);increx=(x2-x1)/length;increy=(y2-y1)/length;x=x1;y=y1;4.2直线段的生成for(i=1;i=length;i++){putpixel(int(x+0.5),int(y+0.5),1);x=x+increx;y=y+increy;}}