第三章++基本图形的扫描转换1.ppt

◆扫描转换的基本概念 ◆绘制像素点函数SetPixel的用法 ◆直线圆和椭圆的中点Bresenham原理 ◆直线反走样原理 3.1 直线的扫描转换 3.2 圆的扫描转换 3.3 椭圆的扫描转换 3.4 反走样算法 3.6 本章小结 3.7 习题 3.1.1 算法原理 3.1.2 构造中点偏差判别式 3.1.3 递推公式 直线的中点Bresenham算法的原理：每次在主位移方向上走一步，另一个方向上走不走步取决于中点偏差判别式的值。 理想直线将平面划分成三个区域： 对于直线上的点，F(x，y)＝0； 对于直线上方的点，F（x，y）＞0； 对于直线下方的点，F（x，y）＜0。 假设直线的斜率为0≤k≤1，则 ，所以确定x方向为主位移方向。 按照Bresenham原理，x方向上每次加1，y方向上加不加1取决于中点偏差判别式的值。 假定直线的当前点是 ，沿主位移x方向走一步，下一点只能在 和 两点中选取。 和 的中点为 ，如图3-2所示。显然，若中点M在理想直线的下方，则 点距离直线近，点亮 ；否则点亮 。 当d0时，中点M在直线的下方，Pu点离直线距离近，下一像素点应点亮Pu，即y方向上走一步； 当d0时，中点M在直线的上方，Pd点离直线距离近，下一像素点应点亮Pd，即y方向上不走步； 当d＝0时，中点M在直线上， Pu、Pd与直线的距离相等，点亮Pu或Pd均可，约定取Pd。 3.1.3 递推公式 3.2 圆的扫描转换 3.2.1 算法原理 事实上，考虑到圆在第一象限内的对称性，本算法可以进一步简化。 因为AC段圆弧和CB段圆弧以对称轴x＝y完全对称，如图3-6所示，所以可以用四条对称轴x＝0，y＝0， x＝y,x＝－y把圆分成8等份。 只要绘制出第一象限内的1/8圆弧Ⅰ，根据对称性就可绘制出整圆，这称为八分法画圆算法。假定第一象限内的任意点为P（x,y），可以顺时针确定另外7个点： P（y，x）P（y，－x）,P（x,－ y ） ,P（－x，－y），P（－y，－x），P（－y，x），P（－x，y）。 3.2.2 构造中点偏差判别式 3.2.3 递推公式 * 下一张 第三章 直线、圆和椭圆是图形设计的最基本图形（图元），从光栅扫描显示器的显示原理和真实感图形生成技术的需要出发，需要使用像素点函数来绘制这些基本图形。 光栅扫描显示器的绘图过程就是在像素点阵中确定最佳逼近于理想图形的像素点集的过程，这个过程称为“图形的扫描转换”，也称为“图形光栅化”。 3.1 直线的扫描转换 直线的扫描转换就是在屏幕像素点阵中用指定颜色点亮最佳逼近于理想直线的像素点集的过程。 3.1.1 算法原理 给定理想直线的起点坐标为P0（x0，y0）， 终点坐标为P1（x1，y1），则直线的隐函数 方程为： 其中，直线的斜率： 直线水平方向位移 ： 直线垂直方向位移 ： （3-1） F（x，y）0 F（x，y）=0 F（x，y）0 直线中点Bresenham算法原理 3.1.2 构造中点偏差判别式 从P（xi，yi）点走第一步后，为了进行下一像素点的选取，需将Pu和Pd的中点M（x i＋1，y i＋0.5）代入隐函数方程，构造中点偏差判别式d。 （3-2） （3-3） M（x i＋2，y i＋1.5） M（x i＋1，y i＋0.5） P（xi，yi） M（x i＋1，y i＋0.5） M（x i＋2，y i＋0.5） P（xi，yi） 中点偏差判别式的递推 d0 d≥0 1.中点偏差判别式的递推公式 在主位移x方向上已走一步的情况下，现在考虑沿主位移方向再走一步，应该选择哪个中点代入中点偏差判别式以决定下一步该点亮的像素，如图3-3所示，分两种情况讨论。 (1)当d0时 ⑵当d≥0时 （3-5） （3-4） 直线的起点坐标为P0（x0，y0），x为主位移方向。因此，第一个中点是（x 0＋1，y 0＋0.5），相应的d的初始值为： 其中，因为（x 0，y 0）在直线上，所以 则： （3-6） 2.中点偏差判别式的初始值 3.2.1 算法原理 3.2.2 构造中点偏差判别式 3.2.3 递推公式 本节主要讲解仅包含加减操作的顺时针绘制1/8圆的中点Bresenham算法原理。 圆的扫描转换 理想圆 F（x，y）0 F（x，y）=0 F（x，y）0 圆心