第2章 基本光栅图形生成技术 显示器是由离散像素组成的矩阵，在绘制具有连续性质的直线、曲线或区域等基本图形时，需要确定最佳逼近它们的像素，这个过程称为光栅化。 虽然几乎所有的程序设计语言都提供了线、圆弧、填充等的绘制函数，但只有学习了基本图形的生成原理和算法，才能超越具体程序设计语言的限制，满足用户的特殊绘图要求。 假定，编程语言提供了一个显示像素函数： SetPixel(x,y,color); 其中，x和y为像素的位置坐标，color为像素的颜色。 1 2.1 光栅图形中点的表示 (x,y)坐标 地址线性表地址线性表 显示屏幕显示屏幕 1D表示 2D表示 像素由其左下角坐标表示像素由其左下角坐标表示 2 2.2直线的扫描转换 一、数学直线 二、光栅平面显示的直线 三、直线的扫描转换 在数学上，理想的 在光栅显示平面上，直线的扫描转换，直线是一条没有宽度的只能用二维光栅格网上尽就是要找出显示平面上、由无数个无限小的连可能靠近这条直线的象素最佳逼近理想直线的那续的点构成的集合。 点的集合来表示它。每个些象素的坐标值，并将象素的坐标x和y只能是整这些象素置成所要求的颜色。 数，也就是说相邻象素的坐标值是阶跃的而不是连续的。 直线的扫描转换 数学直线光栅直线 3 2.3 线的生成算法 由于一幅图中可能包含成千上万条直线，所以要求绘制算法应该： 1、最接近数学上的直线； 2、画线速度尽可能的快； 3 、沿着线段分布的象素应均匀。 不均匀的例子如右图，对同样长的线段进行图中的扫描转换，会因为斜率不同，产生的象素个数不相等，这样将导致象素亮度分布不均匀。 4 ? 直线的生成算法 斜率截距直线方程： y?kx?bk表示斜率，b是y轴截距。 给定两个端点P0(x0,y0)和P1(x1,y1)，线段的斜率k和截距b为： k ? ?y/?x? (y1? y0)/(x1? x0)b ? y0? k?x0从起点到终点，x每次增加(或减少)1，用直线方程计算对应的y值，再用SetPixel(x, int(y),color)输出该像素。 ? 复杂度： 乘法+加法+取整 缺点：每步都需要一个浮点乘法运算和一个取整运算，所以效率太低。 5 ? 数值微分(DDA)法 数值微分法即DDA法(Digital Differential Analyzer) ，是一种基于直线的微分方程来生成直线的方法。 6 一、直线DDA算法描述： 设(x1，y1)和(x2，y2)分别为所求直线的起点和终点坐标，由直线的微分方程得直线的斜率k： = k =直线的斜率 (21) 1. 可通过计算由x方向的增量x引起y的改变来生成直线： xi+1=xi+x yi+1=yi+y=yi+xk (22) (23) 2. 也可通过计算由y方向的增量y引起x的改变来生成直线： yi+1=yi+y (24) xi+1=xi+x=xi+y/k (25) 7 式(22)至(25)是递推的。 二、直线DDA算法思想： 选定|x2x1|和|y2y1|中较大者作为步进方向(假设|x2x1|较大)，取该方向上的增量为一个象素单位(x=1)，然后利用式(21)计算另一个方向的增量 y=xk=k)。通过递推公式究竟用方法1, 还是方法( 2来生成直线？ (22)至(25)，把每次计算出的(xi+1，yi+1)经取整后送到显示为什么？ 器输出，则得到扫描转换后的直线。 算法实现中还应注意直线的生成方向，以决定x及y是取正值还是负值。 8 二、直线DDA算法思想（续） 之所以取x2x1和y2y1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在下图中可看出。 9 举例: 线段P0(0,0)和P1(5,2)的DDA方法扫描转换。 x int(y+0.4) y+0.4 0 0 0+0.4 1 0 0.4+0.4 2 1 0.8+0.4 3 1 1.2+0.4 0 1 2 3 4 5 Line: P 0 (0, 0)- P 1 (5, 2) 3 2 1 4 2 1.6+0.4 5 2 2.0+0.4 10 三、 直线DDA算法的思考 ？复杂度：？复杂度：加加 法法+取整取整 给定两个端点P0(x0,y0)和P1(x1,y1)，线段的斜率k和截距b为： k ? (y1? y0)/(x1? x0)b? y0? k?x0画线过程从x的左端点x0开始，向x右端点步进，步长=1(像素)，计算相应的y坐标：y=kx+b，取像素点(x, int(y)作为当前点的坐标。 计算 yi+1= kxi+1+b=k(xi+ ?x)+b= kxi+b+k?x = yi+k?x 当?x =1时 yi+1 = yi+k （i+1,int(i+1+0.5)xy即：当x每递增1，y递增k(即直线斜率)。 （i,i)x y（i+1,i+1)xy（i,int(i+0.5)xy11 四、 直线DDA算法的实现 1 、已知直线的两端点坐标：(x1，y1)，(x2，y2) 2、已知画线的颜色：color 3、计算两个方向的变化量： x =x2x1 y =y2y1 4、求出两个方向最大变化量的绝对值： steps=max(| x |，| y |) 5、计算两个方向的增量(考虑了生成方向)： dx = x / steps dy = y / steps 6、设置初始象素坐标：x=x1,y=y1 7、用循环实现直线的绘制： for(i=1；i=Math.abs(y1-y0) length=Math.abs(x1-x0); else length=Math.abs(y1-y0); dx = (float)Math.abs(x1-x0)/length; dy = (float) Math.abs(y1-y0)/length; float x= x0; float y= y0; int i=1; while(i=length) SetPixel (x, y, color); x=x+dx; y=int (y+dy ); i+; ? 13 六、直线DDA算法特点： DDA算法简单，实现容易； DDA算法与基本算法相比，减少了浮点乘法，提高了效率。 但是由于在循环中涉及实型数的运算（x与dx、y与dy用浮点数表示），每一步要进行取整，因此生成直线的速度较慢，不利于硬件实现，因而效率仍有待提高。 14 实验报告二 算法 ?算法描述 ?算法的复杂度描述 ?算法实例1： （100，200）和（500，400）的源代码 ?算法实例2： （100，400）和（500，200）的源代码 15 ? Bresenham算法 Bresenham 算法1965 年提出，在生成直线的算法中，Bresenham 算法是最有效的算法。Bresenham 算法是一种基于误差判别式来生成直线的方法。 16 ?一、基本思想 比较从理想直线到位于直线上方的像素的距离 d1和相邻的位于直线下方的像素的距离 d2，根据距离误差项的符号确定与理想直线最近的象素。 yyk+1yyk0P2P P1xkxk+1d2d1x17 一、基本思想（续） 如图3-3所示，对于直线斜率k在01之间的情况，从给定线段的左端点P0(x0, y0)开始，逐步处理每个后续列(x位置)，并在扫描线y值最接近线段的像素上绘出一点。 yi+1 y yi 假设当前直线上的像素坐标为(xi, yi)，那么下一步需要在列xi+1上确定扫描线y的值。 P2 d2 P d 1y值要么不变，要么递增值要么不变，要么递增1，可通过比较，可通过比较d1和和d2来来决定。决定。 xi Xi+1 P1 图3-3 根据误差量来确定理想的像素点 18 二、直线Bresenham 算法描述： Bresenham算法也是采用递推步进的办法，令每次最大变化方向的坐标步进一个象素，同时另一个方向的坐标依据误差判别式的符号来决定是否也要步进一个象素。 我们首先讨论k=y/x，当0k1且x1x2且y1y2时的Bresenham 算法。从DDA直线算法可知这些条件成立时，公式(2-2)、(2-3)可写成： xi+1=xi+x (22) xi+1=xi+1 yi+1=yi+k (26) (27) yi+1=yi+y=yi+xk (23) 19 根据误差项根据误差项d决定决定y是否增是否增1 yi+1 y P2 d2 d1? y? yi? (k（xi?1)? b)? yid1? d2? 2k(xi?1 ） ? 2yi? 2b?1d2? (yi?1)? y? yi?1? (k（xi?1)? b)y ixi P d 1Xi+1 P1 设 y=y1y0, x=x1x0，则k= y/ x，代入上式，得； ?x(d1? d2) ? 2?y?xi? 2?x?yi? 2?y? ?x(2b?1)c ? 2?y? ?x(2b?1)令di? ?x(d1? d2)则di的计算仅包括整数运算，其符号与(d1-d2)的符号相同。 ?当di0时，像素(xi1，yi1)与直线上理想位置更接近； ?当di=0时，两个像素与直线上理想位置一样接近，可约定取(xi1，yi1)。 20 是常量，与像素位置无关 思考问题 ?决策变量di与0之间的大小关系 ?如何确定下一个像素点的决策变量di+1 ?是否可以找出di与di+1的关系式 ?如何确定第一个决策变量di 21 di? ?x(d1? d2) ? 2?y?xi? 2?x?yi? c对于i+1步，误差参数为： di?1? 2?y?xi?1? 2?x?yi?1? cdi?1? di? 2?y?(xi?1? xi)? 2?x?(yi?1? yi)此时参数C已经消去，且xi+1=xi+1,得： di?1? di? 2?y? 2?x?(yi?1? yi)如果选择右上方像素，即：y ，则： i?1? yi? 1如果选择右方像素，即： yi?1? yi，则： di?1? di? 2?y? 2?xdi?1? di? 2?y对于每个整数x，从线段的坐标端点开始，循环的进行误差量的计算。假设直线的初始端点恰好是其象素点的坐标，即满足：y0=kx0+b, 在起始像素(x0，y0)的第一个参数d0为： d0? 2?y? ?x22 决策变量di的作用 ?决定当前像素点的纵坐标（横坐标）是加1还是不变 ?决定下一个像素点的决策变量di+1的表达式 di?1? di? 2?y? 2?xOR di?1? di? 2?y23 举例: 线段P0(0,0)和P1(5,2)的Bresenham 方法扫描转换。 x d 0 1 2 y-x1 2 d+2 y3 3 d+2(y-x)3 4 d+2 y1 5 d+2(y-x)5 y 0 0 0 1 1 Line: P (0, 0)- P 1 (5, 2) 3 2 1 0 1 2 3 4 5 2 2 24 三、 Bresenham 画线算法的实现 条件：0k1且x1x2 1、输入线段的两个端点坐标和画线颜色： x1，y1， x2，y2，color； 2、设置象素坐标初值：x=x1，y=y1； 3、设置初始误差判别值：d=2y-x； 4、分别计算：x=x2-x1、y=y2-y1； 5、循环实现直线的生成： for(x=x1；x=0) y=y+1 ； d=d+2(y -x)； else d=d+2y ； 25 四、直线Bresenham算法特点： 由于程序中不含实型数运算，因此速度快、效率高，是一种有效的画线算法。 ？复杂度：？复杂度：乘乘 法法+加法加法 26 实验报告三 Bresenham算法 ?Bresenham 算法描述 ?Bresenham 算法的复杂度描述 ?Bresenham 算法实例1： （0，0）和（400，50）的源代码 ?Bresenham 算法实例2： （0，200）和（500，0）的源代码 27 实验报告四（选做） ?在生成直线的算法中，我们先后学习了普通直线生成算法、数值微分法（DDA）算法和 Bresenham 算法。写写学习心得和学习所得。 ?注：如果你在课堂或课后学习了以上提到的三种算法（尤其是后两种算法），无论学习效果如何或是自己对三种算法理解程度是深是浅，希望选做实验报告四，为本门课程做一个相对圆满的总结。 28