计算机图形学第三章

第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=m∆x图形学直线的算法是以上面的直线方程、斜率方程、截距方程和增量方程为基础数值微分法（DDA-digitaldifferentialanalyzer）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当∆x＝1时，yi+1＝yi+m算法缺点：在此算法中，y、m必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。Bresenham画线算法Bresenham算法是Bresenham提出的一种精确且有效的光栅生成算法。它用于显示线、圆和其它曲线的整数运算它是目前最有效的线段生成算法考虑斜率0<m<1时的扫描转换情况,如图：设斜线在（xk,yk）已经确定了一个点，下一步是xk+1处的点，如何确定？设点Q为斜线段与xk+1直线的交点，d1、d2分别为点Q距上下平行线yk,yk+1距离设斜线y=m•x+b，点Q的x轴坐标为xk+1，则点Q的y轴坐标为：

y=m（xk+1）+b

则可求出d1、d2的长度d1=m(xk+1)+b-ykd2=(yk+1)–[m(xk+1)+b]则：d1、d2的差值为d1-d2=2m(xk+1)-2yk+2b