第3章 输出图元,输出图元是基本几何结构。 输出图元种类：点、直线线段、圆、 圆锥曲线、二次曲面、样条线段、多 边形填色区域、字符串等。,本章内容,点和线 直线段扫描转换 DDA算法 Bresenham画线算法 中点画线法 圆弧扫描转换 Bresenham画圆算法 中点画圆算法 椭圆弧扫描转换 填充区域图元,点和线,点和线是计算机图形表示的最简单的基本图元 点：将应用程序的单个坐标位置转换成输出设备的相应操作，即为画点操作。 直线扫描转换 当我们对直线进行光栅化时，只能在显示器所给定的有限个象素组成的矩阵中，确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作，这就是通常所说的用显示器绘制直线或直线扫描转换。,图形的扫描转换：在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。,一般采用整数值表示屏幕位置，因此，绘制的位置只能接近两指定端点的实际线段位置。 如（3，3.6），转换为象素点的位置是 即（int（3 +0.5 ），int（3.6+0.5） =（3，4）,直线的扫描转换算法,直线的绘制要求： 直线要直 直线上的点要准确，即无不定向性和断裂情况 直线的亮度、色泽要均匀 画线的速度要快 要求不同直线可具有不同的色泽、亮度、线型等,提出问题： 对于给定直线两端点P0(x0,y0)和P1(x1,y1)，如何在屏幕上画出该直线。 三个常用算法： 数值微分法（DDA） Bresenham算法 中点画线法,直线基础,直线的笛卡儿斜率截距方程为： m-直线的斜率 b - 直线于y轴的截距 给定线段的两个端点（x0,y0), (x1,y1)，可以计算斜率m和截距b：,在x方向上，给定任意增量 x，那么对应的y的增量为 y, 即y = mx 图形学直线的算法是以上面的直线方程、斜率方程、截距方程和增量方程为基础,数值微分法（DDA-digital differential analyzer）,DDA算法是一种线段扫描转换算法，它是在一个坐标轴上以单位间隔对线条取样，从而确定另一个轴上最靠近线段路径的对应整数值。 首先考虑斜率值m在（0，1）之间的直线。,假定直线的起点、终点分别为：（x0,y0), (x1,y1)，且都为整数。 x 、 y轴的单位间隔为1,栅格交点表示 象素点位置,如果采用一般计算方法 那么直线斜率为 这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。,DDA方法思想,由 即：当x每递增1，y递增m(即直线斜率)； 注意上述分析的算法仅适用于|m|1的情形。在这种情况下，x每增加1, y最多增加1。 当 |m|1时，必须把x，y地位互换, y每增加1，x相应增加1/m 。,增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。 DDA算法就是一个增量算法。,|m|1情形时的算法,例：画直线段P0(0,0)-P1(5,2) 则k=0.4,当 x1时， y i+1yi+m,算法缺点：在此算法中，y、m必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。,Bresenham画线算法,Bresenham算法是Bresenham提出的一种精确且有效的光栅生成算法。 它用于显示线、圆和其它曲线的整数运算 它是目前最有效的线段生成算法,考虑斜率0m1时的扫描转换情况,如图： 设斜线在（xk,yk）已经确定了一个点，下一步是xk+1处的点，如何确定？,设点Q为斜线段与xk+1直线的交点，d1、d2分别为点Q距上下平行线yk, yk+1距离 设斜线y=mx+b，点Q的x轴坐标为xk+1，则点Q的y轴坐标为： y=m（xk +1 ）+ b 则可求出d1、d2的长度,d1 =m(xk+1)+b - yk d2 = (yk+1 ) m(xk+1)+b 则： d1、d2的差值为 d1 -d2 = 2 m(xk+1) - 2 yk + 2b - 1,pk =x（d1 -d2 ） pk 0 时, 取上点 pk 0 时, 取下点 pk =0 时, 始终取上(或下)点,