第二章 光栅图形学算法
2.1 直线段的扫描转换算法
2.1.1 直线段扫描转换算法概述
- 光栅显示器屏幕上的直线
- 核心方法：用离散像素点逼近直线
- 直线绘制的三个著名算法
- 数值微分法 (DDA)
- 中点画线法
- Bresenham 算法
2.1.2 数值微分法 (DDA)
- 数值微分法 (DDA - Digital Different Analyzer)
- 核心思想：增量思想
- $y_i=kx_i+b,\ \ y_{i+1}=kx_{i+1}+b$
- $y_{i+1}=kx_{i+1}+b=kx_i+k+b=y_i+k$，即 $y_{i+1}=y_i+k$，$k$ 即为增量。
- 因此即可将原式中的乘法换成加法。
- 算法过程
- $|k|<1$时，$x$ 均匀增加，每次求出 $x$ 对应的 $y$ 值，再将 $y^*=(int)(y+0.5)$ 下取整 $y^*$，得到 $(x,y^*)$ 像素点坐标，再将该像素点涂色即可。
- 算法总结
- $|k|\leq 1$ 时， $x_{i+1}=x_i+1,y_{i+1}=y_i+k$ ，每次令 $y^*=(int)(y_i+0.5)$ ，将像素点 $(x_i,y^*)$ 涂色。
- $|k|>1$ 时， $x$ 、 $y$ 互换，即 $y_{i+1}=y_i+1 $ 。
- 因为 $|k|>1$ 时， $y$ 坐标范围更广，因此令 $y$ 递增求 $x$ 。
2.1.3 中点画线法
-
中点画线法
- 直线一般式方程
- $F(x,y)=0$，$Ax+By+C=0$
- 直线上的点：$F(x,y)=0$
- 直线上方的点：$F(x,y)>0$
- 直线下方的点：$F(x,y)<0$
- 核心思想
- 每次在最大位移方向走一步，而另一个方向是走还是不走取决于中点误差项的判断。
- 假定：$0\leq |k|\leq 1$。因此，每次在 $x$ 方向上加 $1$，$y$ 方向上加 $1$ 或不变需要判断。
- 当 M 在 Q 的下方，即取 $P_u$ 为下一个像素点。否则取 $P_d$ 。
- 直线一般式方程
算法推导过程如下：
-
将 M 带入直线方程， $F(x_m,y_m)=Ax_m+By_m+C$
-
$d_i=F(x_m,y_m)=F(x_i+1,y_i+0.5)=A(x_i+1)+B(y_i+0.5)+C$
-
当 $d_i<0$ 时，M 在 Q 下方，取 $P_u$ .
-
当 $d_i>0$ 时，M 在 Q 上方，取 $P_d $ .
-
当 $d_i=0 $ 时，M 在直线上，取 $P_d$ 或 $P_u$ 均可.
-
$d_i=A(x_i+1)+B(y_i+0.5)+C$，并且
算法递推过程如下：
-
判断下一个点的位置，用增量来表示直线方程
-
$d_0=A+0.5*B$，并且
- 可以将 $d_0$ 改为 $2d_0$ ，避免浮点数运算。
总结：中点画线法将算法提高到整数加法，优于 DDA 算法。
2.1.4 Bresenham 算法
算法特点：提供了一个更一般的算法。该算法不仅有好的效率，而且有更广泛的适用范围。
Bresenham 算法基本思想如下：
-
算法思想是通过各行、各列像素中心构造一组虚拟网格线，按照直线起点到终点的顺序，计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列像素中与此交点最近的像素。
-
假设每次 $x+1$ ， $y$ 的递增 (减) 量为 $0$ 或 $1$ ，它取决于实际直线与最近光栅网格点的距离，这个距离的最大误差为 $0.5$ 。
-
误差项 $d$ 初值 $d_0=0$ ， $d=d+k$ 。一旦 $d\geq1$ ，就把它减去 $1$ ，保证 $d$ 的相对性，且在 $0$ 、 $1$ 之间。
改进 $1$ ：令 $e=d-0.5$
- $e_{0}=-0.5$ ，每走一步有 $e=e+k$，
- $if\ (e>0)\ \ then \ \ e=e-1,\ k=\frac{dy}{dx}$
改进 $2$ ：用 $e*2*\Delta x$ 来替换 $e$
-
$e_0=-\Delta x$ ，每走一步有 $e=e+2*\Delta y$ 。
-
$if\ (e>0) \ \ then \ \ e=e-2\Delta x $
-
算法步骤
-
① 输入直线的两端点 $P_0(x_0,y_0)$ 和 $P_1(x_1,y_1)$ 。
-
② 计算初始值 $\Delta x$ 、 $\Delta y$ 、 $e=-\Delta x$ 、 $x=x_0$ 、 $y=y_0$ 。
-
③ 绘制点 $(x,y)$ 。
-
④ $e$ 更新为 $e+2\Delta y$ ，判断 $e$ 的符号。若 $e>0$ ，则 $(x,y)$ 更新为 $(x+1,y+1)$ ，同时将 $e$ 更新为 $e-2\Delta x$ 。否则 $(x,y) $ 更新为 $(x+1,y)$ 。
-
⑤ 当直线没有画完时，重复步骤 ③、④。否则结束。
2.2 多边形的扫描转换
2.2.1 多边形表示方法
- 顶点表示
- 定义：顶点表示是用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换。
- 缺点：由于没有明确指出哪些像素在多边形内，故不能直接用于面着色。
- 点阵表示
- 定义：点阵表示是用位于多边形内的像素集合来刻画多边形。这种表示丢失了许多几何信息 (如边界、顶点等)，但它却是光栅显示系统显示时所需的表示形式。
- 多边形的扫描转换
- 把多边形的顶点表示转换为点阵表示，即为多边形的扫描转换。
- 多边形分类
- 凸多边形
- 任意两顶点间的连接均在多边形内
- 凸多边形
- 凹多边形
- 任意两顶点间的连线有不在多边形内的
- 含内环的多边形
- 多边形内包含多边形
2.2.2 X-扫描线算法
- 基本思想
- X-扫描线算法填充多边形的基本思想是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作。
- 区间的端点可以通过计算扫描线与多边形边界线的交点获得。
- 算法过程
- 算法核心：按 $X$ 递增顺序排列交点的 $X$ 坐标序列。
- ① 确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大 $y$ 值 $(y_{min}$ 和 $y_{max})$
- ② 从 $y=y_{min}$ 到 $y=y_{max}$ ，每次用一条扫描线进行填充。
- ③ 对一条扫描线填充的过程分为以下四步：
- a. 求交：计算扫描线与多边形各边的交点
- b. 排序：把所有交点按递增顺序进行排序
- c. 交点配对：第一个与第二个，第三个与第四个
- d. 区间填色：把这些相交区间内的像素置成不同于背景色的填充色
- 扫描线与多边形顶点相交时，交点的取舍问题 (交点的个数应保证为偶数个)
- a. 若共享顶点的两条边分别落在扫描线的两边，交点只算 $1$ 个
- b. 若共享顶点的两条边在扫描线的同一边，交点个数为 $0$ 个或 $2$ 个。需要检查两条边另外两个端点的 $y$ 值来判断。
- 两个重要思想
- 扫描线：当处理图形图像时按一条条扫描线处理
- 增量的思想
-
扫描线中的数据结构
- 活性边表 (AET)
- AET：把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点 $x$ 坐标递增的顺序存放在一个链表中。
- 节点内容
- $x$：当前扫描线与边的交点坐标
- $\Delta x$：从当前扫描线到下一条扫描线间 $x$ 的增量，$\Delta x=\frac{1}{k}$
- $y_{max}$：该边所交的最高扫描线的坐标值 $y_{max}$，可以判断何时 “抛弃” 该边
-
- 新边表 (NET)
- 首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个节点，称为一个吊桶，对应多边形覆盖的每一条扫描线。
- NET挂在与该边低端 $y$ 值相同的扫描线桶中，即存放在该扫描线第一次出现的边。
- NET 节点内容
- $y_{max}$：该边的 $y_{max}$
- $x_{min}$：该边较低点的 $x$ 坐标值 $x_{min}$
- $\frac{1}{k}$：该边的斜率$\frac{1}{k}$
-
- 每做一次新的扫描线时，要对已有的边进行三个处理：
- 是否被去除掉
- 如果不被去除，第二就要对它的数据进行更新。所谓更新数据就是要更新它的 $x$ 值，即：$x=x+\frac{1}{k}$
- 看有没有新的边进来，新的边在 NET 里，可以插入排序插进来。
- 优点：避免求交运算。
- 活性边表 (AET)
-
小结
-
扫描线法可以实现已知任意多边形域边界的填充。该填充算法是按扫描线的顺序，计算扫描线与待填充区域的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作。
- 提高算法效率的方法
- 增量的思想
- 连贯性思想
- 构建了一套特殊的数据结构
- 缺点：带填充区域的边界线必须事先知道，因此它的缺点是无法实现对未知边界的区域填充。
-
2.2.3 边缘填充算法
- 基本思想
- 按任意顺序处理多边形的每条边。在处理每条边时，首先求出该边与扫描线的交点，然后将每一条扫描线上交点右方的所有像素取补。多边形的所有边处理完毕之后，填充即完成。
- 算法过程
- 对于每条边，将其上下 $y_{max}$、$y_{min}$ 所构成的矩形区域划分开，取矩形区域的右半部分像素取补。
-
- 特点
- 算法简单，但对于复杂图形，每个像素可能被访问多次。输入和输出量比有效边算法大得多。
2.2.4 栅栏填充算法
- 算法原理
- 栅栏指的是一条过多边形顶点且与扫描线垂直的直线。它把多边形分成两半。在处理每条边与扫描线的交点时，将交点与栅栏之间的像素取补。
2.2.5 边界标志算法
- 算法原理
- 帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的像素打上标志。
- 然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。
- 由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。
2.3 区域填充
2.3.1 区域填充基础概念
- 区域
- 指已经表示成点阵形式的填充图形，是像素的集合。
- 区域填充
- 指将区域内的一点 (常称种子点) 赋予给定颜色，然后将这种颜色扩展到整个区域内的过程。
- 区域可采用内点表示和边界表示两种表示形式。
- 内点表示
- 枚举出区域内部的所有像素，内部的所有像素着同一个颜色，边界像素着与内部像素不同的颜色。
- 边界表示
- 枚举出边界上的所有像素，边界上的所有像素着同一个颜色，内部像素着与边界像素不同的颜色。
- 内点表示
- 连通区域
- 区域填充算法要求区域是连通的，因为只有在连通区域中，才可能将种子点的颜色扩展到区域内的其它点。
- 4向连通区域
- 从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素。
- 8向连通区域
- 从区域上一点出发，可通过八个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。
-
2.3.2 简单四连通种子填充算法
- 种子填充算法原理
- 假设在多边形区域内部有一像素已知，由此出发找到区域内的所有像素，用一定的颜色或灰度来填充。
- 假设区域采用边界定义，即区域边界上所有像素均具有某个特定值，区域内部所有像素均不取这一特定值，而边界外像素则可具有与边界相同的值。
- 种子填充算法实现
- $dfs$ 遍历区域，或者 $bfs$ 遍历，推荐使用 $bfs$ 。
2.3.3 区域填充与多边形扫描转化对比
- 基本思想不同
- 多边形扫描转换是指将多边形的顶点表示转化为点阵表示
- 区域填充只改变区域的填充颜色，不改变区域表示方法
- 基本条件不同
- 在区域填充算法中，要求给定区域内一点作为种子点，然后从这一点根据连通性将新的颜色扩散到整个区域。
- 扫描转换多边形是从多边形的边界 (顶点) 信息出发，利用多种形式的连贯性进行填充的。
2.4 反走样
2.4.1 走样现象
- 走样定义
- “锯齿” 是 “走样” 的一种形式。而走样是光栅显示的一种固有性质。产生走样现象的原因是像素本质上的离散性。
- 走样现象
- ① 光栅图形产生的阶梯形 (锯齿形)
- ② 小物体由于 “走样” 而消失。图形中包含相对微小的物体时，这些物体在静态图形中容易被丢弃或忽略。
- 动画序列中时隐时现，产生闪烁。
- 矩形从左向右移动，当其覆盖某些像素中心时，矩形被显示出来，当没有覆盖像素中心时，矩形不被显示。
-
- 简单地说，如果对一个快速变化的信号采样频率过低，所得样本表示的会是低频变化的信号：原始信号的频率看起来被较低的 “走样” 频率所代替。
2.4.2 反走样技术
- 反走样定义
- 反走样技术，即减少或消除走样效果的技术。
- 采用分辨率更高的显示设备，对解决走样现象有所帮助，因为可以使锯齿相对物体更小一些。
- 非加权区域采样方法
- 原理
- 根据物体的覆盖率计算像素的颜色。覆盖率是指某个像素区域被物体覆盖的比例。
- 方法
- 被多边形覆盖了一半的像素的亮度赋为 $\frac{1}{2}$，覆盖三分之一的像素亮度赋值为 $\frac{1}{3}$，以此类推。
- 缺点
- 像素的亮度与相交区域的面积成正比，而与相交区域落在像素内的位置无关，这仍然会导致锯齿效应。
- 直线条上沿理想直线方向的相邻两个像素有时会有较大的灰度差。
- 原理
- 加权区域采样方法
- 原理
- 将直线段看作是具有一定宽度的狭长矩形。当直线段与像素有交时，根据相交区域与像素中心距离来决定其对像素亮度的贡献。
- 直线段对一个像素的亮度的贡献正比于相交区域与像素中心的距离。设置相交区域面积与像素中心距离的权函数 (高斯函数) 反映相交面积对整个像素亮度的贡献大小。
- 离散计算方法
- 将一个像素划分为 $n=3*3$ 个子像素，加权表可以取为：
- 加权方案：中心子像素的加权是角子像素的 4 倍，是其他像素的 2 倍。对九个子像素的每个网格所计算出的亮度进行平均，然后求出所有中心落于直线段内的子像素。最后计算所有这些子像素对原像素亮度贡献之和。
- 反走样是图形学中的一个根本问题，不可能避免；是图形学中的一个永恒问题。
- 原理
