3.1 直线的扫描转换

3.1.1 直线扫描转换原理

直线的扫描转换是指在图形输出设备上，按照扫描线的顺序，确定一组最佳逼近于直线的像素点并对像素点进行写操作。如图3.1-1所示为用一组像素点来代表直线。

因此，直线生成要解决的具体问题是：已知直线的两个端点P0（x0，y0）和P1（x1，y1），则要求在图形输出设备上，从起点到终点通过逐次循环迭代，找到最接近直线的像素点。所以需要建立循环迭代的增量方程：xi+1＝xi+Δx，yi+1＝yi+Δy。

直线的扫描转换算法的目的就是建立合适的增量方程算法。由于图形可能包含很多条直线，所以，要求直线扫描转换算法的绘制速度要尽可能得快，尽量不要出现浮点数占用大的内存和避免乘、除、开方及角度等复杂运算。

比较常用的直线扫描转换算法有三种：数值微分法（DDA）；中点画线算法；Bresenham算法。

3.1.2 数值微分法

数值微分法（digital differential analyzer，DDA）是直接利用直线斜率的增量方程来计算直线上下一个迭代像素点的方法。

直线的斜率微分方程为

数值微分法的迭代公式如下：

其中

当max（|Δx|，|Δy|）＝|Δx|时，则

当max（|Δx|，|Δy|）＝|Δy|时，则

数值微分法的算法示意图如图3.1-2所示。当直线的斜率k绝对值小于1时，迭代在x方向步进，x向步长为1（个像素），y方向的步进为yi+1＝yi±k，y方向对应的像素点坐标值为round（yi+1），即y方向取最接近yi+1的整数值，故获得的下一个像素点为（xi+1，round（yi+1））；当直线的斜率k绝对值大于1时，迭代在y方向步进，y向步长为1（个像素），x方向的步进为，x方向对应的像素点坐标值为round（xi+1），即x方向取最接近xi+1的整数值，下一个最佳像素逼近点为（round（xi+1），yi+1）。

在编写直线生成算法的程序时，除了实现一般位置的直线算法外，还应该考虑特殊位置直线的生成，例如，y方向的竖直线和x方向的水平线，这样才能获得稳定的算法。下面是考虑各种情况的直线数值微分法算法函数参考代码：

将直线生成函数保存为单独的文件，如文件名BasicGraph.h，并在应用程序中直接引用：

在应用程序中生成直线时，可以采用第2章的有关代码建立应用程序CGTest002，并在视图窗口拾取多个点，利用上述的中点画线函数顺序连接前后点生成直线。实现方法如下。

在视图窗口类的源文件CGTest002View.cpp中加入对BasicGraph1.h的引用，在OnDraw（）函数中就可以直接调用上述的直线数值微分法函数：

执行程序，在视图窗口拾取多个点，生成直线如图3.1-3所示。

数值微分法的特点是增量算法，直观、易实现。但是算法中有除法运算和浮点数，不利于用硬件实现；当图形中有大量的直线时，利用数值微分法会占用较多的内存，对运算速度会有一些影响。

3.1.3 中点画线算法

直线的中点画线算法是一种很巧妙的方法，在算法推导过程中使用了中点的概念，但是进行循环迭代时，却是根据正负值判断，和中点并没有关系。

中点画线法是借助直线的隐式方程的相关理论来实现的，假设直线的两个端点为P0（x0，y0）和P1（x1，y1），直线段隐式方程可表示为

式中

直线方程将空间分成三个区域，其中直线上方的点，将其x、y值代入方程中，F（x，y）＞0，直线下方的点F（x，y）＜0，直线上的点F（x，y）＝0，如图3.1-4所示。

假定直线的斜率0＜k＜1，则迭代在x方向步进，为了判断下一个最佳像素逼近点的位置，首先构造点（xi+1，yi+0.5）的判别式：d＝F（xi+1，yi+0.5）。

如图3.1-5（a）、（b）所示，当判别式d≥0时，直线在点（xi+1，yi+0.5）的上方，这说明直线更接近该点下方的像素点，则取下方的像素点（xi+1，yi）；当判别式d＜0时，直线在点（xi+1，yi+0.5）的下方，这说明直线更接近该点上方的像素点，则取上方的像素点（xi+1，yi+1）。

然后，再构造下一个点的判别式，这时需要根据上面两种情况分别构造。

（1）当d≥0时，则下一个构造点为（xi+2，yi+0.5），如图3.1-6（a）所示，判别式为

此时，d1的增量是a，是个整数。

（2）当d＜0时，则下一个构造点为（xi+2，yi+1.5），如图3.1-6（b）所示，判别式为

此时，d1的增量是a+b，也是个整数。

上述是迭代过程中判别式的增量，现在计算判别式的初始值：

因为点P0（x0，y0）在直线上，故F（x0，y0）＝0，那么，判别式的初始值为

判别式d的增量是整数，只有初始值中包含小数，那么可以用2d代替d，这样在整个算法中就不再出现小数，只有整数运算，即

当di≥0时，取（xi+1，yi），则di+1＝di+a⇒di+1＝di+2a；

当di＜0时，取点（xi+1，yi+1），则di+1＝di+a+b⇒di+1＝di+2（a+b）。

例如：用中点画线法连接两点P0（0，0）和P1（5，4）的直线段，如图3.1-7所示。

计算过程如下：

上述是0＜k≤1的算法，当k＞1时，迭代在y方向步进，需要按照上述方法重新推导判别式初始值d0和迭代时的判别式值d1。在编程实现中点画线算法时，和数值微分法一样，需要考虑其他情况，例如，斜率－1≤k＜0，k≤－1，端点的起始终止顺序和直线特殊位置，这时需要进行相应处理，使算法保持稳定性。下面是一般位置直线的中点画线算法参考代码（特殊位置直线算法代码省略）：

和数值微分法函数的保存方法一样，将中点画线函数也保存在BasicGraph.h文件中，以便在应用程序中直接引用。

中点画线算法在整个运算中都是整数运算，没有出现小数，因此占有的内存相对较少，也便于硬件实现。

3.1.4 Bresenham画线算法

Bresenham画线算法是计算机图形学领域使用最广泛的直线生成算法。在计算直线最佳逼近点的过程中，全部是整数运算，因此可以大幅提升计算速度。

算法原理如下：设直线从起点P0（x0，y0）到终点P1（x1，y1），直线方程可表示为

其中

当直线斜率0＜k≤1时，直线在x方向步进，每次增加一个像素点，设当前直线的最佳逼近点是（xi，yi），则下一个最佳像素点的x坐标xi+1＝xi+1，y坐标yi+1＝yi或者yi+1＝yi+1，yi+1到底取哪个值由当前直线上点的y坐标到yi和yi+1的距离大小而定，如图3.1-8所示。

令

当d1－d2＞0时，则

当d1－d2≤0时，则

当dx＞0时，用dx乘d1－d2不会改变d1－d2值的正负，因此不影响上述y的增量判断。并令pi＝（d1－d2）dx，同时，将代入，计算得

当i＝0时，有

当pi＞0时，取点（xi+1，yi+1），则

即增量为2dy－2dx。

当pi＜0时，取点（xi+1，yi），则

即增量为2dy。

上述是0＜k≤1的Bresenham算法，在编程实现时，和中点画线算法一样，也需要其他斜率时的情况。下面是一般位置直线的Bresenham算法参考代码（特殊位置直线算法代码省略）：

和数值微分法函数以及中点画线函数的保存方法一样，将Bresenham画线函数也保存在BasicGraph.h文件中，以便在应用程序中直接引用。

3.1.5 图形程序设计及VC++的橡皮筋和双缓存交互技术

直线、圆、椭圆等都是基本的图形元素。在进行图形应用时，会使用大量的图形元素，为了区分这些图形元素，非常有必要建立各种图形元素的数据结构或者图形类，这样，便于使用标准的格式。由于图形之间具有一些共同的属性，例如，颜色、线宽、线型等，所以，首先建立一个所有图形元素的基类。例如建立如下基类：

则直线类可继承自该图形基类，再加入直线本身需要的两个端点变量即可。

为便于文件管理，将图形类放入一个单独的文件中，例如保存为文件BasicClass.h，如下所示：

然后将该文件加入工程中，并在视图窗口类中使用时添加文件引用：

在视图窗口类中，建立直线集合：

当拾取到两个点后，将拾取到的两个点生成直线，并加入直线集合中。例如在OnLButtonDown（）函数中代码如下：

然后在OnDraw（）函数中，将直线集合中的每条直线显示出来。为了使应用程序具有扩充性，以及便于代码管理和调用，可以将画线函数封装为函数DrawLines（），这样，在OnDraw（）函数中，只需调用DrawLines（）函数即可。调用DrawLines（）函数的代码如下：

有多种直线生成算法，为了比较各种算法的效果，创建一个非模式对话框来选择不同的算法，并在非模式对话框中建立选择直线生成算法的三个单选按钮，如图3.1-9所示。

为这组单选按钮的第一个按钮建立int整型变量m_iLine，其中，m_iLine＝0代表选择的是数值微分法画线函数，m_iLine＝1代表选择的是中点画线函数，m_iLine＝2代表选择的是Bresenham画线函数。当选中不同的单选按钮时，需要对按钮单击消息BN_CLICKED增加消息处理函数，例如，数值微分法画线按钮的消息处理函数代码如下：

在视图窗口类中声明和使用该非模式对话框（非模式对话框的创建方法见2.2节）：

在工具栏中设置一个画直线的图标，当画直线时，单击画直线工具栏，在其消息函数中，生成画线算法选择的非模式对话框m_lDlg：

在直线生成算法函数DrawLine（）中，根据非模式对话框中算法的选项，选择不同的直线生成算法，代码如下：

执行程序，直线生成效果如图3.1-10所示。

上述通过OnDraw（）函数生成的是位置确定的最终图形，如果在位置最终确定之前希望看到图形的动态变化效果，例如，随着鼠标在视图窗口的移动，能够实时动态地生成图形，并进行观察，就需要用到VC6.0的交互式绘图技术。VC6.0的绘图功能中有一个“异或”的绘图特性，即在屏幕上用异或的模式画图形，相同的位置重新画一次此图形，则会在屏幕上擦除上一次所绘制的内容。利用这种特性画直线时，直线就像橡皮筋一样，随着鼠标在屏幕中位置的移动而移动，长短也随之变化，因此，又称之为橡皮筋技术。

橡皮筋技术一般在鼠标移动时使用，因此，在鼠标移动的映射函数OnMouseMove（）中实现。其实现的代码非常简单，在绘制新位置图形之前，只需调用pDC－>SetROP2（R2_NOT），然后把上次相同位置的图形再绘制一次，即可擦除上次绘制图形，然后，再绘制新图形。具体代码如下所示：

将拾取点的函数修改如下：

通过上面的代码修改处理，即可在视图窗口移动鼠标时实时地动态生成直线，并在两个端点完全确定时再将直线加入直线集合中。橡皮筋技术不仅适用于直线的生成，其他图形如圆、椭圆的生成也可以使用该技术，从而获得动态的图形生成效果。

OnDraw（）函数是绘制图形的主要函数，在程序中使用Invalidate（）函数时，会调用OnDraw（）函数，将图形在显示设备上重新再绘制一遍，当应用程序的窗口发生变化时，例如，窗口移动、窗口缩放或者窗口滚动，也会调用OnDraw（）函数，重绘图形。OnDraw（）函数首先用背景色将显示区域清除，然后，再重绘，由于背景色往往与绘图内容反差很大，这样短时间内背景色与显示图形交替出现，使得窗口看起来有闪烁的感觉。为了避免这种闪烁的现象，可以采用双缓存技术来解决。

双缓存技术的原理可以这样形象地理解：把电脑屏幕看作一块黑板，首先在内存环境中建立一个虚拟的黑板，然后在这块黑板上绘制复杂的图形，等图形全部绘制完毕的时候，再一次性把内存中绘制好的图形复制到屏幕上。也就是除了在屏幕上进行图形显示以外，在内存中也绘制图形，把要显示的图形先在内存中绘制好，然后再一次性将内存中的图形一个点一个点地覆盖到屏幕上去（这个过程非常快，因为是非常规整的内存复制）。这样在内存中绘图时，随便用什么反差大的背景色进行清除都不会闪，因为看不到。当粘贴到屏幕上时，因为内存中最终的图形与屏幕显示图形差别很小（如果没有运动，当然就没有差别），这样看起来就不会闪。

因为背景色是在内存中绘制的，所以，没必要再在屏幕上清除背景色，这样就避免了闪烁。通过重载WM_ERASEBKGND消息函数，去掉屏幕背景绘制。代码如下：

OnDraw（）函数的代码修改如下：

由于双缓存技术是首先在内存中画图形，然后再一次性地将图片复制到显示屏幕上，因此，不适用于图形实时调试的开发环境。在调试图形程序时，当需要逐步调试图形生成过程，并观察生成效果时，建议转换为直接在显示设备上生成图形。