计算机图形学——复习

第一讲 绪论

什么是计算机图形学

计算机图形学(Computer Graphics，简称CG)的内容比较丰富，与很多学科都有交叉，因此笔者认为是无法严格定义的。

在“Wiki百科”和“百度百科”上，对“计算机图形学”的解释为：计算机图形学是一种使用数学算法将二维或三维图形转化为计算机显示器的栅格形式的科学。简单地说，计算机图形学的主要研究内容就是研究如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法。狭义地理解，计算机图形学是数字图象处理或计算机视觉的逆过程。

图形学的研究对象

图形：能在人的视觉系统中产生视觉印象的客观对象

图形学的目的

在计算机中表示、生成、处理和显示图形

和其他学科交叉

  • 数字图像处理：利用计算机对数字图像处理进行底层信息处理
  • 计算机视觉：从数字图像中提取高层次信息
  • 计算机图形学：将各层次信息表达为视觉元素
  • 趋势：这些学科方向不断的交叉融入，形成一个更大的学科方向，可称之为“可视计算”(Visual Computing)

计算机图形学的主要研究内容

建模（Modeling）

  • 在计算机中表达、生成与处理三维模型的数据结构与算法
  • 三维模型的生成方法是当前的热点问题，图形学大众化应用的关键技术难题
  • 主要采取的方法：
    • 计算机辅助设计（CAD）中的主流方法是采用NURBS方法，存在如非正规曲面光滑拼合，复杂曲面表达等问题仍未解决
    • 戏份曲面造型方法，离散迭代曲面构造方法，过程朴素简单实现容易。

渲染（Rendering）

  • 有了模型场景，怎么画出来产生图像，这个核心任务就是渲染要解决的。
  • 常用的真实感绘制方法：光线追踪方法和辐射度方法。
  • 各种渲染技术：全局光照模型、Photo mapping、BTF、BRDF、基于GPU的渲染技术

动画（Animation）

  • 讲义中pass了，也非课程重点
  • 中科大教授解释：连续播放静止图像产生物体运动的效果，制作景物动画，高度物理真实感动态模拟（如各种形变、燃烧爆炸老化等）

人机交互

HCI，人与计算机之间以一定的交互方式活交互界面，来完成确定任务的人与计算机之间的信息交换过程。

其他：渲染只讲了光线追踪相关，额外的没有拓展、GAMS

第二讲 三维模型

几何建模

在计算机中表达一个真实世界的三维对象或虚拟三维形象，就必须先描述其形状。

几何建模：三维对象的表达、构造和处理的计算机算法和过程。

离散化数字化几何数据：

  • 易于表达和传输
  • 渲染硬件和软件的基础数据
  • 大多数获取设备的输出格式
  • 大多数模拟/分析工具需要的输入

走样（aliasing）：用离散数量像素表示连续的量而引起的失真，称为走样。

反走样（在图形显示过程中，用于减少或消除走样的方法），方法：提高分辨率、非加权区域采样、加权区域采样。和某个像素求交，计算相交区域面积，确定像素值。

OpenGL反走样：glEnable(GL_BLEND) //启用混合 glEnable(GL_LINE_SMOOTH) //启用线段反走样

3D模型表达

  • 原始数据：体素、点云、深度图像、多边形
  • 实体模型：八叉树、BSP树、CSG、Sweep
  • 曲面：曲面王哥、细分曲面、参数曲面、隐式曲面
  • 高层次语义结构：Scene Graph

什么是网格（Mesh）

  • 图形学中最常用的表达
  • 简单
  • 可表达复杂形状
  • 图形硬件支持
  • 一般为三角网格

为什么是三角网格

  • 其他多边形网格可以容易剖分为三角形
  • 三点共面：保证平面性
  • 可以容易地定义内外方向、插值操作等

一些概念

  • 边界边：只与一个面相邻
  • 正则边：与且仅与两个面相邻
  • 奇异边：与多于两个面相邻
  • 流行网络：没有奇异边的网格
  • 封闭网络：没有边界边的网格

v+f-e = 2(c-g) - b

网格的数据结构表达

应用：渲染、几何查询（点面关系）、几何操作。大部分网格难以支持高效的上述操作，一般采用三角流行网格。

判断网格的数据结构是否优秀：

  • 构建数据结构的时间复杂度（建立时间复杂度）
  • 进行一个查询操作的时间复杂度（查询时间复杂度）
  • 进行一个网格编辑操作的时间复杂度（更新时间复杂度）
  • 空间复杂度

数据结构表示举例

  • 面列表：
    • 顶点列表：（x,y,z坐标）
    • 面列表：逆时针顶点三元组（v1，v2，v3）
    • 查询复杂度：面包含顶点O(1),顶点相邻O(n)
    • 优点：方便紧凑、可表达非流形网络
    • 缺点：不能有效地支持点、面之间的邻接关查询
  • 邻接矩阵
    • 顶点列表+表示顶点相邻的邻接矩阵
    • 查询复杂度：面包含顶点O(1),顶点相邻O(1),顶点与面相邻O(n)
    • 优点：支持vv的高效查询、支持非流形网络
    • 缺点：没有边的显示逼到啊，不支持如vf，ve，ev等的快速查询
  • 半边结构
    • 流行于大部分几何建模应用
    • 优点：所有查询操作时间复杂度均为O(1)，所有编辑操作时间复杂度均为O(1)
    • 缺点：只能表达流形网络

面列表、邻接表（矩阵）、半边结构。 仔细了解，明白优劣，能写代码。

细分曲面

虽然理论上可以手动地设定每一个顶点、边、面，但这是异常繁琐的。理想的情况：手工构造一个低分辨率的网格，然后逐渐地用自动化算法光滑化，添加更多细节。

细分曲线、NURBS、隐式曲面、实体建模（CSG）

几何建模经典方法（常用的建模方法）

  • 扫描
    • 构造一个对象的三维模型需要一张或多张深度图像
    • 距离扫描仪测量的是物体表面的三维坐标，并以m*n的距离网格形式返回测量值， 这个网格称作深度图像
    • 如果有多张深度图像，对每张图像需要计算出一个刚性变换，以与其他深度图像对齐
    • 使用改进版本ICP算法来计算合适的刚性变换，使得两张深度图像之间点对的最小二乘距离最小
  • 基于图像的建模
    • 从海量图片中构造三维模型
    • 利用计算机诗句的方法来估计每张照片的相对摄影机位置与朝向，同时得到对象的稀疏点云表达
    • 基本的思想：一个点的位置可以通过多张不同位置拍摄的照片确定
    • 给定了这些相机参数和稀疏的点云，有许多致密的重建算法可以用来重建致密的模型
  • 过程式建模
    • 使用算法创建模型
    • 可容易地构造多样化的模型
    • 一般用来构造复杂的、规则性强的模型（地形、植物、建筑、城市）
    • 用一个小的数据集或规则来描述目标模型的高层次语义信息
    • 用算法来生成全部的模型（加入随机性，递归算法）
    • L-system 用来进行植物建模典型系统
      • 递归的形式化语法（符号字母表、生成规则集、非端点富豪递归地生成新的符号或符号序列）
      • 整个过程从一个初符号开始，最后由一个解释器将生成的符号解释为几何结构。
    • 分形
      • 从一个形状开始，用缩放的初始形状来替换形状的一部分
      • 递归地进行替换

几何建模应用举例

  • 去燥/光滑化
    • 输入一个带有噪声的网格，输出一个光滑的网格
    • 目标是去掉高频信息
  • 网格简化
    • 网格常常包含了比需要显示质量更多的面片（一些网格生成算法的分辨率是固定的，不考虑曲面细节，网格可能会在不同的设备上使用）
    • 因此，网格简化的目的是在保持视觉准确性的前提下减少面片的数量
  • 网格编辑
  • 网格分割（将网格分割成有意义的部分）

网格、网格的典型数据结构、几何建模典型方法、几何建模典型应用。

重点讲网格，网格的重要属性。

半边结构只能表达流形网格。

NERBS 曲线 曲面。

第三讲 OpenGL 编程

OpenGL 绘制几何图元

改变状态、指定绘图元素

第四讲 数学基础回顾

重心坐标、插值

线性代数：向量变换，矩阵板换

第五讲

照相机与OpenGL渲染管线

模型变换-摆放物体——从物体坐标系到世界坐标系

视图变换-摆放相机——从世界坐标系到相机坐标系

投影变换-调整焦距——确定放大倍数

视口变换-选择底片——确定照片大小

视图变换——相当于把照相机固定在三脚架上，并使它对准场景。模型变换——设置模型的位置和方向。如何选择？本质上是一致的，把这两种变换割裂开来是没有意义的，有时候使用一种变换要比使用另外一种变换要方便得多。

变换

模型变换-摆放物体

二维变换变换的矩阵表示，矩阵蕴含表达式（图 ）

旋转的矩阵表达（图）

缩放的矩阵表达（图）

平移的矩阵表达（图）

齐次坐标：扩展一维，看上去不自然，但是使得图形学中的变换操作更简便

为什么要用采用齐次坐标

  • 将平移、旋转和缩放等仿射变换统一为矩阵乘法操作
  • 在软硬件实现上更简单
  • 注意顺序
  • 齐次坐标 1 和 0 表示什么（区分坐标和向量0向量1坐标）

视图变换与模型变换

  • 三维齐次坐标下三维旋转与缩放（图，隔一层右上-sin，隔两层左下-sin）
  • 绕任意轴进行旋转（图）
    • v旋转（绕x轴）旋转到xz平面（Rx）
    • v旋转（绕y轴）旋转到z轴（Ry）
    • 绕v旋转一角度
    • 前面变换坐标的逆（旋转矩阵的转置是旋转矩阵的逆）

投影变换

  • 投影变换定义了一个视景体（视景体决定了一个物体是如何映射到屏幕上的，视景体定义了场景中的哪些部分被裁剪到最终的图像之外）
  • 正交投影 glOrtho()
    • 成像尺寸不随深度改变
    • 正交投影将z方向坐标变换为0
  • 透视投影 glPerspective()
    • z方向坐标对x、y方向坐标剪向形变的影响

齐次坐标系

  • 齐次坐标的第四维可以是任意非零值
  • 齐次坐标的四个维度同时乘以一个非零值，所表达的对象（点）不变
  • 当齐次坐标等于0
    • 表达无穷远处的“点”
    • 表达一个向量
    • 不受平移影响 ## 直线透视（透视除法）

视口变换

  • 选择窗口中的绘图区域
  • 对应于选择被冲洗照片的大小

glViewport

  • 注意视口的纵横比与视景体的纵横比保持一致

操纵矩阵堆栈

矩阵的操作还需要复习

void glPushMatrix 复制栈顶矩阵 void glPopMatrix 丢弃栈顶矩阵

1
2
3
4
5
6
7
8
9
10
draw_car_body();
glPushMatrix();
    glTranslate();
    draw_wheel_and_bolte_1();
glPopMatrix();

glPushMatrix();
    glTranslate();
    draw_wheel_and_bolte_2();
glPopMatrix();

第六讲 纹理贴图（Texture）

为什么要纹理贴图

我们如何给模型添加更多的细节？

  • 添加更多的几何元素：更多的三角面片
    • 优点：在光照和其它表面交互中具有真实的表现
    • 缺点：难以生成，并消耗更多的存储和计算资源
  • 将纹理映射到模型上
    • 优点：使用简单、方便，消耗的资源少，可重用
    • 缺点：过于简化、表面几何仍然是光滑的

什么是纹理

  • 计算机图形学的定义（广义）：以图像（包括二维和三维）方式存储的资源，如位图等。
  • 纹理合成的定义（狭义）：具有某种重复模式的图像

纹理贴图的形式化描述

  • 从模型表面S到二维参数域U的映射函数
  • \(f: S \rightarrow U\)
  • 给定模型表面S上任一点p，均有f(p)属于U
  • 这个映射称为纹理映射
  • S上的顶点在U中的坐标称为纹理坐标
  • 纹理图像与参数域U之间存在自然的映射

几何图形表面材质，表达方法。

从模型表面到二维参数的映射函数

球面全局参数化。

启用纹理贴图功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//清理缓存
glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);

//启用纹理贴图
glEnable(GL_TEXTURE_2D);
//指定纹理贴图与材质的混合模式
glTexEnvf(GL_TEXTURE_ENV, AGL_TEXTURE_ENV_MODE,
GL_DECAL);
//绑定纹理
glBindTexture(GL_TEXTURE_2D, texName);

//绘制场景 提供纹理坐标和几何坐标
glBegin(GL_QUADS);
   glTexCoord2f(0.0, 0.0); glVertex3f(-2.0, -1.0, 0.0);
   glTexCoord2f(0.0, 1.0); glVertex3f(-2.0, 1.0, 0.0);
   glTexCoord2f(1.0, 1.0); glVertex3f(0.0, 1.0, 0.0);
   glTexCoord2f(1.0, 0.0); glVertex3f(0.0, -1.0, 0.0);

   glTexCoord2f(0.0, 0.0); glVertex3f(1.0, -1.0, 0.0);
   glTexCoord2f(0.0, 1.0); glVertex3f(1.0, 1.0, 0.0);
   glTexCoord2f(1.0, 1.0); glVertex3f(2.41421, 1.0, -1.41421);
   glTexCoord2f(1.0, 0.0); glVertex3f(2.41421, -1.0, -1.41421);
glEnd();

glFlush();
glDisable(GL_TEXTURE_2D);

其他映射方法：

  • 凹凸映射
  • 环境映射
  • 法向贴图
  • 置换贴图

GL固定流水线过程（图）

固定流水线，回顾

第七讲 自由曲线和自由曲面

曲线曲面造型概论

  • 平面模型：用多边形网格描述形体表面
  • 曲面模型：由曲面片代替平面模型中的小平面片

自由曲线和曲面因不能由画法几何与机械制图方法表清楚，称为工程师们首要解决的问题。人们一直在寻找用数学方法唯一定义自由曲线和曲面的形状

对形状数学描述的要求

  • 从计算机处理的角度
    • 唯一性
    • 几何不变形（形状跟坐标系无关）
    • 易于定界
    • 统一性（统一的数学表达，便于建立统一的数据库）
  • 从形状表示与设计的角度来看
    • 丰富的表单能力：表达两类曲线曲面
    • 易于实现光滑连接
    • 形状易于预测、控制和修改
  • 从其他角度来看
    • 导数易计算
    • 易渲染
    • 易碰撞检测

发展过程：1971 Bazier曲线、1974 B样条曲线和曲面、1975 有理B样条方法 80年代后期 发展成非均匀有理B样条（NURBS）方法，NURBS称为当前大多数商用CAD软件系统的内部表达技术（Solid Edge、CATIA、Inventor等）

曲线曲面的一般参数样条表达

略

Bezier曲线

为什么用参数曲线？

  • 一条曲线可用多边形、折线段来金丝
    • 不能缩放
    • 需要较多的点使曲线变得光滑
  • 阴式曲线 制定。难于制图
  • 参数曲线可以指明运动的点在时刻t时的位置

多项式曲线的优点：容易计算、可微

不用标准多项式来设计的原因：参数对于曲线没有直观意义，不容易调整。

Bezier曲线：用\(\}(1-t)^2,2(1-t),t^2\}\)，而不是幂函数\(\{1,t,t^2\}\)作为基函数，使得系数有了某种直观意义，控制点。

  • Bezier曲线由一条折线决定
    • 称为控制多边形，多边形的顶点称为控制点
    • 控制点按顺序形成一条折线
  • 控制顶点可以为任意数量，3个或者4个是最常见的
    • 曲线的阶 = 控制点的数量
    • 曲线的次数= 曲线的阶- 1
  • Bézier 曲线逼近控制多边形，通过第一个和最后一个顶点，但一般不通过其它的顶点

用样条曲线而不用多项式曲线的原因。

图：Bernserin多项式

要求根据公式画形状。

性质

  • 端点性质：曲线通过首末顶点。带入参数可验证
  • 切矢性质：曲线在首末亮点相切于多边形的起、止边。对三次Bezier曲线求一阶导数：首为3(P1-P0)、末为3(P3-P2)。
  • 对称性：对称点反序仍然可以得到相同的形状
  • 凸包性：Bezier曲线不会越出特征多边形顶点围成的凸包。

插值

在参数空间[0,1]进行均匀茶汁，计算对应的坐标点，然后连接成线，就是折线逼近Bezier曲线

不足：Bezier曲线有三点不足 - 一是特征多边形顶点数决定了Bezier曲线的阶次，n很大时，特征多边形对形状的控制将减弱。 - 二是Bezier曲线不能作局部修改，改变任一控制点将波及整条曲线。 - 三是绘制复杂曲线需要拼接，比较繁琐。

因此发展了B样条曲线，1972年Gordon等用B样条基代替Bernstein基函数，从而改进上述缺点。

后面补充B样条曲线内容

第八讲 真实感绘制

真实感绘制，逐个逐个添加，要素：明暗、阴影、高光

光线跟踪基本实现的伪代码，理解，掌握。

两个关键技术

  • 光照明模型
  • 求交加速算法

第九讲 光照明模型

熟记，入射光，法线如何计算反射光

Phong 照明模型

Blim-Phong

I 那个公式

明暗处理 shading

第十讲 光线求交

发现计算 M^T的问题

包围盒、层次包围盒、均匀网格、八叉树、K-DTree 需要了解四种数据结构构造方法。

题目设置：选择、填空、判断，证明/程序实现/问答题