增量算法d=FM.PPT

第三章 基本图形的扫描转换 强调上课和上机纪律 迟到三次作为旷课一次进行处理，早退二次作为旷课一次进行处理 旷课达三次者，不计平时成绩（20%） 实验作业两次未交者，不计实验成绩（30%) 本章内容 3.1 直线的扫描转换 3.2 圆的扫描转换 3.3 椭圆的扫描转换 3.4 直线的反走样技术 本章小结 习题 前言 光栅图形显示器是一个像素矩阵，如分辨率为640X480，每个像素可以用一种或多种颜色显示，分别称为单色显示器或彩色显示器 在光栅显示器上显示的任何一种图形，实际上都是具有一种或多种颜色的像素的集合 图形的扫描转换 图形的扫描转换：确定一个像素集合及其颜色，用于显示一个图形的过程，称为图形的扫描转换或光栅化，也叫图形的生成 图形生成 图形生成是根据图形的几何信息和属性信息，结合图形生成算法，计算出要显示的中间像素，而不像图像生成是保存了图像的每一像素点的信息 基本图形的生成，首先要根据基本图形的特征找出它的几何信息，然后根据一定的生成算法实时地在显示器上显示出完整的图形 图形扫描转换步骤 一般分为两个步骤：先确定有关像素，再用图形的颜色或其它属性对象素进行某种写操作。后者通常是通过调用设备驱动程序来实现的。所以扫描转换的主要任务就是确定最佳逼近于图形的像素集的生成算法 在一个图形系统中，基本图形（也称为图元、图素等）的生成技术是最基本的，任何复杂的图形都是由基本图形组成的，基本图形生成的质量直接影响该图形系统绘图的质量。所以，需要设计出精确的基本图形生成算法，以确保图形系统绘图的精确性 3.1 直线的扫描转换 3.1.1 概 述 3.1.2 数值微分DDA直线生成算法 3.1.3 中点直线生成算法 3.1.4 Bresenham直线生成算法 3.1.1 概述 直线的扫描转换: 确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作 概述 生成直线一般的准则是： （1）线条应该显得笔直 由连续点组成的直线要显示在离散网格的平面上，一定会有不经过网格的点，如左下图。在这种情况下，必须选择靠近直线的网格点来逼近这条直线。若选择的好，线就显得较直；否则就会较弯曲，如右下图。 概述 （2）直线端点位置应该准确 画出的线段如果不准确，往往会使两条线之间不能很好的镶接，如下图。 （3）直线浓度应该均匀 线段的浓度与单位线段中所显示的点数成正比。要保持线段的浓度均匀端点应该等距分布。只有平行和成45°的线才能做到。 概述 （4）直线浓度应该与线段的长度和斜率无关 要取得均匀的线段浓度，应该保持每单位长度的点数是个常数。一般，采用线段的近似长度，以及生成直线的算法，使在线段近似长度范围内保持线段浓度均匀。 （5）显示线段的速度应快 生成直线可用软件和硬件来实现，一般情况下，硬件要比软件实现得快。 3.1.2 数值微分DDA直线生成算法 数值微分法，DDA（Digital Differential Analyzer）是根据数学上直线的微分方程来设计的 设A(x0,y0)，B(x1,y1)是直线的端点坐标，首先计算出直线的斜率 k=dy/dx=△y/△x=(y1-y0)/(x1-x0) 直线方程为：y=kx+B 或 x=1/k*y+T 作为最底层的光栅图形算法，在通常的CAD图形系统中，会被大量应用，因此，哪怕节约一个加法或减法，也是很了不起的改进。 由此出发点，导致增量算法的思想 根据k值做不同处理 当|k|≤1时，让x每步增加1，y最多增加1，然后用舍掉尾数的方法来确定直线上的像素位置为(x, round(y)) 设当前点为(xi, yi)，则下一个像素xi+1 = xi +1，则 yi+1 =k xi+1 +B =k(xi+1)+B=(k xi +B)+k= yi +k 即当x每递增1时，y递增斜率k 根据k值做不同处理 当|k|1时，应当让y每步递增1，这时x最多增加1，然后然后用舍掉尾数的方法来确定直线上的像素位置为(round(x), y) 设当前点为(xi, yi)，则下一个像素yi+1=yi+1，则 xi+1=1/k*yi+1+T=1/k*(yi+1)+T=(1/k*yi +T)+1/k = xi +1/k 即当y每递增1时，x递增斜率1/k 输出坐标求整 由于屏幕上的坐标为整数坐标，则真正作为输出显示为：y输出=ROUND(yn)，其中函数ROUND ()是指舍尾的整数 因此y输出和yn 之间的量化误差最大为1。为了改善这方面的误差，使x和y的值增加0.5,使量化误差在(-0.5,0.5)范围之间x=x0+0.5y=y0+0.5 ROUND(a)=(int)(a+0.5) DDA直线生成举例 例：画直线段P0(0,0)--P1(5,2) k=0.4