02-3 第二章 基本图形的生成与计算-直线的生成.pptx

第1页：直线的生成

计算机图形学讲义 第2章 基本图形的生成与计算—直线的生成

第2页：直线的生成算法

2.1 直线的生成算法

画一条从 (x1,y1) 到 (x2,y2) 的直线，实质上是一个发现最佳逼近直线的像素序列，并填入色彩数据的过程。这过程也称为直线光栅化。

第3页：直线光栅化的要求

直线光栅化

• 最接近数学上的直线；
• 沿着线段分布的象素应均匀；
• 画线速度尽可能的快。

第4页：直线DDA算法

2.1.1 直线 DDA 算法

设直线的起点坐标为 P1 (x1,y1)，终点坐标为 P2 (x2,y2)，则直线的斜率可由此确定。

第5页：8个象限的坐标增量值

表2.1 8个象限中的坐标增量值：按照从 (x1,y1) 到 (x2,y2) 方向不同，分 8 个象限（图2.1）。对于方向在第 1a 象限内的直线，取增量值 Dx = 1，Dy = m；对于方向在第 1b 象限内的直线，取增量值 Dy = 1，Dx = 1/m。

第6页：DDA算法的实现

DDA算法的实现：研究表中的数据，可以发现两个规律：

1. 当 |dx| > |dy| 时，|Dx| = 1，|Dy| = m；否则 |Dx| = 1/m，|Dy| = 1。
2. Dx、Dy 的符号与 dx、dy 的符号相同。

第7页：DDA算法的特点

• 使用 DDA 算法，每生成一条直线做两次除法，画线中每一点做两次加法。
• 算法简单，实现容易。
• 在循环中涉及实型数据的加减运算，影响了直线的生成速度。

第8页：Bresenham算法的引入

此处的讨论先将直线方向限于 1a 象限（图2.1），在这种情况下，当直线光栅化时，x 每次都增加 1 个单元，即 xi+1 = xi + 1，而 y 的相应增加值应当小于 1。为了光栅化，yi+1 只可能选择图2.2中两种位置之一。

2.1.2 直线 Bresenham 算法

第9页：误差判别式的推导

yi+1 的位置选择 yi+1 = yi 或者 yi+1 = yi + 1，选择的原则是看精确值 y 与 yi 及 yi+1 的距离 d1 及 d2 的大小而定。计算公式为：

y = m(xi + 1) + b（2.1）　d1 = y − yi（2.2）　d2 = yi+1 − y（2.3）

如果 d1 − d2 > 0，则 yi+1 = yi + 1，否则 yi+1 = yi。将式 (2.1)、(2.2)、(2.3) 代入 d1 − d2，再用 dx 乘等式两边，并以 Pi = (d1 − d2) dx 代入上述等式，得：

Pi = 2xi·dy − 2yi·dx + 2dy + (2b − 1) dx（2.4）

由于在 1a 象限 dx 总大于 0，所以 Pi 仍旧可以用作判断符号的误差。Pi+1 = Pi + 2dy − 2(yi+1 − yi) dx（2.5）

第10页：Bresenham算法的步骤

求误差的初值 P1：P1 = 2dy − dx。

综述上面的推导，第 1a 象限内的直线 Bresenham 算法思想如下：

1. 画点 (x1,y1)，dx = x2 − x1，dy = y2 − y1，计算误差初值 P1 = 2dy − dx，i = 1；
2. 求直线的下一点位置 xi+1 = xi + 1。如果 Pi > 0，则 yi+1 = yi + 1，否则 yi+1 = yi；
3. 画点 (xi+1, yi+1)；
4. 求下一个误差 Pi+1，如果 Pi > 0，则 Pi+1 = Pi + 2dy − 2dx，否则 Pi+1 = Pi + 2dy；
5. i = i + 1；如果 i < dx + 1 则转步骤 2；否则结束操作。

第11页：Bresenham算法计算实例

计算实例

有一条直线起点为 P(1,1)、终点为 Q(5,4)，用 Bresenham 算法计算出逼近该直线的像素坐标序列。

解：

第12页：Bresenham算法的优点

1. 不必计算直线的斜率，因此不做除法。
2. 不用浮点数，只用整数。
3. 只做整数加减运算和乘2运算，而乘2运算可以用移位操作实现。

• Bresenham 算法的运算速度很快，适于用硬件实现。
• 讨论：以上讨论的是 0＜△y＜△x 的情况，对于适用所有 8 个方向的直线的生成算法，则要考虑以判断条件 |dx| > |dy| 为分支，并分别将 2a、3a 象限的直线和 3b、4b 象限的直线变换到 1a、4a 和 2b、1b 象限方向去，以实现程序处理的简洁。

第13页：Bresenham算法的实现

Bresenham算法的实现

第14页：本章作业

作业

分别用 DDA 算法和 Bresenham 算法计算出逼近两端点为 P(6,5)、Q(2,2) 的直线的像素坐标序列。