计算机图形学--光栅图形学算法_基础

一、写在前面

光栅图形学算法是计算机图形学的基础，本篇主要记录光栅图形学基础算法原理及实现，供以后快速复习使用。

二、直线段的扫描转换算法

1.数值微分法（DDA）

（1）简介

DDA算法全称：Digital Differential Analyzer。

引进图形学中一个很重要的思想——增量思想。

（2）原理

直线斜截式方程： $y=kx+b$ 上述方程中包含有乘法运算，可以通过简单变形来消去乘法运算： $\begin{align} y_{i+1}&=kx_{i+1}+b\\ &=k(x_i+1)+b\\ &=kx_i+b+k\\ &=y_i+k \end{align}$

由于像素坐标为整数，而斜率 k 的值可能为小数，所以需要将计算结果增加 0.5 之后取整：y = (int)(y + k + 0.5f)

（3）优缺点

优点：

1.引入了增量思想，将原本的乘法运算变为了增量加法运算，提升了算法效率。

缺点：

1.未考虑最大位移方向。在斜率 k 的值小于 1 的时候，该算法表现正常；当斜率 k 的值远大于 1 的时候，该算法画出来的直线像素点过于稀疏。
2.取整运算，影响算法效率。

（4）实现

下面实现的为改进后的 DDA 算法，算法考虑了最大位移方向：

/*
	DDA：Digital Differential Analyzer 数值微分分析（线段扫描转换算法 / 增量算法）
	重点：寻找最大位移方向，在该方向上逐步得到各像素位置
*/
#include "DDA.h"
#include <math.h>
#include <GLFW/glfw3.h>

inline int DDA::round(const float n)
{
	return (int)(n + 0.5);
}
void DDA::LineDDA(int x0, int y0, int xend, int yend)
{
	int dx = xend - x0, dy = yend - y0, maxStep;
	float xIncrement, yIncrement, x = x0, y = y0;
	//  获取最大位移方向
	if (abs(dx) > abs(dy))
		maxStep = abs(dx);
	else
		maxStep = abs(dy);
	//  增量计算
	xIncrement = float(dx) / float(maxStep);
	yIncrement = float(dy) / float(maxStep);
	//  输出最佳逼近的像素点
	for (int i = 0; i <= maxStep; i++)
	{
		//putpixel(round(x), round(y));
		x += xIncrement;
		y += yIncrement;
	}
}

2.中点画线法

（1）简介

中点画线法考虑了最大位移方向，同时消除了浮点运算。DDA 算法中采用的是直线的斜截式方程，而中点画线算法采用的是直线的一般方程。

（2）原理

直线一般式： $F(x,y)=Ax+By+C \qquad \text {A,B,C为整数}$

将中点 M 代入直线一般式中：

若结果小于 0 则说明中点 M 在直线下方，则应该选取中点 M 上方的点 Pu 作为直线上显示的像素点；（因为 Pu 距离直线较近）

若结果大于 0 则说明中点 M 在直线上方，则应该选取中点 M 下方的点 Pd 作为直线上显示的像素点。

1.当 F(M0) < 0 时，会选取 Pu 作为直线上显示的像素点，继 M0 之后的下一个中点即为 M1，如下图所示：

令 d = F(M)，则： $\begin{align} d&=F(x_i+1,y_i+0.5)\\ &=A(x_i+1)+B(y_i+0.5)+C \end{align}$ 当 d < 0 时，选取 Pu 点。同时可以递推计算下一个 d 的值： $\begin{align} d&=F(x_i+2,y_i+1.5)\\ &=A(x_i+2)+B(y_i+1.5)+C\\ &=F(x_i+1,y_i+0.5)+A+B\\ &=d+A+B \end{align}$

2.当 F(M0) >= 0 时，会选取 Pd 作为直线上显示的像素点，继 M0 之后的下一个中点即为 M1，如下图所示：

当 d >= 0 时，选取 Pd 点。同时可以递推计算下一个 d 的值： $\begin{align} d&=F(x_i+2,y_i+0.5)\\ &=A(x_i+2)+B(y_i+0.5)+C\\ &=F(x_i+1,y_i+0.5)+A\\ &=d+A \end{align}$

3.计算 d 的初始值：

$\begin{align} d_0&=F(x_0+1,y_0+0.5)\\ &=A(x_0+1)+B(y_0+0.5)+C\\ &=F(x_0,y_0)+A+0.5B\\ &=A+0.5B \end{align}$

4.综上：

$\left\{ \begin{align} d_0&=A+0.5B\\ d&=d+A+B \qquad \text {d < 0}\\ d&=d+A \qquad \text {d >= 0} \end{align} \right.$

因为定义了A、B、C为整数，为了消除算法中的浮点运算，所以将A、B、C均乘 2。

如下式： $\left\{ \begin{align} d_0&=2A+B\\ d&=d+2A+2B \qquad \text {d < 0}\\ d&=d+2A \qquad \text {d >= 0} \end{align} \right.$

（3）优缺点

优点：

1.考虑了最大位移方向（对 DDA 的改进）
2.消除了浮点运算（对 DDA 的改进）

缺点：

1.使用的方程是直线的一般式，算法的使用依赖于方程形式，不够通用。

3.Bresenham 算法

（1）简介

Bresenham 发明的，经典图形学算法。结合了 DDA 和中点画线法的优点，不再依赖方程形式，具有通用性，不但可以绘制直线，还可以绘制圆、椭圆等曲线。

（2）原理

下面只讨论 0 <= k <=1 时的情形。

使用直线斜截式。下图中的 k 即为直线斜率，每个格子边长为 1。

随着横坐标 x 依次递增，只需要判断纵坐标 y 是否加 1 即可。

如上图所示，记录一个值，记为 d，x 每增加 1，d 增加 k，当 d 超过 1 的时候取超过 1 的小数部分。

此时要判断 y 是否加 1，只需判断 d 值是否大于 0.5。若 d > 0.5，则 y 加 1；若 d <= 0.5，则 y 不变。

d 的初始值 d0 = 0。

综上： $\begin{align} d_0&=0\\ d&=d+k\\ x_{i+1}&=x_i+1\\ y_{i+1}&=y_i \qquad \text {d <= 0.5}\\ y_{i+1}&=y_i+1 \qquad \text {d > 0.5 d = d - 1} \end{align}$ 为了避免 d 与浮点数比较，令 e = d - 0.5： $\begin{align} e_0&=-0.5\\ e&=e+k\\ x_{i+1}&=x_i+1\\ y_{i+1}&=y_i \qquad \text {e <= 0}\\ y_{i+1}&=y_i+1 \qquad \text {e > 0 e = e - 1} \end{align}$ 因为斜率 k = delta(y) / delta(x)，为了避免浮点运算，将上式乘以 2 倍的 delta(x)： $\begin{align} e_0&=-\Delta{x}\\ e&=e+2\Delta{y}\\ x_{i+1}&=x_i+1\\ y_{i+1}&=y_i \qquad \text {e <= 0}\\ y_{i+1}&=y_i+1 \qquad \text {e > 0 e = e - 2delta(x)} \end{align}$ 其中 delta(y) 和 delta(x) 均为所绘制的直线的两个端点的坐标之差。

如此一来，便消除了所有的浮点运算。

（3）优缺点

优点：

1.集合了 DDA 和中点画线法的优点。
2.直线的绘制不依赖于所使用的的方程形式，只需要知道直线两端点坐标即可。（对 中点画线法 的改进）

（4）实现

下面只实现了 0 <= k <=1 时的情形：

#include "Bresenham.h"
#include <math.h>
//  0<=k<=1时：
void Bresenham::LineBrecenham(int x0, int y0, int xend, int yend)
{
	int e, dx = xend - x0, dy = yend - y0, x = x0, y = y0;
	e = -dx;
	while (x < xend)
	{
		e += 2 * dy;
		x++;
		if (e > 0)
		{
			y++;
			e -= 2 * dx;
		}
		//putpixel(round(x), round(y));
	}
}

4.总结

DDA 算法：把效率提高到了每步只做一个加法
中点画线算法：进一步把效率提高到每步只做一个整数加法
Bresenham 算法：提供了一个更一般的算法，该算法不仅有好的效率，而且有更广泛的适用范围。

三、多边形的扫描转换与区域填充算法

多边形类型：

凸多边形：任意两点间的连线均在多边形内
凹多边形：存在两点连线不在多边形内的
含内环的多边形：多边形内包含多边形

多边形的扫描转换目的：已知多边形顶点，如何找到内部点阵。

1.X 扫描线算法

（1）简介

按照扫描线顺序，计算扫描线与多边形的相交区间，然后填充指定颜色。

（2）原理

X 扫描线为平行于 X 轴的直线；X 扫描线扫描是由下往上进行扫描；算法核心是按 X 递增顺序排列交点的 X 坐标序列。

步骤：

1.确定多边形所占有的最大扫描线数，得到多边形顶点纵坐标 y 的最小和最大值（ymin 和 ymax）

如上图，由 P2 和 P4 点可知 ymin = 1，由 P7 点可知 ymax = 12。所以最大扫描线数为：12 = 12 - 1 + 1。
2.从 y = ymin 到 y = ymax，每次用一条扫描线进行填充。
3.对一条扫描线进行填充的过程可分为四个步骤：
- a.求交：计算扫描线与多边形各边的交点
  
  此处可优化的点：扫描线只需要与有效边进行求交运算，而不是所有的边。
- b.排序：把所有交点按 X 坐标的递增顺序进行排序
  
  把上图中 P1P2 与 X 扫描线的交点称为第一个交点，则第二个交点为 P2P3 与 X 扫描线的交点，第三个交点为 P3P4…，第四个交点为 P4P5…。
- c.交点配对：第一个交点与第二个交点，第三个交点与第四个交点。
- d.区间填色：填充像素颜色。
4.注意：当 X 扫描线与多边形顶点相交的时候，此时算作几个交点？

记 n 为该顶点与 X 扫描线相交的上方的边数：
- 如 P2 上方边数有 2 条：P1P2 和 P2P3
- P1 上方的边数有 1 条：P1P7
- P3 上方的边数为有 0 条
当 n 为 1 时，算作 1 个交点；当 n 为 0 时，算作 0 个交点；当 n 为 2 时，算作 2 个交点。

（3）优缺点

缺点：

1.效率不高，求交的计算量太大。

2.改进的 X 扫描线算法

（1）简介

该算法的重要意义：提出了图形学中的两个重要思想：

1.扫描线：当处理图形时按一条条扫描线处理
2.增量思想

（2）原理

改进：

1.在处理一条扫描线时，仅对与它相交的多边形的边（有效边）进行求交运算。
2.考虑扫描线的连贯性。

扫描线的连贯性：当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序很可能相同或相似。

如上图，蓝色扫描线与红色扫描线与有效边的交点顺序就是相同的，都是先与 P1P4 边相交，再与 P2P3 边相交。
3.考虑多边形的连贯性。

多边形的连贯性：当某条边与当前扫描线相交时，很可能也与下一条扫描线相交。

如上图，边 P1P4 与蓝色扫描线相交，同时也与红色扫描线相交。
4.为了避免求交运算，引入特殊的数据结构：
- （1）活性边表（AET）：把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点 x 坐标递增的顺序存放在一个链表中。
- （2）结点内容：
  - x：当前扫描线与边的交点坐标
  - delta(x)：从当前扫描线到下一条扫描线间 x 的增量
    
    x 增量的求法见下（3）。
  - ymax：该边所交的最高扫描线的坐标值 ymax
    
    通过它可以知道何时可以将该边从活性边表中删除。（详解，见下（4））
  - next 指针：指向下一个结点
- （3）随着扫描线的移动，扫描线与多边形的交点和上一次交点相关，如下图所示：
  
  令直线斜率为 k：
  $\begin{align} k&=\frac{\Delta{y}}{\Delta{x}}\\ &=\frac{y_{i+1}-y_i}{x_{i+1}-x_i} \end{align}$
  因为扫描线每次向上移动为 y 轴坐标加 1，即相邻扫描线 y 坐标之差为 1。
  
  变形可得：
  $\begin{align} x_{i+1}-x_i&=\frac{1}{k}\\ x_{i+1}&=x_i+\frac{1}{k}\\ \Delta{x}&=\frac{1}{k} \end{align}$
- （4）需要知道一条边何时不再与下一条扫描线相交，以便及时将该边从活性边表中删除，避免与下一条扫描线做无用的求交运算。
  
  该边所交的最高扫描线的坐标值 ymax，当下一条扫描线的 y 值大于该边的 ymax 的时候，将该边从活性边表中删除。
  
  活性边表的例子，当前扫描线为图中红线时候的活性边表如下图所示：
  
  注意：活性边表 是需要排序的：按照交点 x 坐标由小到大排序。
5.为了方便 活性边表 的建立与更新，构造 新边表（NET），用于存放多边形边的信息。
- （1）构造一个 纵向链表 ：链表长度为多边形所占有的最大扫描线数，如上图，纵向链表长度即为：10 = 10 - 1 + 1。
  
  链表的每一个结点称为一个吊桶，每个吊桶对应一条扫描线。
- （2）新边表 NET ：由多个链表构成，链表中的每个结点都包含对应边的信息。结点的结构：
  - ymax ：该边所包含的所有像素点中纵坐标的最大值。
  - xmin ：该边所包含的所有像素点中纵坐标最小的像素点的横坐标的值。
  - 1/k ：该边斜率的倒数。
  - next ：指向下一个结点的指针。下一个结点对应的边与当前边拥有相同的 xmin 。
- （3）新边表 NET 例子：新边表包含一个纵向链表以及四个单链表
6.新的扫描线进行扫描时，需要经过 3 步：
- （1）将 新边表 NET 中和扫描线对应的边结点（单链表）用插入排序法插入 活性边表 AET 中。
- （2）查看 活性边表 AET 中是否有边需要被删除。
- （3）将 活性边表 AET 中各结点的 x 值递增 delta(x) = 1/斜率。

（3）优缺点

优点：

1.提高了算法效率，引进了：
- 增量思想
- 连贯性思想
- 构建了一套特殊的数据结构（活性边表 AET 和新边表 NET）
2.可以实现对任意类型的多边形的区域填充（凸、凹、含内环的多边形）

缺点：

1.无法实现对未知边界的区域填充。

（4）伪代码

3.边缘填充算法

（1）简介

对多边形每条边逐边向右取补。

（2）原理

流程如下图：

（3）优缺点

优点：

1.算法简单

缺点：

1.对于复杂图形，被重复访问的像素点很多

（4）改进：可以使用栅栏填充算法

（略…）

4.边标志算法

（1）简介

先画边界后填色。

基本思想：

用一种特殊的颜色在帧缓冲器中将多边形的边界勾画出来
将着色的像素点依 x 坐标递增的顺序两两配对
将每一对像素所构成的扫描线区间内的所有像素置为填充色

（2）原理

分为两个步骤：

Step1：打标记

对多边形的每条边进行直线扫描转换（将多边形边界所经过的像素打上标记）

此处打标记原理同 X 扫描线算法中的 “当 X 扫描线与多边形顶点相交的时候，此时算作几个交点？”一样。
Step2：填充

为每个像素点设置一个 bool 变量： Inside ，表示该像素点是否在多边形内部，是否需要填色。

Inside 初始值为 false；每当遇到标记点时就取反，然后根据 Inside 的值进行颜色填充（为 true 则填充，反之不填充）

如下图所示：

（3）优缺点

优点：

1.对每个像素仅访问一次，避免对同一像素的大量重复赋值。（对 边缘填充算法 和 栅栏填充算法 的改进）
2.使用软件实现该算法，速度与改进后的 X 扫描线算法速度相当；但用硬件实现，速度大大提高。

缺点：

1.仍然需逐条扫描线地对帧缓存中的元素进行搜索和比较。

5.区域填充算法

（1）简介

区域：已经表示成点阵形式的填充图形，是像素的集合。包含有内点和边界点。

区域填充：将区域内的一点（种子点）赋予给定的颜色，然后将该颜色扩展到整个区域内的过程。要求区域是连通的。

区域分为：四向连通区域和八向连通区域：

（2）原理

简单的四连通种子填充算法（区域填充递归算法）：

（3）优缺点

优点：

1.递归实现，算法简单。

缺点：

1.栈结构占空间
2.部分像素会多次入栈，降低算法效率
3.递归效率低，进栈/出栈操作费时费内存。

改进：区域填充的扫描线算法

四、反走样算法

1.简介

（1）走样（Aliasing）

走样是光栅显示的一种固有性质。走样现象产生的原因是像素的离散性。

（2）走样现象

a.光栅图形产生的锯齿形

b.微小物体的忽略或时隐时现

矩形从左向右移动，当其覆盖某些像素中心时，矩形被显示出来；当没有覆盖像素中心时，矩形不被显示。

（3）反走样

方法一：提升硬件

通过提高 n 倍分辨率的方式来降低锯齿感，其代价是 n^2 倍存储器和扫描转换时间。

此法代价太大，不可取。

方法二：“模糊”化以消除锯齿感

使用相关反走样算法，模糊化锯齿边缘的像素，以达到降低锯齿感的作用。

过取样 / 后滤波（supersampling）
区域取样 / 前滤波（area sampling）

反走样效果展示：（右图为反走样之后的）

2.过取样 / 后滤波（supersampling）

（1）简单过取样

原理

在高分辨率下取样计算，然后在低分辨率（原分辨率）下对像素属性取简单平均。

假设原显示分辨率为 m*n ，现在将原分辨率细分为 2m*2n个子像素。现在一个像素点包含 4 个子像素，然后对理想直线穿过的子像素取简单平均。

如下图，1 号像素点的亮度 = 1 / 4；2 号像素点的亮度 = 2 /4……

优缺点

优点：

简单

缺点：

相邻像素之间的颜色不会互相影响，会产生色泽不均匀的问题。
采用的是简单平均，得到的抗锯齿效果很轻微。

（2）重叠过取样

原理

在高分辨率下取样计算，然后在低分辨率（原分辨率）下对像素属性取简单平均。

假设原显示分辨率为 m*n ，现在将原分辨率细分为 (2m + 1)*(2n + 1)个子像素。现在一个像素点包含 9 个子像素，并且相邻像素点之间会有 3 个子像素重合，即相邻像素之间的颜色会互相影响，此法是对 简单过取样 的一种改进。最后对理想直线穿过的子像素取简单平均。

优缺点

优点：

1.相邻像素之间的颜色会互相影响，不会产生色泽不均匀的问题。（对 简单过取样 的改进）

缺点：

1.采用的是简单平均，得到的抗锯齿效果很轻微。（略好于 简单过取样）

（3）基于加权模板的过取样

原理

理论上理想直线越靠近像素中心，该像素点应该越亮。即子像素中心部分对整个像素的亮度贡献应该最大。

在 重叠过取样 的基础上，为 9 个子像素分配权重值，将简单平均变为加权平均。权重值模板如下图：

优缺点

优点

1.使用模板进行加权平均，得到的抗锯齿效果好于简单平均。（好于 重叠过取样）

缺点

1.权值设定影响反走样效果。

3.区域取样 / 前滤波（area sampling）

过取样依据的是理想直线，但真实情况显示的往往不是直线而是一个有宽度的矩形，所以对矩形区域的取样称作区域取样。

每个 “像素点的亮度” 与 “像素点和区域相交的面积” 成正比。以此产生模糊边界来消除锯齿感。

此时，关键问题在于计算相交区域的面积。面积计算方式：

方法一：精确计算

通过相交的精确起点位置 D 和直线斜率 k 来计算相交区域的面积，如下图所示：
方法二：近似计算（类似于 过取样）
- Step1：将屏幕像素细分成 n 个更小的子像素
- Step2：计算落在相交区域内的子像素个数 m
- Step3：相交区域近似面积 = m / n

（1）简单的区域取样

原理

同上述的方法二。

简单的区域取样 又叫做 立方体滤波 取样，各相交区域对亮度贡献均相同（= 立方体高度）。

优缺点

优点：

1.简单

缺点：

1.相交区域越靠近像素点的中心，对像素点亮度贡献应该更大，而不是均匀的。

（2）加权区域取样

原理

接近理想直线的像素应当分配更多灰度值。
相邻两像素的滤波器相交，有利于缩小直线条上相邻像素的灰度差。

可以采用区别于 立方体滤波 的 圆锥滤波 和 高斯滤波：

此时不再是计算区域面积，而是对体积进行积分。

其中圆锥滤波：

优缺点

优点：

1.相交区域越靠近像素点的中心，对像素点亮度贡献更大。（对 简单的区域取样 的改进）
2.相邻两像素的滤波器相交，使得相邻像素之间的颜色会互相影响，不会产生色泽不均匀的问题。

缺点：

1.需要积分计算体积，比较复杂。

五、裁剪算法

裁剪算法有 点的裁剪 和 直线段的裁剪 。点的裁剪 需要判断图形中的每个点是否在窗口内，比较费时；通常使用 直线段的裁剪 。

1.Cohen-Sutherland 算法

（1）简介

又称 编码裁剪算法

（2）原理

对每个直线段分三种情况处理：

1.直线两端点均在裁剪窗口内：“简取”
2.直线两端点均在裁剪窗口外，且满足一定条件：“简弃”
3.除上述两种情况之外的情况：需要将直线和裁剪窗口边界求交，然后分段判断

编码规则：

为每个端点赋以四位二进制编码：D3D2D1D0

1.若 x < xleft，D0 = 1；否则 D0 = 0

D0 对应裁剪窗口的左边界
2.若 x > xright，D1 = 1；否则 D1 = 0

D1 对应裁剪窗口的右边界
3.若 y < ybottom，D2 = 1；否则 D2 = 0

D2 对应裁剪窗口的下边界
4.若 y > ytop，D3 = 1；否则 D3 = 0

D3 对应裁剪窗口的上边界

裁剪窗口及其延长线将平面划分成了 9 个区域，编码之后如下图：

直线的裁剪步骤：

1.为直线的端点编码：code1 和 code2
2.对 code1 和 code2 取位运算：
- **或运算 **[^或运算]：若 code1 code2 = 0，则简取
- 与运算 & **[^与运算]：若 code1 & code2 ≠ 0，则 **简弃
3.若无法直接简取或简弃，则按顺序与裁剪窗口边界求交（顺序一般为：左右下上）。交点与端点构成新的线段，对新的线段重复步骤 1 和步骤 2。

（3）优缺点

优点：

1.编码思想作用很大
2.在线段完全可见、线段完全不可见的两种情况下，该算法效率很高。

缺点：

1.若线段处于下图所示位置，则该算法效率很低。需要对裁剪窗口四条边分别求交，而此操作实际上并无作用，因为最终该线段明显会被裁减掉。

2.中点分割法

（1）简介

同 Cohen-Sutherland 一样，需要进行编码；也将线段与裁剪窗口的关系分为三种。

中点分割算法的核心思想：通过 二分逼近 来确定直线与裁剪窗口的交点。

会设定一个误差值，当中点与裁剪窗口边界的坐标值在规定误差范围内时，即确定了直线与裁剪窗口的交点。

3.Liang-Barsky 算法

（1）简介

著名的直线裁剪算法，在大多数情况下该算法裁剪效率优于 Cohen-Sutherland 算法。

（2）原理

1.将直线看做有向线段
2.使用参数方程表示直线 $x = x_{1} + u * (x_{2} - x_{1})\\ y = y_{1} + u * (y_{2} - y_{1})$
3.将裁剪窗口的四条边（包括其延长线）分为：入边、出边
4.通过不等式判断线段上的点是否在裁剪窗口内： $\begin{align} x_{left} &≤ x_{1} + u * \Delta{x} ≤ x_{right}\\ y_{bottom} &≤ y_{1} + u * \Delta{y} ≤ y_{top} \end{align}$ 变形： $\begin{align} u * (-\Delta{x}) &≤ x_{1} - x_{left}\\ u * \Delta{x} &≤ x_{right} - x_{1}\\ u * (-\Delta{y}) &≤ y_{1} - y_{bottom}\\ u * \Delta{y} &≤ y_{top} - y_{1} \end{align}$

令： $\begin{align} p_{1} &= -\Delta{x}\\ p_{2} &= \Delta{x}\\ p_{3} &= -\Delta{y}\\ p_{4} &= \Delta{y}\\ q_{1} &= x_{1} - x_{left}\\ q_{2} &= x_{right} - x_{1}\\ q_{3} &= y_{1} - y_{bottom}\\ q_{4} &= y_{top} - y_{1} \end{align}$ 得： $u * p_{k} ≤ q_{k} \qquad \text{k∈{1,2,3,4}}$

k = 1,2,3,4 对应于 左、右、下、上 边界
5.直线与裁剪窗口边界（包含延长线）共有四个交点

如下图灰色圆点：

四个交点对应的参数 u 的值如下计算 $u_{k} = \frac{q_{k}}{p_{k}}\qquad p_{k}≠0,k∈\text1\\$

由 4. 知：
- pk < 0 时：对应入边交点（2个）
- pk > 0 时：对应出边交点（2个）
6.显示在裁剪窗口内的线段端点

端点对应的 u 值如下计算： $\begin{align} u_{max} &= max(0,u_{k}|_{p_{k}<0},u_{k}|_{p_{k}<0})\\ u_{min} &= min(u_{k}|_{p_{k}>0},u_{k}|_{p_{k}>0},1) \end{align}$ 最后代回参数方程计算坐标。

（3）优缺点

优点：

1.引入了入边和出边的思想
2.引入了 有向线段 思想，将线段的裁剪简化为了射线的裁剪
3.在多数情况下，该算法有较好的效率

缺点：

1.只适用于矩形窗口裁剪

六、消隐算法

消隐算法按消隐空间分类：

（1）物体空间的消隐算法
- Roberts 算法
- 光线投射法
（2）图像空间的消隐算法（主流消隐算法）
- Z-Buffer 消隐算法
- 区间扫描线算法
- 区域子分割算法

1.Z-Buffer 消隐算法

（1）简介

能跟踪屏幕上每个像素深度的算法，该算法使计算机生成复杂图形成为可能。

（2）原理

使用两个数组作为缓冲器：

1.帧缓冲器（属性数组）

intensity(x,y)：存储每个可见像素的颜色
2.深度缓冲（深度数组）

depth(x,y)：存储每个可见像素的深度值（距离屏幕越近深度值越大，深度值大的覆盖深度值小的）

首先将 Z-Buffer 中各单元的初始值设置为最小值，当需要改变某个像素颜色的时候，首先检查当前多边形的深度值是否大于该像素点原来的深度值。若大于，则说明当前多边形更靠近观察点，可以将其颜色值写入帧缓冲器中，同时更新当前像素点的深度值。

步骤：

（3）优缺点

优点：

1.算法简单
2.可自定义绘制物体顺序，有利于硬件实现

缺点：

1.使用了深度缓冲，占用较大空间
2.没有利用图形的相关性与连续性（严重缺陷，不利于提高效率）
3.像素级别的消隐算法，效率低

（4）改进

使用一个 深度缓冲变量 来替换 深度缓冲数组 减小算法的空间消耗。

步骤：

（5）改进后的问题

改进后的算法虽然减小了空间消耗，但是判断像素点(i , j)是否在投影多边形内是一个比较复杂的问题。

（6）点与多边形的包含性检测

射线法

过该点向y轴负方向做射线：

交点个数为奇数：点在内部
交点个数为偶数：点在外部
射线过顶点：（左开右闭）
- 顶点左边有边：计数
- 顶点右边有边：不计数

射线法的计算量很大，而且结果依赖于计算精度，不够稳定。

弧长法（以顶点符号为基础的弧长累加法）

假设 p 为被测点，以 p 为原点做平面直角坐标系，各顶点所属象限有符号如下：

不计算实际弧长，而是根据顶点到顶点的象限变化得到弧长值。逆时针为正，顺时针为负，每跨越一个象限增加 0.5π。

例如：

第一象限到第一象限：弧长记为 0
第一象限到第二象限：弧长记为 0.5π
第二象限到第一象限：弧长记为 -0.5π
第一象限到第三象限：弧长记为 π
第一象限到第四象限：弧长记为 -0.5π

图中点p 的弧长累计值 = p1p2 + p2p3 + p3p4 + p4p5 + p5p1

= 0.5π + 0.5π + 0.5π + 0π + 0.5π

= 2π

弧长累计值：

为 0 ：点在多边形外部
为 2π：点在多边形内部
为 π：点在多边形上

该方法的计算量显著减小

2.区间扫描线算法

3.区域子分割算法（Warnock 算法）

将物体投影到全屏幕窗口，然后递归分割窗口，直到窗口内目标足够简单，可以显示为止。

计算机图形学--光栅图形学算法_基础

目录

一、写在前面

二、直线段的扫描转换算法

1.数值微分法（DDA）

（1）简介

（2）原理

（3）优缺点

（4）实现

2.中点画线法

（1）简介

（2）原理

（3）优缺点

3.Bresenham 算法

（1）简介

（2）原理

（3）优缺点

（4）实现

4.总结

三、多边形的扫描转换与区域填充算法

1.X 扫描线算法

（1）简介

（2）原理

（3）优缺点

2.改进的 X 扫描线算法

（1）简介

（2）原理

（3）优缺点

（4）伪代码

3.边缘填充算法

（1）简介

（2）原理

（3）优缺点

（4）改进：可以使用栅栏填充算法

4.边标志算法

（1）简介

（2）原理

（3）优缺点

5.区域填充算法

（1）简介

（2）原理

（3）优缺点

四、反走样算法

1.简介

（1）走样（Aliasing）

（2）走样现象

a.光栅图形产生的锯齿形

b.微小物体的忽略或时隐时现

（3）反走样

2.过取样 / 后滤波（supersampling）

（1）简单过取样

原理

优缺点

（2）重叠过取样

原理

优缺点

（3）基于加权模板的过取样

原理

优缺点

3.区域取样 / 前滤波（area sampling）

（1）简单的区域取样

原理

优缺点

（2）加权区域取样

原理

优缺点

五、裁剪算法

1.Cohen-Sutherland 算法

（1）简介

（2）原理

（3）优缺点

2.中点分割法

（1）简介

3.Liang-Barsky 算法

（1）简介

（2）原理

（3）优缺点

六、消隐算法

1.Z-Buffer 消隐算法

（1）简介