framebuffer画线和画圆.pptVIP

3.2 线的生成算法 3.2.1 直线的生成算法 3.2 线的生成算法 3.2.1 直线的生成算法 3.2 线的生成算法 3.2.1 直线的生成算法 数值微分(DDA)法 数值微分(DDA)法 Bresenham算法 思考：k的取值不在0~1之间时，如何处理？X，Y对换 当k1时，x总是增加1，再用Bresenham误差量判别式可以确定y是否增加1。 当k0时，要考虑x或y不是递增1，而是递减1。（不要） 3.2.2 圆的生成算法 3.2.2 圆的生成算法 中点画圆法 中点画圆法 中点画圆法 中点画圆法 * * 在数学上，直线是没有宽度的、由无数个点构成的集合。对直线进行光栅化就是在显示器所给定的有限个像素矩阵中，确定最佳逼近于该直线的一组像素。然后按照扫描线顺序，对这些像素进行写操作，这就是直线的扫描转换。 对于水平线、垂直线和45°线，选择哪些光栅元素是显而易见的，而对于其它方向的直线，像素的选择较为困难。 斜率截距直线方程： k表示斜率，b是y轴截距。 给定两个端点P0(x0,y0)和P1(x1,y1)，线段的斜率k和截距b为： 从起点到终点，x每次增加(或减少)1，用直线方程计算对应的y值，再用SetPixel(x, int(y+0.5),color)输出该像素。 复杂度：乘法+加法+取整 上述方法称为直线绘制基本算法，缺点：每步都需要一个浮点乘法运算和一个四舍五入运算，所以效率太低。由于一个图中可以包含成千上万条直线，所以要求绘制算法应尽可能的快。 给定两个端点P0(x0,y0)和P1(x1,y1)，线段的斜率k和截距b为： 画线过程从x的左端点x0开始，向x右端点步进，步长=1(个像素)，计算相应的y坐标：y=kx+b，取像素点(x, round(y))作为当前点的坐标。 计算 yi+1= kxi+1 + b = k(xi+ ?x) + b = kxi + b + k?x = yi + k?x 当?x =1时 yi+1 = yi + k 即：当x每递增1， y递增k(即直线斜率)。 图3-1 DDA算法基本原理 复杂度：加法+取整 上述采用的增量计算方法称为数值微分算法(Digital Differential Analyzer，简称DDA)。数值微分法的本质，是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。 图3-1 DDA算法基本原理 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++; ? ? x int(y+0.5) y+0.5 0 0 0+0.5 1 0 0.4+0.5 2 1 0.8+0.5 3 1 1.2+0.5 4 2 1.6+0.5 5 2 2.0+0.5 图3-2 直线段的DDA扫描转换 举例: 线段P0(0,0)和P1(5,2)的DDA方法扫描转换 DDA算法与基本算法相比，减少了浮点乘法，提高了效率。但是x与dx、y与dy用浮点数表示，每一步要进行四舍五入后取整，不利于硬件实现，因而效率仍有待提高。 Bresenham算法是1965年提出的，基本原理是：借助于一个误差量(直线与当前实际绘制像素点的距离)，来确定下一个像素点的位置。算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查误差量的符号，就可以确定该下一列的像素位置。 图3-3 根据误差量来确定理想的像素点 假设当前直线上的像素坐标为(xi, yi)，那么下一步需要在列xi+1上确定扫