山东大学软件学院软件工程计算机图形学复习笔记（2025）

写在前面：

现在是考完试的第二天，考试的内容还是有一部分没有复习到的……

• 根据三角形的3个顶点坐标和内部某点坐标D，写出点D的基于面积的权重坐标
• Bresenham的算法描述与改进策略（这里ppt上很不清晰）以及直线反走样的算法思想

而且！今年（2025）居然没有考任何一个裁剪算法！我复习的好认真的！哭哭

总之预祝学弟学妹们考试顺利吧

Review

以简答题、论述题、程序题为主，包括上课讲过的简单数学计算

实验0.4，考试0.6 （考的一定讲过、记得重要的opengl函数叫什么、个别单词用英文、数学原理要理解）

最后一节课zyf老师重点强调的内容如下：

1. 几何处理阶段

• 建模
  • 3D模型表示（多边形网格、参数曲面等）
• Delaunay三角化
  • 三角剖分算法（最大化最小角、空外接圆性质）
• 拉普拉斯算子
  • 网格平滑或几何处理（如拉普拉斯网格变形）

2. 变换与投影

• 仿射变换
  • 旋转、缩放、平移
  • OpenGL函数：glRotate, glScale, glTranslate
• 摄像机定义
  • 视点（eye）、目标（at）、上向量（up）
  • OpenGL函数：gluLookAt
• 投影变换
  • 正交投影（glOrtho）
  • 透视投影（gluPerspective/glFrustum）
• 投影前标准化
  • 规范化设备坐标（NDC，-1到1范围）
  • 目的：简化裁剪和深度缓冲（z-buffer）处理

3. 消隐与裁剪

• 消隐
  • 背向面剔除（Backface Culling，基于法向量与视线夹角）
  • 深度缓冲（Z-buffer算法，glEnable(GL_DEPTH_TEST)）
• 裁剪（Clipping）
  • 算法：Cohen-Sutherland（线段裁剪）、Cyrus-Beck、Liang-Barsky、Sutherland-Hodgman（多边形裁剪）

4. 光栅化与着色

• 光栅化
  • Bresenham算法（直线/圆扫描转换）
  • 扫描线填充（多边形填充）
• 光照明模型
  • Phong模型（环境光+漫反射+高光）
  • Blinn-Phong（改进高光计算，半角向量）
• 着色（Shading）
  • Flat（平面）、Gouraud（插值顶点颜色）、Phong（插值法向量）

5. 纹理与映射

• 纹理映射
  • UV坐标映射（3D→2D参数化）
• Mipmap
  • 生成：预计算多级分辨率纹理
  • 存储：金字塔结构
  • 目的：解决远处纹理走样（OpenGL：glGenerateMipmap）
• 凹凸映射
  • 法线贴图（Normal Mapping）
  • 环境映射（Environment Mapping，如立方体贴图）

6. 显示与优化

• 双缓冲机制
  • 前缓冲（显示）+后缓冲（绘制）
  • 解决闪烁问题（OpenGL：glutInitDisplayMode(GLUT_DOUBLE)）
• 帧缓冲（Frame Buffer）
  • 颜色缓冲、深度缓冲、模板缓冲

7. 其他高级处理

• 图像矢量化
  • 目的：将位图转为矢量图形（缩放无损）
  • 方法：Marching Squares
• 隐式平面网格化
  • 方法：Marching Cubes

重点补充

图形绘制流水线 (Classic Graphics Pipeline)

图形绘制流水线用于将3D场景渲染成2D图像。整个流程可以概括为以下步骤:

顶点(Vertex) → 顶点处理(Vertex Processor) → 裁剪和图元组装(Clipper and Primitive Assembly) → 光栅化(Rasterizer) → 片元处理(Fragment Processor) → 像素(Pixels)

1. 顶点处理：流水线的起点,处理3D模型的顶点数据。它执行坐标变换和颜色计算,这些操作可以并行进行,提高效率。
2. 裁剪和图元组装：将顶点组装成基本图元,然后进行裁剪,去除视见体外的部分。
3. 光栅化：将图元转换为屏幕上的像素,生成包含颜色、位置和深度信息的片元。
4. 片元处理：处理光栅化生成的片元,进行纹理映射、光照计算、透明度测试和深度测试等操作。
5. 像素：处理后的片元信息被用来更新帧缓存中的像素数据，最终会显示在屏幕上。

1. 顶点处理 (Vertex Processing)

• 输入: 3D模型的顶点数据
• 主要功能:
  • 执行坐标变换
  • 计算每个顶点的颜色值
• 特点:
  • 各个顶点的处理是彼此独立的
  • 可以并行处理,提高效率
• 坐标变换:
  • 每次变换都可以用一个矩阵表示
  • 多次变换 = 矩阵的相乘或级联
• 常见变换:
  • 模型变换: 物体空间 → 世界空间
  • 视图变换: 世界空间 → 相机空间
  • 投影变换: 相机空间 → 裁剪空间

2. 裁剪和图元组装 (Clipping and Primitive Assembly)

• 图元组装:
  • 将顶点组装成基本图元(如线段、三角形、多边形)
  • 必须在裁剪之前完成
• 裁剪:
  • 目的: 去除视见体(view frustum)外的部分
  • 过程: 逐个图元进行裁剪
  • 结果: 保留完全在视见体内的图元,去除完全在视见体外的图元,部分可见的图元会被切割

3. 光栅化 (Rasterization)

• 定义: 将图元转换为屏幕上的像素
• 输入: 图元(如三角形)
• 输出: 一组片元(fragments)
• 片元信息:
  • 颜色
  • 位置(屏幕坐标)
  • 深度信息(用于处理遮挡关系)
• 过程:
  • 确定图元覆盖的像素
  • 为每个被覆盖的像素生成一个片元

4. 片元处理 (Fragment Processing)

• 目的: 确定每个片元的最终颜色
• 输入: 光栅化生成的片元
• 处理:
  • 纹理映射: 将纹理应用到片元
  • 光照计算: 根据光源和材质属性计算片元颜色
  • alpha测试: 根据透明度决定是否丢弃片元
  • 深度测试: 处理遮挡关系
• 输出: 更新帧缓存中的像素颜色

5. 像素 (Pixels)

• 最终结果: 帧缓存中的像素数据
• 这些像素数据最终会被显示在屏幕上,形成我们看到的图像

双缓冲（Double Buffer）

1. 是什么？

双缓冲机制使用两个缓冲区来存储和显示图像：前缓冲（Front Buffer）和后缓冲（Back Buffer）。

• 前缓冲：当前显示在屏幕上的图像。
• 后缓冲：正在绘制的下一帧图像。

2. 为什么需要双缓冲？

• 单缓冲的问题：
  在单缓冲模式下，绘制直接发生在显示缓冲器中。当绘制较复杂时（例如逐像素渲染），用户会看到绘制过程的中间状态，导致屏幕闪烁或画面撕裂。
• 双缓冲的解决方式：
  所有绘制操作在后端缓冲器完成，完成后通过交换缓冲器瞬间显示到屏幕，确保画面连续性和流畅性。

3. 工作原理

1. 在后缓冲中绘制新的一帧。
2. 完成绘制后，交换前缓冲和后缓冲。
3. 新的一帧立即显示在屏幕上，同时开始在新的后缓冲中绘制下一帧。

4. 意义

• 消除闪烁：用户只看到完整的帧，不会看到绘制过程。
• 提高性能：可以在绘制新帧的同时显示当前帧。
• 平滑的动画效果：帧之间的过渡更加连贯。

5. 代码示例（OpenGL/GLUT）

glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB | GLUT_DEPTH);// 设置显示模式：双缓冲、RGB颜色模式、深度测试
// 设置窗口大小和位置并创建窗口……
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);// 清除颜色缓冲和深度缓冲
//进行图形绘制……
glutSwapBuffers();// 交换前后缓冲    

Delaunay三角化及其性质

定义

Delaunay三角化是针对给定点集P的一种三角剖分，满足空圆性质：对于任意三角形，其外接圆内不包含P中的其他点。

四个重要性质

1. Voronoi图的对偶图：Delaunay三角化与Voronoi图互为“对偶”

2. 形成点集的凸包：Delaunay三角化的外部边界恰好是点集 P 的凸包（即包含所有点的最小凸多边形）

3. 满足空圆特性：任意三角形的外接圆内不包含点集 P 的其他点。这是Delaunay三角化的定义性质。

4. 最大化最小角：在所有可能的三角剖分中，Delaunay三角化会最大化所有三角形中的最小内角，尽量避免产生“瘦长”的三角形

视图变换与gluLookAt

gluLookAt是OpenGL实用库(GLUT)中用于定义视图变换的函数，其原型为：

void gluLookAt(GLdouble ex, GLdouble ey, GLdouble ez,  // 相机位置GLdouble cx, GLdouble cy, GLdouble cz,  // 观察目标点GLdouble qx, GLdouble qy, GLdouble qz); // 上方向向量

1. 相机位置(ex, ey, ez)：相机在世界坐标系中的位置坐标
2. 观察目标点(cx, cy, cz)：相机镜头对准的点在世界坐标系中的位置
3. 上方向向量(qx, qy, qz)：定义相机"向上"方向的向量

1. 视图坐标系(t-u-v)的构建

gluLookAt函数的核心是构建一个新的坐标系(t-u-v坐标系)，其中：

1. v轴（视线的负方向）：$ v = -(c - e) = -(cx-ex, cy-ey, cz-ez) $，然后归一化为单位向量

2. t轴（右方向）：$ t = q \times v $ （上方向向量q与v轴的叉积，得到与两者都垂直的右方向），然后归一化为单位向量

3. u轴（上方向）：$ u = v \times t $（v轴与t轴的叉积，确保u轴与两者都垂直），不需要再归一化，因为v和t已经是正交单位向量

2. 视图变换矩阵

视图变换矩阵将世界坐标系中的点转换到视图坐标系中。这个矩阵可以分解为：

1. 平移矩阵 T：将相机位置(e)移动到原点
2. 旋转矩阵 R：将t-u-v坐标系对齐到x-y-z坐标系

组合后的视图变换矩阵为：
$$M=R\cdot T$$

$$M=\left[\begin{array}{cccc}{t}_x& t_y& t_z& 0\\ u_x& u_y& u_z& 0\\ v_x& v_y& v_z& 0\\ 0& 0& 0& 1\end{array}\right]\cdot \left[\begin{array}{cccc}1& 0& 0& -e_x\\ 0& 1& 0& -e_y\\ 0& 0& 1& -e_z\\ 0& 0& 0& 1\end{array}\right]$$

$$M=\left[\begin{array}{cccc}{t}_x& t_y& t_z& -\mathbf{t}\cdot \mathbf{e}\\ u_x& u_y& u_z& -\mathbf{u}\cdot \mathbf{e}\\ v_x& v_y& v_z& -\mathbf{v}\cdot \mathbf{e}\\ 0& 0& 0& 1\end{array}\right]$$

3. 注意

1. 必须调用glLoadIdentity()：在调用gluLookAt之前，通常需要先调用glLoadIdentity()重置当前矩阵为单位矩阵
2. 执行顺序：OpenGL的矩阵操作是从下往上应用的，所以视图变换会先执行

全局光照与局部光照

1. 局部光照(Local Illumination)

定义：局部光照模型仅考虑光源直接照射到物体表面的光照效果，不考虑光线在场景中的多次反射和折射。

特点：

• 计算速度快，实时性好
• 真实度相对较低
• 适合实时渲染应用(如游戏)

局限性：

• 无法表现间接光照(如颜色渗透、柔和阴影等)
• 缺乏全局光照效果(如焦散、环境光遮蔽等)

2. 全局光照(Global Illumination)

定义：全局光照模型模拟光线在场景中的多次反射、折射和吸收，考虑所有表面和光源的相互作用。

特点：

• 计算复杂度高，渲染速度慢
• 真实度高，能表现逼真的光照效果
• 适合离线渲染(如电影、建筑可视化)

视见体归一化(Normalization)

视见体归一化是图形渲染管线中的一个关键步骤，它将各种不同的投影方式统一转换为标准形式进行处理，极大简化了后续的裁剪和投影操作。

1.1 什么是视见体归一化？

视见体归一化是指将任意定义的裁剪空间(视见体)转换为标准立方体空间的变换过程。

1.2 归一化变换的作用

• 将用户自定义的裁剪体积(可能是任意形状的视锥体或平行六面体)转换为标准化的裁剪体积

2. 归一化的具体意义

• 统一投影处理：经过归一化后，两种投影方式在标准空间内表现形式相同，都是[-1,1]³的立方体。
• 流水线标准化：统一裁剪算法、简化硬件设计
• 算法简化：所有投影类型使用相同的后续处理流程
• 硬件友好：GPU可以设计统一固定的裁剪和光栅化单元
• 效率提升、数学优雅

正交投影视见体的归一化矩阵和函数

1. 正交投影视见体

在计算机图形学中,正交投影视见体是一个长方体空间,定义了可见的3D空间范围。它由六个参数定义:

• left (l): 视见体的左边界
• right ®: 视见体的右边界
• bottom (b): 视见体的底边界
• top (t): 视见体的顶边界
• near (n): 视见体的近平面
• far (f): 视见体的远平面

这个长方体内的所有物体都会被投影到2D平面上。

2. 归一化过程

归一化的目的是将正交投影视见体变换到一个标准化的空间,即将其转换为一个中心在原点、范围为[-1, 1]³的立方体。

• 步骤1：将中心平移至原点
• 步骤2：对立方体进行缩放，使其在x、y、z三个方向上的边界范围均为-1到1。此时长方体将变为一个尺寸为2×2×2的立方体
• 步骤3：相对于x-y平面进行反射（镜像对称变换）

该ppt图片有误，第一行中间的矩阵的3行3列处 没有负号！

3. glOrtho

glOrtho 是 OpenGL 中的一个函数，用于设置一个正交投影矩阵

void glOrtho(GLdouble left,   GLdouble right,  // x 轴范围（左、右）GLdouble bottom, GLdouble top,    // y 轴范围（下、上）GLdouble near,   GLdouble far     // z 轴范围（近、远）
);

OpenGL 透视投影

OpenGL 提供了两种主要的透视投影设置方式：glFrustum 和 gluPerspective。

1. glFrustum 函数

void glFrustum(GLdouble left, GLdouble right, GLdouble bottom, GLdouble top, GLdouble near, GLdouble far);

参数意义：

• left, right：近裁剪平面左右边界的x坐标
• bottom, top：近裁剪平面下上边界的y坐标
• near, far：近、远裁剪平面的z坐标（必须为正数）

特点：

• 直接指定视锥体的六个裁剪平面
• 适合需要非对称视锥体的特殊场景
• 使用起来相对复杂，需要手动计算各个参数

2. gluPerspective 函数

void gluPerspective(GLdouble fovy, GLdouble aspect, GLdouble zNear, GLdouble zFar);

参数意义：

• fovy：垂直方向的视野角度（Field of View in Y direction），单位为度
• aspect：宽高比（width/height）
• zNear, zFar：近、远裁剪平面的距离（必须为正数）

特点：

• 更直观，通过视野角度和宽高比来定义视锥体
• 适合大多数常规3D应用场景
• 内部实际上是转换为glFrustum调用

3. 透视投影矩阵

$$\left[\begin{array}{cccc}\frac{2\cdot near}{right-left}& 0& \frac{right+left}{right-left}& 0\\ 0& \frac{2\cdot near}{top-bottom}& \frac{top+bottom}{top-bottom}& 0\\ 0& 0& -\frac{far+near}{far-near}& -\frac{2\cdot far\cdot near}{far-near}\\ 0& 0& -1& 0\end{array}\right]$$

4. 实际应用示例

使用gluPerspective设置一个45度视野、匹配窗口比例的视锥体：

glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluPerspective(45.0, (GLdouble)width/height, 0.1, 100.0);

Mipmap 与纹理过滤

1. 纹理走样问题

当纹理被缩小显示时（即一个像素覆盖多个纹素），会产生摩尔纹和闪烁等走样现象。这是因为采样频率低于纹理本身的频率，违反了奈奎斯特采样定理。

2. Mipmap 解决方案

Mipmap 的核心思想是预计算多级纹理，构建一个图像金字塔：

• 第0层：原始分辨率纹理（如1024×1024）
• 第1层：1/2分辨率（512×512）
• 第2层：1/4分辨率（256×256）
• …
• 第n层：1×1纹理

3. Mipmap 性质

• 范围查询：快速获取任意正方形区域的平均值
• 空间换时间：额外占用33%的存储空间（1/4 + 1/16 + 1/64 + … ≈ 1/3）
• 近似计算：假设查询区域是正方形

4. Mipmap 实现细节

层级选择

计算当前像素在纹理空间中的覆盖范围，确定合适的mipmap层级：

层级D = log₂(max(∂u/∂x, ∂v/∂x, ∂u/∂y, ∂v/∂y))

其中∂u/∂x等表示纹理坐标对屏幕坐标的偏导数。

三线性插值（Trilinear Interpolation）

解决层级切换时的不连续问题：

1. 在相邻两个层级（D和D+1）分别做双线性插值
2. 对两个结果再进行线性插值（基于小数部分）

5. Mipmap 的局限性

• 当纹理在某个方向被拉伸时（如地面纹理向远处延伸），Mipmap会统一模糊所有方向，导致过度模糊。

• Mipmap只能处理正方形区域查询，无法适应长方形或斜向拉伸的情况。

6. 各向异性过滤（Anisotropic Filtering）

基本原理

扩展Mipmap概念，存储不同长宽比的纹理：

• 不仅存储1:1的正方形纹理
• 还存储2:1、4:1等长方形纹理

实现方式

• 计算像素在纹理空间中的实际覆盖区域（可能是长方形）
• 选择最接近的预过滤纹理进行采样
• 现代GPU通常支持2x、4x、8x、16x各向异性过滤

7. 纹理过滤模式

当一个纹素覆盖多个像素时：

• 最近邻（Nearest）：直接取最近的纹素，产生锯齿
• 双线性（Bilinear）：取4个相邻纹素的加权平均

当一个像素覆盖多个纹素时：

• Mipmap最近邻：选择最接近的mipmap层级
• Mipmap双线性：在同一层级内双线性插值
• 三线性：跨层级插值
• 各向异性：考虑方向性的高级过滤

基本Bresenham算法（光栅化直线）

核心思想

通过误差项（决策参数）决定下一个像素点的选择，仅使用整数加减和位运算，避免乘除和浮点操作。

算法步骤

1. 输入：直线起点 $(x_0,y_0)$ 和终点 $(x_1,y_1)$。
2. 计算差值：
   • $dx=|x_1-x_0|$
   • $dy=|y_1-y_0|$
3. 初始化决策参数：
   • $p=2dy-dx$ （斜率 $0\le m\le 1$ 时）
4. 逐点绘制：
   • 从起点开始，沿长轴（假设为x轴）逐步移动。
   • 若 $p\ge 0$，选择对角像素（y增加），并更新 $p=p+2(dy-dx)$。
   • 若 $p<0$，选择相邻像素（y不变），并更新 $p=p+2dy$。

示例（斜率 < 1）

def bresenham(x0, y0, x1, y1):dx = abs(x1 - x0)dy = abs(y1 - y0)p = 2 * dy - dxx, y = x0, y0points = []for _ in range(dx + 1):points.append((x, y))if p >= 0:y += 1 if y1 > y0 else -1p += 2 * (dy - dx)else:p += 2 * dyx += 1 if x1 > x0 else -1return points

复杂场景的消隐算法（Hidden Surface Removal, HSR）

1. Z-Buffer（深度缓冲）算法

原理：通过维护一个与屏幕分辨率相同的深度缓冲区（Z-Buffer），存储每个像素当前最近的深度值，最终保留深度最小的像素。

算法步骤：

1. 初始化：

   • 为每个像素初始化颜色缓冲区（ColorBuffer）为背景色。
   • 初始化深度缓冲区（ZBuffer）为最大深度值（如 ∞）。

2. 逐多边形处理：

   • 对每个多边形进行光栅化，得到其覆盖的屏幕像素 (x, y)。
   • 对每个像素 (x, y)，计算其深度值 z（从多边形插值得到）。
   • 比较 z 与 ZBuffer[x][y]：
     • 若 z < ZBuffer[x][y]：
       更新 ZBuffer[x][y] = z，并将 ColorBuffer[x][y] 设为该多边形的颜色。
     • 否则：跳过该像素。

3. 输出：最终 ColorBuffer 即为消隐后的图像。

复杂度：

• 时间：O(n × p)（n 为多边形数量，p 为单个多边形的平均像素数）。
• 空间：O(screen_resolution)。

2. 画家算法（Painter’s Algorithm）

原理：按多边形到视点的距离从远到近排序，依次绘制（后绘制的近处多边形覆盖远处多边形）。

算法步骤：

1. 深度排序：

   • 计算每个多边形的最大深度值（或中心点深度）。
   • 按深度从远到近对多边形排序。

2. 处理重叠：

   • 若多边形之间存在循环遮挡（如A挡B，B挡C，C挡A），需拆分多边形。

3. 绘制：

   • 按排序顺序从远到近光栅化多边形。

问题：

• 深度排序复杂度高（O(n log n)），且需处理循环遮挡（可能导致拆分）。

3. BSP树（Binary Space Partitioning）算法

原理：通过递归空间划分构建二叉树，支持动态视点下的高效消隐。

算法步骤：

1. 构建BSP树：

   • 选择一个多边形作为根节点，将空间划分为两个子空间（前向和背向）。
   • 递归处理子空间中的多边形，直到所有多边形纳入树中。

2. 遍历渲染：

   • 从视点出发，按以下顺序遍历：
     • 若视点在分割平面前方：先绘制后方子树，再当前节点，最后前方子树。
     • 若视点在后方：顺序相反。

优势：适合静态场景的预处理，动态视点下效率高。

Phong着色的优势

通过像素级光照计算，显著提升高光精度和表面平滑度，成为实时图形学的里程碑式技术。

1. 更精确的高光：逐像素计算光照，避免Gouraud着色的高光丢失问题，使镜面反射更锐利、自然。
2. 平滑的光照过渡：通过法线插值减少Mach Band效应，低多边形模型也能呈现曲面效果。
3. 支持复杂材质
4. 适配GPU并行计算

Cyrus-Beck

Cyrus-Beck算法是一种用于线段裁剪的计算机图形学算法，特别适用于凸多边形裁剪窗口。它是对Cohen-Sutherland算法的改进，能够更高效地处理任意凸多边形裁剪区域。

算法基本原理

Cyrus-Beck算法基于参数化方法和向量分析来确定线段与裁剪边界的交点。算法的核心思想是：

1. 将线段表示为参数方程形式
2. 对裁剪多边形的每条边计算法向量
3. 通过向量点积运算确定线段与各边的交点参数
4. 根据交点参数确定可见部分

算法步骤详解

1. 线段参数化表示

给定线段$P_0{P}_1$，可以用参数t表示为：$P(t)=P_0+(P_1-P_0)t，其中t\in [0,1]$

2. 裁剪边法向量计算

对于凸多边形的每条边，计算其内法向量N（指向多边形内部）

3. 交点参数计算

对于多边形的一条边上的任意点$A$，根据点积性质有：$N\cdot (P(t)-A)=0$

代入$P(t)$的表达式：$N\cdot (P_0+(P_1-P_0)t-A)=0$

解这个方程得到$t$：$t=[N\cdot (A-P_0)]/[N\cdot (P_1-P_0)]$

4. 参数分类

计算$D=N\cdot (P_1-P_0)$：

• 如果D > 0：线段从裁剪边外部进入内部 → t是潜在进入点
• 如果D < 0：线段从裁剪边内部到外部 → t是潜在离开点

5. 确定最终参数范围

计算所有边的 $t$ 值后：

• $t_{enter}=max(所有入点t,0)$
• $t_{exit}=min(所有出点t,1)$

如果 $t_{enter}\le t_{exit}$ ，则可见部分为P($t_{enter}$)到P($t_{exit}$)

算法伪代码

function CyrusBeck(P0, P1, polygon):t_enter = 0t_exit = 1d = P1 - P0for each edge in polygon:A, B = edge.start, edge.endN = computeNormal(A, B)  # 计算内法向量# 计算P_E (这里可以用A或B作为边上的任意一点)P_E = Anumerator = dot(N, P_E - P0)denominator = dot(N, d)if denominator == 0:if numerator < 0:  # 线段完全在外部return None# 否则平行且在内部，继续检查其他边else:t = numerator / denominatorif denominator > 0:  # 潜在入点if t > t_enter:t_enter = telse:  # 潜在出点if t < t_exit:t_exit = tif t_enter <= t_exit:return (P0 + d * t_enter, P0 + d * t_exit)else:return None  # 完全不可见

Liang-Barsky

Liang-Barsky算法是一种高效的线段裁剪算法,用于确定一条线段与矩形裁剪窗口的交点。

算法原理

核心思想是使用参数方程来表示线段,然后通过计算参数的范围来确定线段与裁剪窗口的交点。

1. 线段参数方程:
   给定线段的两个端点 $(x1,y1)$ 和 $(x2,y2)$ ,我们可以用参数方程表示线段上的任意点 $(x,y)$ :

   x = x1 + t(x2 - x1)
y = y1 + t(y2 - y1)

   其中 t 是一个在 [0, 1] 范围内的参数。

2. 裁剪窗口:
   假设裁剪窗口由左下角 (xmin, ymin) 和右上角 (xmax, ymax) 定义。

3. 裁剪条件:
   线段在裁剪窗口内的部分必须满足以下条件:

   xmin <= x <= xmax
ymin <= y <= ymax

4. 参数范围计算:
   将线段方程代入裁剪条件,我们可以得到 t 的范围:

   t_enter = max(0, t_left, t_bottom)
t_exit = min(1, t_right, t_top)

   其中:
   t_left = (xmin - x1) / (x2 - x1)
t_right = (xmax - x1) / (x2 - x1)
t_bottom = (ymin - y1) / (y2 - y1)
t_top = (ymax - y1) / (y2 - y1)

5. 裁剪判断:

   • 如果 t_enter > t_exit,则线段完全在裁剪窗口外。
   • 否则,线段的裁剪部分为 t_enter 到 t_exit 的范围。

算法实现

以下是 Liang-Barsky 算法的 Python 实现:

def liang_barsky(x1, y1, x2, y2, xmin, ymin, xmax, ymax):dx = x2 - x1dy = y2 - y1p = [-dx, dx, -dy, dy]q = [x1 - xmin, xmax - x1, y1 - ymin, ymax - y1]t_enter = 0t_exit = 1for i in range(4):if p[i] == 0:if q[i] < 0:return None  # 线段平行于边界且在外部else:t = q[i] / p[i]if p[i] < 0:t_enter = max(t_enter, t)else:t_exit = min(t_exit, t)if t_enter > t_exit:return None  # 线段完全在窗口外x_enter = x1 + t_enter * dxy_enter = y1 + t_enter * dyx_exit = x1 + t_exit * dxy_exit = y1 + t_exit * dyreturn (x_enter, y_enter, x_exit, y_exit)

算法优势

1. 效率高: Liang-Barsky 算法在大多数情况下比其他裁剪算法（如Cohen-Sutherland算法）更快。
2. 通用性: 该算法可以轻松扩展到3D空间。
3. 数值稳定: 相比于一些其他算法,Liang-Barsky算法在处理特殊情况(如线段与裁剪窗口边界重合)时更加稳定。

从物体坐标到屏幕坐标的转换

物体坐标 → 模型变换 → 世界坐标 → 视图变换 → 观察坐标 → 投影变换 → 裁剪坐标 → 透视除法 → NDC → 视口变换 → 视口坐标 → 屏幕坐标；这个转换过程是OpenGL渲染管线的核心部分，理解它对于正确设置视图和投影非常重要。

1. 物体坐标 (Object Coordinates)

物体坐标也称为模型坐标或局部坐标，是物体在其自身坐标系中的原始坐标值。这些坐标由应用程序定义，通常与具体的物体相关。

2. 世界坐标 (World Coordinates)

通过模型变换(Model Transformation)，物体坐标被转换为世界坐标。这一步将物体放置在场景中的适当位置，可能包括平移、旋转和缩放等操作。

3. 观察坐标 (View Coordinates)

通过视图变换(View Transformation)，世界坐标被转换为观察坐标。OpenGL默认将"相机"放在原点(0,0,0)，朝向负Z轴方向。视图变换实际上是将整个场景变换到相机坐标系中。

4. 裁剪坐标 (Clip Coordinates)

通过投影变换(Projection Transformation)，观察坐标被转换为裁剪坐标。在二维情况下，通常使用正交投影(Orthographic Projection)，由glOrtho()或gluOrtho2D()函数定义。

例如：

glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glOrtho(x_min, x_max, y_min, y_max, -1.0, 1.0);

这将定义一个裁剪窗口(也称为观察矩形)，在这个窗口之外的物体将被裁剪掉。

5. 规范化设备坐标 (Normalized Device Coordinates, NDC)

裁剪坐标经过透视除法后，被转换为NDC，范围在[-1,1]之间。在二维情况下，x和y坐标都在[-1,1]范围内。

6. 视口坐标 (Viewport Coordinates)

通过视口变换(Viewport Transformation)，NDC被映射到视口中。视口由glViewport(u, v, w, h)定义，其中：

• (u,v)是视口左下角在窗口中的位置(像素)
• w和h是视口的宽度和高度(像素)

数学表达式为：

x_v = (x_ndc + 1) / 2 * w + u  # x + 1 的目的是将NDC的范围从 [-1, 1] 映射到 [0, w]，然后再加上视口的偏移量 u
y_v = (y_ndc + 1) / 2 * h + v

7. 窗口坐标 (Window Coordinates)

视口坐标与窗口坐标通常是相同的，除非有多个视口。窗口由glfwSetWindowSize(window, ww, wh)定义大小。

8. 屏幕坐标 (Screen Coordinates)

最终，窗口坐标被转换为屏幕坐标。屏幕坐标的原点(0,0)通常位于屏幕左上角，y轴向下。

9. 关于计算

1. 定义坐标系

• 裁剪窗口（Clipping Window）：由 glOrtho(x_min, x_max, y_min, y_max) 定义，坐标范围为 (x_c, y_c)。
• 视口（Viewport）：由 glViewport(u, v, w, h) 定义，左下角位于 (u, v)，宽度 w，高度 h。
• 窗口（Window）：由 glfwSetWindowPos(x_pos, y_pos) 和 glfwSetWindowSize(ww, wh) 定义，左下角位于 (x_pos, y_pos)，总宽度 ww，总高度 wh。
• 屏幕（Screen）：最终像素坐标 (x_s, y_s)，原点在屏幕左上角。

2. 坐标变换步骤

(1) 裁剪窗口 → 视口（Viewport）

将裁剪窗口坐标 (x_c, y_c) 映射到视口坐标 (x_v, y_v)：
$$x_v=\frac{x_c-x_{min}}{x_{max}-x_{min}}\times w$$
$$y_v=\frac{y_c-y_{min}}{y_{max}-y_{min}}\times h$$

(2) 视口 → 窗口（Window）

叠加视口的偏移量 (u, v)：
$$x_w=x_v+u$$
$$y_w=y_v+v$$

(3) 窗口 → 屏幕（Screen）

• X 方向：直接加上窗口位置偏移 x_pos。

• Y 方向：反转 Y 轴（屏幕 Y 轴向下）并叠加窗口偏移 y_pos：
  $$x_s=x_w+x_{pos}$$

  $$y_s=wh-y_w+y_{pos}$$

3. 最终映射公式

合并所有步骤，得到裁剪窗口到屏幕的完整映射：
$$x_s=\left(\frac{x_c-x_{min}}{x_{max}-x_{min}}\times w+u\right)+x_{pos}$$
$$y_s=wh-\left(\frac{y_c-y_{min}}{y_{max}-y_{min}}\times h+v\right)+y_{pos}$$

拉普拉斯光顺算法

拉普拉斯光顺(Laplacian Smoothing)是计算机图形学中一种常用的网格光顺(Mesh Smoothing)技术，主要用于去除三维网格模型表面的噪声，改善网格质量。

算法基本思想

通过调整网格顶点的位置来减少曲率变化，使网格表面更加光滑。

1. 对于网格中的每个顶点，计算其拉普拉斯坐标(Laplacian coordinate)
2. 根据拉普拉斯坐标调整顶点位置
3. 迭代执行上述过程直到达到满意的光滑效果

算法数学表达

拉普拉斯光顺的基本公式如下：

$$P_{new}=P_{old}+\lambda \times L(P_{old})$$
其中：

• $P_{old}$ 是顶点原始位置
• $P_{new}$ 是顶点新位置
• λ是控制收敛速度的参数(0 < λ < 1)
• $L(P_{old})$ 是顶点P的拉普拉斯算子

拉普拉斯算子L的计算方式为：

$$L=(1/d\times \Sigma Q_k)-P_{old}=\Sigma (1/d\times (Q_k-P_{old}))$$
其中：

• $$Q_k$$ 是$P_{old}$ 的邻接顶点
• $d$ 是$P_{old}$ 的邻接顶点数量

算法实现步骤

1. 初始化：选择光滑参数λ和迭代次数
2. 计算拉普拉斯坐标：
   • 对于每个顶点P，找到其所有邻接顶点$Q_k$
   • 计算邻接顶点的平均位置 $(1/d\times \Sigma Q_k)$
   • 计算拉普拉斯坐标 L = 平均位置 - P
3. 更新顶点位置：$P_{new}=P_{old}+\lambda \times L$
4. 迭代：重复步骤2-3直到达到预定迭代次数

CG01

计算机图形学概述

• 定义：利用计算机研究图形的表示、生成、处理和显示的学科。

核心技术

• 建模（Modeling）
• 渲染（Rendering）
• 动画（Animation）
• 交互（HCI）

CG02

图形渲染管线

顶点处理

• 坐标系转换：
  • 物体坐标 → 相机坐标 → 屏幕坐标
  • 通过矩阵变换实现
• 计算顶点颜色

投影

• 透视投影：所有投影线汇聚于投影中心
• 平行投影：投影线平行，用投影方向代替投影中心

图元装配

• 在裁剪和光栅化前，必须将顶点组装成几何对象：
  • 线段
  • 多边形
  • 曲线和曲面

裁剪

• 虚拟相机只能看到部分场景
• 视见体外的物体被裁剪掉

光栅化

• 将裁剪后的图元离散化为像素表示
• 生成片元（潜在像素）：
  • 具有帧缓冲位置
  • 颜色和深度属性
  • 顶点属性通过插值确定

片元处理

• 确定帧缓冲中像素的最终颜色
• 考虑因素：
  • 纹理映射
  • 顶点颜色插值
  • 遮挡情况（隐藏面消除）

CG04

图形渲染模式

立即模式（已弃用）

glBegin(GL_POLYGON);glVertex3f(0.0, 0.0, 0.0);glVertex3f(0.0, 1.0, 0.0);glVertex3f(0.0, 0.0, 1.0);
glEnd();

缺点：每个顶点单独传输，CPU-GPU通信瓶颈

保留模式（现代方式）

1. 将顶点数据存储在数组中
2. 通过缓冲区对象一次性发送到GPU
3. 使用VAO（顶点数组对象）管理状态

OpenGL图元类型

多边形限制：

• 必须简单（边不相交）
• 凸的（无凹陷）
• 平面（所有顶点共面）

现代OpenGL主要渲染三角形

三角剖分与Delaunay三角化

多边形三角化算法

1. 凸多边形：从任意顶点开始顺序连接
2. 凹多边形：递归分割或耳切法

Delaunay三角化特性

• Voronoi图的对偶图
• 形成点集的凸包
• 满足空圆特性（外接圆不包含其他点）
• 最大化最小角，避免"瘦长"三角形

坐标系与视图变换

坐标系类型

1. 对象/模型坐标（应用定义的单位）
2. 世界坐标（全局场景）
3. 视图坐标（相机相对）
4. 窗口坐标（像素位置）

正交投影

glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glOrtho(left, right, bottom, top, near, far);
// 2D简化版
gluOrtho2D(left, right, bottom, top);

默认视图体积：中心在原点，边长为2的立方体

视口与窗口管理

坐标映射流程：

1. 视图坐标 → 视口坐标
2. 视口坐标 → 窗口坐标
3. 窗口坐标 → 屏幕坐标

关键函数：

glViewport(x, y, width, height);  // 设置绘制区域
glfwSetWindowPos(window, x, y);   // 窗口位置
glfwSetWindowSize(window, w, h);  // 窗口尺寸

数学映射关系：
从裁剪窗口(xmin,ymax)到视口(xv,yv)的线性变换：

x_viewport = (x - xmin)/(xmax - xmin) * vw + xv
y_viewport = (y - ymin)/(ymax - ymin) * vh + yv

CG07

Sierpinski镂垫与分形几何

Sierpinski镂垫(又称Sierpinski三角形或Sierpinski垫片)是一种经典的分形图案。它是一种自相似的几何形状，可以通过简单的递归过程生成。

二维构造

1. 初始步骤：从一个实心等边三角形开始
2. 递归步骤：
   • 连接三角形三边的中点，将原三角形分割成4个较小的全等三角形
   • 移除中心的三角形(保留边界)
   • 对剩下的3个三角形重复上述过程

三维扩展

在3D中，可以从四面体开始：

1. 计算每条边的中点
2. 用这些中点构建四个较小的四面体
3. 移除中心的立体部分
4. 对每个小四面体重复此过程

分形特性

自相似性：整体结构由按比例缩小的自身副本组成，每个子三角形都是整个结构的精确缩小版

分形维数：

• 面积趋向于零：每次迭代移除部分面积，极限情况下面积为零
• 周长趋向于无穷大：每次细分都增加总边界长度
• 分数维度：其Hausdorff维数为log₃2 ≈ 1.585，介于1维(线)和2维(面)之间

核心算法

递归细分三角形：

void divide_triangle(point2 a, point2 b, point2 c, int m) {point2 ab, ac, bc;if(m > 0) {ab = (a + b)/2;  // 计算中点ac = (a + c)/2;bc = (b + c)/2;divide_triangle(a, ab, ac, m-1);  // 递归处理子三角形divide_triangle(c, ac, bc, m-1);divide_triangle(b, bc, ab, m-1);}else { triangle(a,b,c); }  // 绘制终止条件
}

3D实现要点

1. 启用深度测试：glEnable(GL_DEPTH_TEST)
2. 清除深度缓冲区：glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT)
3. 使用3D点：point3代替point2

图像矢量化（Image Vectorization）

目的：将基于像素的位图（如PNG、JPEG）转换为由数学公式或几何元素（如点、线、曲线）定义的矢量图形（如SVG）。矢量图形具有无限缩放无损的特性，适用于图标、字体、工程图纸等场景。

常用方法：基于边缘检测的方法、基于区域分割的方法、基于网格生成的方法、基于参数曲线拟合的方法、基于深度学习的端到端方法

Marching Squares（二维）

• 原理：将图像划分为均匀的二维网格，对每个网格单元（4个顶点）根据像素值是否超过阈值（如灰度值）生成二进制状态（0或1），共16种可能状态（2⁴）。通过插值确定等值线（轮廓线）与网格边的交点，连接这些交点形成多边形边界。

• 步骤：

  1. 对图像二值化（如黑/白分割）。

  2. 遍历每个网格单元，根据顶点状态查表（预定义的16种边连接方式）。

  3. 线性插值计算交点（如右图）：

     • 若顶点A值 > 阈值c，顶点B值 < 阈值，交点在AB边上的位置为：

     

     $$x=x_i+\frac{(f_A-c)}{(f_A-f_B)}\Delta x$$

  4. 连接交点形成闭合多边形。

隐式平面网格化（Implicit Surface Meshing）

目的：将隐式函数（如 $f(x,y,z)=0$ 定义的曲面）转换为显式的三角形网格。

Marching Cubes（三维）

• 原理：
  1. 空间划分：将3D空间划分为均匀立方体网格。
  2. 顶点标记：对每个立方体的8个顶点计算 $f(x,y,z)$，标记为“内部”（$f<0$）或“外部”（$f\ge 0$）。
  3. 状态查表：根据256种（2⁸）可能的顶点状态，预定义三角化方案。
  4. 插值与三角化：在立方体边上线性插值求交点，连接交点生成三角形面片。
     • 交点坐标计算（类似Marching Squares）：
       $$P=P_1+\frac{(c-f_1)}{(f_2-f_1)}(P_2-P_1)$$

CG08

基本几何元素

点(Points)

• 定义：空间中的位置（用大写字母表示）
• 点与向量的关系：
  • 点-点相减得到向量
  • 点-向量相加得到点

仿射空间(Affine Spaces)

• 定义：点与向量空间的组合
• 允许的运算：
  • 向量-向量加法 → 向量
  • 标量-向量乘法 → 向量
  • 点-向量加法 → 点
  • 标量-标量运算 → 标量
• 所有运算都与坐标系无关

直线与平面

直线表示

• 参数形式：P(α) = P₀ + αd
  • 通过点P₀，方向为d的所有点
• 其他表示形式：
  • 显式：y = mx + h
  • 隐式：ax + by + c = 0
  • 参数式：
    • x(α) = (1-α)x₀ + αx₁
    • y(α) = (1-α)y₀ + αy₁

线性插值

• 两点间的线性插值：P(α) = αR + (1-α)Q
• 当0 ≤ α ≤ 1时，得到线段上所有点

平面表示

• 由一点和两个向量定义
• 或由三个点定义
• 参数形式：P(α,β) = R + αu + βv

法向量

• 每个平面都有一个法向量n垂直于它
• 可通过叉积计算：n = u × v
• 等价形式：(P(α)-P₀)·n = 0

凸性(Convexity)

• 定义：对象中任意两点间的线段都在对象内
• 凸包：包含一组点的最小凸对象

点积与叉积

点积(Dot Product)

• 定义：v·w = v₁w₁ + v₂w₂ + v₃w₃
• 性质：
  • 对称性：v·w = w·v
  • 非退化性：v·v = 0 ⇔ v = 0
  • 双线性
• 应用：
  • 向量长度：$||v||=\surd (v\cdot v)$
  • 两点距离：$||Q-P||$
  • 向量夹角：$arccos(v\cdot w/(||v||||w||))$
  • 向量归一化：v’ = v/||v||

叉积(Cross Product)

• 定义：
  $$v\times w=[v_2{w}_3-v_3{w}_2,v_3{w}_1-v_1{w}_3,v_1{w}_2-v_2{w}_1]$$

• 性质：

  • 结果向量垂直于v和w构成的平面
  • 长度：$||v||\cdot ||w||\cdot |sin\theta |$

线性代数基础

线性无关

• 定义：向量组v₁,v₂,…,vₙ线性无关当且仅当
  • α₁v₁ + α₂v₂ + … + αₙvₙ = 0 ⇒ α₁=α₂=…=0

维数与基

• 维数：向量空间中最大线性无关向量数
• 基：n维空间中任意n个线性无关向量
• 向量表示：v = α₁v₁ + α₂v₂ + … + αₙvₙ

坐标系与齐次坐标

坐标系

• 表示向量需要基
• 表示点需要基和原点（构成坐标系框架）

齐次坐标(Homogeneous Coordinates)

• 点表示：[x y z 1]ᵀ
• 向量表示：[x y z 0]ᵀ

优势：

• 统一表示点和向量
• 所有标准变换（旋转、平移、缩放）可用4×4矩阵实现
• 图形硬件管线使用4维表示

坐标变换

坐标系变换是指将一个点从一个坐标系（通常是世界坐标系）转换到另一个新坐标系（由基向量 t, u, v 定义）的过程。我们给定新坐标系的基向量 t, u, v 和一个点 p 在世界坐标系中的坐标，要求计算 p 在新坐标系中的坐标。

坐标系变换的核心是：

1. 构造变换矩阵 M，其行是新坐标系的基向量 t, u, v。
2. 用 M 乘以点的世界坐标，得到其在新坐标系中的坐标。
3. 几何上，新坐标是点在各新基向量上的投影。

变换矩阵 M 的构造

新坐标系的基向量 t, u, v 分别表示新坐标系的 x’, y’, z’ 轴在世界坐标系中的方向。变换矩阵 M 是一个 4×4 的齐次矩阵，形式如下：

$$M=\left[\begin{array}{cccc}{x}_t& y_t& z_t& 0\\ x_u& y_u& z_u& 0\\ x_v& y_v& z_v& 0\\ 0& 0& 0& 1\end{array}\right]$$
注意：

• 这里假设新坐标系的原点与世界坐标系的原点相同（没有平移部分），因此变换矩阵的最后一行为 [0 0 0 1]。
• 如果新坐标系的原点不是世界坐标系的原点，则需要额外的平移变换（通常用齐次坐标的第四列表示）。

点 p 的坐标变换

给定点 p 在世界坐标系中的坐标 p = (x, y, z)，我们将其表示为齐次坐标形式 p = [x y z 1]ᵀ，然后计算其在新坐标系中的坐标：

$$p^{\prime }=M\cdot p=\left[\begin{array}{cccc}{x}_t& y_t& z_t& 0\\ x_u& y_u& z_u& 0\\ x_v& y_v& z_v& 0\\ 0& 0& 0& 1\end{array}\right]\left[\begin{array}{c}x\\ y\\ z\\ 1\end{array}\right]$$

层次建模

• 复杂对象由基本图元构建
• 通过变换（平移、缩放等）组合基本图元

CG09

几何变换基础

为什么需要变换？

• 构建复杂物体层次结构
• 创建动画效果
• 调整物体位置、方向和大小
• 实现不同视角的观察

变换类型

1. 刚体变换：保持点间距离不变，包括旋转和平移
2. 仿射变换：保持直线性，包括旋转、平移、缩放和剪切
3. 投影变换：用于3D到2D的投影

基本变换矩阵

齐次坐标

齐次坐标使用4维向量表示3D点：[x y z w]ᵀ，其中w=1表示点，w=0表示向量。这使得所有变换都可以用4×4矩阵表示。

平移变换

平移矩阵 $T(d_x,d_{\gamma },d_z)$ ：

[ 1  0  0 dₓ ]
[ 0  1  0 dᵧ ]
[ 0  0  1 dz ]
[ 0  0  0  1 ]

旋转变换

• 绕z轴旋转θ角度：

[ cosθ -sinθ  0  0 ]
[ sinθ  cosθ  0  0 ]
[  0     0    1  0 ]
[  0     0    0  1 ]

• 绕x轴旋转θ角度：

[ 1    0     0    0 ]
[ 0  cosθ -sinθ  0 ]
[ 0  sinθ  cosθ  0 ]
[ 0    0     0    1 ]

• 绕y轴旋转θ角度：

[ cosθ  0  sinθ  0 ]
[  0    1    0    0 ]
[-sinθ  0  cosθ  0 ]
[  0    0    0    1 ]

缩放变换

缩放矩阵 $S(s_x,s_{\gamma },s_z)$ ：

[ sₓ  0   0   0 ]
[ 0   sᵧ  0   0 ]
[ 0   0   sz 0 ]
[ 0   0   0   1 ]

剪切变换

沿x轴的剪切矩阵：

[ 1  cotθ  0  0 ]
[ 0    1   0  0 ]
[ 0    0   1  0 ]
[ 0    0   0  1 ]

变换组合与实例变换

变换顺序

矩阵乘法顺序与变换应用顺序相反。例如，先平移后旋转表示为M = R × T。

绕任意点旋转

绕非原点点p旋转的步骤：

1. 平移使p到原点：T(-p)
2. 旋转：R(θ)
3. 平移回原位置：T§
   组合矩阵：M = T§ × R(θ) × T(-p)

实例变换

建模中常用TRS变换：缩放(S)、旋转®、平移(T)
组合矩阵：M = T × R × S

OpenGL中的变换实现

矩阵操作

• 设置当前矩阵模式：glMatrixMode(GL_MODELVIEW)
• 加载单位矩阵：glLoadIdentity()
• 矩阵乘法：glMultMatrixf(m)
• 变换函数：
  • glTranslatef(dx, dy, dz)
  • glRotatef(angle, x, y, z)
  • glScalef(sx, sy, sz)

矩阵堆栈

用于保存和恢复变换状态：

• 保存当前矩阵：glPushMatrix()
• 恢复矩阵：glPopMatrix()

应用实例

旋转立方体实现

void display() {glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);glLoadIdentity();glRotatef(theta[0], 1.0, 0.0, 0.0); // X轴旋转glRotatef(theta[1], 0.0, 1.0, 0.0); // Y轴旋转glRotatef(theta[2], 0.0, 0.0, 1.0); // Z轴旋转colorcube(); // 绘制立方体
}

CG10

1. 三维图形变换

1.1 方向缩放变换矩阵推导

方向缩放（Directional Scaling）是指沿着某个特定方向 v 进行缩放（放大或缩小），而其他方向保持不变。我们需要构造一个变换矩阵 M，使得：

• 沿着方向 v 的向量分量缩放 S 倍，
• 垂直于 v 的分量保持不变。

给定单位方向向量：
$$\mathbf{v}=\left[\begin{array}{c}a\\ b\\ c\end{array}\right],\text{满足}{a}^2+b^2+c^2=1$$
任意向量 p 可以分解为：

• 沿 v 方向的分量：$ \text{proj}_{\mathbf{v}} \mathbf{p} = (\mathbf{p} \cdot \mathbf{v}) \mathbf{v} $
• 垂直于 v 的分量：$ \text{perp}_{\mathbf{v}} \mathbf{p} = \mathbf{p} - (\mathbf{p} \cdot \mathbf{v}) \mathbf{v} $

缩放目标：

• 沿 v 的分量缩放 S 倍：$ S \cdot (\mathbf{p} \cdot \mathbf{v}) \mathbf{v} $
• 垂直分量保持不变：$ \mathbf{p} - (\mathbf{p} \cdot \mathbf{v}) \mathbf{v} $

因此，变换后的向量 p’ 为：
$${\mathbf{p}}^{\prime }=S(\mathbf{p}\cdot \mathbf{v})\mathbf{v}+\left(\mathbf{p}-(\mathbf{p}\cdot \mathbf{v})\mathbf{v}\right)$$
$$=\mathbf{p}+(S-1)(\mathbf{p}\cdot \mathbf{v})\mathbf{v}$$

为了用矩阵表示 $ (\mathbf{p} \cdot \mathbf{v}) \mathbf{v} $，我们可以构造 投影矩阵 P：
$$P=\mathbf{v}{\mathbf{v}}^T=\left[\begin{array}{c}a\\ b\\ c\end{array}\right]\left[\begin{array}{ccc}a& b& c\end{array}\right]=\left[\begin{array}{ccc}{a}^2& ab& ac\\ ab& b^2& bc\\ ac& bc& c^2\end{array}\right]$$
作用：
$$P\mathbf{p}=\mathbf{v}{\mathbf{v}}^T\mathbf{p}=\mathbf{v}(\mathbf{v}\cdot \mathbf{p})=(\mathbf{p}\cdot \mathbf{v})\mathbf{v}$$
即，P 将 p 投影到 v 方向上。

我们希望：
$${\mathbf{p}}^{\prime }=\mathbf{p}+(S-1)(\mathbf{p}\cdot \mathbf{v})\mathbf{v}$$
用矩阵表示：
$${\mathbf{p}}^{\prime }=\mathbf{p}+(S-1)P\mathbf{p}=\left(I+(S-1)P\right)\mathbf{p}$$
因此，缩放矩阵 M 为：
$$M=I+(S-1)P$$
为了兼容平移变换，通常使用 齐次坐标，因此最终的 4×4 变换矩阵 为：
$$M=\left[\begin{array}{cccc}1+(S-1)a^2& (S-1)ab& (S-1)ac& 0\\ (S-1)ab& 1+(S-1)b^2& (S-1)bc& 0\\ (S-1)ac& (S-1)bc& 1+(S-1)c^2& 0\\ 0& 0& 0& 1\end{array}\right]$$

1.2 方向缩放变换矩阵

1. 投影矩阵 $ P = \mathbf{v} \mathbf{v}^T $ 用于计算沿 v 的分量。
2. 缩放矩阵 $ M = I + (S - 1)P $：
   • 沿 v 方向缩放 S 倍，
   • 其他方向保持不变。
3. 齐次坐标 扩展为 4×4 矩阵，便于组合其他变换（如平移）。

1.3 另一种解法

给定单位向量v(a,b,c)，要沿此方向放大S倍，变换矩阵推导如下：

1. 构造旋转矩阵R，使v与z轴对齐
2. 沿z轴缩放S倍
3. 应用逆旋转R⁻¹

最终变换矩阵为：

M = R⁻¹·S·R

其中a,b,c是v与各坐标轴夹角的余弦值。

三维观察与投影

特性	正交投影	透视投影
投影线	平行	汇聚
保持	距离和角度	仅平行于投影面的角度
应用	工程制图	真实感渲染
深度	无变化	近大远小

OpenGL Viewing Pipeline

OpenGL 的渲染管线中，观察流程（Viewing Pipeline）负责将 3D 场景转换为 2D 屏幕图像，主要分为三个阶段：

阶段	变换	API	作用
模型视图变换	世界坐标 → 观察坐标	gluLookAt	定义相机位置和方向,将物体从世界坐标系转换到观察坐标系
投影变换	观察坐标 → 裁剪坐标	glOrtho / gluPerspective	正交或透视投影，将 3D 场景投影到 2D 投影平面
视口变换	NDC → 屏幕坐标	glViewport	将投影后的坐标映射到屏幕像素位置

1. 模型视图变换（ModelView Transformation）

将物体从 世界坐标系 转换到 观察坐标系（以相机为原点的坐标系）。

方法：gluLookAt(eye, center, up)

gluLookAt 定义了相机的位置、朝向和上方向，并构建观察矩阵：

• eye：相机位置（世界坐标系）。
• center：相机对准的目标点（世界坐标系）。
• up：相机的“上方向”向量（通常为 (0,1,0)）。

观察坐标系（t-u-v 坐标系）

1. 计算三个基向量：

   • 观察方向 v（相机 -z 轴）：
     $$v=\text{normalize}(eye-center)$$
   • 右方向 t（相机 x 轴）：
     $$t=\text{normalize}(up\times v)$$
   • 上方向 u（相机 y 轴）：
     $$u=v\times t$$

2. 构建观察矩阵：
   $$M_{\text{view}}=\left[\begin{array}{cccc}{t}_x& t_y& t_z& -t\cdot eye\\ u_x& u_y& u_z& -u\cdot eye\\ v_x& v_y& v_z& -v\cdot eye\\ 0& 0& 0& 1\end{array}\right]$$

   • 该矩阵将世界坐标系的点转换到相机坐标系。

2. 投影变换（Projection Transformation）

将 3D 场景投影到 2D 平面（近裁剪面），分为 正交投影 和 透视投影。

(1) 正交投影（Orthographic Projection）

API：glOrtho(left, right, bottom, top, near, far)
特点：

• 无透视效果（平行投影）。
• 物体大小与距离无关。

投影矩阵：
$$M_{\text{ortho}}=\left[\begin{array}{cccc}\frac{2}{right-left}& 0& 0& -\frac{right+left}{right-left}\\ 0& \frac{2}{top-bottom}& 0& -\frac{top+bottom}{top-bottom}\\ 0& 0& -\frac{2}{far-near}& -\frac{far+near}{far-near}\\ 0& 0& 0& 1\end{array}\right]$$

(2) 透视投影（Perspective Projection）

API：

• glFrustum(left, right, bottom, top, near, far)（不对称视锥）
• gluPerspective(fovy, aspect, near, far)（对称视锥）

特点：

• 模拟人眼视角（近大远小）。
• 通过透视除法（x/w, y/w）实现深度效果。

3. 视口变换（Viewport Transformation）

将投影后的 标准化设备坐标（NDC） [-1,1]×[-1,1] 映射到屏幕像素坐标 [0,width]×[0,height]。

API：glViewport(x, y, width, height)

变换公式：
$$x_{\text{screen}}=\frac{width}{2}\cdot x_{\text{NDC}}+x+\frac{width}{2}$$
$$y_{\text{screen}}=\frac{height}{2}\cdot y_{\text{NDC}}+y+\frac{height}{2}$$

深度映射：
$$z_{\text{screen}}=\frac{far-near}{2}\cdot z_{\text{NDC}}+\frac{far+near}{2}$$

4. 代码示例

// 设置模型视图矩阵
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
gluLookAt(eyeX, eyeY, eyeZ, centerX, centerY, centerZ, upX, upY, upZ);// 设置投影矩阵
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluPerspective(45.0, (GLfloat)width/(GLfloat)height, 0.1, 100.0);// 设置视口
glViewport(0, 0, width, height);

规范化变换（Normalization Transformation）

规范化变换的目标是将 任意观察体（Viewing Volume，如透视投影的视锥或正交投影的长方体）转换为 标准立方体（Canonical View Volume，即 $[-1,1]\times [-1,1]\times [-1,1]$）。这一过程是投影变换的核心步骤，确保后续的裁剪和视口映射能统一处理。

1. 规范化变换的步骤

(1) 平移至原点

将观察体的中心移动到坐标系原点。 假设观察体的中心坐标为 $(a,b,c)$，则平移矩阵为：
$$T=\left[\begin{array}{cccc}1& 0& 0& -a\\ 0& 1& 0& -b\\ 0& 0& 1& -c\\ 0& 0& 0& 1\end{array}\right]$$
作用：

• 对于正交投影的观察体（如 glOrtho(left, right, bottom, top, near, far)），中心点为：
  $$a=\frac{left+right}{2},b=\frac{bottom+top}{2},c=\frac{near+far}{2}$$
• 对于透视投影的视锥（如 glFrustum(left, right, bottom, top, near, far)），同样计算中心点并平移。

(2) 缩放为标准尺寸

将平移后的观察体缩放至标准立方体 $[-1,1{]}^3$。 假设观察体的宽度、高度、深度分别为：
$$w=right-left,h=top-bottom,d=far-near$$
则缩放矩阵为：
$$S=\left[\begin{array}{cccc}\frac{2}{w}& 0& 0& 0\\ 0& \frac{2}{h}& 0& 0\\ 0& 0& \frac{2}{d}& 0\\ 0& 0& 0& 1\end{array}\right]$$
作用：

• 将 $x$ 方向从 $[left,right]$ 映射到 $[-1,1]$。
• 将 $y$ 方向从 $[bottom,top]$ 映射到 $[-1,1]$。
• 将 $z$ 方向从 $[near,far]$ 映射到 $[-1,1]$（需结合下一步的反射处理）。

(3) 反射处理深度值（OpenGL 的 NDC 约定）

在 OpenGL 中，标准化设备坐标（NDC） 的 $z$ 轴方向是 右手系（即 $-1$ 表示近裁剪面，$1$ 表示远裁剪面）。但观察坐标系可能是左手系（如透视投影的视锥），因此需要反射 $z$ 轴。

**反射矩阵（沿 $z$ 轴取反）：**确保 $z$ 轴方向符合 OpenGL 的 NDC 约定（近裁剪面 $z=-1$，远裁剪面 $z=1$）。
$$R=\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& -1& 0\\ 0& 0& 0& 1\end{array}\right]$$

2. 组合变换矩阵

规范化变换的完整矩阵是 平移 → 缩放 → 反射 的组合：
$$M_{\text{normalize}}=R\cdot S\cdot T$$

3. 代码实现（伪代码）

def normalize_view_volume(left, right, bottom, top, near, far):# 平移至原点a = (left + right) / 2b = (bottom + top) / 2c = (near + far) / 2T = translate(-a, -b, -c)# 缩放至标准立方体w = right - lefth = top - bottomd = far - nearS = scale(2/w, 2/h, 2/d)# 反射 z 轴（OpenGL 约定）R = scale(1, 1, -1)return R * S * T

CG11

一、为什么需要着色？

1.1 着色与三维感知

原始多边形模型仅通过线框或单一颜色填充无法表现真实物体的立体感。着色技术通过模拟光线与物体表面的交互，创造了以下效果：

• 深度感知：通过明暗变化表现物体表面凹凸
• 材质表现：不同材料对光线的反射特性
• 光照效果：阴影、高光等增强真实感

1.2 着色发展历程

二、光线散射模型

光线击中物体表面后发生三种主要交互：

1. 吸收：部分光能被材料吸收
2. 漫反射：光线向各个方向均匀散射
3. 镜面反射：光线按入射角对称反射

三、Phong反射模型

Phong 光照模型是一种经典的局部光照模型，用于模拟物体表面在不同光照条件下的视觉效果。它将反射光分为 环境光（Ambient）、漫反射（Diffuse） 和 镜面反射（Specular） 三个分量，通过线性叠加得到最终的光照效果。

1. 模型组成

(1) 环境光（Ambient Light）

作用： 模拟间接光照（如场景中的全局漫反射光），确保物体即使不被直接照射也不会完全黑暗。

公式：
$$I_a=k_a\cdot I_{as}$$

• $ I_a $：环境光反射强度
• $ k_a $：环境光反射系数（材质属性，$ 0 \leq k_a \leq 1 $）
• $ I_{as} $：环境光源强度

特点：

• 与物体表面法线 n 和光线方向 l 无关。
• 均匀作用于所有表面。

(2) 漫反射（Diffuse Reflection）

作用： 模拟粗糙表面对光的均匀散射（如纸张、墙壁），遵循 Lambert 余弦定律：反射光强度与入射角和法线夹角的余弦成正比。

公式：
$$I_d=k_d\cdot I\cdot \max (0,\mathbf{n}\cdot \mathbf{l})$$

• $ I_d $：漫反射光强度
• $ k_d $：漫反射系数（材质属性，$ 0 \leq k_d \leq 1 $）
• $ I $：光源强度
• $ \mathbf{n} $：表面法向量
• $ \mathbf{l} $：光线方向（从表面指向光源）
• $ \max(0, \mathbf{n} \cdot \mathbf{l}) $：确保夹角不超过 90°（否则无光照）。

特点：

• 与观察方向 v 无关。
• 光线入射角越小（$ \mathbf{n} \cdot \mathbf{l} $ 越大），漫反射越强。

(3) 镜面反射（Specular Reflection）

作用： 模拟光滑表面的高光效果（如金属、塑料），反射光集中在镜面反射方向附近。

公式：
$$I_s=k_s\cdot I\cdot (\mathbf{v}\cdot \mathbf{r}{)}^{\alpha }$$

• $ I_s $：镜面反射光强度
• $ k_s $：镜面反射系数（材质属性，$ 0 \leq k_s \leq 1 $）
• $ \mathbf{v} $：观察方向（从表面指向相机）
• $ \mathbf{r} $：反射光线方向（$ \mathbf{r} = 2(\mathbf{n} \cdot \mathbf{l})\mathbf{n} - \mathbf{l} $）
• $ \alpha $：光泽度（Shininess），控制高光范围（值越大，高光越集中）。

特点：

• 高光强度取决于观察方向 v 与反射方向 r 的夹角。
• $ \alpha $ 越大，高光越锐利（如金属）；越小则越柔和（如塑料）。

2. 完整 Phong 光照方程

将三个分量叠加，得到最终光照强度：
$$I=\underset{\text{环境光}}{\underbrace{k_a{I}_{as}}}+\underset{\text{漫反射}}{\underbrace{k_{d}I(\mathbf{n}\cdot \mathbf{l})}}+\underset{\text{镜面反射}}{\underbrace{k_{s}I(\mathbf{v}\cdot \mathbf{r}{)}^{\alpha }}}$$

参数总结：

参数	含义	范围
$ k_a $	环境光反射率	[0,1]
$ k_d $	漫反射率	[0,1]
$ k_s $	镜面反射率	[0,1]
$ \alpha $	光泽度	通常 1~1000
$ \mathbf{n} $	表面法向量	单位向量
$ \mathbf{l} $	光线方向	单位向量
$ \mathbf{v} $	观察方向	单位向量
$ \mathbf{r} $	反射方向	$ \mathbf{r} = 2(\mathbf{n} \cdot \mathbf{l})\mathbf{n} - \mathbf{l} $

3. 优缺点

优点：

• 计算简单，适合实时渲染（如 OpenGL、游戏引擎）。
• 能模拟基本的光照效果（漫反射、高光）。

缺点：

• 镜面反射计算依赖观察方向，不符合物理真实（Blinn-Phong 改进为半程向量）。
• 未考虑阴影、全局光照等复杂效果。

四、改进的Phong模型

Phong模型的改进主要集中在两个方面：计算优化（Blinn-Phong）和物理真实性增强（距离衰减）。

1. Blinn-Phong 模型

问题背景

原始Phong模型的镜面反射计算需要求反射向量 r：
$$\mathbf{r}=2(\mathbf{n}\cdot \mathbf{l})\mathbf{n}-\mathbf{l}$$
这一步涉及向量运算，在实时渲染中计算成本较高。

解决方案：半角向量（Halfway Vector）

Blinn-Phong 提出用 半角向量 h 替代反射向量 r：
$$\mathbf{h}=\frac{\mathbf{l}+\mathbf{v}}{\Vert \mathbf{l}+\mathbf{v}\Vert }$$
其中：

• $\mathbf{l}$：光线方向（指向光源）
• $\mathbf{v}$：观察方向（指向相机）
• $\mathbf{h}$：l 和 v 的角平分线方向

改进后的镜面反射公式

$$I_s=k_{s}I(\mathbf{n}\cdot \mathbf{h}{)}^{\beta }$$

• $\beta$：新的光泽度参数，需比Phong模型的 $\alpha$ 更大（通常 $\beta \approx 4\alpha$）以匹配视觉效果。

优势

1. 计算效率更高：
   • 避免了反射向量 r 的计算。
   • 半角向量 h 只需一次归一化。
2. 视觉效果相似：
   • 当 $\beta$ 调整适当时，高光效果与Phong模型几乎无法区分。

几何意义

• $(\mathbf{n}\cdot \mathbf{h})$ 衡量表面法线与半角向量的对齐程度。
• 当 h 与 n 完全对齐时（即观察方向与反射方向一致），高光最强。

2. 距离衰减（Distance Attenuation）

问题背景

在真实世界中，光源强度随距离增加而减弱（平方反比定律）。原始Phong模型未考虑这一点，导致所有位置的光照强度相同，显得不真实。

解决方案：衰减因子

引入距离衰减函数：
$$f_{att}=\frac{1}{c_1+c_{2}d+c_3{d}^2}$$
其中：

• $d$：光源到表面的距离
• $c_1,c_2,c_3$：可调参数，控制衰减曲线

衰减曲线示例

• 近距离：$c_1$ 主导，衰减缓慢（如室内灯光）。
• 远距离：$c_3{d}^2$ 主导，快速衰减（如街灯）。

3. 改进后的完整光照方程

$$I=\underset{\text{环境光}}{\underbrace{k_a{I}_{as}}}+f_{att}\cdot \left(\underset{\text{漫反射}}{\underbrace{k_{d}I(\mathbf{n}\cdot \mathbf{l})}}+\underset{\text{镜面反射}}{\underbrace{k_{s}I(\mathbf{n}\cdot \mathbf{h}{)}^{\beta }}}\right)$$

4. 对比总结

特性	Phong模型	Blinn-Phong模型
镜面反射计算	需计算反射向量 r	使用半角向量 h
计算成本	较高（需反射运算）	较低（只需加法和归一化）
参数调整	光泽度 $\alpha$	光泽度 $\beta \approx 4\alpha$
物理真实性	无距离衰减	支持距离衰减

五、着色实现技术

5.1 平面着色(Flat Shading)

• 每个多边形使用单一法线
• 计算一次光照应用于整个面
• 优点：计算量小
• 缺点：马赫带效应明显

5.2 Gouraud着色

• 消除明显棱边
• 但高光区域可能丢失

5.3 Phong着色

• 高质量高光效果
• 计算量较大

CG12

在图形渲染管线中，几何处理阶段结束后，顶点被组装成图元（如线段、多边形）。接下来的关键步骤包括：

1. 裁剪：剔除视见体外的图元
2. 光栅化/扫描转换：确定哪些像素会受到每个图元的影响
3. 片元处理：包括隐藏面消除、抗锯齿等

裁剪技术

线段裁剪

确定线段与裁剪窗口（或任意凸多边形区域）的可见部分。

Cohen-Sutherland算法

核心思想：通过区域编码快速判断线段与矩形窗口的位置关系，优先处理简单情况（完全可见/完全不可见），在不计算交点的情况下删除尽可能多的cases，仅对复杂情况计算交点。

实现步骤：

1. 为每个端点计算4位编码（outcode），编码规则（4位二进制码，每位表示一个方向）：

   

   • 1 表示满足上述条件（在窗口外），0 表示不满足（在窗口内或边界上）。
   • 例如：编码 0101 表示线段端点位于窗口左下方。

2. 处理四种情况：

   

   • Case 1：两端点编码均为 0000 → 线段完全在窗口内，直接接受。
   • Case 2：两端点编码的按位与不为 0000 → 线段完全在窗口外同一侧，直接拒绝。
   • Case 3：两端点编码一点为0000，一点不为0000，则一端在窗口内，一端在外 → 计算交点，替换外部点，循环该过程（裁剪掉外部点到交点的线段）
   • Case 4：两端点编码都不为0，则可能线段完全在裁剪窗口外侧，也可能部分穿过 → 计算交点，循环该过程

优缺点：

• 优点：对简单情况（完全可见/不可见的线段）处理极快。
• 缺点：需多次迭代计算交点，效率不如参数化算法。

扩展为3D：

Cyrus-Beck算法

核心思想：适用于任意凸多边形裁剪窗口，基于参数化线段表示和法向量测试。

关键概念：

• 参数化线段：P(t) = P₀ + t(P₁ - P₀), t ∈ [0,1]
• 裁剪边法向量：N 指向窗口内部。

算法步骤：

1. 对每条裁剪边，计算交点参数 t（且只保留在 0-1 之间的）：
   $$t=\frac{N\cdot (P_0-A)}{-N\cdot (P_1-P_0)}$$

   • A 是裁剪边上任意一点

   • P(t) = P₀ + t(P₁ - P₀) 是线段上任意一点

   • 若P(t)是线段与裁剪边的交点，则有(P(t) - A) · N = 0

     

2. 分类t值：

   • N·(P₁ - P₀) < 0 → 潜在离开点（P_out）
   • N·(P₁ - P₀) > 0 → 潜在进入点（P_in）

3. 计算tₛ和tₑ：

   • tₛ = max{0, max{P_in}}
   • tₑ = min{1, min{P_out}}

伪代码：

优缺点：

• 优点：支持任意凸多边形窗口。
• 缺点：计算量较大。

Liang-Barsky算法

核心思想：Cyrus-Beck算法的优化版，针对轴对齐矩形窗口，通过参数不等式简化计算。

参数计算：对于线段 $ P(t) = (x_0 + t \Delta x,\ y_0 + t \Delta y) $，其中 $ t \in [0,1] $，其在轴对齐矩形窗口内的可见部分需满足以下不等式组：
$$\{\begin{array}{l}{x}_{\text{left}}\le x_0+t\Delta x\le x_{\text{right}}\\ y_{\text{bottom}}\le y_0+t\Delta y\le y_{\text{top}}\end{array}$$
其中：

• $ \Delta x = x_1 - x_0 $，$ \Delta y = y_1 - y_0 $（线段端点 $ P_0(x_0,y_0) $ 到 $ P_1(x_1,y_1) $ 的增量）
• 窗口边界：$ [x_\text{left}, x_\text{right}] \times [y_\text{bottom}, y_\text{top}] $

算法步骤：

对比总结

1. Cohen-Sutherland算法

   • 优点：适合大多数线段可以快速判断为“完全可见”或“完全不可见”的情况（即“平凡接受/拒绝”）。
   • 缺点：对于需要多次裁剪的线段，重复计算会导致效率较低。

2. Cyrus-Beck算法

   • 优点：计算交点参数t的效率高，且裁剪点的坐标只需计算一次。不依赖平凡接受/拒绝的判断，适合需要裁剪大量线段的情况。
   • 缺点：没有针对平凡接受/拒绝的优化。

3. Liang-Barsky算法

   • 是Cyrus-Beck算法的优化版本，进一步提升了效率。

适用场景：

• Cohen-Sutherland：适合简单场景，多数线段无需复杂裁剪。
• Cyrus-Beck/Liang-Barsky：适合复杂场景，尤其是需要频繁裁剪线段的情况。

多边形裁剪

Sutherland-Hodgman算法

基本思想：逐边裁剪多边形，每次处理一个裁剪窗口的边。

四种边情况处理：

1. 起点在内，终点在内 → 添加终点
2. 起点在内，终点在外 → 添加交点
3. 起点在外，终点在外 → 不添加
4. 起点在外，终点在内 → 添加交点和终点

3D裁剪

• 使用6位编码（6个裁剪面）（Cohen-Sutherland算法的3D扩展）

• 在归一化后裁剪（裁剪体积变为直角平行六面体）

• 平面-线段交点计算：
  $$t=n\cdot (p_0-p_1)/n\cdot (p_2-p_1)$$

  推导过程：

  1. 直线参数方程：p(t) = p₁ + t(p₂ - p₁)
  2. 平面方程：n·(p - p₀) = 0
  3. 联立求解：
     n·(p₁ + t(p₂ - p₁) - p₀) = 0
     => n·(p₁ - p₀) + t n·(p₂ - p₁) = 0
     => t = n·(p₀ - p₁) / n·(p₂ - p₁)

裁剪性能优化技术

• 包围盒（Bounding Box）：先对简单包围盒进行裁剪测试
• 管线化裁剪：独立处理各裁剪边，形成处理流水线
• 归一化坐标：简化裁剪计算

光栅化（扫描转换）

基本概念

光栅化是将几何图元（如线段、多边形等）转换为二维像素网格（即光栅图像）的过程。核心任务是确定哪些像素应该被激活以最佳近似原始几何形状。例如：

• 画线段时，需要确定哪些像素连起来最像一条直线
• 填充多边形时，需要判断哪些像素位于多边形内部

线段绘制算法

1. DDA算法（Digital Differential Analyzer）

原理：基于直线的微分方程 dy/dx = m（斜率）

• 当 |m| ≤ 1 时：x每步增加1，y增加m

  for x in range(x0, x1):y += mdraw_pixel(x, round(y))
  

• 当 |m| > 1 时：y每步增加1，x增加1/m（角色互换）

问题：

• 需要浮点运算，效率较低
• 斜率较大时会出现不连续的像素（可通过角色互换缓解）

2. Bresenham算法

• 问题背景：传统DDA算法需要浮点运算，效率较低
• 关键洞察：对于斜率0≤m≤1的直线，每个x坐标下只需在两个候选像素之间选择
• 决策机制：通过整数决策参数确定最接近理想直线的像素
• 核心改进：完全使用整数运算，通过决策变量选择像素

算法步骤（|m| < 1 情况）：

1. 初始化：d = 2Δy - Δx（Δx=x1-x0, Δy=y1-y0）
2. 每步迭代：
   • 如果 d ≥ 0：选择上方像素 (x+1, y+1)，更新 d = d + 2(Δy - Δx)
   • 如果 d < 0：选择下方像素 (x+1, y)，更新 d = d + 2Δy

示例：从(0,0)到(5,2)

Δx=5, Δy=2
初始d=4-5=-1
迭代过程：
x=0, y=0, d=-1 → 选(1,0), d=-1+4=3
x=1, y=0, d=3 → 选(2,1), d=3+2(-3)=-3
x=2, y=1, d=-3 → 选(3,1), d=-3+4=1
x=3, y=1, d=1 → 选(4,2), d=1+2(-3)=-5
x=4, y=2, d=-5 → 选(5,2), d=-5+4=-1

斜率>1时：交换x和y的角色（沿y方向步进）

CG13

一、多边形扫描转换算法

1.1 基本概念

扫描转换（Scan Conversion）是将几何图元（如多边形）转换为帧缓冲区中像素的过程，也称为填充（Fill）。关键问题是如何判断像素位于多边形内部：

• 奇偶测试法：从像素点发出一条射线，计算与多边形边界的交点数量。奇数表示内部，偶数表示外部。
• 环绕数法：计算多边形环绕该点的次数，非零表示内部。

1.2 凹多边形处理

OpenGL原生只能正确处理凸多边形。对于凹多边形，需要先进行**曲面细分（Tessellation）**将其分解为凸多边形（通常是三角形）的组合。常用算法包括：

• 约束Delaunay三角剖分：保持原始多边形边界的三角剖分方法（最大化最小角，避免狭长三角形）
• 受控网格生成：根据几何特征生成适应性网格
• 耳切法：递归切除多边形的"耳朵"（凸顶点形成的三角形）将其分解为三角形集合

1.3 扫描线填充算法 (Scanline Fill)

多边形区域填充算法，通过逐行扫描并确定多边形边界内的像素来实现填充。

1. 按水平扫描线从上到下(或从下到上)逐行处理
2. 对于每条扫描线，计算与多边形各边的交点
3. 对这些交点按x坐标排序
4. 在交点对之间填充像素

流程：

1. 边表(ET)：存储所有非水平边的信息（按ymin排序），包含：

   • y_max（边的最高y值）
   • x_min（边的最低点的x值）
   • 1/m（边的倒数斜率）

2. 活动边表(AET)：存储与当前扫描线相交的边，按x交点排序

3. 填充步骤：

   • 从最低扫描线开始，将ET中ymin=当前y的边加入AET
   • 遍历AET，按x交点两两配对，填充区间内的像素
   • 更新AET中边的x值：x += 1/m
   • 移除y >= y_max的边
   • y++，重复直到所有扫描线处理完毕

1.4 种子填充算法

包括**漫水填充（Flood Fill）**及其改进版本：

• 4连通/8连通：决定填充方向
• 扫描线种子填充：减少递归深度，使用栈管理种子点

二、隐藏面消除技术

2.1 基本分类

• 物体空间方法：在三维空间中进行几何测试，通过比较物体之间的相对位置关系来确定可见性。这类方法的复杂度通常是O(n²)，其中n是场景中的物体数量。（特点：精度高（在数学上精确计算）、计算量大、适合简单场景或预处理）
• 图像空间方法：在二维投影平面上对每个像素进行处理，决定最终显示哪个表面。复杂度为O(nk)，k是每个像素可能覆盖的多边形数量。（特点：与屏幕分辨率相关、适合硬件实现、现代图形管线的主流方法）

2.2 具体算法

2.2.1 画家算法（Painter’s Algorithm）

模拟油画创作过程，按照物体到观察者的距离从远到近依次绘制（后进先出）。

按深度值对多边形排序
for 每个多边形 from 最远到最近:绘制该多边形

优点：实现简单、不需要额外内存

缺点：

1. 深度排序困难：最优排序时间复杂度为O(n log n)
2. 循环遮挡问题：当三个或多个物体互相遮挡时无法确定正确顺序

2.2.2 背面剔除（Back-Face Culling）

在渲染过程中自动剔除不可见的背面多边形，从而提高渲染效率

基本原理

1. 可见性判断：一个面（face）是可见的当且仅当其法向量与视线方向的夹角θ满足 -90° ≤ θ ≤ 90°（即cosθ ≥ 0）。

2. 数学表达：这等价于视线向量v与面法向量n的点积v·n ≥ 0。

3. 平面方程：在3D空间中，每个面可以用平面方程ax + by + cz + d = 0表示，其中(a,b,c)就是面的法向量n。

标准化情况下的简化

在标准化坐标系中（当n = (0,0,1,0)ᵀ时，此时平面被归一化）：

• 只需要测试法向量的z分量c的符号
• 如果c > 0，表示面朝观察者（可见）
• 如果c < 0，表示背对观察者（不可见）

在OpenGL中，可以通过简单的命令启用背面剔除：

glEnable(GL_CULL_FACE);
glCullFace(GL_BACK);  // 指定剔除背面

对于非封闭或非凸物体，需要更复杂的可见性判断算法，如深度缓冲(Z-buffer)与背面剔除结合使用

2.2.3 Z缓冲算法（Z-Buffer / Depth Buffer）

最常用的隐藏面消除方法：

初始化深度缓冲为∞
初始化颜色缓冲为背景色for 每个多边形:for 多边形覆盖的每个像素(x,y):计算当前多边形在该像素的深度值zif z < Z缓冲[x][y]:更新颜色缓冲[x][y]Z缓冲[x][y] = z

优势：简单可靠，硬件友好；缺点：内存消耗大

启用方法：

glutInitDisplayMode(GLUT_DEPTH);
glEnable(GL_DEPTH_TEST);
glClear(GL_DEPTH_BUFFER_BIT);

2.2.4 BSP树

二进制空间分割树：

• 预处理阶段构建空间划分树
• 按照视点位置决定绘制顺序
• 适合静态场景的快速可见性判断

CG14

一、纹理映射基础概念

1.1 视觉真实感的追求

• 几何模型 → 着色模型 → 纹理映射 构成真实感图形的递进关系
• 单纯几何模型无法表现表面细节（如橘子表面的凹凸纹理）
• 纹理映射通过将2D图像"粘贴"到3D表面，显著提升真实感

1.2 纹理映射的优势

• 避免创建超精细几何模型（节省计算资源）
• 通过简单几何体+复杂纹理实现细节表现
• 典型应用：水果表面、砖墙、皮肤等不规则纹理

二、核心映射技术

2.1 基础映射类型

类型	原理	应用场景
纹理映射	将2D图像映射到3D表面	表面图案、颜色细节
环境映射	反射环境图像到表面	金属、玻璃等反光材质
凹凸映射	通过法线扰动模拟凹凸	砖墙、皮肤等微观结构

2.2 坐标系统转换

1. 参数坐标 (u,v) ：定义曲面参数化
2. 纹理坐标 (s,t) ：纹理图像空间坐标（0-1范围）
3. 世界坐标 (x,y,z)：3D物体空间
4. 窗口坐标 (X,Y)：最终图像的生成位置

2.3 映射策略

• 正向映射：纹理空间→物体空间（计算复杂，不喜欢）

• 逆向映射：屏幕像素→物体上的点→纹理空间（实际常用）
• 两步映射：先映射纹理到简单中介表面（如圆柱/球体）

三、高级映射技术(两步映射)

3.1 参数化方法

• 圆柱映射：

  

• 球面映射：类似原理但存在极点畸变

• 立方体映射：6个正方形面组成的环境贴图

3.3 走样与反走样

OpenGL实现：

glEnable(GL_LINE_SMOOTH);  // 直线反走样
glEnable(GL_POLYGON_SMOOTH); // 多边形反走样

1. 问题：点采样导致摩尔纹/锯齿

• 点采样（Point Sampling）：在图形渲染中，通常通过离散的像素点（如屏幕像素）对连续信号（如纹理、几何边缘）进行采样。
• 走样（Aliasing）：当信号的频率高于采样频率的一半（奈奎斯特极限）时，高频信息会被错误地重建为低频信号，导致视觉瑕疵。具体表现包括：
  • 锯齿（Jaggies）：几何边缘（如斜线、曲线）呈现阶梯状不平滑。
  • 摩尔纹（Moire Patterns）：规则纹理（如网格、条纹）在缩小或旋转时产生虚假的波纹图案。

原因：点采样无法捕获连续信号的全部信息，尤其在高频区域（如锐利边缘或密集纹理）丢失细节。

2. 解决方案

(1) 区域平均（Area Averaging）

• 核心思想：将像素视为一个小的区域（而非单个点），计算该区域覆盖信号的平均值（如颜色、亮度），从而平滑高频变化。
• 实现方式：
  • 超采样抗锯齿（SSAA）：以更高分辨率渲染场景，再对子像素结果取平均。例，4x SSAA 对一个像素计算 4 个子样本平均值。
  • 多重采样抗锯齿（MSAA）：仅在几何边缘（如三角形边界）进行多重采样，降低计算开销。
• 效果：减轻锯齿，但计算成本较高。

(2) Mipmap 多级纹理

• 核心思想：预生成纹理的一系列缩小版本（多级金字塔），根据像素在屏幕上的覆盖面积自动选择合适的分辨率，避免高频信号丢失。根据对象与视点之间的距离使用不同级别的纹理。
• 关键点：
  • 层级选择：通过像素与纹理的映射关系计算层级（如基于相邻像素的纹理坐标差）。
  • 三线性过滤（Trilinear Filtering）：在相邻两个 Mipmap 层级之间进行双线性插值，进一步平滑过渡。
• 优势：显著减少纹理缩小时的摩尔纹，且内存开销仅增加 1/3。
• 局限：仅适用于各向同性（均匀缩放）的情况，对斜向拉伸的纹理可能模糊。

(3) 各向异性过滤（Anisotropic Filtering）

• 核心思想：扩展 Mipmap，解决非均匀缩放（如地面纹理在透视下的远距离倾斜）导致的模糊问题。
• 实现原理：
  • 沿纹理的主要拉伸方向（各向异性方向）采样多个 Mipmap 区域，加权平均。
  • 例如，16x 各向异性过滤会沿拉伸方向采样 16 次。
• 效果：保留斜视角下纹理的清晰度，但计算量大于 Mipmap。
• 对比 Mipmap：
  • Mipmap：适合视角正对或均匀缩放的纹理。
  • 各向异性过滤：适合透视投影下的地面、墙面等倾斜表面。

3. 技术对比与应用场景

方法	适用场景	计算成本	效果
区域平均（SSAA/MSAA）	几何边缘抗锯齿	高	平滑但性能开销大
Mipmap	纹理缩小（各向同性）	低	减少摩尔纹，可能模糊
各向异性过滤	纹理斜向拉伸（各向异性）	中高	保持清晰，需更多带宽

四、Mipmap技术详解

1.原理与实现

Mipmap是一种多级纹理映射技术，用于优化纹理采样，减少走样（如摩尔纹和锯齿），同时提高渲染效率。

（1）预生成纹理金字塔

• 核心思想：提前为原始纹理生成一系列逐级缩小的版本（即“金字塔”结构），从最高分辨率（如 1024×1024）逐步降采样到最低（1×1）。

• 层级计算：

  • 第 0 级：原始纹理（最高分辨率）。
  • 第 1 级：长宽各缩小一半（如 512×512）。
  • 第 $n$ 级：直到 1×1 纹理。

• 存储开销：

  • 每级纹理大小是上一级的 1/4（面积比），总存储量为：
    $$1+\frac{1}{4}+\frac{1}{16}+\cdots =\frac{4}{3}$$
  • 因此，额外内存占用仅为原始纹理的 1/3。

（2）层级选择公式

Mipmap 需要根据像素在纹理图上的覆盖范围（即纹理的采样频率）自动选择合适的层级 $D$。公式如下：
$$D={\log }_2\left(\max \left(\sqrt{{\left(\frac{du}{dx}\right)}^2+{\left(\frac{dv}{dx}\right)}^2},\sqrt{{\left(\frac{du}{dy}\right)}^2+{\left(\frac{dv}{dy}\right)}^2}\right)\right)$$

• 物理意义：
  • $\frac{du}{dx},\frac{dv}{dx}$：纹理坐标 $u,v$ 沿屏幕 $x$ 方向的变化率（即“一个像素覆盖多少纹理”）。
  • $\frac{du}{dy},\frac{dv}{dy}$：沿屏幕 $y$ 方向的变化率。
  • 公式计算的是纹理在屏幕空间的最大拉伸率，取对数后得到 Mipmap 层级 $D$。
• 示例：
  • 若纹理被缩小到 1/4（即 2 倍降采样），则 $D={\log }_2(2)=1$，选择第 1 级 Mipmap。

4.2 过滤方式

Mipmap 的层级选择后，还需决定如何从选定的层级中采样纹理。不同的过滤方式在性能和质量之间权衡：

过滤方式	性能	质量	原理
最近邻	最快	锯齿明显	直接取最近的纹理像素（texel），不插值。
双线性	中等	改善模糊	在当前 Mipmap 层级内，对 4 个最近 texel 进行线性插值。
三线性	较慢	最佳过渡（平滑）	在相邻两个 Mipmap 层级之间分别做双线性插值，再对结果线性混合。

（1）最近邻（Nearest Neighbor）

• 操作：直接取当前层级中最接近采样点的 texel。
• 问题：在纹理放大或缩小时均可能产生锯齿。
• 适用场景：复古风格渲染或性能敏感场景（如早期游戏）。

（2）双线性（Bilinear）

• 操作：
  1. 确定当前 Mipmap 层级 $D$。
  2. 在该层级中，找到采样点周围的 4 个 texel。
  3. 对它们的颜色进行水平和垂直方向的线性插值。
• 优势：比最近邻更平滑，适合中等质量需求。
• 局限：在 Mipmap 层级切换处可能出现突兀变化（如地面纹理的“游泳”现象）。

（3）三线性（Trilinear）

• 操作：
  1. 计算连续的两个 Mipmap 层级 $D$ 和 $D+1$。
  2. 在每层分别做双线性插值，得到颜色 $C_D$ 和 $C_{D+1}$。
  3. 根据 $D$ 的小数部分（如 $D=1.3$），按比例混合 $C_D$ 和 $C_{D+1}$。
• 优势：消除 Mipmap 层级间的跳跃，过渡更自然。
• 代价：比双线性多一次插值计算，性能略低。

五、凹凸映射与法线贴图

5.1 技术演进

（1）高度图（Bump Mapping，1978年 Blinn 提出）

• 核心思想：通过灰度图（高度图） 模拟表面凹凸，不改变几何形状，仅影响光照计算。

• 实现方式：

  • 每个像素的灰度值表示高度偏移量（如 0=凹陷，1=凸起）。

  • 法线计算：
    $$\mathbf{n}=\left(-\frac{\partial d}{\partial x},-\frac{\partial d}{\partial y},1\right)$$

    • $d$：高度图采样值。
    • $\frac{\partial d}{\partial x},\frac{\partial d}{\partial y}$：通过差分计算（如 Sobel 算子）估算梯度。

  • 光照计算：修改法线后，按 Phong/Blinn-Phong 模型计算明暗。

• 优点：内存占用小（单通道灰度图）。

• 缺点：

  • 仅适用于低频率凹凸（如粗糙表面）。
  • 边缘轮廓仍平坦（因几何未改变）。

（2）现代法线贴图（Normal Mapping）

• 核心思想：直接存储扰动后的法线向量（RGB 对应 XYZ），取代高度图计算。
• 数据存储：
  • RGB 通道 → 法线分量（通常切线空间下）：
    • R: $N_x$（切线方向）
    • G: $N_y$（副切线方向）
    • B: $N_z$（法线方向，通常为主贡献）
  • 法线向量需归一化（$ |\mathbf{n}| = 1 $）。
• 着色计算：
  • 逐像素读取法线贴图值，直接参与光照计算（如漫反射 $ \mathbf{L} \cdot \mathbf{n} $）。
• 优点：
  • 支持高频细节（如砖缝、皮肤褶皱）。
  • 计算效率高（无需实时差分计算）。
• 缺点：
  • 内存占用较高（3 通道 vs 高度图的 1 通道）。
  • 仍无法改变几何轮廓。

5.2 实现流程

（1）创建高模并烘焙法线贴图

1. 高模（High-Poly Model）：
   • 使用雕刻软件（如 ZBrush）制作含细节的模型（如木纹、锈迹）。
2. 低模（Low-Poly Model）：
   • 简化几何体，保留大致形状（如游戏角色基础网格）。
3. 烘焙（Baking）：
   • 通过 3D 软件将高模的法线信息投影到低模 UV 坐标上，生成法线贴图。

（2）应用简化模型 + 法线贴图

1. 渲染管线：

   • 在着色器（Shader）中采样法线贴图，将切线空间的法线转换到世界/视图空间。

   • 计算公式示例（切线空间→世界空间）：
     $${\mathbf{n}}_{\text{world}}=T\cdot n_x+B\cdot n_y+N\cdot n_z$$

     • $T,B,N$：低模的切线（Tangent）、副切线（Bitangent）、法线（Normal）向量。

2. 光照计算：

   • 使用扰动后的法线 ${\mathbf{n}}_{\text{world}}$ 计算漫反射、高光等效果。

六、OpenGL Texture Mapping

1. 指定纹理（Specify the Texture）

目标：将图像数据加载为OpenGL可用的纹理对象。
步骤：

1. 读取或生成图像
2. 绑定纹理对象
3. 传递图像数据到GPU
4. 启用纹理

2. 分配纹理坐标（Assign Texture Coordinates）

目标：定义纹理如何映射到几何体的顶点。

• 映射关系由应用决定

3. 设置纹理参数（Specify Texture Parameters）

环绕方式（Wrapping） 、 过滤方式（Filtering）

CG15

一、缓冲区基础概念

1.1 缓冲区定义

缓冲区(Buffer)在计算机图形学中是一个核心概念，它本质上是一块内存区域，用于存储图像数据。一个缓冲区可以通过以下三个参数来定义：

• 空间分辨率(n×m)：表示缓冲区的宽度和高度，以像素为单位
• 深度/精度(k)：表示每个像素所占的位数(bit)，决定了缓冲区能存储的颜色精度

1.2 OpenGL中的缓冲区类型

OpenGL提供了多种类型的缓冲区，每种都有特定的用途：

• 前缓冲区(Front Buffer)：当前显示在屏幕上的图像
• 后缓冲区(Back Buffer)：正在绘制的图像，绘制完成后会交换到前缓冲区
• 深度缓冲区(Depth Buffer)：存储每个像素的深度值，用于深度测试

二、缓冲区操作

写入模式

OpenGL提供16种像素写入模式，通过位运算组合源像素（Source）和目标像素（Destination），实现灵活的图像合成。常见模式如下：

模式	运算符	公式	用途
替换	-	D = S	直接覆盖目标像素（默认模式）
或(OR)	`	`	`D = S
异或(XOR)	^	D = S ^ D	可逆操作（菜单高亮/隐藏）

异或(XOR)模式详解

XOR模式的特殊性在于其可逆性：两次异或同一像素会恢复原始值。
典型应用：快速绘制/擦除临时图形（如菜单框、选取框、橡皮筋）

// 伪代码示例：菜单显示与隐藏
void ToggleMenu(PixelBuffer S, PixelBuffer M) {S = S ^ M;  // 第一次：显示菜单（异或混合）S = S ^ M;  // 第二次：恢复原始画面（菜单消失）
}

优势：无需存储背景像素，操作高效。
限制：颜色可能失真（因异或运算非线性）。
）现代法线贴图（Normal Mapping）

• 核心思想：直接存储扰动后的法线向量（RGB 对应 XYZ），取代高度图计算。
• 数据存储：
  • RGB 通道 → 法线分量（通常切线空间下）：
    • R: $N_x$（切线方向）
    • G: $N_y$（副切线方向）
    • B: $N_z$（法线方向，通常为主贡献）
  • 法线向量需归一化（$ |\mathbf{n}| = 1 $）。
• 着色计算：
  • 逐像素读取法线贴图值，直接参与光照计算（如漫反射 $ \mathbf{L} \cdot \mathbf{n} $）。
• 优点：
  • 支持高频细节（如砖缝、皮肤褶皱）。
  • 计算效率高（无需实时差分计算）。
• 缺点：
  • 内存占用较高（3 通道 vs 高度图的 1 通道）。
  • 仍无法改变几何轮廓。

5.2 实现流程

（1）创建高模并烘焙法线贴图

1. 高模（High-Poly Model）：
   • 使用雕刻软件（如 ZBrush）制作含细节的模型（如木纹、锈迹）。
2. 低模（Low-Poly Model）：
   • 简化几何体，保留大致形状（如游戏角色基础网格）。
3. 烘焙（Baking）：
   • 通过 3D 软件将高模的法线信息投影到低模 UV 坐标上，生成法线贴图。

（2）应用简化模型 + 法线贴图

1. 渲染管线：

   • 在着色器（Shader）中采样法线贴图，将切线空间的法线转换到世界/视图空间。

   • 计算公式示例（切线空间→世界空间）：
     $${\mathbf{n}}_{\text{world}}=T\cdot n_x+B\cdot n_y+N\cdot n_z$$

     • $T,B,N$：低模的切线（Tangent）、副切线（Bitangent）、法线（Normal）向量。

2. 光照计算：

   • 使用扰动后的法线 ${\mathbf{n}}_{\text{world}}$ 计算漫反射、高光等效果。

六、OpenGL Texture Mapping

1. 指定纹理（Specify the Texture）

目标：将图像数据加载为OpenGL可用的纹理对象。
步骤：

1. 读取或生成图像
2. 绑定纹理对象
3. 传递图像数据到GPU
4. 启用纹理

2. 分配纹理坐标（Assign Texture Coordinates）

目标：定义纹理如何映射到几何体的顶点。

• 映射关系由应用决定

3. 设置纹理参数（Specify Texture Parameters）

环绕方式（Wrapping） 、 过滤方式（Filtering）