会计学3.1直线的生成算法图3.1.1直线的像素化(VRC变换)点阵设备中直线的生成方法主要有：对称DDA法、简单DDA法、Bresenham算法、中点画线法等，每种方法各有优缺点。矢量设备中直线的生成方法主要有：逐点比较法、正负法、Bresenham算法等。直线的生成算法是在设备坐标系(如屏幕坐标系、绘图机坐标系等)中进行的，要求直线已知点即起点和终点的坐标为设备坐标。若已知点坐标为世界坐标则要换算成设备坐标。1.DDA法DDA法即数字微分分析法(DigitalDifferentialAnalyzer)。我们知道，直线微分方程为当ε取值不同时，便形成对称DDA法和简单DDA法。下面以屏幕上生成直线为例来介绍这两种算法。(1)对称DDA法。对称DDA法取ε=2-n，n由下面关系式决定：2n-1≤max(|Δx|,|Δy|)≤2n,n为正整数计算点的公式为【例1】用对称DDA法在起点A(2，1)和终点B(12，7)之间生成一段直线。求解的第一步是计算初值Δx,Δy,n。这里Δx=10,Δy=6,n=4。第二步按递推公式循环计算点的坐标，并取整显示。表3.1.1是本例的循环计算过程。图3.1.2是其屏幕显示结果。表3.1.1对称DDA法计算过程图3.1.2对称DDA法生成的直线对称DDA法生成的直线比较精确，像点位置偏离直线不超过半个像素。逻辑上也比较简单，用2的负指数幂作为ε，意味着把存放Δx和Δy的寄存器通过移位操作就可得到点与点之间的坐标增量εΔx、εΔy，而不用除法计算，计算直线上每一点只用两次加法即可实现。对称DDA法适合用硬件来实现，当然也可用软件来实现。(2)简单DDA法。简单DDA法取。计算点的公式为图3.1.3简单DDA法生成的直线简单DDA法是按Δx,Δy绝对值较大的方向走步的，在这个方向上，每步走一个像素，然后再确定另一个方向的走步。简单DDA法生成直线的精度同对称DDA法，但它在求一个点时要做两次除法以决定坐标增量值。简单DDA法不适合硬件实现，只适合于软件处理。2.Bresenham直线生成算法由Bresenham提出的算法最初是为数控绘图机设计的，后来被广泛用于光栅扫描图形显示器。Bresenham直线生成算法实际上也是简单DDA算法，即在某一计长方向上，每次必变化一个单位步长或一个像素单位，另一方向上的变化量可通过计算得到。这种算法只用到整型数计算，不必作四舍五入操作，而且在计算判别式时，计算量很小，因而得到广泛的应用。下面我们介绍在光栅扫描图形显示器上实现的这种算法。假设要生成的直线起点为(xa,ya)、终点为(xb,yb)，经变换后直线起点为(0，0)、终点为(Δx,Δy)，其中Δx=xb-xa,Δy=yb-ya。此时直线方程可简化为/现在我们推导由Pi-1确定下一个像素点的递推关系式。由于由于此时Δx为正，故我们可以用Δx(s-t)的正、负作为选择Si和Ti的标准。若令di=Δx(s-t)，则有di=2(r·Δy-q·Δx)+2Δy-Δx将r=xi-1，q=yi-1代入，于是di=2xi-1·Δy-2yi-1·Δx+2Δy-Δx将式(3-1)中的i用i+1替换，便有di+1=2xi·Δy-2yi·Δx+2Δy-Δx用di+1减去di得di+1-di=2Δy(xi-xi-1)-2Δx(yi-yi-1)由于此时走步方向为x方向，即xi-xi-1=1，重写上式得di+1=di+2Δy-2Δx(yi-yi-1)若di≥0，即s≥t，则选Ti,此时yi=yi-1+1Di+1=di+2(Δy-Δx)若di<0,即s<t，则选Si，此时yi=yi-1di+1=di+2Δy根据以上分析，我们可得到斜率在0~1之间的Bresenham直线生成递推计算公式：上式中的坐标x0、y0、xi-1,yi-1、xi,yi均为以直线起点为坐标原点的局部坐标系下的坐标。当斜率大于1时，只需将x,y交换计算即可(此时以y方向作为走步方向，每次增加一个像素单位)，显示时再将x,y换过来。对于任意走向的直线，在用式(3-5)计算时，Δx,Δy要用绝对值代入，并根据Δx,Δy的正、负号决定x,y方向增量的正负。3.生成直线的逐点比较法逐点比较法就是在输出直线或圆弧的过程中，每走完一步就与理论的直线或圆弧进行比较，确定当前点是在线或弧上，还是在线或弧的一侧，然后再决定下一步的走向，这样一步一步地逼近所画直线或圆弧。逐点比较法是针对笔式绘图机提出的。根据绘图机的结构原理及数字控制原理，绘图机的笔架可能的移动方向(称为走步方向)有八个：+X、-X、+Y、-Y、+X+Y、-X+Y、-X-Y、+X-Y。其中+X、-X、+Y、-Y四个走步方向是一般绘图机