计算机图形学 - 快速指南

计算机图形学 - 基础

计算机图形学是用编程在电脑屏幕上绘画的艺术。它涉及数据的计算、创建和处理。换句话说，我们可以说计算机图形学是用于图像生成和处理的渲染工具。

阴极射线管

图形系统中的主要输出设备是视频监视器。视频监视器的主要元件是阴极射线管 (CRT)，如下图所示。

CRT 的工作原理很简单：

电子枪发射电子束（阴极射线）。
电子束穿过聚焦和偏转系统，将其引导到磷光涂层屏幕上的指定位置。
当电子束撞击屏幕时，磷光体在电子束接触的每个位置发出一个小光点。
它通过快速将电子束重新导回相同的屏幕点来重绘图像。

我们可以通过两种方式（随机扫描和光栅扫描）在屏幕上显示物体。

光栅扫描

在光栅扫描系统中，电子束逐行从上到下扫描屏幕。当电子束移动到每一行时，光束强度会打开和关闭以创建发光点的图案。

图像定义存储在称为刷新缓冲区或帧缓冲区的内存区域中。该内存区域保存所有屏幕点的强度值集。然后从刷新缓冲区检索存储的强度值，并逐行（扫描线）“绘制”到屏幕上，如下图所示。

每个屏幕点被称为像素 (picture element) 或pel。在每条扫描线结束时，电子束返回到屏幕的左侧以开始显示下一条扫描线。

随机扫描（矢量扫描）

在这种技术中，电子束仅指向屏幕上要绘制图像的部分，而不是像光栅扫描那样从左到右、从上到下扫描。它也称为矢量显示、笔划写入显示或书法显示。

图像定义存储为一组线描命令，位于称为刷新显示文件的内存区域中。要显示指定的图像，系统会循环遍历显示文件中的命令集，依次绘制每个组件线。处理完所有线描命令后，系统会循环回到列表中的第一条线命令。

随机扫描显示器设计为每秒绘制图像的所有组件线 30 到 60 次。

计算机图形学的应用

计算机图形学有许多应用，其中一些列在下面：

计算机图形用户界面 (GUI) - 一种图形化的、面向鼠标的范例，允许用户与计算机交互。
商务演示图形 - “一图胜千言”。
地图绘制 - 绘制地图。
天气图 - 实时地图绘制，符号表示。
卫星成像 - 地球图像。
照片增强 - 锐化模糊照片。
医学成像 - MRI、CAT 扫描等 - 非侵入性内部检查。
工程图纸 - 机械、电气、土木等 - 取代过去的蓝图。
排版 - 在出版物中使用字符图像 - 取代过去的铅字。
建筑 - 施工图纸、外观草图 - 取代过去的蓝图和手绘图。
艺术 - 计算机为艺术家提供了一种新的媒介。
培训 - 飞行模拟器、计算机辅助教学等。
娱乐 - 电影和游戏。
仿真和建模 - 取代物理建模和模拟

直线生成算法

一条线连接两点。它是图形中的基本元素。要绘制一条线，您需要两点，您可以在这两点之间绘制一条线。在以下三种算法中，我们将线的其中一点表示为$X_{0}, Y_{0}$，线的另一点表示为$X_{1}, Y_{1}$。

DDA 算法

数字微分分析仪 (DDA) 算法是一种简单的直线生成算法，这里将逐步解释。

步骤 1 - 获取两端点的输入 $(X_{0}, Y_{0})$ 和 $(X_{1}, Y_{1})$。

步骤 2 - 计算两端点之间的差值。

dx = X₁ - X₀
dy = Y₁ - Y₀

步骤 3 - 基于步骤 2 中计算出的差值，您需要确定放置像素的步数。如果 dx > dy，则需要在 x 坐标上增加更多步数；否则在 y 坐标上增加更多步数。

if (absolute(dx) > absolute(dy))
   Steps = absolute(dx);
else
   Steps = absolute(dy);

步骤 4 - 计算 x 坐标和 y 坐标的增量。

Xincrement = dx / (float) steps;
Yincrement = dy / (float) steps;

步骤 5 - 通过连续递增 x 和 y 坐标来放置像素，并完成直线的绘制。

for(int v=0; v < Steps; v++)
{
   x = x + Xincrement;
   y = y + Yincrement;
   putpixel(Round(x), Round(y));
}

Bresenham 直线生成算法

Bresenham 算法是另一种增量扫描转换算法。该算法的一大优点是它只使用整数计算。沿 x 轴以单位间隔移动，并在每一步中选择两个不同的 y 坐标。

例如，如下图所示，从位置 (2, 3) 您需要在 (3, 3) 和 (3, 4) 之间进行选择。您希望选择更靠近原始直线的点。

在样本位置 $X_{k}+1$，与数学直线的垂直距离标记为 $d_{upper}$ 和 $d_{lower}$。

从上图中，数学直线上 $x_{k}+1$ 处的 y 坐标为：

Y = m($X_{k}$+1) + b

所以，$d_{upper}$ 和 $d_{lower}$ 给出如下：

$$d_{lower} = y-y_{k}$$

$$= m(X_{k} + 1) + b - Y_{k}$$

和

$$d_{upper} = (y_{k} + 1) - y$$

$= Y_{k} + 1 - m (X_{k} + 1) - b$

您可以使用这些信息来做出关于哪个像素更靠近数学直线的简单决策。这个简单的决策是基于两个像素位置之间的差异。

$$d_{lower} - d_{upper} = 2m(x_{k} + 1) - 2y_{k} + 2b - 1$$

让我们用 dy/dx 代替 m，其中 dx 和 dy 是端点之间的差值。

$$dx (d_{lower} - d_{upper}) =dx(2\frac{\mathrm{d} y}{\mathrm{d} x}(x_{k} + 1) - 2y_{k} + 2b - 1)$$

$$ = 2dy.x_{k} - 2dx.y_{k} + 2dy + 2dx(2b-1)$$

$$ = 2dy.x_{k} - 2dx.y_{k} + C$$

所以，直线上第 k 步的决策参数 $P_{k}$ 由下式给出：

$$p_{k} = dx(d_{lower} - d_{upper})$$

$$ = 2dy.x_{k} - 2dx.y_{k} + C$$

决策参数 $P_{k}$ 的符号与 $d_{lower} - d_{upper}$ 的符号相同。

如果 $p_{k}$ 为负，则选择下像素，否则选择上像素。

记住，坐标变化沿 x 轴以单位步长发生，因此您可以使用整数计算完成所有操作。在步骤 k+1 处，决策参数给出如下：

$$p_{k +1} = 2dy.x_{k + 1} - 2dx.y_{k + 1} + C$$

从中减去 $p_{k}$，我们得到：

$$p_{k + 1} - p_{k} = 2dy(x_{k + 1} - x_{k}) - 2dx(y_{k + 1} - y_{k})$$

但是，$x_{k+1}$ 与 $x_{k+1}$ 相同。所以：

$$p_{k+1} = p_{k} + 2dy - 2dx(y_{k+1} - y_{k})$$

其中，$Y_{k+1} – Y_{k}$ 为 0 或 1，取决于 $P_{k}$ 的符号。

在 $(x_{0}, y_{0})$ 处计算的第一个决策参数 $p_{0}$ 给出如下：

$$p_{0} = 2dy - dx$$

现在，记住以上所有要点和计算，以下是斜率 m < 1 的 Bresenham 算法：

步骤 1 - 输入直线的两个端点，将左端点存储在 $(x_{0}, y_{0})$ 中。

步骤 2 - 绘制点 $(x_{0}, y_{0})$。

步骤 3 - 计算常数 dx、dy、2dy 和 (2dy – 2dx)，并获得决策参数的第一个值：

$$p_{0} = 2dy - dx$$

步骤 4 - 沿着直线的每个 $X_{k}$（从 k = 0 开始），执行以下测试：

如果 $p_{k}$ < 0，则下一个要绘制的点是 $(x_{k}+1, y_{k})$，并且

$$p_{k+1} = p_{k} + 2dy$$ 否则，

$$(x_{k}, y_{k}+1)$$

$$p_{k+1} = p_{k} + 2dy - 2dx$$

步骤 5 - 重复步骤 4 (dx – 1) 次。

对于 m > 1，确定每次递增 y 时是否需要递增 x。

求解后，决策参数 $P_{k}$ 的方程非常相似，只是方程中的 x 和 y 会互换。

中点算法

中点算法是由 Bresenham 提出的，后来由 Pitteway 和 Van Aken 修改。假设您已经将点 P 放置在 (x, y) 坐标处，并且直线的斜率为 0 ≤ k ≤ 1，如下图所示。

现在您需要决定是否将下一个点放在 E 或 N。这可以通过识别最接近点 N 或 E 的交点 Q 来选择。如果交点 Q 最接近点 N，则将 N 视为下一个点；否则为 E。

要确定这一点，首先计算中点 M(x+1, y + ½)。如果直线与连接 E 和 N 的垂直线的交点 Q 在 M 以下，则取 E 为下一个点；否则取 N 为下一个点。

为了检查这一点，我们需要考虑隐式方程：

F(x,y) = mx + b - y

对于正 m，在任何给定的 X 处，

如果 y 在直线上，则 F(x, y) = 0
如果 y 在直线上方，则 F(x, y) < 0
如果 y 在直线下方，则 F(x, y) > 0

圆生成算法

在屏幕上绘制圆圈比绘制直线复杂一些。有两种流行的圆生成算法：Bresenham 算法和中点圆算法。这些算法基于确定绘制圆所需后续点的思想。让我们详细讨论这些算法：

圆的方程为 $X^{2} + Y^{2} = r^{2}$，其中 r 为半径。

Bresenham 算法

我们无法在光栅显示器上显示连续的弧线。相反，我们必须选择最接近的像素位置来完成弧线。

从下图可以看出，我们已将像素放在 (X, Y) 位置，现在需要决定将下一个像素放在哪里：N (X+1, Y) 或 S (X+1, Y-1)。

这可以通过决策参数 d 来决定。

如果 d <= 0，则选择 N(X+1, Y) 作为下一个像素。
如果 d > 0，则选择 S(X+1, Y-1) 作为下一个像素。

算法

步骤 1 - 获取圆心坐标和半径，并分别将其存储在 x、y 和 R 中。设置 P=0 和 Q=R。

步骤 2 - 设置决策参数 D = 3 – 2R。

步骤 3 - 当 P ≤ Q 时，重复步骤 4 到步骤 8。

步骤 4 - 调用 Draw Circle (X, Y, P, Q)。

步骤 5 - 增加 P 的值。

步骤 6 - 如果 D < 0，则 D = D + 4P + 6。

步骤 7 - 否则设置 R = R - 1，D = D + 4(P-Q) + 10。

步骤 8 − 调用 Draw Circle (X, Y, P, Q) 函数。

Draw Circle Method(X, Y, P, Q).

Call Putpixel (X + P, Y + Q).
Call Putpixel (X - P, Y + Q).
Call Putpixel (X + P, Y - Q).
Call Putpixel (X - P, Y - Q).
Call Putpixel (X + Q, Y + P).
Call Putpixel (X - Q, Y + P).
Call Putpixel (X + Q, Y - P).
Call Putpixel (X - Q, Y - P).

中点算法

步骤 1 − 输入半径 r 和圆心 $(x_{c,} y_{c})$，并得到以原点为中心的圆周上的第一个点，方法为：

(x₀, y₀) = (0, r)

步骤 2 − 计算决策参数的初始值：

$P_{0}$ = 5/4 – r (参见下面的描述以了解此公式的简化方法。)

f(x, y) = x² + y² - r² = 0

f(x_i - 1/2 + e, y_i + 1)
        = (x_i - 1/2 + e)² + (y_i + 1)² - r² 
        = (x_i- 1/2)² + (y_i + 1)² - r² + 2(x_i - 1/2)e + e²
        = f(x_i - 1/2, y_i + 1) + 2(x_i - 1/2)e + e² = 0

Let d_i = f(x_i - 1/2, y_i + 1) = -2(x_i - 1/2)e - e²
Thus,

If e < 0 then di > 0 so choose point S = (x_i - 1, y_i + 1).
d_i+1    = f(x_i - 1 - 1/2, y_i + 1 + 1) = ((x_i - 1/2) - 1)² + ((y_i + 1) + 1)² - r²
        = d_i - 2(x_i - 1) + 2(y_i + 1) + 1
        = d_i + 2(y_{i + 1} - x_{i + 1}) + 1
		  
If e >= 0 then di <= 0 so choose point T = (x_i, y_i + 1)
   d_i+1 = f(x_i - 1/2, y_i + 1 + 1)
       = d_i + 2y_i+1 + 1
		  
The initial value of di is
   d₀ = f(r - 1/2, 0 + 1) = (r - 1/2)² + 1² - r²
      = 5/4 - r {1-r can be used if r is an integer}
		
When point S = (x_i - 1, y_i + 1) is chosen then
   d_i+1 = d_i + -2x_i+1 + 2y_i+1 + 1
	
When point T = (x_i, y_i + 1) is chosen then
   d_i+1 = d_i + 2y_i+1 + 1

步骤 3 − 从 K=0 开始，在每个 $X_{K}$ 位置执行以下测试：

If P_K < 0 then next point on circle (0,0) is (X_K+1,Y_K) and
   P_K+1 = P_K + 2X_K+1 + 1
Else
   P_K+1 = P_K + 2X_K+1 + 1 – 2Y_K+1
	
Where, 2X_K+1 = 2X_K+2 and 2Y_K+1 = 2Y_K-2.

步骤 4 − 确定其他七个象限的对称点。

步骤 5 − 将每个计算出的像素位置 (X, Y) 移动到以 $(X_{C,} Y_{C})$ 为中心的圆周路径上，并绘制坐标值。

X = X + X_C,   Y = Y + Y_C

步骤 6 − 重复步骤 3 到 5，直到 X >= Y。

多边形填充算法

多边形是由一系列顶点组成的有序列表，如下图所示。为了用特定颜色填充多边形，需要确定落在多边形边界上的像素以及落在多边形内部的像素。本章将介绍如何使用不同的技术填充多边形。

扫描线算法

该算法通过扫描线与多边形边的相交来工作，并填充相交点对之间的多边形。以下步骤描述了该算法的工作原理。

步骤 1 − 从给定的多边形中找出 Ymin 和 Ymax。

步骤 2 − 扫描线与多边形的每条边从 Ymin 到 Ymax 相交。命名多边形的每个交点。根据上图，它们被命名为 p0、p1、p2、p3。

步骤 3 − 按 X 坐标的递增顺序排序交点，即 (p0, p1)、(p1, p2) 和 (p2, p3)。

步骤 4 − 填充位于多边形内部的所有坐标对，并忽略交替的坐标对。

泛洪填充算法

有时我们会遇到一个对象，我们希望用不同的颜色填充它的区域及其边界。我们可以用指定的内部颜色绘制此类对象，而不是像边界填充算法那样搜索特定的边界颜色。

它不依赖于对象的边界，而是依赖于填充颜色。换句话说，它用填充颜色替换对象的内部颜色。当不再存在原始内部颜色的像素时，算法完成。

同样，该算法依赖于四连通或八连通的像素填充方法。但它不是寻找边界颜色，而是寻找所有属于内部的相邻像素。

边界填充算法

边界填充算法顾名思义。该算法选择对象内部的一个点，并开始填充，直到它到达对象的边界。为了使该算法工作，边界颜色和我们填充的颜色应该不同。

在这个算法中，我们假设整个对象的边界颜色相同。边界填充算法可以通过 4 连通像素或 8 连通像素来实现。

4 连通多边形

在这种技术中，使用 4 连通像素，如下图所示。我们在当前像素的上方、下方、右侧和左侧放置像素，这个过程将持续到我们找到具有不同颜色的边界。

算法

步骤 1 − 初始化种子点 (seedx, seedy)、填充颜色 fcolor 和默认颜色 dcol 的值。

步骤 2 − 定义多边形的边界值。

步骤 3 − 检查当前种子点是否为默认颜色，如果是，则重复步骤 4 和 5，直到到达边界像素。

If getpixel(x, y) = dcol then repeat step 4 and 5

步骤 4 − 将种子点的默认颜色更改为填充颜色。

setPixel(seedx, seedy, fcol)

步骤 5 − 使用四个相邻点递归地执行该过程。

FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)

步骤 6 − 退出

这种技术存在一个问题。考虑如下所示的情况，我们试图填充整个区域。这里，图像只被部分填充。在这种情况下，不能使用 4 连通像素技术。

8 连通多边形

在这种技术中，使用 8 连通像素，如下图所示。我们像在 4 连通技术中那样，在当前像素的上方、下方、右侧和左侧放置像素。

除此之外，我们还在对角线上放置像素，以便覆盖当前像素的整个区域。这个过程将持续到我们找到具有不同颜色的边界。

算法

步骤 1 − 初始化种子点 (seedx, seedy)、填充颜色 fcolor 和默认颜色 dcol 的值。

步骤 2 − 定义多边形的边界值。

步骤 3 − 检查当前种子点是否为默认颜色，如果是，则重复步骤 4 和 5，直到到达边界像素。

If getpixel(x,y) = dcol then repeat step 4 and 5

步骤 4 − 将种子点的默认颜色更改为填充颜色。

setPixel(seedx, seedy, fcol)

步骤 5 − 使用四个相邻点递归地执行该过程。

FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx, seedy + 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy - 1, fcol, dcol)

步骤 6 − 退出

4 连通像素技术未能填充下图中标记的区域，而 8 连通技术则不会出现这种情况。

内外测试

此方法也称为计数法。在填充对象时，我们经常需要识别特定点是在对象内部还是外部。可以通过两种方法来识别特定点是在对象内部还是外部。

奇偶规则
非零环绕数规则

奇偶规则

在这种技术中，我们计算从任何点 (x, y) 到无穷大的直线与边的相交次数。如果交点数为奇数，则点 (x, y) 为内部点。如果交点数为偶数，则点 (x, y) 为外部点。以下是一个示例，以便您更好地理解：

从上图可以看出，从点 (x, y) 出发，左侧的交点数为 5，右侧的交点数为 3。因此，总交点数为 8，这是一个奇数。因此，该点被认为在对象内。

非零环绕数规则

此方法也用于简单多边形，以测试给定点是否为内部点。可以用大头针和橡皮筋轻松理解。将大头针固定在多边形的一条边上，并将橡皮筋系在上面，然后沿着多边形的边拉伸橡皮筋。

当多边形的所有边都被橡皮筋覆盖时，检查已固定在待测试点上的大头针。如果我们在该点找到至少一个环绕，则认为该点在多边形内，否则可以说该点不在多边形内。

另一种替代方法是，为多边形的所有边指定方向。从待测试点画一条扫描线到 X 方向的最左侧。

向上方向的所有边赋值为 1，其他方向的边赋值为 -1。
检查扫描线经过的边的方向值，并将它们加起来。
如果这些方向值的总和非零，则待测试点为内部点，否则为外部点。
在上图中，我们将扫描线经过的边的方向值相加，总和为 1 – 1 + 1 = 1；这是一个非零值。因此，该点被称为内部点。

观察与裁剪

裁剪在计算机图形学中的主要用途是移除位于视区之外的对象、线或线段。视变换对点相对于视景体的位置不敏感——特别是那些位于观察者后面的点——因此在生成视图之前必须移除这些点。

点裁剪

从给定窗口中裁剪点非常容易。考虑下图，其中矩形表示窗口。点裁剪告诉我们给定点 (X, Y) 是否在给定窗口内；并决定我们是否将使用窗口的最小和最大坐标。

如果 X 位于 Wx1 ≤ X ≤ Wx2 之间，则给定点的 X 坐标在窗口内。同样，如果 Y 位于 Wy1 ≤ Y ≤ Wy2 之间，则给定点的 Y 坐标在窗口内。

线裁剪

线裁剪的概念与点裁剪相同。在线裁剪中，我们将裁剪窗口外部的线段部分，只保留窗口内部的部分。

Cohen-Sutherland 线裁剪算法

该算法使用如下图所示的裁剪窗口。裁剪区域的最小坐标为 $(XW_{min,} YW_{min})$，最大坐标为 $(XW_{max,} YW_{max})$。

我们将使用 4 位来划分整个区域。这 4 位分别表示区域的顶部、底部、右侧和左侧，如下图所示。这里，顶部和左侧位设置为 1，因为它位于左上角。

线段有 3 种可能性：

线段可能完全在窗口内（此线段应被接受）。
线段可能完全在窗口外（此线段将完全从区域中移除）。
线段可能部分在窗口内（我们将找到交点，只绘制区域内的线段部分）。

算法

步骤 1 − 为每个端点分配区域代码。

步骤 2 − 如果两个端点的区域代码均为 0000，则接受此线段。

步骤 3 − 否则，对两个区域代码执行逻辑与运算。

步骤 3.1 − 如果结果不是 0000，则拒绝该线段。

步骤 3.2 − 否则需要裁剪。

步骤 3.2.1 − 选择窗口外的线段端点。

步骤 3.2.2 − 找到窗口边界上的交点（基于区域代码）。

步骤 3.2.3 − 用交点替换端点并更新区域代码。

步骤 3.2.4 − 重复步骤 2，直到找到一个被平凡接受或平凡拒绝的裁剪线段。

步骤 4 − 对其他线段重复步骤 1。

Cyrus-Beck 线裁剪算法

该算法比 Cohen-Sutherland 算法更高效。它采用参数线表示和简单的点积。

线的参数方程为：

P₀P₁:P(t) = P₀ + t(P₁-P₀)

设 N_i 为外法向量 E_i。现在在边 E_i 上选择任意点 P_Ei，则点积 N_i∙[P(t) – P_Ei] 确定点 P(t) 是否“在裁剪边内”、“在裁剪边外”或“在裁剪边上”。

如果 N_i.[P(t) – P_Ei] < 0，则点 P(t) 在内部。

如果 N_i.[P(t) – P_Ei] > 0，则点 P(t) 在外部。

如果 N_i.[P(t) – P_Ei] = 0，则点 P(t) 在边上（交点）。

N_i∙[P(t) – P_Ei] = 0

N_i∙[ P₀ + t(P₁-P₀) – P_Ei] = 0 (用 P₀ + t(P₁-P₀) 代替 P(t))

N_i∙[P₀ – P_Ei] + N_i∙t[P₁-P₀] = 0

N_i∙[P₀ – P_Ei] + N_i∙tD = 0 (用 D 代替 [P₁-P₀])

N_i∙[P₀ – P_Ei] = - N_i∙tD

t 的方程变为：

$$t = \tfrac{N_{i}.[P_{o} - P_{Ei}]}{{- N_{i}.D}}$$

它对以下条件有效：

N_i ≠ 0（不会发生错误）
D ≠ 0 (P₁ ≠ P₀)
N_i∙D ≠ 0 (P₀P₁与E_i不平行)

多边形裁剪 (Sutherland-Hodgman算法)

多边形也可以通过指定裁剪窗口来裁剪。Sutherland-Hodgman多边形裁剪算法用于多边形裁剪。在这个算法中，多边形的所有顶点都针对裁剪窗口的每条边进行裁剪。

首先，多边形针对多边形窗口的左边缘进行裁剪，以获得多边形的新顶点。然后使用这些新顶点，针对裁剪窗口的右边缘、上边缘和下边缘裁剪多边形，如下图所示。

在处理多边形边与裁剪窗口的边时，如果边不完全在裁剪窗口内，则找到一个交点，并裁剪从交点到外部边的部分边。下图显示了左、右、上和下边缘的裁剪：

文本裁剪

计算机图形学中使用各种技术来进行文本裁剪。这取决于用于生成字符的方法和特定应用程序的要求。文本裁剪有三种方法，如下所示：

全部或无字符串裁剪
全部或无字符裁剪
文本裁剪

下图显示了全部或无字符串裁剪：

在全部或无字符串裁剪方法中，根据裁剪窗口，我们要么保留整个字符串，要么拒绝整个字符串。如上图所示，STRING2完全在裁剪窗口内，因此我们保留它；STRING1仅部分在窗口内，因此我们拒绝它。

下图显示了全部或无字符裁剪：

这种裁剪方法基于字符而不是整个字符串。在这种方法中，如果字符串完全在裁剪窗口内，则我们保留它。如果它部分在窗口外，则：

只拒绝字符串中在窗口外的部分。
如果字符位于裁剪窗口的边界上，则我们丢弃整个字符并保留其余字符串。

下图显示了文本裁剪：

这种裁剪方法基于字符而不是整个字符串。在这种方法中，如果字符串完全在裁剪窗口内，则我们保留它。如果它部分在窗口外，则：

只拒绝字符串中在窗口外的部分。
如果字符位于裁剪窗口的边界上，则我们只丢弃字符中在裁剪窗口外的部分。

位图图形

位图是描述图像的像素集合。它是一种计算机图形，计算机使用它来存储和显示图片。在这种类型的图形中，图像逐位存储，因此被称为位图图形。为了更好地理解，让我们考虑下面的例子，我们使用位图图形绘制一个笑脸。

现在我们将看到这个笑脸是如何在计算机图形中逐位存储的。

仔细观察原始笑脸，我们可以看到有两条蓝线，在上图中分别表示为B1、B2和E1、E2。

同样，笑脸分别由A4、B5、C6、D6、E5和F4的组合位表示。

位图图形的主要缺点是：

我们无法调整位图图像的大小。如果尝试调整大小，像素会变得模糊。
彩色位图可能非常大。

二维变换

变换意味着通过应用规则将某些图形更改为其他内容。我们可以进行各种类型的变换，例如平移、缩放、旋转、错切等。当变换发生在二维平面上时，称为二维变换。

变换在计算机图形学中起着重要的作用，用于重新定位屏幕上的图形并更改其大小或方向。

齐次坐标

为了执行一系列变换，例如先平移后旋转再缩放，我们需要遵循一个顺序过程：

平移坐标；
旋转平移后的坐标；然后
缩放旋转后的坐标以完成复合变换。

为了缩短这个过程，我们必须使用3×3变换矩阵而不是2×2变换矩阵。为了将2×2矩阵转换为3×3矩阵，我们必须添加一个额外的虚拟坐标W。

这样，我们可以用3个数而不是2个数来表示点，这称为**齐次坐标**系统。在这个系统中，我们可以用矩阵乘法表示所有变换方程。任何笛卡尔点P(X, Y)都可以通过P’ (X_h, Y_h, h)转换为齐次坐标。

平移

平移将对象移动到屏幕上的不同位置。可以通过将平移坐标(t_x, t_y)添加到原始坐标(X, Y)来平移二维点，以获得新的坐标(X’, Y’)。

从上图中，可以写出：

X’ = X + t_x

Y’ = Y + t_y

对(t_x, t_y)称为平移向量或位移向量。上述方程也可以用列向量表示。

$P = \frac{[X]}{[Y]}$ p' = $\frac{[X']}{[Y']}$T = $\frac{[t_{x}]}{[t_{y}]}$

我们可以写成：

P’ = P + T

旋转

在旋转中，我们将对象围绕其原点旋转特定角度θ（theta）。从下图中，我们可以看到点P(X, Y)位于距原点距离为r的水平X坐标角度φ处。

假设您想将其旋转角度θ。旋转到新的位置后，您将得到一个新的点P’ (X’, Y’)。

使用标准三角函数，点P(X, Y)的原始坐标可以表示为：

$X = r \, cos \, \phi ...... (1)$

$Y = r \, sin \, \phi ...... (2)$

同样，我们可以表示点P’ (X’, Y’)为：

${x}'= r \: cos \: \left ( \phi \: + \: \theta \right ) = r\: cos \: \phi \: cos \: \theta \: − \: r \: sin \: \phi \: sin \: \theta ....... (3)$

${y}'= r \: sin \: \left ( \phi \: + \: \theta \right ) = r\: cos \: \phi \: sin \: \theta \: + \: r \: sin \: \phi \: cos \: \theta ....... (4)$

将公式(1)和(2)分别代入(3)和(4)，我们将得到

${x}'= x \: cos \: \theta − \: y \: sin \: \theta $

${y}'= x \: sin \: \theta + \: y \: cos \: \theta $

将上述方程用矩阵形式表示，

$$[X' Y'] = [X Y] \begin{bmatrix} cos\theta & sin\theta \\ −sin\theta & cos\theta \end{bmatrix}OR $$

P’ = P ∙ R

其中R是旋转矩阵

$$R = \begin{bmatrix} cos\theta & sin\theta \\ −sin\theta & cos\theta \end{bmatrix}$$

旋转角度可以是正的也可以是负的。

对于正旋转角度，我们可以使用上述旋转矩阵。但是，对于负角度旋转，矩阵将发生变化，如下所示：

$$R = \begin{bmatrix} cos(−\theta) & sin(−\theta) \\ -sin(−\theta) & cos(−\theta) \end{bmatrix}$$

$$=\begin{bmatrix} cos\theta & −sin\theta \\ sin\theta & cos\theta \end{bmatrix} \left (\because cos(−\theta ) = cos \theta \; and\; sin(−\theta ) = −sin \theta \right )$$

缩放

要更改对象的大小，可以使用缩放变换。在缩放过程中，您会扩展或压缩对象的大小。缩放可以通过将对象的原始坐标与缩放因子相乘来实现，以获得所需的结果。

让我们假设原始坐标是(X, Y)，缩放因子是(S_X, S_Y)，生成的坐标是(X’, Y’)。这可以用下面的数学方法表示：

X' = X . S_X 和 Y' = Y . S_Y

缩放因子S_X、S_Y分别沿X和Y方向缩放对象。上述方程也可以用矩阵形式表示如下：

$$\binom{X'}{Y'} = \binom{X}{Y} \begin{bmatrix} S_{x} & 0\\ 0 & S_{y} \end{bmatrix}$$

或

P’ = P . S

其中S是缩放矩阵。缩放过程如下图所示。

如果我们将小于1的值提供给缩放因子S，那么我们可以减小对象的大小。如果我们提供大于1的值，那么我们可以增加对象的大小。

反射

反射是原始对象的镜像。换句话说，我们可以说它是一个180°的旋转操作。在反射变换中，对象的大小不会改变。

下图分别显示了关于X轴和Y轴以及关于原点的反射。

错切

使物体形状倾斜的变换称为错切变换。有两种错切变换：**X错切**和**Y错切**。一种移动X坐标值，另一种移动Y坐标值。但是，在这两种情况下，只有一个坐标改变其坐标，而另一个保留其值。错切也称为**倾斜**。

X错切

X错切保留Y坐标，并对X坐标进行更改，这会导致垂直线向右或向左倾斜，如下图所示。

X错切的变换矩阵可以表示为：

$$X_{sh} = \begin{bmatrix} 1& shx & 0\\ 0& 1 & 0\\ 0& 0 & 1 \end{bmatrix}$$

Y' = Y + Sh_y . X

X’ = X

Y错切

Y错切保留X坐标，并更改Y坐标，这会导致水平线变换成向上或向下倾斜的线，如下图所示。

Y错切可以用矩阵形式表示为：

$$Y_{sh} \begin{bmatrix} 1& 0 & 0\\ shy& 1 & 0\\ 0& 0 & 1 \end{bmatrix}$$

X’ = X + Sh_x . Y

Y’ = Y

复合变换

如果平面变换T1之后是第二个平面变换T2，则结果本身可以用单个变换T表示，它是按该顺序取的T1和T2的组合。这写成T = T1∙T2。

复合变换可以通过连接变换矩阵来实现，以获得组合变换矩阵。

组合矩阵：

[T][X] = [X] [T1] [T2] [T3] [T4] …. [Tn]

其中[Ti]是任何组合的

平移
缩放
错切
旋转
反射

变换顺序的改变会导致不同的结果，因为一般矩阵乘法不是可交换的，即[A] . [B] ≠ [B] . [A]，并且乘法的顺序。组合变换的基本目的是通过对点应用单个组合变换来提高效率，而不是一个接一个地应用一系列变换。

例如，要围绕任意点(X_p, Y_p)旋转一个对象，我们必须执行三个步骤：

将点(X_p, Y_p)平移到原点。
绕原点旋转。
最后，将旋转中心移回它原本的位置。

三维计算机图形学

在二维系统中，我们只使用 X 和 Y 两个坐标，但在三维系统中，会增加一个额外的 Z 坐标。三维图形技术及其应用是娱乐、游戏和计算机辅助设计行业的基础。它也是科学可视化领域持续的研究方向。

此外，三维图形组件现在几乎成为每台个人电脑的组成部分，虽然传统上它们主要用于游戏等图形密集型软件，但它们正越来越多地被其他应用程序使用。

平行投影

平行投影丢弃 z 坐标，并将物体上每个顶点的平行线延伸，直到它们与视平面相交。在平行投影中，我们指定投影方向而不是投影中心。

在平行投影中，投影中心到投影平面的距离是无限大的。在这种类型的投影中，我们用线段连接投影顶点，这些线段对应于原始物体上的连接。

平行投影不太逼真，但它们有利于精确测量。在这种类型的投影中，平行线保持平行，但角度不保持不变。各种类型的平行投影如下所示。

正投影

在正投影中，投影方向垂直于投影平面。正投影有三种类型：

正面投影
顶面投影
侧面投影

斜投影

在斜投影中，投影方向不垂直于投影平面。在斜投影中，我们可以比正投影更好地观察物体。

斜投影有两种类型：**骑士投影**和**内阁投影**。骑士投影与投影平面成 45° 角。在骑士投影中，垂直于视平面的线的投影长度与其本身相同。在骑士投影中，所有三个主要方向的缩短因子都相等。

内阁投影与投影平面成 63.4° 角。在内阁投影中，垂直于观察表面的线以其实际长度的一半投影。下图显示了这两种投影：

等轴测投影

显示物体多个侧面的正投影称为**轴测正投影**。最常见的轴测投影是**等轴测投影**，其中投影平面在模型坐标系中与每个坐标轴相交于等距。在这种投影中，线的平行性保持不变，但角度不保持不变。下图显示了等轴测投影：

透视投影

在透视投影中，投影中心到投影平面的距离是有限的，物体的尺寸与距离成反比，看起来更逼真。

距离和角度不保持不变，平行线也不保持平行。相反，它们都汇聚在一个点上，这个点称为**投影中心**或**投影参考点**。透视投影有三种类型，如下表所示。

**一点**透视投影易于绘制。
**两点**透视投影能更好地展现深度感。
**三点**透视投影最难绘制。

下图显示了三种透视投影：

平移

在三维平移中，我们除了 X 和 Y 坐标外，还要平移 Z 坐标。三维平移的过程与二维平移类似。平移将物体移动到屏幕上的不同位置。

下图显示了平移的效果：

可以通过将平移坐标 $(t_{x,} t_{y,} t_{z})$ 添加到原始坐标 (X, Y, Z) 来平移三维空间中的点，从而得到新的坐标 (X', Y', Z')。

$T = \begin{bmatrix} 1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ t_{x}& t_{y}& t_{z}& 1\\ \end{bmatrix}$

P’ = P∙T

$[X′ \:\: Y′ \:\: Z′ \:\: 1] \: = \: [X \:\: Y \:\: Z \:\: 1] \: \begin{bmatrix} 1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ t_{x}& t_{y}& t_{z}& 1\\ \end{bmatrix}$

$= [X + t_{x} \:\:\: Y + t_{y} \:\:\: Z + t_{z} \:\:\: 1]$

三维变换

旋转

三维旋转与二维旋转不同。在三维旋转中，我们必须指定旋转角度以及旋转轴。我们可以围绕 X、Y 和 Z 轴进行三维旋转。它们以矩阵形式表示如下：

$$R_{x}(\theta) = \begin{bmatrix} 1& 0& 0& 0\\ 0& \cos\theta & -\sin\theta& 0\\ 0& \sin\theta & \cos\theta& 0\\ 0& 0& 0& 1\\ \end{bmatrix} R_{y}(\theta) = \begin{bmatrix} \cos\theta& 0& \sin\theta& 0\\ 0& 1& 0& 0\\ -\sin\theta& 0& \cos\theta& 0\\ 0& 0& 0& 1\\ \end{bmatrix} R_{z}(\theta) =\begin{bmatrix} \cos\theta & -\sin\theta & 0& 0\\ \sin\theta & \cos\theta & 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1 \end{bmatrix}$$

下图解释了围绕各个轴的旋转：

缩放

您可以使用缩放变换来更改对象的大小。在缩放过程中，您可以扩展或压缩对象的尺寸。缩放可以通过将对象的原始坐标乘以缩放因子来获得所需的结果。下图显示了三维缩放的效果：

在三维缩放操作中，使用三个坐标。假设原始坐标为 (X, Y, Z)，缩放因子分别为 $(S_{X,} S_{Y,} S_{z})$，生成的坐标为 (X', Y', Z')。这可以用下面的数学公式表示：

$S = \begin{bmatrix} S_{x}& 0& 0& 0\\ 0& S_{y}& 0& 0\\ 0& 0& S_{z}& 0\\ 0& 0& 0& 1 \end{bmatrix}$

P’ = P∙S

$[{X}' \:\:\: {Y}' \:\:\: {Z}' \:\:\: 1] = [X \:\:\:Y \:\:\: Z \:\:\: 1] \:\: \begin{bmatrix} S_{x}& 0& 0& 0\\ 0& S_{y}& 0& 0\\ 0& 0& S_{z}& 0\\ 0& 0& 0& 1 \end{bmatrix}$

$ = [X.S_{x} \:\:\: Y.S_{y} \:\:\: Z.S_{z} \:\:\: 1]$

错切

使物体形状倾斜的变换称为**剪切变换**。与二维剪切一样，我们可以在三维空间中沿 X 轴、Y 轴或 Z 轴剪切物体。

如上图所示，有一个坐标 P。您可以剪切它以获得新的坐标 P'，这可以用三维矩阵形式表示如下：

$Sh = \begin{bmatrix} 1 & sh_{x}^{y} & sh_{x}^{z} & 0 \\ sh_{y}^{x} & 1 & sh_{y}^{z} & 0 \\ sh_{z}^{x} & sh_{z}^{y} & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

P’ = P ∙ Sh

X’ = X + Sh_{x}^{y} Y + Sh_{x}^{z} Z

Y' = Sh_{y}^{x}X + Y +sh_{y}^{z}Z

Z' = Sh_{z}^{x}X + Sh_{z}^{y}Y + Z

变换矩阵

变换矩阵是变换的基本工具。一个 n x m 维的矩阵与物体的坐标相乘。通常使用 3 x 3 或 4 x 4 矩阵进行变换。例如，考虑以下用于各种操作的矩阵。

$T = \begin{bmatrix} 1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ t_{x}& t_{y}& t_{z}& 1\\ \end{bmatrix}$	$S = \begin{bmatrix} S_{x}& 0& 0& 0\\ 0& S_{y}& 0& 0\\ 0& 0& S_{z}& 0\\ 0& 0& 0& 1 \end{bmatrix}$	$Sh = \begin{bmatrix} 1& sh_{x}^{y}& sh_{x}^{z}& 0\\ sh_{y}^{x}& 1 & sh_{y}^{z}& 0\\ sh_{z}^{x}& sh_{z}^{y}& 1& 0\\ 0& 0& 0& 1 \end{bmatrix}$
平移矩阵	缩放矩阵	剪切矩阵
$R_{x}(\theta) = \begin{bmatrix} 1& 0& 0& 0\\ 0& \cos\theta & -\sin\theta& 0\\ 0& \sin\theta & \cos\theta& 0\\ 0& 0& 0& 1\\ \end{bmatrix}$	$R_{y}(\theta) = \begin{bmatrix} \cos\theta& 0& \sin\theta& 0\\ 0& 1& 0& 0\\ -\sin\theta& 0& \cos\theta& 0\\ 0& 0& 0& 1\\ \end{bmatrix}$	$R_{z}(\theta) = \begin{bmatrix} \cos\theta & -\sin\theta & 0& 0\\ \sin\theta & \cos\theta & 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1 \end{bmatrix}$
旋转矩阵

计算机图形学曲线

在计算机图形学中，我们经常需要将不同类型的物体绘制到屏幕上。物体并非总是平面的，我们常常需要绘制曲线来绘制物体。

曲线类型

曲线是无限大的点集。每个点都有两个邻居，除了端点。曲线可以大致分为三类：**显式曲线、隐式曲线**和**参数曲线**。

隐式曲线

隐式曲线表示通过使用可以测试点是否在曲线上的过程来定义曲线上的点集。通常，隐式曲线由以下形式的隐函数定义：

f(x, y) = 0

它可以表示多值曲线（对于一个 x 值有多个 y 值）。一个常见的例子是圆，其隐式表示为

x² + y² - R² = 0

显式曲线

数学函数 y = f(x) 可以绘制成曲线。这样的函数是曲线的显式表示。显式表示不是通用的，因为它不能表示垂直线，并且也是单值的。对于每个 x 值，函数通常只计算一个 y 值。

参数曲线

具有参数形式的曲线称为参数曲线。显式和隐式曲线表示只有在已知函数时才能使用。实际上使用的是参数曲线。二维参数曲线具有以下形式：

P(t) = f(t), g(t) 或 P(t) = x(t), y(t)

函数 f 和 g 成为曲线任意点的 (x, y) 坐标，当参数 t 在某个区间 [a, b]（通常为 [0, 1]）内变化时，可以得到这些点。

贝塞尔曲线

贝塞尔曲线是由法国工程师**皮埃尔·贝塞尔**发现的。这些曲线可以在其他点的控制下生成。使用控制点逼近切线来生成曲线。贝塞尔曲线可以用数学方法表示为：

$$ \sum_{k=0}^{n} P_{i}{B_{i}^{n}}(t) $$

其中 $p_{i}$ 是点集，${B_{i}^{n}}(t)$ 表示伯恩斯坦多项式，其由下式给出：

$$ {B_{i}^{n}}(t) = \binom{n}{i} (1 - t)^{n-i}t^{i} $$

其中**n**是多项式的次数，**i**是索引，**t**是变量。

最简单的贝塞尔曲线是从点 $P_{0}$ 到 $P_{1}$ 的直线。二次贝塞尔曲线由三个控制点确定。三次贝塞尔曲线由四个控制点确定。

贝塞尔曲线的性质

贝塞尔曲线具有以下性质：

它们通常遵循控制多边形的形状，控制多边形由连接控制点的线段组成。
它们总是通过第一个和最后一个控制点。
它们包含在其定义控制点的凸包中。
定义曲线段的多项式的次数比定义多边形的点数少 1。因此，对于 4 个控制点，多项式的次数为 3，即三次多项式。
贝塞尔曲线通常遵循定义多边形的形状。
端点处切向量的方向与由第一段和最后一段确定的向量方向相同。
贝塞尔曲线的凸包性质确保多项式平滑地跟随控制点。
任何直线与贝塞尔曲线相交的次数不超过它与控制多边形相交的次数。
它们在仿射变换下是不变的。
贝塞尔曲线具有全局控制性，这意味着移动一个控制点会改变整个曲线形状。
给定的贝塞尔曲线可以在点t=t0处细分为两段贝塞尔曲线段，这两段曲线段在对应于参数值t=t0的点处连接在一起。

B样条曲线

由伯恩斯坦基函数生成的贝塞尔曲线灵活性有限。

首先，指定的polygon顶点数决定了定义曲线的最终多项式的阶数。
第二个限制特性是，混合函数的值在整个曲线上的所有参数值上都不为零。

B样条基包含伯恩斯坦基作为特例。B样条基是非全局的。

B样条曲线定义为控制点Pi和B样条基函数$N_{i,}$ k (t)的线性组合，如下所示：

$C(t) = \sum_{i=0}^{n}P_{i}N_{i,k}(t),$ $n\geq k-1,$ $t\: \epsilon \: [ tk-1,tn+1 ]$

其中，

{$p_{i}$: i=0, 1, 2….n} 为控制点
k是B样条曲线的多分段多项式的阶数。k阶意味着曲线由k-1次的分段多项式段组成。
$N_{i,k}(t)$是“归一化B样条混合函数”。它们由阶数k和一组非递减的实数（通常称为“节点序列”）描述。

$${t_{i}:i = 0, ... n + K}$$

N_i, k函数描述如下：

$$N_{i,1}(t) = \left\{\begin{matrix} 1,& if \:u \: \epsilon \: [t_{i,}t_{i+1}) \\ 0,& 其他 \end{matrix}\right.$$

如果k > 1，则

$$N_{i,k}(t) = \frac{t-t_{i}}{t_{i+k-1}-t_i} N_{i,k-1}(t) + \frac{t_{i+k}-t}{t_{i+k} - t_{i+1}} N_{i+1,k-1}(t)$$

和

$$t \: \epsilon \: [t_{k-1},t_{n+1})$$

B样条曲线的性质

B样条曲线具有以下性质：

对于任何参数值，B样条基函数之和为1。
每个基函数对于所有参数值都为正或零。
除k=1外，每个基函数只有一个最大值。
曲线的最大阶数等于定义多边形的顶点数。
B样条多项式的次数与定义多边形的顶点数无关。
B样条允许对曲线表面进行局部控制，因为每个顶点只影响其相关基函数非零的参数值范围内的曲线形状。
曲线表现出变化递减特性。
曲线通常遵循定义多边形的形状。
可以通过将其应用于定义多边形的顶点来将任何仿射变换应用于曲线。
曲线位于其定义多边形的凸包内。

计算机图形学曲面

多边形曲面

物体表示为曲面的集合。3D物体表示分为两类。

边界表示法 (B-reps) − 它将3D物体描述为一组将物体内部与环境隔开的曲面。
空间划分表示法 − 通过将包含物体的空间区域划分为一组小的、不重叠的、连续的实体（通常是立方体）来描述内部属性。

最常用的3D图形物体的边界表示法是一组封闭物体内部的表面多边形。许多图形系统都使用这种方法。存储多边形集合用于物体描述。这简化并加快了物体的表面渲染和显示，因为所有曲面都可以用线性方程描述。

多边形曲面在设计和实体建模应用中很常见，因为它们的线框显示可以快速完成，从而可以大致指示表面结构。然后通过在多边形表面上插值阴影图案来产生逼真的场景以进行照明。

多边形表

在这种方法中，曲面由顶点坐标集和相关属性指定。如下图所示，有五个顶点，从v₁到v₅。

每个顶点存储x、y和z坐标信息，在表中表示为v₁: x₁, y₁, z₁。
边表用于存储多边形的边信息。在下图中，边E₁位于顶点v₁和v₂之间，在表中表示为E₁: v₁, v₂。
多边形曲面表存储多边形中存在的曲面数量。从下图可以看出，曲面S₁由边E₁、E₂和E₃覆盖，这可以在多边形曲面表中表示为S₁: E₁, E₂和E₃。

平面方程

平面曲面的方程可以表示为：

Ax + By + Cz + D = 0

其中(x, y, z)是平面上的任意一点，系数A、B、C和D是描述平面空间属性的常数。我们可以通过使用平面中三个非共线点的坐标值求解一组三个平面方程来获得A、B、C和D的值。让我们假设平面的三个顶点是(x₁, y₁, z₁)、(x₂, y₂, z₂)和(x₃, y₃, z₃)。

让我们求解以下联立方程以求A/D、B/D和C/D的比率。你可以得到A、B、C和D的值。

(A/D) x₁ + (B/D) y₁ + (C/D) z₁ = -1

(A/D) x₂ + (B/D) y₂ + (C/D) z₂ = -1

(A/D) x₃ + (B/D) y₃ + (C/D) z₃ = -1

为了以行列式形式获得上述方程，将克莱姆法则应用于上述方程。

$A = \begin{bmatrix} 1& y_{1}& z_{1}\\ 1& y_{2}& z_{2}\\ 1& y_{3}& z_{3} \end{bmatrix} B = \begin{bmatrix} x_{1}& 1& z_{1}\\ x_{2}& 1& z_{2}\\ x_{3}& 1& z_{3} \end{bmatrix} C = \begin{bmatrix} x_{1}& y_{1}& 1\\ x_{2}& y_{2}& 1\\ x_{3}& y_{3}& 1 \end{bmatrix} D = - \begin{bmatrix} x_{1}& y_{1}& z_{1}\\ x_{2}& y_{2}& z_{2}\\ x_{3}& y_{3}& z_{3} \end{bmatrix}$

对于具有参数A、B、C和D的任何点(x, y, z)，我们可以说：

Ax + By + Cz + D ≠ 0 表示该点不在平面上。
Ax + By + Cz + D < 0 表示该点在曲面内部。
Ax + By + Cz + D > 0 表示该点在曲面外部。

多边形网格

3D曲面和实体可以用一组多边形和线元素来近似。这种曲面称为多边形网格。在多边形网格中，每条边最多由两个多边形共享。多边形或面的集合共同构成物体的“外壳”。

此方法可用于表示图形中各种实体/曲面。可以使用隐藏曲面消除算法渲染多边形网格。多边形网格可以用三种方式表示：

显式表示
指向顶点列表的指针
指向边列表的指针

优点

它可用于模拟几乎任何物体。
它们很容易表示为顶点的集合。
它们很容易转换。
它们很容易在电脑屏幕上绘制。

缺点

只能近似描述曲线曲面。
很难模拟某些类型的物体，例如头发或液体。

可见面检测

当我们查看包含非透明物体和曲面的图片时，我们无法看到那些位于更靠近眼睛的物体后面的物体。我们必须去除这些隐藏曲面才能获得逼真的屏幕图像。这些曲面的识别和去除称为隐藏曲面问题。

去除隐藏曲面问题有两种方法：物体空间方法和图像空间方法。物体空间方法在物理坐标系中实现，图像空间方法在屏幕坐标系中实现。

当我们想在二维屏幕上显示三维物体时，我们需要识别从选择的观察位置可见的屏幕部分。

深度缓冲区 (Z-缓冲区) 方法

此方法由Cutmull开发。这是一种图像空间方法。其基本思想是测试每个曲面的Z深度以确定最接近（可见）的曲面。

在此方法中，每个曲面都单独处理，一次一个像素位置地跨越曲面。比较像素的深度值，最接近（最小z）的曲面决定要在帧缓冲区中显示的颜色。

它在多边形的曲面上非常有效地应用。曲面可以以任何顺序处理。为了覆盖靠近的多边形，使用名为帧缓冲区和深度缓冲区的两个缓冲区。

深度缓冲区用于存储曲面处理时(x, y)位置的深度值 (0 ≤ depth ≤ 1)。

帧缓冲区用于存储每个位置(x, y)的颜色值的强度值。

z坐标通常归一化为[0, 1]范围。z坐标的0值表示后裁剪平面，z坐标的1值表示前裁剪平面。

算法

步骤1 − 设置缓冲区值：

Depthbuffer (x, y) = 0

Framebuffer (x, y) = 背景颜色

步骤2 − 处理每个多边形（一次一个）

对于多边形的每个投影的(x, y)像素位置，计算深度z。

如果Z > depthbuffer (x, y)

计算曲面颜色，

设置depthbuffer (x, y) = z，

framebuffer (x, y) = surfacecolor (x, y)

优点

易于实现。
如果在硬件中实现，则可以减少速度问题。
它一次处理一个对象。

缺点

它需要大量的内存。
这是一个耗时的过程。

扫描线方法

这是一种识别可见曲面的图像空间方法。此方法仅对单个扫描线具有深度信息。为了需要一条扫描线的深度值，我们必须在处理下一条扫描线之前，同时对相交于给定扫描线的全部多边形进行分组和处理。为此，维护两个重要的表：边表和多边形表。

边表 − 它包含场景中每条线的坐标端点、每条线的反斜率以及指向多边形表的指针，以将边连接到曲面。

多边形表 − 它包含平面系数、表面材质属性、其他表面数据，并且可能是指向边表的指针。

为了方便搜索穿过给定扫描线的表面，会形成一个活动的边列表。活动列表仅存储按 x 值递增顺序排列的、与扫描线相交的那些边。此外，还会为每个表面设置一个标志，以指示扫描线上的某个位置是在表面内部还是外部。

每个扫描线上的像素位置都是从左到右处理的。在与表面的左侧交点处，表面标志被打开；在右侧交点处，标志被关闭。只有当多个表面的标志在某个扫描线位置都被打开时，才需要执行深度计算。

区域细分法

区域细分法通过定位代表单个表面一部分的那些视区来发挥优势。将总视区细分为越来越小的矩形，直到每个小区都是单个可见表面的投影部分或根本没有表面。

继续此过程，直到细分很容易被分析为属于单个表面，或者直到它们被缩小到单个像素的大小。一个简单的做法是在每一步都将区域连续地细分为四个相等的部分。表面可能与指定的区域边界具有四种可能的关联。

包围表面 − 完全包围该区域的表面。
重叠表面 − 部分在区域内，部分在区域外的表面。
内部表面 − 完全在区域内的表面。
外部表面 − 完全在区域外的表面。

确定区域内表面可见性的测试可以用这四种分类来表示。如果以下条件之一为真，则不需要对指定区域进行进一步细分 −

所有表面相对于该区域都是外部表面。
该区域内只有一个内部、重叠或包围表面。
包围表面遮挡了区域边界内的所有其他表面。

背面检测

一种快速简单的对象空间方法，用于识别多面体的背面，基于“内外”测试。如果点 (x, y, z) 满足平面参数 A、B、C 和 D 的多边形表面“内部”条件，则当内部点位于视线与表面的连线上时，多边形必须是背面（我们在这个面内，无法从我们的观看位置看到它的正面）。

我们可以通过考虑多边形表面的法向量N 来简化此测试，该法向量具有笛卡尔分量 (A, B, C)。

一般来说，如果 V 是从眼睛（或“相机”）位置朝观看方向的向量，则如果以下条件成立，则该多边形为背面

V.N > 0

此外，如果对象描述被转换为投影坐标，并且您的观看方向平行于观看 z 轴，则 −

V = (0, 0, V_z) 并且 V.N = V_ZC

这样我们只需要考虑法向量N的分量 C 的符号。

在右手系观看系统中，观看方向沿负 $Z_{V}$ 轴，如果 C < 0，则多边形为背面。此外，我们无法看到法向量 z 分量 C = 0 的任何面，因为您的观看方向朝向该多边形。因此，一般来说，如果多边形的法向量的 z 分量值为 −，我们可以将任何多边形标记为背面

C <= 0

类似的方法可用于采用左手系观看系统的包。在这些包中，平面参数 A、B、C 和 D 可以根据以顺时针方向指定的（与右手系中使用的逆时针方向不同）多边形顶点坐标计算。

此外，背面法向量指向远离观看位置，当观看方向沿正 $Z_{v}$ 轴时，由 C >= 0 标识。通过检查定义对象的不同平面的参数 C，我们可以立即识别所有背面。

A 缓冲区方法

A 缓冲区方法是深度缓冲区方法的扩展。A 缓冲区方法是由卢卡斯影业为渲染系统 Renders Everything You Ever Saw (REYES) 开发的一种可见性检测方法。

A 缓冲区扩展了深度缓冲区方法以允许透明度。A 缓冲区中的关键数据结构是累积缓冲区。

A 缓冲区中的每个位置都有两个字段 −

深度字段 − 它存储一个正数或负数。
强度字段 − 它存储表面强度信息或指针值。

如果深度 >= 0，则该位置存储的数字是与相应像素区域重叠的单个表面的深度。然后，强度字段存储该点表面颜色的 RGB 分量和像素覆盖百分比。

如果深度 < 0，则表示对像素强度有多个表面的贡献。然后，强度字段存储指向表面数据的链表的指针。A 缓冲区中的表面缓冲区包括 −

RGB 强度分量
不透明度参数
深度
面积覆盖百分比
表面标识符

算法的执行方式与深度缓冲区算法相同。深度和不透明度值用于确定像素的最终颜色。

深度排序法

深度排序法同时使用图像空间和对象空间操作。深度排序法执行两个基本功能 −

首先，按深度递减的顺序对表面进行排序。
其次，按顺序扫描转换表面，从深度最大的表面开始。

多边形表面的扫描转换在图像空间中执行。这种解决隐藏面问题的的方法通常被称为画家算法。下图显示了深度排序的效果 −

算法首先按深度排序。例如，多边形的初始“深度”估计可以取为多边形的任何顶点的最近 z 值。

让我们取列表末尾的多边形 P。考虑所有其 z 范围与 P 重叠的多边形 Q。在绘制 P 之前，我们进行以下测试。如果任何以下测试为正，则我们可以假设可以在 Q 之前绘制 P。

x 范围是否不重叠？
y 范围是否不重叠？
P 是否完全位于 Q 平面与视点相对的一侧？
Q 是否完全位于 P 平面的与视点相同的一侧？
多边形的投影是否不重叠？

如果所有测试都失败，则使用另一个平面对 P 或 Q 进行分割。将新的切割多边形插入深度顺序中，并继续该过程。理论上，这种分区可能会生成 O(n²) 个单独的多边形，但在实践中，多边形的数量要少得多。

二元空间划分 (BSP) 树

二元空间划分用于计算可见性。要构建 BSP 树，应从多边形开始并标记所有边。一次只处理一条边，扩展每条边使其将平面分成两部分。将第一条边作为根节点放入树中。根据后续边是在内部还是外部添加后续边。跨越已在树中的边的扩展的边被分成两部分，并且两者都被添加到树中。

从上图来看，首先取A作为根。
列出图 (a) 中的所有节点。
将所有位于根节点A前面的节点放在节点A的左侧，并将所有位于根节点A后面的节点放在右侧，如图 (b) 所示。
首先处理所有前面的节点，然后处理后面的节点。
如图 (c) 所示，我们将首先处理节点B。由于节点B前面没有任何内容，因此我们已放置 NIL。但是，我们在节点B的后面有节点C，因此节点C将位于节点B的右侧。
对节点D重复相同的过程。

计算机图形学分形

法国/美国数学家 Benoit Mandelbrot 博士发现了分形。分形一词源于拉丁词fractus，意思是破碎的。

什么是分形？

分形是由计算机根据单个公式生成的非常复杂的图像。它们是使用迭代创建的。这意味着一个公式会一遍又一遍地使用略微不同的值重复，同时考虑来自先前迭代的结果。

分形用于许多领域，例如 −

天文学 − 用于分析星系、土星环等。
生物学/化学 − 用于描绘细菌培养物、化学反应、人体解剖结构、分子、植物等。
其他 − 用于描绘云、海岸线和边界线、数据压缩、扩散、经济、分形艺术、分形音乐、景观、特效等。

分形的生成

分形可以通过反复重复相同的形状来生成，如下图所示。图 (a) 显示了一个等边三角形。在图 (b) 中，我们可以看到三角形被重复以创建星形。在图 (c) 中，我们可以看到图 (b) 中的星形被反复重复以创建新的形状。

我们可以进行无限次的迭代来创建所需的形状。在编程方面，使用递归来创建此类形状。

几何分形

几何分形处理自然界中具有非整数或分形维度的形状。为了几何地构造确定性（非随机）自相似分形，我们从给定的几何形状（称为起始体）开始。然后用称为生成器的图案替换起始体的子部分。

例如，如果我们使用上图中所示的起始体和生成器，我们可以通过重复它来构造良好的图案。起始体中的每一段直线段在每一步都由四段等长线段替换。比例因子为 1/3，因此分形维数为 D = ln 4/ln 3 ≈ 1.2619。

此外，起始体中每段线段的长度在每一步都增加 4/3 倍，因此随着曲线中添加更多细节，分形曲线的长度趋于无穷大，如下图所示 −

计算机动画

动画意味着在计算机图形中赋予任何对象生命。它具有将能量和情感注入看似最无生命的物体中的能力。计算机辅助动画和计算机生成的动画是计算机动画的两个类别。它可以通过电影或视频呈现。

动画背后的基本思想是以足够快的速度播放录制的图像，以欺骗人眼将其解释为连续运动。动画可以让一系列静态图像栩栩如生。动画可用于许多领域，例如娱乐、计算机辅助设计、科学可视化、培训、教育、电子商务和计算机艺术。

动画技术

动画师发明并使用了各种不同的动画技术。基本上有六种动画技术，我们将在本节中逐一讨论。

传统动画（逐帧）

传统上，大部分动画都是手工完成的。动画中的所有帧都必须手工绘制。由于每秒动画需要 24 帧（胶片），因此即使是最短的电影的创作也需要付出巨大的努力。

关键帧动画

在这种技术中，会绘制出故事板，然后艺术家绘制动画的主要帧。主要帧是发生突出变化的帧。它们是动画的关键点。关键帧动画要求动画师指定对象的关键位置。然后计算机通过在这些位置之间平滑插值来自动填充缺失的帧。

过程动画

在过程动画中，对象是通过过程（一组规则）而不是关键帧动画来动画的。动画师指定规则和初始条件并运行模拟。规则通常基于用数学方程式表达的现实世界的物理规则。

行为动画

在行为动画中，自主角色至少在某种程度上决定自己的动作。这赋予角色一定的即兴发挥能力，并使动画师无需指定每个角色动作的每一个细节。

基于表演（动作捕捉）

另一种技术是动作捕捉，其中基于磁力或视觉的传感器以三维方式记录人和动物对象的动作。然后，计算机使用这些数据来为对象制作动画。

这项技术使许多著名运动员能够为体育视频游戏中的人物提供动作。动作捕捉在动画师中非常流行，主要是因为一些常见的 human actions 可以相对容易地捕捉到。然而，主体和图形角色的形状或尺寸之间可能存在严重差异，这可能导致精确执行方面的问题。

基于物理（动力学）

与关键帧动画和电影不同，模拟使用物理定律来生成图像和其他对象的运动。模拟可以很容易地用于生成略微不同的序列，同时保持物理真实感。其次，实时模拟允许更高程度的交互性，真人可以操纵模拟角色的动作。

相比之下，基于关键帧和动作的应用程序从预先计算的动作库中选择和修改动作。模拟的一个缺点是需要专业知识和时间来手工制作合适的控制系统。

关键帧

关键帧是在我们定义动画变化的帧。当我们创建逐帧动画时，每一帧都是关键帧。当有人在计算机上创建 3D 动画时，他们通常不会指定任何给定对象在每一帧上的精确位置。他们创建关键帧。

关键帧是对象改变其大小、方向、形状或其他属性的重要帧。然后，计算机计算出所有中间帧，从而为动画师节省大量时间。下图描绘了用户绘制的帧和计算机生成的帧。

变形

物体形状从一种形式转变为另一种形式的过程称为变形。这是最复杂的变换之一。

变形看起来像是两幅图像以非常流畅的动作融为一体。从技术角度来看，两幅图像会发生扭曲，并在它们之间发生淡入淡出。

打印页面