直线的绘制(光栅化).ppt

第3章 基本光栅图形生成技术 3.1 本章的主要内容 本章介绍基本二维图形的绘制，包括直线、圆弧、椭圆弧的生成，多边形的填充以及更一般区域的填充。 显示器是由离散像素组成的矩阵，在绘制具有连续性质的直线、曲线或区域等基本图形时，需要确定最佳逼近它们的像素，这个过程称为光栅化。当光栅化按照扫描线的顺序进行时，它被称为扫描转换。 光栅化和扫描转换是光栅图形学的基本问题，其算法的好坏对系统的效率有直接的关系。 3.2 线的生成算法 3.2.1 直线的生成算法 问题所在： 在数学上，直线是连续的，由无数个点构成的集合。x,y坐标均为实数。 但在显示器上，只能用有限的像素表示，像素的坐标是整数值。 因此，绘制时，需要将直线段离散化为有限的像素，这些像素应该尽可能地连续、尽量避免出现锯齿，并最佳逼近于给定的直线段。此外，绘制直线是非常基本的绘图操作，一个图中往往包括成千上万条直线，所以，算法应该尽可能地快。 对于水平线、垂直线和45°线，选择哪些光栅元素是显而易见的，而对于其它方向的直线，像素的选择较为困难。 缺点：每步都需要一个浮点乘法运算和一个四舍五入运算，所以效率太低。由于一个图中可以包含成千上万条直线，所以要求绘制算法应尽可能的快。 给定直线段的两个端点P0(x0,y0)和 P1(x1,y1)，斜率截距直线方程： 从起点到终点，x每次增加(或减少)1，用直线方程计算对应的y值，再用SetPixel(x, int(y+0.5),color)输出该像素。上述方法称为直线绘制基本算法。复杂度：乘法+加法+取整 直线绘制基本算法 数值微分(DDA)法 画线过程从x的左端点x0开始，向x右端点步进，x+=?x，计算相应的y坐标：y=kx+b，取像素点(round(x), round(y))作为当前点的坐标。 图3-1 DDA算法基本原理 给定直线段的两个端点P0(x0,y0)和 P1(x1,y1)，直线方程： 设第i个点(xi,yi), yi= kxi+b 第i+1个点(xi+1,yi+1), 令xi+1= xi+ ?x, 则yi+1=k(xi+ ?x)+b=yi+k?x = yi+?y, ?y= k?x 当?x =1时 yi+1 = yi+k 复杂度：加法+取整 上述采用的增量计算方法称为数值微分算法(Digital Differential Analyzer，简称DDA)。数值微分法的本质，是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。 注意: ?x, ?y的选择. void DDALine(int x0,int y0,int x1,int y1,int color) ? int i； float dx, dy, length,x,y; if (fabs(x1-x0)=fabs(y1-y0)) length=fabs(x1-x0); else length=fabs(y1-y0); dx = (x1-x0)/length; dy=(y1-y0)/length; i=1;x= x0;y= y0; while(i=length) { SetPixel (int(x+0.5), int(y+0.5), color); x=x+dx; y=y+dy; i++; ? ? DDA算法与基本算法相比，减少了浮点乘法，提高了效率。但是x与dx、y与dy用浮点数表示，每一步要进行四舍五入后取整，不利于硬件实现，因而效率仍有待提高。 Bresenham算法 Bresenham算法1965年提出，基本原理是：借助于一个误差量(直线与当前实际绘制像素点的距离)，来确定下一个像素点的位置。算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查误差量的符号，就可以确定该下一列的像素位置。 Yi +1 y yi xi xi+1 d2 d1 图3-3 根据误差量来确定理想的像素点 假设当前直线上的像素坐标为(xi, yi)，那么下一步需要在列xi+1上确定扫描线y的值。y值要么不变，要么递增1，可通过比较d1和d2来决定。 如图3-3所示，对于直线斜率k在0~1之间的情况，从给定线段的左端点P0(x0, y0)开始，逐步处理每个后续列(x位置)，并在扫描线y值最接近线段的像素上绘出一点。 判别式（误差参数）： 设Δy=y1－y0, Δx=x1－x0，则k=