③Bresenham法
区域填充是一个彩色区域，可以是均匀的也可以是不均匀的，区域边界可以是直线也可以是曲线。
可提供不同的内部填充类型用以充满区域内部，填充的类型可能是不同的颜色，不同的灰度或者不同的填充图案。还可以用方程生成的梯度变化曲线完成填充过程。阴影填充可以通过来自一个光源的投影直线计算出，因而在填充区域中的像素相应地发生变化。用户可根据系统硬件和软件，用一种或几种色彩进行填充，也可使用多种颜色填充区域。 δ=tgβ－tgα=
当δ＜0时，表示笔在OA线段下方，应该向+Y方向走一步 当δ＞0时，表示笔在OA线段上方，应该向+X方向走一步
由于分母XMXA＞0，因此只需判断分子 YMXA－YAXM的正负 即可，得偏差公式：
FM＝YMXA－YAXM 对任意点，偏差函数的一般形式为： Fi＝XAYi－YAXi 其中，XA，YA是终点A坐标。 2）递推公式
由公式可以看出，由于每次要计算两次乘法和一次减法，所以计算工作量大， 为了简化计算，可设法用前一点的偏差来推算后一点的走步方向以及走步后的偏差，这种方法称为递推法。递推公式很容易用计算机实现。
递推公式可根据下图用偏差函数判断笔进方向的图例得出
设笔当前位置为 M1(X1，Y1)，此时F1＝Y1XA－ YAX1＜0，应走+Y一步到M2即X2＝X1，Y2=Y1＋1，＋1表示走一步M2处的偏差为：F2=Y2XA－YAX2=F1＋XA（用X2＝X1，Y2=Y1＋1代入得到）
若F2≥0，应走＋X一步到M3，则X3=X2＋1，Y3=Y2，M3处的偏差为：F3=Y3XA－YAX3=Y2XA－YAX2－YA=F2－YA
这样依次进行下去，就得到第i步的递推公式 ：
当Fi≥0时，向+X方向走一步，此时偏差Fi＋1＝Fi－YA（i=1，2，??n）。 当Fi≤0时，向+Y方向走一步，此时偏差Fi＋1＝Fi＋XA（i=1，2，??n）。
偏差Fi的推算，只用到终点坐标值XA ，YA而与中间点的坐标值无关，且只需进行加减运算。
3）任意象限偏差计算
对于第二、三、四象限的直线，也可类似推出。当直线段处于第二、三、四象限时，偏差值的计算及走步方向如下表所示： 二、 数值微分法(DDA法) 1.定义
数值微分法即DDA法（Digital Differential Analyzer），这是一种基于直线的微分方程来生成直线的方法。 2.数值微分法的原理
设（x1，y1）和（x2，y2）分别为所求直线的端点坐标，由直线的微分方程得 可通过计算由x方向的增量Δx引起y的改变来生成直线， 由yi＋1=yi＋Δy（yi为直线上某步的初值）
则 可通过计算由y方向的增量引起x的改变来生成直线
若设Xi＋1＝Xi＋Δx 则：实际上是一个递推公式，即yi+1由前一点的yi和X的增量 求得； Xi＋1由前一点的Xi和Y的增量求得。 3.DDA的算法基本思想
选定x2－x1和y2－y1中较大者作为步进方向（假设x2－x1较大）取该方向上的Δx为一个像素单位长， 即x每次递增一个像素，然后利用前面公式计算相应的y值，把每次计算出的（xi＋l, yi＋1）经取整后顺序输出到显示器，则得光栅化后的直线。 为什么取x2－xl和y2－y1中较大者步方向？ 此图中Y2－Y1＝8>X2-X1=4
三、 Bresenham法 1、问题提出
DDA法就是根据直线的斜率来计算出下一个y值，经取整后以确定下一个像素点，因为进行取整运算，这就难以避免所取像素点偏在实际直线的某一侧。而Bresenham算法根据直线的斜率确定或者选择变量在X轴或Y轴方向每次递增一个单位，其变量的增量值根据实际直线与网格交点与像素点的距离来选择像素点而取0或1，这距离称为误差，记作e。 (1)偏差e
实际直线与网格交点与像素点之间的距离称偏差e。以左图第一个八分图的直线为例，即直线的斜率在0～1之间。
若通过（0，0）的直线的斜率大于1/2，即e＞l／2，它与x＝1直线的交点离y＝l直线较y＝0直线近，因此取像素点（1，1）。具体见图中的e2 如果斜率小于l／2，即e＜l／2，则应取像素点（l，0）。具体见图中的e1
当斜率等于 l／2时，即 e=l／2，没有确定选择标准，但算法选择（l，l）像素点。 e>1/2 e<1/2
2、Bresenham法基本思想
Bresenham法基本思想是：使得每次只要检查误差项的符号就可以决定实际的增量。 (2)偏差e的计算
由图可知，在步进一个像素点后的误差为原误差加上直线的斜率，即e=e＋Δy/Δx
为了简化判断可设e’＝e－l／2，这样只要判断e’的符号即可,首先令误差项的初值为－1／2。
初始，如果e’＝Δy／Δx－1／2大于或等于零，则x加1，y加1；如果小于零，x加1，y不动（由前面的图可以看出）。 4.3 曲线的生成
在科学技术中常常需要绘制曲线，而绘制曲线的根据或要求各不相同，通常遇到的约有下述几种情况。
（1）规则曲线的绘制：已知曲线的方程，要求画出曲线
（2）曲线拟合：由试验或观测得到了一批数据点，要求用一个函数近似地表明数据点坐标间的关系，并画出函数的图像（曲线）。
（3）曲线插值：由试验、观测或计算得到了由若干个离散点组成的点列，要求用光滑的曲线把这些离散点连结起来。曲线插值与曲线拟合不同，拟合并不要求曲线通过数据点。 （4）曲线逼近：在曲线形状设计中，给定了折线轮廓，要求用曲线逼近这个折线轮廓。 上述各类问题都要求画出曲线，不同的是，规则曲线的绘制中曲线的方程为已知，而曲线拟合、曲线插值、曲线逼近问题则需要首先找出或构造出曲线的方程，再根据曲线方程画出曲线。除圆等少数曲线外，根据方程画曲线一般是先计算出曲线上一系列适当靠近的点，然后依次将这些点用直线连起来，得到一条由折线表示的近似曲线。只要这些点靠得足够近，看起来就是一条光滑的曲线。
当判断结果落在圆外时，向－X方向走一步。直到再次到达圆内为止。 一、圆弧的生成 1．逐点比较法 (1)基本思想
逐点比较法绘制圆弧的原理与逐点比较法生成线段类似，也是在图形输出设备上每步输出逼近欲画的圆弧。
用逆时针画第一象限中的AB圆弧的过程如下：
从始点（xA，yA）点开始画起，首先向圆内走一步，也就是先向－X方向走一步，然后与所要画的圆弧进行比较
判断结果，落在圆内时向Y方向走一步，依次类推，一直到达圆处为止 当画到终点以（xB，yB）时，终止比较，AB圆弧绘制结束。
逐点比较法绘制圆弧时一般定为先进后出，有顺圆走向和逆圆走向两种移动规则。 顺时针走向 逆时针走向
(2)判别函数
从上面绘制圆弧的过程可知，归根到底，是用什么方法来比较当前点是否落在圆内，还是落在圆外，然后决定走向。设圆心为o（x0，y0），起点坐标为A（xA，yA），终点坐标为B（xB，yB），并假定绘图笔当前点位置为M（xM，yM），于是圆的半径为R，即 令FM＝RM－R作为判别函数。为了简化计算，取
（由于RM－R很小）作为判别函数，显然： ①FM＜0，表示M点在圆弧内 走+Y方向 ②FM＞0，表示M点在圆弧外 走-X方向
③FM＝0，表示M点在圆弧上 走-X方向(约定） 因此，根据FM的正负，可以确定走向。 2、数值微分法（DDA法） (1)一般DDA法
1)一般递推公式
圆弧的DDA法和直线段DDA法类似，也是根据圆弧的微分方程来实现的，我们以圆心在坐标系原点，半径为R的一段圆弧为例来讨论。 角度DDA法比上面介绍的DDA法更加容易理解，它实际上就是把圆或圆弧分成N等分。用N段相邻的直线来逼近圆或圆弧，这种方法显然是建立在直线段生成算法的基础之上的，因而其效率要低些，但很好理解。 二、椭圆的生成(Bresenham法) (1)基本思想
主要考虑标准椭圆的生成，中心在原点（中心若不在原点可以通过平移得到），长短半轴都是对称的。由于椭圆是轴对称函数，因此只要考虑第一象限的情况，其它象限中像素点的位置可以通过对称性得到。
在介绍直线段生成的时候，Bresenham方法实际上就是每一步在某直线真实点周围的若干像素点中选取一个最靠近真实点的像素作为该步的绘制点。 同理，在椭圆的Bresenham法中也是采用了相同的机制予以实现。为了更加准确的判定出哪个像素点是最近点，引入了一个中点加以辅助判断，因此，也将该方法称为中点Bresenham算法。 (2) 标准的椭圆方程
其中，a和b分别是椭圆的长短半轴的半径
在第1象限的椭圆弧需要做一个划分，即同时经过椭圆弧上斜率为-1的切线点与原点的直线将第1象限划分为两个区域，如图4.21所示。
在上半区，?x的增量比较重要，而在下半区，?y的增量更为明显。 (3) 原理详解和判别公式
如图4.22所示，先考察上半区的放大方格，像素点P(xp, yp)是当前选取的像素点，由于上半区主要考虑X方向上的增量，因此下一步有两个候选的像素点，分别是H(xp+1, yp)和L(xp+1, yp-1)。
将标准的椭圆方程进行改写，可得F(x, y)=b2x2+a2y2-a2b2=0
通过观察，可以判定H点距离椭圆的真实点更加靠近，因此下一步应该选取H点作为椭圆像素点。当然，计算机必须通过严格的计算才能得出这一结论。引入点M(xp+1, yp-0.5)作为H点和L点之间的中点，由此可以定义判别公式如下： dTM= F(xp+1, yp-0.5)=b2(xp+1)2+a2(yp-0.5)2-a2b2 dTM= F(xp+1, yp-0.5)=b2(xp+1)2+a2(yp-0.5)2-a2b2 （1）如果dTM <0，就选择像素点H，并且引入新的中点，即M的下一个中点M’(xp+2, yp-0.5)，此时将M’代入判别公式，将得到：
dTM’= F(xp+2, yp-0.5)=b2(xp+2)2+a2(yp-0.5)2-a2b2= dTM +b2(2xp+3) 可知b2(2xp+3)为? dTM。 （2）如果dTM >0，就选择像素点L，并且引入新的中点，即M的下一个中点M’’(xp+2, yp-1.5)，此时将M’’代入判别公式，将得到：
dTM’’= F(xp+2, yp-1.5)=b2(xp+2)2+a2(yp-1.5)2-a2b2= dTM +b2(2xp+3)+ a2(-2yp+2) 可知b2(2xp+3) + a2(-2yp+2)为? dTM。
这样只要根据? dTM的值是否为正或负，就可以完成椭圆弧上半区的绘制工作。 同理，椭圆弧下半区主要考虑Y方向的步进， 其原理和上半区是相同的。
下面来讨论图4.22两个区域中点M的初始值问题。由于椭圆的起始点为(0, b)，因此第一个中点MT0的坐标为(1, b-0.5)，对应的判别公式为dT0= F(1, b-0.5)= b2+a2(-b+0.25)。假设上半区的最后一个点的坐标为(x, y)，则判别所需中点的坐标为(x+0.5, y-1)，对应的判别公式为dB0= F(x+0.5, y-1)= b2(x+0.5) 2+a2(y-1) 2-a2b2。 椭圆的生成实际上是圆的特殊情况，那么中点Bresenham算法是否能够用于圆弧的生成呢？答案是肯定的而且更为简便，圆弧具有八方对称性，因此只需要画出八分之一圆弧就可以了。 4.4区域填充
区域是指相互连通的一组像素的集合。区域通常由一个封闭的轮廓来定义，处于一个封闭轮廓线内的所有像素点即构成一个区域。
所谓区域填充就是将区域内的像素置成新的颜色值或图案。区域填充是计算机绘图的一种基本操作，相当一部分绘图都用到它。 对于区域填充来说，它要解决两个问题： ①确定需要填充哪些象素， ②确定用什么颜色或图案。
处于一个封闭轮廓线内的所有像素点即构成一个区域 区域填充就是将区域内的像素置成新的颜色值或图案
我们知道多边形是常用基本图形，它是由一组边围成，封闭区域，多边形也可以是凸、凹或是带空洞。多边形区域填充就是将区域内的像素置成新的颜色值或图案。由于任何一个封闭曲线都可以用多边形来逼近，所以多边形填充实用面广。 一、多边形区域填充 1．区域内部点判断准则
区域填充首先判断一个象素点是否处于多边形区域内,其判断准则如下： 从该点向无穷远处引出一条射线（也称扫描线），若射线与区域边界交点目标数目为奇数，则此点在区域内。若射线与区域边界交点目标数目为偶数，则此点为区域外点。
（2）当扫描线重合多边形某条边界水平线时，如该水平边线前后两条边线是一上一下的，则该水平边线两个端点作为一个交点，即扫描线与该水平边界线相交了一次。 2．边相关性及边记录 很显然，不能利用区域内部点判别准则对显示平面上每个点逐个判别，这样计算量太大。 事实上，相对于一个给定多边形区域来说，显示平面上每个像素点内外特性是互相关联的。相邻像素间具有相关属性。在实施多边形填充时，利用扫描线相关性，就无需对扫描线上所有像素点逐个地进行内外特性判断，只需对一条扫描线从左到右求出该扫描线与区域边界交点，这些交点必将扫描线分成内外交替线段，这些交点x值大小依次排列。 3．边表ET和活动边表AET （1）边表ET
边表是一个包含多边形全部边记录的表，它按y坐标（与扫描线一一对应）递增（或递减）的顺序存放区域边界的所有边。每个y坐标值存放一个或者说几个边记录。当某条扫描线yi碰到多边形边界的新边时（以边线底端为准），则在ET表中相应的y坐标值处写入一个边记录。当同时有多条边进入时，则在ET表中按链表结构写入相应数目的多个记录，这些记录是按边线较低端点的x值增加的顺序排列。当没有新边加入时，表中对应的y坐标值处存储内容为空白。
注意：在ET表中：①与x轴平行的边不计入。②多边形的顶点分为两大类：一类是局部极值点，如下图中的P1、P3；另一类是非极值点，如下图中的P2、P4、P5。当扫描线与第一类顶点相遇时，应看作两个点；当扫描线与第二类顶点相遇时，应视为一个点。 ⑵活动边表AET
活动边表AET是一个只与当前扫描线相交的边记录链表。随着扫描线从一条到另一条的转换，AET表也应随之变动，利用 yi+1=yi+1, xi+1=xi+1/m
可以算出AET表中x域中的新值xi。凡是与这一条扫描线相交的任何新边都加到AET表中，而与之不相交的边又被从AET表中删除掉了。下图列出了图4.40中多边形在扫描线
相关推荐：
loading