文章目录
- 前言
- 一. 计算机图形学是什么？有什么？为什么学？当前发展？
- 二. 基础概念
- 三. 基本图形的生成与计算
- 四. 图形变换与输出
- 五. 曲线与曲面
- 六. 基本造型方法
- 七. 网格重建与几何处理
- 八. 基于视觉与人工智能的三维重建
- 九. 真实感图形显示
- 十. 动态仿真与动画
- 十一. OpenGL中数据传输与图形渲染
- 十二. 计算机图形学中的优化技术与策略
- 十三. 三维运动碰撞与处理
- 十四. 计算机图形学简单应用
- 15. 习题答案
前言
欢迎来到 计算机图形学 的世界！无论你是刚刚入门还是希望系统提升自己的知识水平，这个教程将为你提供一个完整且系统的学习路径。从 基础概念 到 进阶技术，将一步步引导你掌握计算机图形学的核心知识，帮助你在这一领域取得扎实的进步。
计算机图形学是现代技术的基石之一，涉及 图形渲染、动态仿真、几何建模、视觉效果 等多个方面。它不仅是计算机科学的核心领域，也是许多前沿技术的基础，能从更底层的角度优化诸如计算机视觉、三维重建等领域的算法模型。虽然网络上有很多教程资源，但许多资料零散且不系统，而且缺乏深入应用，对于初学者来说可能难以建立系统的知识框架。因此，本文旨在以清晰且系统化的方式，从基础到深入，全面覆盖计算机图形学的各个重要方面。
本教程将系统地引导你从计算机图形学的基础开始，逐步深入到高级技术和应用。你将掌握基础概念，学习如何创建和渲染图形；学习关键技术和算法，如几何变换和光照模型；探索优化与性能提升，提高渲染效率；并通过实践项目将理论应用于实际开发中。
通过系统的学习和实践，你将建立一个全面的知识框架，为进一步的学习和实际应用打下坚实的基础。如果你对计算机图形学充满热情，希望 详细、清晰、系统 地掌握这一领域的知识以及有一定拓展延伸，本文将是你理想的选择。
【为做教学适配，使用OpenGL版本偏早，系统性学习OpenGL参考文章：LearnOpenGL，当然，如果有朝一日这个大坑能填完的话会写一篇手搓OpenGL的课程】
一. 计算机图形学是什么？有什么？为什么学？当前发展？
二. 基础概念
2.1 20道基础知识 Q&A
-
图形的分类、要素与表达方式
- 分类：
- 几何图形：简单的几何形状，如直线、圆形等。
- 真实感图形：复杂的、具有真实感的图形，如照片或3D模型。 - 要素：
- 几何要素：点、线、面等基本元素。
- 非几何要素：纹理、光照等附加效果。 - 表达方式：
- 点阵法：使用像素点阵表示图像。
- 参数法：通过计算图形位置比例等参数来描述图形，如矢量图形。
- 分类：
-
计算机图形系统的组成
- 图形系统：包括 计算、存储、对话、输入、输出 功能。
- 图形软件：实现特定功能的软件。
- 图形应用数据结构：存放图形对象描述信息的数据文件。
- 图形应用软件：
- 核心部分，处理图形生成与处理，如 PhotoShop、Maya 等。
- 图形支撑软件：提供规范性接口的基础软件。 - 图形硬件：包括显示器、显卡等硬件设备。
-
分辨率（光点、像素点、屏幕分辨率）
- 光点：显示器上最小的发光点，以直径表示。
- 像素点：屏幕上显示的最小单位，依据分辨率决定。
- 屏幕分辨率：屏幕上显示的像素数量，表示为
水平像素数量 × 垂直像素数量。
-
显示分辨率
- 文本显示模式：
水平方向最大字符数 × 垂直方向最大字符数。 - 图形显示模式：
水平方向最大像素点数 × 垂直方向最大像素点数。
- 文本显示模式：
-
显卡分辨率
- 显卡能输出给显示器的最大像素点数量。
- 电脑最高分辨率由 显卡 和 显示器 共同决定。
-
帧率与刷新率
- 帧率（FPS）：每秒钟显示的帧数。
- 刷新率：显示器每秒刷新的次数，单位为赫兹（Hz）。
-
帧缓存器
- 存储每帧图像数据的内存。
- 容量计算：
宽度 × 高度 × 色深（位数）。
-
显示器的点距
- 相邻像素点之间的距离，例如 15 寸显示器点距为 0.28mm。
-
显示卡的作用与性能指标
- 作用：用于处理和输出图像，与显示器组成计算机显示系统。
- 性能指标：包括显存容量、处理速度、支持的分辨率等。
-
等离子显示器原理
- 利用等离子体放电发光，每个像素由三个等离子体组成，显示色彩通过调节气体放电亮度实现。
-
液晶显示器原理
- 通过液晶分子的光线调制来控制光的通过与阻挡，从而显示图像。
-
阴极射线管显示原理
- 电子枪发射电子束击打荧光屏，产生图像。
-
彩色CRT常用方法
- 三基色法：使用红、绿、蓝三种颜色的电子束来混合显示各种颜色。
-
LOD技术
- Level of Detail：根据视距调整图形的细节层次，以优化渲染效率。
-
IBR技术
- Image-Based Rendering：一种基于图像的渲染技术，通过使用拍摄的图像来生成三维场景。
-
图形与图像的区别
- 图形：包括抽象的几何形状和模型。
- 图像：包含实际的像素数据，如照片或扫描图像。
-
图形图像的构成属性
- 图形：包括形状、颜色、线条等。
- 图像：包括像素、分辨率、色彩深度等。
-
位图与矢量图定义与区别
- 位图（点阵图/光栅图）：由像素点组成的图像，放大后会失真。
- 矢量图：由数学方程描述的图形，缩放后不失真。
-
图形扫描转化或光栅化的概念和步骤
- 概念：将矢量图形转换为像素点表示的过程。
- 步骤：确定像素位置、颜色填充、生成光栅图像。
-
系统设计画线算法应考虑的方面
- 算法效率：计算速度和资源消耗。
- 图形精度：线条的准确性和光滑度。
- 应用场景：不同用途（如2D或3D图形）对算法的要求。
2.2 计算机图形学设备及组成
2.2.1 设备分类
-
矢量型输入输出设备
- 以矢量形式处理图形数据。
- 主要包括矢量显示器和矢量绘图仪。
-
光栅扫描型输入输出设备
- 以光栅（像素）形式处理图形数据。
- 包括光栅显示器（如CRT、LCD）和光栅打印机。
2.2.2 输入设备
交互式输入设备
- 触摸屏：允许用户通过触摸屏幕来进行操作，常见于智能手机、平板电脑等设备。
- 手柄：用于游戏或模拟操作，通过物理按钮和操纵杆与计算机交互。
- 鼠标：最常用的输入设备之一，通过移动和点击进行精确操作。
二维图形输入设备
- 光笔：通过光电技术检测屏幕上的位置，通常用于图形绘制和标记。
- 数码相机：用于拍摄现实世界的图像，将其转换为数字格式进行处理。
- 图形扫描仪：将纸质文档或图像扫描成数字格式，以便计算机进行处理和存储。
三维图形输入设备
- 三维扫描仪与深度相机：用于捕捉物体的三维形状和深度信息，常用于3D建模和仿真。
- 三维物体材质外观捕捉设备：用于捕捉物体的材质特性和外观，提供真实感的三维渲染。
- 光穹：一种高精度的三维扫描设备，用于在光学条件下捕捉物体的完整三维信息。
2.2.3 输出设备
二维显示器
- 定义：二维显示器是指只能显示平面图像的显示设备，通常只能在两个维度（水平和垂直）上呈现内容。
- 常见类型：包括液晶显示器（LCD）、发光二极管显示器（LED）、阴极射线管显示器（CRT）等。
- 应用场景：广泛用于计算机显示器、电视屏幕、手机屏幕等，适合日常办公、视频播放、游戏等用途。
早期图形显示器为矢量式，后来变为光栅式，目前所有显示器虽然硬件不同，但是都采用了光栅式显示方式
矢量显示器
- 定义：矢量显示器是一种通过直接在屏幕上绘制线条来显示图像的设备。这些线条由显示器的电子束根据输入的矢量图形数据绘制，形成图像。
- 特点：
- 高分辨率：矢量显示器的分辨率不受像素网格限制，理论上可以达到无限高的分辨率。
- 线条精度：适合显示复杂的线条图形，如CAD设计、航空图等。
- 局限性：无法显示填充区域的图像，通常只适用于显示线条和轮廓。
- 应用场景：早期的航空、军事显示系统，矢量图形游戏机等。
比较经典的可以看看 60年前的4K显示器，1970年的Tektronix CRT显示器
光栅扫描式显示器与帧缓存原理
- 定义：光栅扫描式显示器通过逐行扫描的方式，将图像的每个像素逐一显示在屏幕上。它是当前最常见的显示技术，用于显示各种类型的图像和视频。
- 特点：
- 像素显示：通过光栅扫描的方式在屏幕上逐行绘制图像，每一行由多个像素点组成。
- 广泛适用：能够显示复杂的图形和色彩丰富的图像，适合多种显示需求。
- 局限性：分辨率受限于屏幕的像素数量，图像质量会受到像素网格的影响。
- 应用场景：广泛用于计算机显示器、电视屏幕、手机屏幕等，适合从日常办公到高清电影播放的各种用途。
2.3 帧缓存原理详细解释
帧缓存（Frame Buffer） 是计算机图形系统中用于存储图像数据的内存区域。它的主要作用是保存即将显示到屏幕上的图像数据。帧缓存的内容会不断被刷新，以生成动态的图像效果。
2.3.1 帧缓存的基本概念
帧缓存通常是一个二维数组，每个元素对应屏幕上的一个像素。每个像素包含颜色信息，这些信息被存储在内存中，以便最终显示在屏幕上。帧缓存的工作流程如下：
- 图像生成：计算机生成图像数据，将这些数据存储在帧缓存中。
- 图像显示：帧缓存中的数据被送到显示器，显示器将这些数据转换成图像，并显示在屏幕上。
- 刷新：帧缓存内容不断更新，屏幕上的图像也随之改变，形成动态画面。
2.3.2 帧缓存的结构
- 像素（Pixel）：帧缓存的基本单元，每个像素包含了显示颜色的信息。在RGB模式下，每个像素可能由红、绿、蓝三个颜色分量组成。
- 分辨率（Resolution）：帧缓存的分辨率决定了其存储的像素数量，例如1920x1080分辨率的帧缓存包含1920x1080个像素。
- 颜色深度（Color Depth）：每个像素的颜色信息所占用的位数。例如，24位颜色深度的帧缓存意味着每个像素由8位的红色、绿色和蓝色组成，总共24位。
以上是一个能产生8种灰度等级光强的帧存储器，中间通过引入一个字宽W=4的颜色查找表来限制帧缓存器的增加以降低成本，当W > N时可以有 2 W 2^{W} 2W个灰度等级，但每次只有 2 N 2^{N} 2N可用 ，而对于我们常见的0~255RGB模式显示原理如下：
2.3.3 总结
帧缓存是计算机图形系统中关键的组成部分，它负责存储和管理图像数据，确保图像能够顺利地显示在屏幕上。了解帧缓存的工作原理，对于掌握图形系统的运作、优化显示效果具有重要意义。
三维显示器
- 定义：三维显示器能够显示具有深度感的图像，使观众感受到立体效果。它通过技术手段让图像从平面延伸到三维空间。
- 常见类型：包括裸眼3D显示器、使用3D眼镜的显示器、全息投影设备等。
几种显示技术比较
2.3 OpenGL的基础知识
2.3.1 介绍
OpenGL (Open Graphics Library，开放式图形库) 一般被认为是跨平台的图形渲染 API（应用程序接口），主要用于创建二维和三维图形应用程序。它提供了一组灵活且强大的命令，使开发者能够生成复杂的图形。目前已成为事实上的工业标准。
实际上OpenGL并不是 API ，仅仅是一个由Khronos组织制定并维护的规范(Specification)。OpenGL规范严格规定了每个函数的执行与输出。内部每个函数是如何实现的由OpenGL库的开发者自行决定。因为OpenGL规范并没有规定实现的细节，具体的OpenGL库允许使用不同的实现，只要其功能和结果与规范相匹配（亦即，作为用户不会感受到功能上的差异）。
OpenGL的大多数实现都是由 显卡厂商 编写的，当产生一个bug时通常可以通过升级显卡驱动来解决。（这也是为什么总是建议你偶尔更新一下显卡驱动。）
所有版本的OpenGL规范文档都被公开的寄存在 Khronos 那里。如果你想深入到OpenGL的细节与具体运作，这个规范也是一个很棒的参考。
2.3.2 工作原理
-
上下文 (Context)：OpenGL自身是一个巨大的状态机(State Machine)，在使用 OpenGL 之前，必须创建一个 OpenGL 上下文。上下文是 OpenGL 所有状态、资源和操作的集合。通常通过平台特定的工具库（如 GLFW、GLUT）来创建上下文。
例如：
glfwInit(); // 初始化 GLFW GLFWwindow* window = glfwCreateWindow(800, 600, "OpenGL Window", NULL, NULL); // 创建窗口并绑定 OpenGL 上下文 glfwMakeContextCurrent(window); // 设置当前上下文 -
渲染管线：OpenGL 的核心是图形渲染管线，这是一系列处理步骤，将三维模型转换为可显示的二维图像。渲染管线分为 可编程管线 和 固定功能管线。（可以当成对输入的图像数据的处理流水线）
早期的OpenGL使用立即渲染模式（Immediate mode，也就是固定渲染管线），这个模式下OpenGL像数学公式一样简单但不够灵活，而开发者迫切希望能有更多的灵活性。随时间推移，开发者为了实现更精细的功能往往需要叠加嵌套多个“数学公式”（固定渲染管线），效率远不如自行编写公式，于是 从OpenGL3.2开始，规范文档开始废弃立即渲染模式，并鼓励开发者在OpenGL的核心模式(Core-profile)（可编程渲染管线）下进行开发。
2.4 计算机图形学的历史渊源（可跳过）
计算机图形学的起源可以追溯到20世纪50年代。当时，计算机主要用于数值计算，但一些研究者开始探索如何利用计算机生成图像。这一时期的标志性事件包括：
- 1950年代：MIT的 Whirlwind 项目展示了早期的图形显示能力，使用矢量显示器绘制简单的线条图形。
- 1962年：Ivan Sutherland 开发了 Sketchpad，这是第一个图形交互系统，被认为是现代计算机图形学的奠基之作。
- 1963年：IBM发布了第一个商业矢量图形显示器。
- 1968年：Sutherland 开发了第一个虚拟现实系统（The Sword of Damocles），进一步推动了图形学的发展。
1970年代和1980年代是计算机图形学快速发展的时期，主要体现在以下几个方面：
- 1970年代：开发了多边形图形技术，允许渲染复杂的3D形状。1974年，Ed Catmull（后来的皮克斯创始人之一）提出了 z-buffering 技术，用于隐藏面消除。
- 1982年：SGI（硅谷图形公司）发布了GL（后来成为OpenGL的基础），这是一个用于3D图形渲染的标准API。
1990年代至今：图形硬件与实时渲染
随着计算机图形硬件的发展，尤其是GPU（图形处理单元）的出现，实时3D渲染成为可能：
- 1992年：OpenGL发布，成为3D图形渲染的行业标准。
- 2000年代：随着GPU性能的飞跃，计算机图形学在游戏、电影特效、虚拟现实等领域得到了广泛应用。
2.5 习题一
- 简述随机扫描显示器与光栅扫描显示器工作原理与特点
- 帧缓冲器与显示器分辨率关系
三. 基本图形的生成与计算
3.1 直线的扫描转换
3.1.1 直线段扫描转换算法概述
核心方法：将直线段从数学形式转换为一系列离散的像素点，以在栅格设备（如显示器）上显示。
实质是寻找一个最佳逼近直线的像素序列并向光栅中填入色彩数据。
3.1.2 数值微分法
核心思想：增量
当研究各象限直线生成规律时可以发现如下规律：
- Dx、Dy的符号与dx、dy符号相同
- 当|dx|>|dy|时： ∣ d x ∣ = 1 , ∣ d y ∣ = m ; 否则 ∣ d x ∣ = 1 / m , ∣ d y ∣ = 1 |dx|=1, |dy|=m;否则 |dx|=1/m, |dy|=1 ∣dx∣=1,∣dy∣=m;否则∣dx∣=1/m,∣dy∣=1
据此可以简化DDA算法为：
void DDA_Line(float x0, float y0, float x1, float y1) {
float dx = x1 - x0;
float dy = y1 - y0;
int steps = max(abs(dx), abs(dy));
float xIncrement = dx / steps;
float yIncrement = dy / steps;
float x = x0;
float y = y0;
for (int i = 0; i <= steps; i++) {
SetPixel(round(x), round(y)); // 绘制像素点
x += xIncrement;
y += yIncrement;
}
}
3.1.3 中点画线法
- 直线方程一般式：
F
(
x
,
y
)
=
0
F(x, y) = 0
F(x,y)=0，
A
x
+
B
y
+
C
=
0
Ax + By + C = 0
Ax+By+C=0
- 直线上的点： F ( x , y ) = 0 F(x,y)=0 F(x,y)=0
- 直线上方的点： F ( x , y ) > 0 F(x,y)>0 F(x,y)>0
- 直线下方的点： F ( x , y ) < 0 F(x,y)<0 F(x,y)<0
- 核心是根据最大位移方向上与中点的偏差决定是否偏走。
算法推导过程
- 将点 M 带入直线方程： F ( x m , y m ) = A x m + B y m + C F(x_m, y_m) = Ax_m + By_m + C F(xm,ym)=Axm+Bym+C
- 计算
d
i
d_i
di：
d
i
=
F
(
x
i
+
1
,
y
i
+
0.5
)
=
A
(
x
i
+
1
)
+
B
(
y
i
+
0.5
)
+
C
d_i = F(x_i + 1, y_i + 0.5) = A(x_i + 1) + B(y_i+ 0.5) + C
di=F(xi+1,yi+0.5)=A(xi+1)+B(yi+0.5)+C
- 当 d i < 0 d_i<0 di<0 时，Q在中点M上方，取 P u P_u Pu 下一个像素点
- 当 d i > 0 d_i>0 di>0 时，Q在中点M下方，取 P d P_d Pd 下一个像素点
- 当 d i = 0 d_i=0 di=0 时，Q在中点M下方，取 P u P_u Pu 或者 P d P_d Pd 均可
递推公式：
{ x i + 1 = x i + 1 y i + 1 = { y i + 1 + 1 ( d > 0.5 ) y i ( d ≤ 0.5 ) \begin{cases} x_{i+1} = x_i + 1 \\ y_{i+1} = \begin{cases} y_{i+1} + 1 & (d>0.5)\\ y_i & (d \leq 0.5) \end{cases} \end{cases} ⎩ ⎨ ⎧xi+1=xi+1yi+1={yi+1+1yi(d>0.5)(d≤0.5)
中点画线法将算法提高到整数加法，效率优与DDA
3.1.4 Bresenham算法（重点）
该算法在1965年被Bresenham提出，该算法拥有更好的效率与适用范围
- 假设 x + 1 x+1 x+1，则 y y y 的递增(减)量为 0 0 0 或 1 1 1，它取决于实际直线与光栅网格点的距离，这个距离的最大误差为 0.5 0.5 0.5.
- 误差项 d d d 初值 d 0 d_0 d0 ， d = d + k d = d + k d=d+k。一旦 d > 1 d > 1 d>1，就把它减去1，保证 d d d 的相对性，且在 0 、 1 0、1 0、1 之间。
可以观察到我们从中点画线法的递推公式中作出以下改进:
- 改进1：令 e = d − 0.5 e =d-0.5 e=d−0.5
- 改进2：令 e ∗ 2 ∗ Δ x e * 2 * Δx e∗2∗Δx 替换 e
Bresenham算法的优点如下：
- 不必计算直线的斜率，因此不必做除法
- 不用浮点数，只用整数
- 只做整数加减与乘 2 2 2 运算，而乘 2 2 2 运算可以直接移位
3.2 圆的扫描转换的Bresenham算法
基本思想
在每一步中，根据当前像素点与理想圆的位置关系，决定下一个像素点的位置。它通过比较两个可能的像素点与理想圆的距离，选择距离更近的像素点作为下一个像素点。
初始化：
- 确定圆的半径 r r r 和圆心坐标 ( x c , y c ) (x_c,y_c) (xc,yc)
- 设当前像素点坐标为 ( x , y ) (x,y) (x,y), 初始值为 ( 0 , r ) (0,r) (0,r)
- 计算决策变量 d = 3 − 2 r d = 3 - 2r d=3−2r
绘制八分之一圆：
- 当
x
≤
y
x \leq y
x≤y时，执行以下步骤：
- 如果 d < 0 d < 0 d<0，则 d = d + 4 x + 6 , x = x + 1 , y d = d + 4x + 6,x = x + 1,y d=d+4x+6,x=x+1,y不变
- 如果 d > = 0 d >= 0 d>=0，则 d = d + 4 ( x − y ) + 10 , x = x + 1 , y = y − 1 d = d + 4(x - y) + 10,x = x + 1,y = y - 1 d=d+4(x−y)+10,x=x+1,y=y−1
- 将当前像素点 ( x , y ) (x,y) (x,y)以及其对称点绘制出来
最后利用对称性绘制其余七个八分之一圆
3.3 多边形扫描转换
3.3.1 多边形表示方法
-
顶点表示
- 定义：顶点表示是用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换。
- 缺点：没有名且指出哪些像素在多边形内，无法直接用于面着色
-
点阵表示
- 定义：点阵表示是用位于多边形内的像素集合来刻画多边形。这种表示丢失了许多几何信息 (如边界、顶点等)，但它却是光栅显示系统显示时所需的表示形式。
- 定义：点阵表示是用位于多边形内的像素集合来刻画多边形。这种表示丢失了许多几何信息 (如边界、顶点等)，但它却是光栅显示系统显示时所需的表示形式。
把多边形的顶点表示转换为点阵表示，即为多边形的扫描转换
3.3.2 扫描线填色算法（X-扫描线算法）
这类算法建立在多边形边界的矢量数据上，可用于程序填色与交互填色
基本思想：用扫描线顺序扫描多边形，将扫描线与多边形一系列交点按成对
x
x
x 坐标记录，对成对
x
x
x 坐标区间栅格进行填色
算法过程：
- ① 确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大 y y y 值 ( y m i n , y m a x ) (y_{min},y_{max}) (ymin,ymax)
- ② 从
y
m
i
n
y_{min}
ymin 到
y
m
a
x
y_{max}
ymax 依次用扫面线进行扫描填充
- a. 求交：计算扫描线与多边形各边的交点
- b. 排序：把所有交点按递增顺序进行排序
- c. 交点配对：第一个与第二个，第三个与第四个
- d. 区间填色：把这些相交区间内的像素置成不同于背景色的填充色
问题处理与改进
- 水平边处理
- 水平边 ( y 1 , y 2 ) (y_1,y_2) (y1,y2) 与水平扫描线重合，无法求交点，因此直接删去
- 递归算法求扫描线与边交点
- 以 ( x 1 , y 1 ) ( x 2 , y 2 ) (x_1,y_1) (x_2,y_2) (x1,y1)(x2,y2) 端点的边与第 i + 1 i+1 i+1 条扫描线的交点为
{ y i + 1 = y i − 1 x i + 1 = x i − ( x 2 − x 1 / y 2 − y 1 ) \begin{cases} y_{i+1} = y_i - 1 \\ x_{i+1} = x_{i} - ({x_2 -x_1}/{y_2 -y_1}) \end{cases} {yi+1=yi−1xi+1=xi−(x2−x1/y2−y1)
- 多边形交点取舍问题
- a. 若共享顶点的两条边分别落在扫描线的两边，交点只算 1 1 1 个
- b. 若共享顶点的两条边在扫描线的同一边，交点个数为 0 0 0 个或 2 2 2 个。需要检查两条边另外两个端点的 y y y 值来判断。
- 通过活性边表减少求交量计算
- 对于一根扫描线而言，与之相交的边仅占一部分，对所 >有边求交点的操作存在很大资源浪费
- 活性边表（AET）
- AET：把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点 x xx 坐标递增的顺序存放在一个链表数据结构中。
- 链表节点内容：
- x x x :当前扫描线与多边形边交点坐标
- Δ x Δx Δx ：从当前扫描线到下一条扫描线间的 x x x 增量， Δ x = 1 / k Δx=1/k Δx=1/k
- y m a x y_{max} ymax：该边所交的最高扫描线的坐标值 y m a x y_{max} ymax ,可以判断何时 “抛弃” 该边
-
- 新边表（NET）
- 首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个节点，称为一个吊桶，对应多边形覆盖的每一条扫描线。
- NET挂在与该边低端 y y y 值相同的扫描线桶中，即存放在该扫描线第一次出现的边。
- NET 节点内容
- y m a x y_{max} ymax：该边 Y m a x Y_{max} Ymax
- x m i n x_{min} xmin：该边较低点的 x x x 坐标 x m a x x_{max} xmax
- 1 / k 1/k 1/k：该边斜率
-
- 每次进行新扫描要对已有的边进行三个处理：
- 是否被去除
- 如果不去除则对数据进行更行【更新其 x x x 值： x = x + 1 / k x =x +1/k x=x+1/k】
- 查看有无新的边进来，新的边在NET中可以插入排序插进来
实现源码参考
计算机图形学のY-X扫描线算法
其程序整体结构如下：
- 小结
- 扫描线法可以实现已知任意多边形域边界的填充。该填充算法是按扫描线的顺序，计算扫描线与待填充区域的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作。
- 缺点：带填充区域的边界线必须事先知道，因此它的缺点是无法实现对未知边界的区域填充。
3.3.3 边缘填充算法
- 基本思想：
- 按任意顺序处理多边形每条边。求出该边与扫描线的交点，然后对右方所有像素进行 取补 操作，多变形所有边处理完成后即能完成填充。
边缘填充算法源码参考
Graphics—边缘填充算法
- 特点：算法简单，但对于复杂图形可能会导致每个像素被访问多次。资源浪费比有效边算法大得多
3.3.4 栅栏填充算法4
-
基本思想
- 栅栏指的是一条过多边形顶点且与扫描线垂直的直线。它把多边形分成两半。在处理每条边与扫描线的交点时，将交点与栅栏之间的像素取补。
-
栅栏填充算法源码参考
计算机图形学 栅栏填充算法 C++源码及运行示例 -
特点：
- 优点：
- 栅栏填充算法适合规则图形，尤其是那些具有平行边界的多边形，填充速度快且容易实现。
- 算法的计算过程较为简单，不需要处理复杂的边界交点。
- 缺点：
- 对于形状不规则的多边形，栅栏填充算法的效率较低，填充质量也可能不理想。
- 需要为每种多边形设计合适的栅栏线方案，否则填充效果不佳。
- 优点：
3.3.5 边界标志算法
- 算法原理
- 边界标记：帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的像素打上标志。
- 区域填充：然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。
- 硬件实现优势：由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。
3.4 区域填充算法
主要任务是对封闭区域进行颜色或图案的填充。目前越来越多先进的区域填充算法被提出，以提高填充速度、减少计算资源消耗，并增强处理复杂形状的能力。
3.4.1 区域填充基本概念
- 区域：已经形成点阵的像素集合
- 区域填充：将区域内的一点常称为（种子点）赋予颜色，然后扩展至整个区域
- 区域表示形式：
- 内点表示
- 枚举出区域内部的所有像素，内部的所有像素着同一个颜色，边界像素着与内部像素不同的颜色。
- 边界表示
- 枚举出边界上的所有像素，边界上的所有像素着同一个颜色，内部像素着与边界像素不同的颜色。
- 内点表示
- 连通区域
- 4向连通
- 从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素。
- 8向连通
- 从区域上一点出发，可通过八个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。
- 4向连通
3.4.2 四联通种子填色算法
- 算法思想：从区域内的某个种子点开始，向四个方向（上下左右）递归填充，直到整个区域填满
- 算法步骤：
- 选择种子点：在封闭区域内选择一个未填充的种子点作为起点。
- 递归检查：从种子点出发，检查其上下左右四个邻域像素。如果邻域像素属于待填充区域且未被填充，则对其进行填充，并将该像素作为新的种子点，继续递归填充。
- 停止条件：当所有可填充的像素都被处理后，递归过程结束，区域填充完成。
- 局限性：
- 该算法可能导致栈溢出，特别是在处理大面积或复杂区域时。
- 填充效率较低，适合处理较小和简单的图形。
四（八）联通种子填充算法详细说明与源码参考
【Algorithm】种子填充算法
3.4.3 区域填充与多边形扫描转换对比
3.5 字符生成
3.5.1 点阵式字符
3.5.2 矢量式字符
3.5.3 方向编码式字符
3.5.4 轮廓字型技术
3.6 圆形求交
3.6.1 求交点算法（列出几何公式，不做算法设计）
3.6.2 求交线算法
3.6.3 包含判定算法
3.6.3.1 叉积判断法
3.6.3.2 夹角之和检验法
3.6.3.3 交点计数检验法
3.6.4 重叠判定算法
3.6.5 凸包计算
3.7 图形剪裁
3.7.1 直线剪裁 Cohen-Sutherland 算法、中点分割算法与 Liang-Barsky 算法
3.7.2 多边形裁剪 Sutherland-Hodgeman 算法
3.7.3 字符串裁剪（串精度、字符精度、像素精度）
3.8 走样与反走样技术
3.8.1 走样现象
3.8.2 反走样技术（非加权与加权区域采样方法）
3.9 OpenGL中的二维图形显示
3.10 习题二
四. 图形变换与输出
4.1 几何变换
4.1.1 二维图形几何变换
4.1.1.1 向量基础
4.1.1.2 二维图形变换原理
4.1.1.3 平移变换
4.1.1.4 旋转变换
4.1.1.5 变比变换
4.1.1.6 变换矩阵与联级变换
4.1.2 三维图形几何变换
4.1.2.1 旋转变换
4.1.2.2 变比变换
4.1.3 曲线几何变换
4.2 坐标系统及其变换
4.2.1 坐标系统
4.2.2 观察变换
4.2.3 投影变换
4.2.3.1 平行投影
4.2.3.2 透视投影
4.2.4 窗口视区变换
4.3 OpenGL中的变换
4.4 习题三
五. 曲线与曲面
5.1 曲线和曲面的绘制
5.2 Bezier曲线曲面
5.3 B样条曲线曲面
5.4 NURBS曲线曲面
5.5 细分曲线曲面
5.6 OpenGL中的曲线绘制
5.7 习题四
六. 基本造型方法
6.1 概述
6.2 结构实体几何模型
6.3 分解模型
6.3.1 八叉树表达
6.3.2 八叉树操作
6.3.3 线性八叉树
6.4 边界模型
6.4.1 翼边结构
6.4.2 半边结构
6.4.3 欧拉操作
6.4.4 基本体元生成
6.5 非传统造型技术
6.5.1 分型造型
6.5.2 粒子系统
6.6 习题五
七. 网格重建与几何处理
7.1 Delaunay网格重建
7.2 网格重建的多项式拟合
7.3 基于三维微分属性的网格重建
7.4 网格修补
7.5 网格简化
7.6 网格滤波与光测
7.7 习题六
八. 基于视觉与人工智能的三维重建
8.1 基于双目视觉的三维重建
8.1.1 基本原理与流程
8.1.2 传统立体匹配方法
8.1.3 基于深度视觉的端到端立体匹配
8.2 基于运动的三维形状重建
8.2.1 从运动恢复结构的基本流程与概念
8.2.2 深度学习在运动恢复结构中的应用
8.3 基于明暗的三维形状重建
8.3.1 基于明暗的三维形状重建基本原理与方法
8.3.2 深度学习在明暗重建形状中的应用
8.4 基于先验知识的三维重建
8.4.1 基于先验知识的几何形状参数化模型
8.4.2 基于学习的参数化人体重建
8.5 习题七
九. 真实感图形显示
9.1 真实感图形显示的物理基础
9.1.1 光在场景中的运输
9.1.2 光源的属性和表达
9.1.3 物体表面的反射属性
9.1.4 颜色空间
9.2 绘制方程
9.2.1 概述
9.2.2 纹理映射的基本原理
9.2.3 纹理映射的反走样
9.2.4 纹理映射在绘制中的应用
9.3 基于几何投影的绘制方法
9.3.1 概述
9.3.2 表面光照模型的简化计算
9.3.3 面消隐
9.3.4 明暗光滑处理
9.3.5 阴影生成
9.4 光线跟踪
9.4.1 概述
9.4.2 Whitted光照模型
9.4.3 采样策略
9.4.4 反射和折射
9.5 习题八
十. 动态仿真与动画
10.1 动态仿真的基本概念
10.1.1 动态仿真的数学建模
10.1.2 物理学基础与应用
10.2 动画技术的基本概念
10.2.1 动画类型
10.2.2 动画建模与渲染
10.2.3 关键帧动画
10.3 骨骼动画与形状变换
10.3.1 骨骼动画的基础
10.3.2 骨骼动画与形状变换算法
10.4 基于GPU的光线跟踪程序实现
10.5 习题九
十一. OpenGL中数据传输与图形渲染
11.1 OpenGL中的数据传输
11.1.1 数据类型
11.1.2 数据结构
11.1.3 数据传输流程
11.2 OpenGL中的图形渲染
11.2.1 渲染流程
11.2.2 渲染技术
11.2.3 渲染优化方法
11.3 OpenGL性能优化技术
11.3.1 渲染性能分析
11.3.2 渲染优化策略
11.3.3 硬件加速技术
11.4 习题十
十二. 计算机图形学中的优化技术与策略
12.1 光照与阴影优化
12.1.1 实时光照模型
12.1.2 阴影映射技术
12.1.3 动态光照优化
12.2 模型简化与纹理优化
12.2.1 网格简化技术
12.2.2 纹理压缩技术
12.2.3 优化策略
12.3 渲染优化与算法
12.3.1 优化算法
12.3.2 渲染效果优化
12.3.3 硬件加速优化
十三. 三维运动碰撞与处理
13.1 碰撞处理简介
13.2 离散碰撞检测技术
13.2.1 BVH加速结构
13.2.2 空间哈希
13.2.3 三角形离散求交
13.3 连续碰撞检测技术
13.3.1 三角形连续碰撞求交
13.3.2 连续分离轴技术
13.3.3 几何过滤器
13.4 基于多核/GPU的碰撞检测并行加速
13.4.1 面向多核并行加速
13.4.2 面向GPU的并行加速
13.5 物理仿真中的碰撞响应
13.5.1 刚体仿真
13.5.2 柔体仿真
13.5.3 流体仿真
13.6 碰撞处理开放平台
13.6.1 多核加速的并行连续碰撞检测库
13.6.2 GPU加速的布料仿真API
13.7 习题十
十四. 计算机图形学简单应用
14.1 机械运动中的碰撞检测
14.1.1 传动装置运动仿真
14.1.2 机械臂运动仿真
14.2 科学计算可视化
14.2.1 科学计算可视化概念与意义
14.2.2 标量场可视化
14.2.3 矢量场可视化
14.2.4 张量场可视化
14.2.5 可视化应用
15. 习题答案
二、基础概念
-
简述随机扫描显示器与光栅扫描显示器工作原理与特点
-
随机扫描显示器:
- 工作原理：随机扫描显示器（也称矢量显示器）直接控制电子束沿着图形的轮廓进行绘制，而不是逐行扫描。电子束在屏幕上移动时，只绘制图形的边界，适合绘制线条和简单图形。
- 特点：
- 精确性高：非常适合绘制直线和简单几何图形。
- 不适合绘制复杂图形：对于复杂的填充图形或图像，效率较低。
- 低分辨率：一般分辨率较低，不适合显示复杂的图像。
-
光栅扫描显示器:
- 工作原理：光栅扫描显示器逐行扫描屏幕，从上到下，从左到右绘制图像。每一行由一系列像素组成，通过改变每个像素的颜色来显示图像。
- 特点：
- 适合显示复杂图像：能够显示复杂的图形和图像，包括照片、视频等。
- 分辨率高：分辨率较高，适合显示细节丰富的图像。
- 通用性强：被广泛应用于各种显示设备，如电视、电脑显示器等。
-
-
帧缓冲器与显示器分辨率关系
-
帧缓冲器是用于存储图像数据的内存区域，包含了显示器每个像素的颜色信息。帧缓冲器的大小和显示器的分辨率直接相关。
-
分辨率越高，需要存储的像素数据越多，帧缓冲器的大小也随之增加。例如，对于一个1920x1080分辨率的显示器，每帧图像包含 2,073,600 个像素，如果每个像素用 32 位（4 字节）表示颜色，则帧缓冲器需要大约 8MB 的存储空间。
-
帧缓冲器大小计算:
- 计算公式：
帧缓冲器大小 = 分辨率宽度 x 分辨率高度 x 每个像素所占字节数 - 示例：对于分辨率为 1920x1080 的显示器，假设每个像素占用 4 字节，帧缓冲器的大小为：
1920 x 1080 x 4 = 8,294,400 字节（约 8MB）
- 计算公式：
-