Pu（x i＋1，y i）
圆中点Bresenham算法原理
31
3.2.2 构造中点偏差判别式
从P（xi，yi）开始，为了进行下一像素点的选取， 需将Pu和Pd的中点M（x i＋1，y i－0.5）代入隐函数， 构造中点偏差判别式：
d F ( x M , y M ) F ( xi 1, yi 0.5) ( xi 1) 2 ( yi 0.5) 2 R 2 （3-9）
d 0 F ( x0 1, y0 0.5) y0 0.5 k ( x0 1) b
y 0 kx0 b k 0.5
其中，因为（x 0，y 0）在直线上，所以 y0 kx0 b 0 则：
d 0 0.5 k
（3-6）
23
3.2 圆的扫描转换
,）
29
假定圆当前点是P（xi，yi）,下一点 只能在Pu（x i＋1，y i）和Pd（x i ＋1，yi－1）中选取，如图3-7所示。 Pu和Pd的中点为M（x i＋1，y i－ 0.5）显然，若M点在理想圆弧的下方， 则Pu点离圆弧近，点亮Pu；否则应点 亮Pd。
30
y
P（xi，yi） M（x i+1，y i－0.5） Pd（x i＋1，yi－1）
yi 1 yi 1 yi
(d 0) (d 0)
（3-3）
20
三、 递推公式
1.中点偏差判别式的递推公式 在主位移x方向上已走一步的情况下，现 在考虑沿主位移方向再走一步，应该选择哪个中 点代入中点偏差判别式以决定下一步该点亮的像 素，如图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） P（xi，yi）
中点画线法
一、原理： 每次在主位移方向上走一步，另一个方 向上走不走步取决于中点偏差判别式的 值。 给定理想直线的起点坐标为P0（x0， y0），终点坐标为P1（x1，y1），则直 线的隐函数方程为：
F(x, y) y kx b 0
k
（3-1）
其中，直线的斜率：
直线水平方向位移 ：
x 0 1 2 3 4 5 int(y+0.5) 0 0 1 1 2 2 y+0.5 0+0.5 0.4+0.5 0.8+0.5 1.2+0.5 Line: P0(0, 0)-- P1(5, 2) 1.6+0.5 3 2.0+0.5
2 1 0 1 2 3 4 5
缺点： 在此算法中，y、k必须是float， 13 且每一步都必须对y进行舍入取整，不利于硬 件实现。
（3-10）
32
3.2.3 递推公式
1.中点偏差判别式的递推公式
现在如果考虑主位移方向再走 一步，应该选择哪个中点代入中点 偏差判别式以决定下一步应该点亮 的像素，分两种情况讨论。
33
⑴当d<0时，下一步的中点坐标为： M（x i＋2，y i－0.5）。 所以下一步中点偏差判别式为： 2 2 2 dr 1 ( xi 1) ( yi 0.5) R 2xi 3 di 2xi 3
直线、圆、椭圆是图形设计的最基本的图形（图 元）。 图形的扫描转换（光栅化）：在像素点阵中确定 最佳逼近于理想图形的像素占集的过程。
4
步骤如下：
1、确定有关像素 2、用图形的颜色或其它属性，对像素进行写操作。
对一维图形，不考虑线宽，则用一个像素宽的 直线来显示图形。 二维图形的光栅化，即区域的填充：确定像素 集，填色或图案。 任何图形的光栅化，必须显示在一个窗口内， 否则不予显示。即确定一个图形的哪些部分在 窗口内，哪些在窗口外，即裁剪。
基本图形（直线、圆、椭圆） 的扫描转换
◆扫描转换的基本概念 ◆绘制像素点函数SetPixel的
用法 ◆直线圆和椭圆的中点 Bresenham原理 ◆直线反走样原理
3.1 3.2 3.3 3.4 3.6 3.7
直线的扫描转换 圆的扫描转换 椭圆的扫描转换 反走样算法 本章小结 习题
什么是扫描转换？
d0 F (1, R 0.5)
2 2
（3-13）
1 ( R 0.5) R 1.25 R
M（x i＋2，y i＋0.5）
d<0
d≥0
中点偏差判别式的递推
21
(1)当d<0时
d i 1 F ( xi 2, yi 1.5) yi 1.5 k ( xi 2) b
yi 0.5 k ( xi 1) b 1 k d i 1 k
直线垂直方向位移 ：
x x1 x0
y y1 y 0
Δy y 1 y 0 Δx x1 x 0
y
x
理想直线将平面划分成三个区域： 对于直线上的点，F(x，y)＝0； 对于直线上方的点，F（x，y）＞0； 对于直线下方的点，F（x，y）＜0。 假设直线的斜率为0≤k≤1，则 x ，所以 y 确定x方向为主位移方向。 按照Bresenham原理，x方向上每次加1， y方向上加不加1取决于中点偏差判别式的 值。
34
P（xi，yi）
M（x i＋1，y i－0.5） M（x i+2，y i－0.5） M（x i＋2，y i－1.5）
M（x i＋1，y i－0.5）
d<0
d≥0
中点偏差判别式的递推
35
2.中点偏差判别式的初始值
圆的起点为P0（0，R），x为主位移方 向。因此，第一个中点是（1，R-0.5）， 对应的d的初始值为：
（3-11）
⑵当d≥0时，下一步的中点坐标为： M（x i＋2，y i－1.5）。 所以下一步中点偏差判别式为：
d i 1 F ( xi 2, yi 1.5) ( xi 2) 2 ( yi 1.5) 2 R 2（3-12）
( xi 1) 2 ( yi 0.5) 2 R 2 2 xi 3 (2 yi 2) d i 2( xi yi ) 5
float dx, dy, y, k; dx, = x1-x0, dy=y1-y0; k=dy/dx, y=y0;
for (x=x0; xx1, x++)
drawpixel (x, int(y+0.5), color); y=y+k;
12
例：画直线段P0(0,0)--P1(5,2)
（3-2）19ຫໍສະໝຸດ 当d<0时，中点M在直线的下方，Pu点 离直线距离近，下一像素点应点亮 Pu，即y方向上走一步；
当d>0时，中点M在直线的上方，Pd点 离直线距离近，下一像素点应点亮 Pd，即y方向上不走步； 当d＝0时，中点M在直线上， Pu、Pd 与直线的距离相等，点亮Pu或Pd均 可，约定取Pd。
数值微分法（ＤＤＡ）
假定直线的起点、终点分别为：（x0,y0), (x1,y1)，且都为整数。
。 。
(X i , Yi)
。
栅格交点表示象素点位置
(X i+1 ,Yi + k) (X i , Int(Yi +0.5))
。
8
基本思想
已知过端点P0 (x0, y0), P1(x1, y1)的直线 段L y=kx+b 直线斜率为 y1 y0
17
F（x，y）>0
F（x，y）=0
直线中点Bresenham算法原理
F（x，y）<0
18
二、 构造中点偏差判别式
从P（xi，yi）点走第一步后， 为了进行下一像素点的选取，需 将Pu和Pd的中点 M（x i＋1，y i＋0.5）代入隐函 数方程，构造中点偏差判别式d。
d F ( xM , y M ) F ( xi 1, yi 0.5) yi 0.5 k ( xi 1) b
10
增量算法：在一个迭代算法中，如果每 一步的x、y值是用前一步的值加上一个 增量来获得，则称为增量算法。 DDA算法就是一个增量算法。这种方法 直观，但效率太低，因为每一步需要一 次浮点乘法和一次舍入运算。
11
void DDALine(int x0,int y0,int x1,int y1,int color) int x；
16
假定直线的当前点是 P( xi , yi ) ， 沿主位移x方向走一步，下一点只能 P 在 P d ( xi 1, yi ) u ( xi 1, yi 1) 和 P P d 的中点 两点中选取。 和 u 为 M ( xi 1, yi 0.5)，如图3-2所 示。显然，若中点M在理想直线的下 方，则 P u 点距离直线近，点 亮 P 。 u ；否则点亮 P d
5
图形显示前需要：扫描转换+裁剪 ●裁剪---〉扫描转换：最常用，节约计算时间。 ●扫描转换---〉裁剪：算法简单；
6
3.1 直线的扫描转换
直线的扫描转换: 确定最佳逼近于该直线的一组 象素，并且按扫描线顺序，对这些象素进行写 操作。 三个常用算法：
数值微分法（DDA） 中点画线法 Bresenham算法。
当d<0时，中点M在圆内，下一像素点应点亮 Pu，即y方向不退步；当d>0时，中点M在圆外，下 一像素点应点亮Pd，即y方向退一步；当d＝0时， 中点M在圆上， Pu、Pd和圆的距离相等，点亮Pu 或Pd均可，约定取Pd。
因此，
yi yi 1 yi - 1
(d 0) (d 0)
3.2.1 算法原理 3.2.2 构造中点偏差判别式 3.2.3 递推公式
24
本节主要讲解仅包含加减操作的顺时 针绘制1/8圆的中点Bresenham算法原理。