第4章二维线画图元及属性1.ppt

第四章 二维线画图元及属性 概述 扫描转换 在数学上，直线是没有宽度的、由无数个点构成的集合。对直线进行光栅化就是在显示器所给定的有限个像素矩阵中，确定最佳逼近于该直线的一组像素(像素集)。 线画图元的扫描转换 计算出落在线段上或充分靠近它的一串像素，并以此像素集近似代替连续直线在屏幕上显示的过程。 二维基本图元 点、直线、多边形、园、弧、曲线及字符串等。 概述 光栅扫描显示系统的网格表示 概述 概述 概述 概述 4.1 直线的扫描转换及算法 直接计算法 直线的笛卡儿斜率截距方程：y=m*x+b 4.1 直线的扫描转换及算法 直接计算法 步骤 从起点到终点，每次 x增加(或减少)1，即|?x|=1； 用直线方程计算对应的?y值(?y=m* ?x)； 再用PutPixel(x, int(y+0.5),color)输出该像素。 int(y+0.5)对y起四舍五入的作用，例如：y=0.5时， int(y+0.5)=1; y=0.4时， int(y+0.5)=0 复杂度 乘法+加法+取整 缺点 每步都需要一个浮点乘法运算和一个四舍五入运算，所以效率太低。由于一个图中可以包含成千上万条直线，所以要求绘制算法应尽可能的快。 4.1 直线的扫描转换及算法 数值微分法 即DDA(Digital Differential Analyzer)算法，是根据直线的微分方程来计算Δx或Δy生成直线的扫描转换算法。 在一个坐标轴上以单位间隔对线段取样, 以决定另一个坐标轴方向上最靠近理想线段的整数值。 数值微分法的本质，是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。 4.1 直线的扫描转换及算法 数值微分法 给定两个端点P0(x0,y0)和P1(x1,y1)， 线段方程y=m*x+b 其中：斜率m=(y1-y0)/(x1-x0)； 截距b=y1-m*x1 斜率m0的直线（假设从左端点到右端点） ①如果m≤1，则取?x=1， ?y=m (4.5) ②如果m≥1，则取?y=1， ?x=1/m (4.6) 4.1 直线的扫描转换及算法 数值微分法 步骤：给定：两个端点P0(x0,y0)和P1(x1,y1)， 则：dx=(x1-x0)； dy=(y1-y0); 根据|dx|、|dy|，哪个大，哪个为步长参数： ①当|dx||dy|，即|m|1时， 若x0x1，即直线从左到右，则?x=1， ?y=m 若x0x1，即直线从右到左，则?x=-1， ?y=-m ②当|dx|≤|dy|，即|m|≥1时， 若x0x1，即直线从左到右，则?y=1， ?x=1/m 若x0x1，即直线从右到左，则?y=-1， ?x=-1/m 4.1 直线的扫描转换及算法 数值微分法 复杂度：加法+取整 优缺点：减少了浮点乘法，提高了效率。但是x与dx、y与dy用浮点数表示，每一步要进行四舍五入后取整，不利于硬件实现，因而效率仍有待提高。 4.1 直线的扫描转换及算法 Bresenham算法 1965年提出 基本原理是：借助于一个误差量(直线与当前实际绘制像素点的距离)，来确定下一个像素点的位置。算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查误差量的符号，就可以确定下一列的像素位置。 4.1 直线的扫描转换及算法 Bresenham算法 考虑以下情况： 第一象限 ?x0 ?y≥0 ?x ≥?y 即 m≤1 4.1 直线的扫描转换及算法 Bresenham算法 如图4.3所示，假设当前直线上的像素坐标为(xi, yi)，那么下一步需要在列xi+1上确定扫描线y的值。y值要么不变，要么递增1，可通过比较?i和?i+1来决定。 设M：直线与Xi+1线的交点；P1、P2：最接近线段的像素 K： P1、P2的中点 ?i：M到y=yi的距离 ?i+1：M到y=yi+1的距离 则：如果M在K下方，取P2 如果M在K上方，取P1 或者：若?i0.5，取P2 若?i≥0.5，取P1 4.1 直线的扫描转换及算法 Bresenham算法 令Wi=?i-0.5=m(xi+1)+b-yi-0.5 ①如果Wi0，则?i0.5，取P2(xi+1, yi) Wi+1 =[m(xi+1+1)+b-yi+1]-0.5 =[m(xi+1+1)+b-yi]-0.5