【笔记】《计算机图形学》(1&2)——导言与数学工具

之前说接下来要写下机器学习的总结，但是回看了下吴恩达的机器学习发现没有太多总结的必要，往上的笔记已经很足够了(摸了)。那么从这篇开始就来记录我心心念念已久的图形学内容

这系列的笔记来自著名的图形学虎书《Fundamentals of Computer Graphics》，这里我为了保证与最新的技术接轨看的是英文第五版，而没有选择第二版的中文翻译版本。不过在记笔记时多少也会参考一下中文版本

这系列的笔记依然按照我之前的想法，只记录我认为比较关键的部分，因此如果有人要看我的这些文章请务必也要自己去看书，笔记仅仅起到提示与总结的作用

这第一篇包含了原书中第一和第二章的内容，也就是导言部分和数学回顾部分，导言部分很多都是老生常谈的内容，只最简单地带过，数学回顾部分大多是大学数学中有提及的内容，着重记录了向量运算和三角形的重心坐标系部分，这部分与图形学密切相关

下面是这本书英文版和中文版的封面，以作参考：

1.1 图形学领域

图形学主要分为三个大领域：

1. 建模
2. 渲染
3. 动画

而最常会涉及到计算机图形学的交叉领域则有：

1. 用户交互UI
2. 虚拟现实
3. 可视化
4. 图像处理
5. 三维扫描
6. 图像计算

1.2 主要应用

1. 电子游戏
2. 动画
3. 特效
4. 电影
5. CAD/CAM
6. 拟真软件
7. 医学图像
8. 信息可视化

1.3 图形API

图形API指一系列提供了例如将图形和三维表面绘制到屏幕的窗口中的基本操作的函数

主要有两大类图形和UI的API：

1. 以Java为代表的，完全标准化并作为编程语言的一部分被提供出来的API组件，有很强的可移植性
2. 以Direct3D和OpenGL为代表的，大多作为C++的软件库出现，一般在不同的系统间都是不同的，不方便移植

但无论使用哪一类API，其基础的图形调用都是相同的，书中的概念都可以应用到上面

1.4 图形管线

图形管线是一个特殊的软件/硬件子系统，可以高效的有透视地绘制原始三维信息

图形管线中曾经有一个疑难问题就是z值缓冲透视问题，如今通过一个四维齐次空间结构几乎完美地解决了。管线处理图像的速度很大程度上依赖于需要绘制的三角形数量，对此人们提出了按照与目标模型距离为核心的细节层级技术(LOD)来解决这个问题

1.5 数据问题

大多数计算机都是用IEEE的浮点数标准进行数据的计算的

关于IEEE的浮点数标准关键要记住几个特殊情况：

1. 所有的有限数都小于+∞
2. 所有的有限数都大于-∞
3. －∞小于+∞
4. 任何包含了NaN的表达式结果也是NaN
5. 任何得到NaN的表达式转为bool为false

浮点数的计算法则和高等数学中的计算差不多，想清楚再用即可，尽量不要让函数的返回值是特殊数字防止加大后续判断的开销

1.6 效率

随着时代的进步，如今制约程序设计最大的问题是内存占用而非处理速度了，当程序要在内存占用和运行速度之间折中时，最好偏向内存优化那边

尽量编写直截了当的代码，这会让后续的维护舒服很多，把时间花在优化性能上要比花在处理bug和加新特性上有意义得多

1.7 图形程序的设计与编程

对于图形程序来说，有一系列优质高效的关于向量和矩阵处理的函数和类是非常关键的，这是图形元素的关键

这些数据结构主要包括：

1. 二维向量vector2
2. 三维向量vector3
3. 四维向量hvector
4. 颜色值rgb
5. 变换矩阵transform
6. 图像数组image
7. 整数类intervals
8. 正交基orthonormal bases
9. 坐标系框架coordinate frames

图形程序常常需要用浮点数计算，推荐使用double进行几何变换，用float进行颜色变换，用float存储数据到硬盘中，用double处理内存数据，如果可以的话尽量用float处理数据除非有充分证据表明某个地方必须要用到double的高精度

有几个很好用的处理图形程序问题的debug技巧：

1. 输出有问题的部分的图像，观察问题部分的特点，猜测问题可能的原因并进行相应的测试。这样可以不直接检查错误可能出现的地方而是通过结果猜测错误缩小目标范围，速度会快很多
2. 暂时创建一个调试用的项目副本，将测试正常的额外部分代码关闭，然后输出可能出问题的代码生成的画面来缩小错误代码的范围
3. 使用调试器在可能出问题的代码附近设置条件断点，因为图形学的代码一般都有大量嵌套的循环，需要条件断点来确定暂停的位置
4. 将运行中的一些数据格式化输出出来查看，花些时间在优化内部数据的输出上能大幅提高后续debug的效率，磨刀不误砍柴功

2.1 集合与映射

几个集合标识

区间

对数

2.2 解二次方程

这一节没什么内容。主要是记得用判别式D=B^2-4AC在求解前判断根的数量

2.3 三角学

asin，acos之类是普通三角函数的逆函数，其中有一个atan2函数输入参数"对边和邻边"返回对角的度数

常用的一些三角函数变换

2.4 向量

点乘展开

叉乘展开

如果想要转换向量坐标在不同坐标系中的表示，例如要将uvw坐标中表示的向量转换到xyz坐标中表示，首先我们需要有uvw坐标系的基uvw在xyz坐标系中的表示，然后将目标向量的坐标与这三个基的这个表示相乘，这样就可以得到xyz中表示的目标向量。

在这里我们还可以将这三个基组合成矩阵A，这样只要让矩阵左乘目标向量即可完成转换

而当我们需要将xyz的坐标转换回uvw中，则应对变换矩阵A进行求逆，然后同样左乘这个矩阵即可逆操作

因为这个特性当我们需要对a坐标系中的向量实施b坐标系中的c转换时，我们应该先将向量左乘变换矩阵A变到b坐标系中，再应用c转换，然后再使用逆矩阵A-1将转换后的向量变回a坐标系中的坐标表示

如果两个坐标系的原点位置不同，转换到相同坐标系中后直接进行原点偏移即可

有时我们需要从一个向量构造一组比较适合这个向量的标准正交基也就是一组相互垂直且模长为1的向量来构建坐标系。常用方法是：

• 选定这个向量转为单位向量作为其中一个基；
• 对一个与这个基相同的向量，将其坐标中最小的数字改写为1，这样这个向量与原先的基会有比较大的角度保证叉乘时的精度，接着两个向量叉乘得到第二个基；
• 最后这两个基叉乘可以得到垂直的第三个基来构建坐标系

从两向量建基则更简单，如果两个向量a和b已经是正交的则直接用刚才的方法标准化即可

如果两向量并不正交，则类似单向量的情况

上面的构建基的方法一般得不到互相垂直的一组基，如果觉得得到的结果不够理想，开销最小的方法就是选择不太相同的另一组w和u来构造基，如果还是不够理想，可以使用奇异值分解SVD来得到接近于原先坐标系的正交基

2.5 曲线和曲面

二维梯度的计算：

对隐式曲线方程f的x和y如下图求偏导即可，f的值是xy在三维空间中对一个曲面映射出来的高度值。这里要注意尽管我们脑内对这个式子可能仍然想象是一个曲面，但是实际上更加合适的想象是一条有颜色的曲线，因为在二维的处理部分我们真正面对的是一个三维曲面在二维平面上的切面，对于z值我们是无法操控的

因此上面式子算出来的梯度向量是z值上升最快的方向，专业点说是值增长最快的方向导数向量。即是对所取点处的xy平面进行偏导，得到的向量是在xy平面上的能使得f变化最大的方向

我们常说梯度与法线方向相同，仍然要谨记这里是二维的有值的曲线，也就不难理解梯度为什么与切线垂直了，因为这里的切线恰恰是三维曲面切平面在这个点的平面上的交线

二维直线的一般式 Ax+By+C=0 中，点(a,b)到线的距离为：

类似的某点的三维曲面的梯度或者说法向量可以由下式得到，同样的此时要想象为一个彩色的三维曲面：

2.6 线性插值

这一节没什么内容。线性插值是最简单的插值方法，以线性多项式对一个区间内进行插值

2.7 三角形

重心坐标系与重心是不同的。重心，对于均质物体等同于形心，三角形的重心位于三角形三边中线的交点上

而重心坐标系是在三角形中描述一个点的非常实用的坐标系，在图形学中由于三角形是大多数图形程序中组成模型的最基本元素，因此用三角形定位各个三角形内部点的坐标非常重要

重心坐标系的关键是利用三角形的边和顶点来定位坐标，如下图我们二维中可以用三角形的一点a和两条边作为基描述中间蓝点p的坐标

显然此时我们可以用下式描述点p

然后将这公式进行变形，可以得到更简洁的公式，从此我们可以用(β,γ)来描述一个点的坐标

此时如果α，β，γ中有哪个坐标在[0,1]之外，则表示这个点在此三角形外

那么重心坐标的好处在哪里呢，好处在于我们可以轻松从坐标α，β，γ中很方便地进行图形学中很关键的三角形颜色插值，而且可以很简单地得到点到边的距离比值，从下图中可以看到，由于平行线距离只差一个常量的原因，如果我们假设边到另一个顶点的距离为1，则坐标分量就是距离的比值了

那么如果我们已知点p的xyz坐标，想要得到其重心坐标，有几个方法：

第一种是代数法，直接按照前面的定义法的思路构造求解β，γ的线性方程组，然后再求解α即可

第二种是几何法，运用前面说到的距离比值的特性，我们先按照点法式列出如下的方程，只有当x，y恰好在ab构成的直线上时值才会为0

那么如果我们此时代入的点不在线上，必然得到的函数值就是点到直线的距离。但是只有一个距离不够，我们需要的是点分量在三角形内的比值，因此我们将这个值除以代入另一个顶点的值就可以得到坐标分量

同理可以得到其他的分量值

第三种是面积法，这里我们要知道重心坐标的分量比恰好就是三角形被划分出的子三角形的面积比，具体的证明在很多地方都可以找到。由于面积比定理，我们可以通过计算面积来得到坐标

三维空间中的三角形依然可以直接利用上述的方法来得到坐标

而面积法对三维空间中的三角形很有用。首先我们可以通过三角形两边向量的叉乘模长乘1/2得到三角形的面积，将叉乘展开就可以简单理解。然后我们可以用下面的公式计算出重心坐标，其中三个额外的向量是目标点到子三角形其中一个顶点的向量，用来计算子三角形的坐标