《第三章 基本图形的扫描转换》由会员分享，可在线阅读，更多相关《第三章 基本图形的扫描转换（60页珍藏版）》请在金锄头文库上搜索。
1、 第三章主讲：孔令德2扫描转换的基本概念扫描转换的基本概念绘制像素点函数绘制像素点函数SetPixel的用法的用法直线圆和椭圆的中点直线圆和椭圆的中点Bresenham原原 理理直线反走样原理直线反走样原理n3.1 直线的扫描转换n3.2 圆的扫描转换n3.3 椭圆的扫描转换n3.4 反走样算法n3.6 本章小结n3.7 习题3.1 3.1 直线的扫描转换直线的扫描转换n 3.1.1 算法原理n 3.1.2 构造中点偏差判别式n 3.1.3 递推公式n 直线的中点Bresenham算法的原理：每次 在主位移方向上走一步，另一个方向上走不 走步取决于中点偏差判别式的值。n 给定理想直线的起点坐标
2、为P0（x0，y0 ），终点坐标为P1（x1，y1），则直线的隐 函数方程为：3.1.1 3.1.1 算法原理算法原理其中，直线的斜率： 直线水平方向位移 ：直线垂直方向位移 ：（3-1）理想直线将平面划分成三个区域：对于直线上的点，F(x，y)0；对于直线上方的点，F（x，y）0；对于直线下方的点，F（x，y）0。 假设直线的斜率为0k1，则 ， 所以确定x方向为主位移方向。按照Bresenham原理，x方向上每次 加1，y方向上加不加1取决于中点偏差判 别式的值。假定直线的当前点是 ， 沿主位移x方向走一步，下一点只能 在 和 两点中选取。 和 的中点为 ，如图3-2所示。显然，若中点M在
3、 理想直线的下方，则 点距离直 线近，点亮 ；否则点亮 。F（x，y）0F（x，y）=0F（x，y）0时，中点M在直线的上方，Pd点离 直线距离近，下一像素点应点亮Pd， 即y方向上不走步；当d0时，中点M在直线上， Pu、Pd与 直线的距离相等，点亮Pu或Pd均可， 约定取Pd。（3-3）3.1.3 3.1.3 递推公式递推公式M（x i2，y i1.5）M（x i1，y i0.5）P（xi，yi）M（x i1，y i0.5）M（x i2，y i0.5）P（xi，yi）中点偏差判别式的递推d0F（x，y）=0F（x，y）0时，中点M在圆外，下一 像素点应点亮Pd，即y方向退一步；当d0时，中
4、 点M在圆上， Pu、Pd和圆的距离相等，点亮Pu或Pd 均可，约定取Pd。因此，（3-10）3.2.3 递推公式1.中点偏差判别式的递推公式现在如果考虑主位移方向再走 一步，应该选择哪个中点代入中点 偏差判别式以决定下一步应该点亮 的像素，分两种情况讨论。当d0F（x，y）=0F（x，y）0时，中点M在椭圆外， 下一像素点应点亮Pd，即y方向退一步；当d0时， 中点M在椭圆上，Pu、Pd和椭圆的距离相等，点亮Pu或 Pd均可，约定取Pd，如图3-13所示。（3-16）P（xi，yi）Pu（x i1，y i）M（x i+1，y i-0.5）Pd（x i1，yi1）图3-13 上半部分像素点的选
5、取因此，（3-17）3.3.3 3.3.3 上半部分上半部分的递推公式的递推公式P（xi，yi ) )M（x i1，y i0.5）M（x i2，y i0.5）P（xi，yi）M（x i1，y i0.5）M（x i2，y i1.5）d10时，中点M在椭圆外，下一像素点应点亮Pl，即x方向上不走步；当d20时，中点M在椭圆上，Pl、Pr和椭圆的距离相等，点亮Pl或Pr均可，约定取Pl，如图3-15所示。因此，（3-22）3.3.5 3.3.5 下半部分下半部分的递推公式的递推公式1.中点偏差判别式的递推公式现在如果考虑主位移方向上再走一步，应该 选择哪个中点代入中点偏差判别式以决定应该点 亮的像素
6、，如图3-16所示，分两种情况讨论。P（xi，yi）M（x i0.5，y i1）M（x i1.5，y i2）d20P（xi，yi）M（x i0.5，y i1）M（x i0.5，y i2）d20图3-16 下半部分中点偏差判别式的递推当d20时，下一步的中点坐标为：M（x i1.5 ，y i2）。所以下一步中点偏差判别式为：（3-23）当d20时，下一步的中点坐标为：M（x i0.5 ，y i2）。所以下一步中点偏差判别式为：（3-24） y向分量为： 则对于上半部分椭圆上一点任意P （xi，yi） 如果在其当前中点M（xi1，yi0.5）处 ，满足x向分量小于y 向分量：2.中点偏差判别式d2
7、的初值由图3-11知道，在上半部分，法矢 量的x向分量小于y向分量；在C点，法矢量 的x向分量等于y向分量；在下半部分，法 矢量的x向分量大于y向分量。由公式3-15知 道：x向分量为： （3-25） 假定图3-17中P（xi，yi）点是椭 圆上半部分的最后一个像素，M （xi1，yi0.5）是用于判断点亮 Pu和Pd像素的中点。由于下一像素转入了下半部分 ，所以其中点改为判断Pl和Pr的中点 M（xi0.5，yi1），所以下半部 分的初值d20为：（3-26）P（xi，yi）Pu（xi1，yi）Pl（xi，yi1）M（xi1，yi0.5）Pd（xi1，yi1）= Pr（xi1，yi1）图3-
8、17 下半部分的初值3.4 反走样算法 考虑将偏差e作为加权参数，同时用上下（或 左右）两个像素点的颜色来表示交点f的颜色。 像素a的颜色为c1RGB（e255，e255， e255），像素b的颜色为c2 RGB（1e） 255，（1e）255，（1e）255），两 个像素点颜色的各个相应分量级别之和等于255 。当偏差e越小时，c1的分量e255值越小 ，颜色越暗，同时c2的分量（1e）255值越 大，颜色越亮；反之亦然。用两个像素来表示理 想线条上的一个点，并依据两个像素与理想直线 的距离而调节其灰度级别，所绘制的线条可以达 到视觉上消除阶梯的效果。P6P4P2P3P1P5123距离理想直
9、线 0.8个像素远的 像素灰度为80距离理想直线 0.2个像素远 的像素灰度为 20距离理想直线0.45 个像素远的像素灰 度为45距离理想直线0.1 个像素远的像素 灰度为10距离理想直线 0.55个像素远的 像素灰度为55距离理想直线0.9 个像素远的像素 灰度为90AB3.6 3.6 本章小结本章小结本章主要讲解了直线、圆和椭圆的中点Bresenham算法原理以及直线的反走样技术。直线、圆和椭圆作为图形基本图元，其生成算法的优劣对整个图形系统的效率至关重要。在像素级生成算法中，中点Bresenham 算法避免了复杂运算，使用了最小的计算量，使单点基本图形生成算法已无优化的余地，已经成为使
10、用最广泛的扫描转换算法。走样是直线光栅化扫描转换的必然结果，只能减轻，不可避免，如何设计直线的反走样算法是计算机图形学的前沿研究课题。 3.7 3.7 习题习题1.计算起点坐标为（0,0），终点坐标（12,9 ）直线的中点Bresenham算法的每一步坐标值 以及中点偏差判别式d的值，填入表3-1中，并 用黑色点亮图3-29中的直线像素。图3-29像素点阵 表3-1 x,y和d的值xydxyd00-0.2575-0.511086-0.2521-0.7597032-0.5107-0.7543-0.25118-0.5540129-0.2564-0.752.给定直线的起点坐标为P0（x0，y0）、
11、终点坐标为P1（x1，y1），容易计算出直 线的斜率k。假设0k1且x0x1，则x 方向为主位移方向，绘制直线的递推公式 为：这称为数值微分法（Digital Differential Analyzer，DDA），请使 用MFC编程实现DDA算法并在屏幕上输出 直线的斜率。3.将中点Bresenham算法推广到绘制任意 斜率的直线，对边界像素的处理原则是 “起点闭区间、终点开区间”，即要求 所绘直线达到VC+的MoveTo()和 LineTo()函数的绘制效果。使用对话框 输入直线的起点和终点坐标，试以屏幕 中心为二维坐标系原点，绘制任意斜率 的直线。 4.使用对话框输入直线的起点和终点坐 标
12、，以屏幕中心为二维坐标系原点，绘 制任意斜率的反走样直线。5.以屏幕中心为二维坐标系原点，使用 距离加权反走样算法绘制反走样圆。6.以屏幕中心为二维坐标系原点，使用 距离加权反走样算法绘制反走样椭圆。7.*在屏幕上绘制4030的网格（模拟屏 幕纵横比为4:3），每个网格为边长为20个像 素的正方形。设定虚拟网格坐标系的原点为左 上角第一个网格中点，虚拟网格坐标系的x轴 水平向右，y轴垂直向下。根据输入对话框给 定的起点坐标和终点坐标，请使用0k1的 中点Bresenham算法，点亮每个代表像素的网 格正方形来实现直线的像素级绘制。屏幕网格 如图3-30所示，绘制结果如图3-31所示。图3-31 直线的像素级绘 制效果图图3-30 屏幕网格划分8.使用对话框输入直线的起点和终点坐标，以 屏幕中心为二维坐标系原点，给定直线的起点 颜色（如红色），终点颜色（如蓝色）。请使 用中点Bresenham算法绘制任意斜率的颜色渐 变直线，如图3-32所示。图3-32 颜色渐变直线效果图9.*使用GetCurrentTime()函数读取系统 时间，对时钟指针进行反走样处理，绘 制反走样时钟。图3-33的左侧为走样时 钟，右侧为反走样时钟。
