• [ ] 基础知识
  • [ ] 数学
    • [ ] 叉乘能计算向量左右方向（右手定则）
      • [ ] 有矩阵形式 $A^*b$
  • [ ] 物理
  • [ ] 信号处理（采样）
  • [ ] 数值计算
• [ ] 光栅化
• [ ] 渲染、网格
• [ ] 光线追踪
• [ ] 模拟仿真

个人积累

• 硬件中的缓冲，就当成数据传输，因为是使用缓冲区传输
  • 在硬件下一帧绘制之前，把顶点缓冲区准备好，然后进行绘制
• 因为矩阵计算的可结合性，所以计算矩阵一般是先进行矩阵（变换）计算
• 顶点：对于渲染管线，图元是有顶点构成的（所以要根据顶点定义图元），各种复杂图形是由基础图元构成的。
  • 对于缓冲区本身是无意义的，关键看图形接口 API 怎么去解释这段缓冲区数据

基础知识

变换

（线性组合为新的坐标，这个线性组合的矩阵值是新向量空间的基）

基础变换

• 可逆变换
  • 都可以拆成一个个初等变换
  • 结合律
• 缩放
• 反射：对称轴
• 切变（sheer）：
  • 一个轴距离不变，一个变化
  • 距离不变的轴所对应空间的基进行了旋转
• 旋转：逆矩阵等于转置（正交矩阵）
  • 绕某点旋转可以分解为，原点旋转加上来回平移
  • 三维旋转：罗格里格斯公式
• 平移：不能简单的写成矩阵相乘，而是形式 $x^{’}=Ax+b$ 非其次
  • 所以需要高一维去表示
  • 即 $\begin{matrix}x^{’} \cr 1\end{matrix}=\left[\begin{matrix} A&b\cr0&1 \end{matrix}\right]\left[\begin{matrix} x\cr1 \end{matrix}\right]$
  • 矩阵变成了 4*3 的形式（仿射 Affine 矩阵）
  • 齐次坐标（加一个维度）：Vector 值为 1，Point 值为 0（两个向量相减，1 值被减去）$\left(\begin{array}{c}x/w \cr y/w \cr 1\end{array}\right)$
    • 矩阵是后进行平移，如要先平移要写出一个新的矩阵

Viewing 观测变换

视图相机变换

• 概念
  • 位置向量：position
  • 方向向量：loot-at、Gaze-direction
  • 向上向量：Up-direction，方向向量的旋转轴
  • 相机空间：相机在 0 点 看向 -z （右手系）
    • 先求逆：从标准坐标到任意坐标好求
    • 又因为旋转矩阵的转置就是逆，所以直接算出来了
    • 相机空间的变换矩阵说明清楚，其他物体也就可以直接变换到相机空间

投影变换

• 视锥体：从相机出发，视线范围的空间几何体
• 

正交投影（平行投影）

• 视锥体的边是完全平行的（是一个正方体），不会有近大远小现象
• 三视图
  • lr：左右
  • tb：上下
  • 这些在程序中一般用 FOV 以及 Aspect 进行表示，三角函数关系
  • fn：远近

变换矩阵：

齐次除法：平移后把物体拉成一个标准正方体（中心在原点）的各边长度缩放到 2，即范围为 -1～1；在标准坐标外（视锥体外）的会被裁剪

透视投影

• 人眼的观测方式
• 视锥体从一个点出发，是一个锥台（四棱锥）
• n 平面和 f 平面大小不一样
  • f 能看到的范围更广，所以同样的物体大小更小

做法是把锥台挤成一个正方体，然后再用正交投影。即：$M_{persp}=M_{ortho}*M_{persp\to ortho}$

• n 平面不变，后续到 f 平面逐渐挤压
• 中心也不变
• 变化的只有 xy 轴坐标
  • 画出侧视图：能看到 n 平面和 f 平面的比值关系（已知特殊点的对应关系）
    
    奇次化：
    
    即：
    
    接下来求出未知向量即可
• 根据 n 平面上所有值不变的特点可得：第三行为 （0，0，A，B），与 x y 无关
  • 根据齐次坐标的任意性，(x，y，n，1) == （nx，ny，n^2，n）
  • 也就是第三行计算后得到 n^2
  • 但是 n 与 xy 无关，所以前面两位为 0
  • 得到： $A*n+B = n^2$
    
• f 平面上 z 值不变
  • 取 x，y 为 0 为特殊点，但是 z 不变
  • 有：$A*f+B = f^2$ （变换矩阵第三行）

通过两个特殊点的推论算出 A、B，从而得到整个变换矩阵

投影变换矩阵为：

$$ M_{persp\to ortho}=\left(\begin{matrix} n & 0 & 0 & 0\cr 0 & 1 & 0 & 0\cr 0 & 0 & n+f & -nf\cr 0 & 0 & 0 & 1\cr \end{matrix}\right) $$

个人补充：

一般映射到屏幕上还差两个步骤：

• 透视除法：NDC Space（规范化设备坐标）
  • 齐次除法，w 轴（第 4 轴）齐次为 1，范围就能是 [-1,1] 之间
  • 映射输出：把 NDC 映射到 Screen [0,1]
    • 与标量的 0-1 映射方式一致，对每个坐标进行一次运算

• 视口变换：Screen Space（屏幕坐标）

Model：

• [ ] IK

光栅化

视口变换

从投影空间变换到具体屏幕上

定义

• 屏幕坐标由具体的像素构成，带有宽和高的整形参数
• 像素中心点是屏幕坐标各加 0.5 得到

变换矩阵

$$ M_{screen}=\left(\begin{matrix} \frac{width}{2} & 0 & 0 & \frac{width}{2}\cr 0 & \frac{height}{2} & 0 & \frac{height}{2}\cr 0 & 0 & 1 & 0\cr 0 & 0 & 0 & 1\cr \end{matrix}\right) $$

投影空间的范围是 -1~1，长度是 2，所以按照比例缩放加上中心点的平移能得到

BoundingBox

包围盒，AABB，表示一个多边形的最大最小坐标范围形成的正方形，如果是三维就是正方体。只需要两个向量，分别表示最大和最小。

光栅化 Resterizing

把多边形（一般选取三角形，有最基本元素的优秀性质）光栅化为屏幕像素

此处只考虑 x y 轴，在前面所得的正方体空间中进行光栅化。

用一个连续函数对像素中心点进行采样（Sample 这个概念很重要，光栅化很多都是在处理这个采样，函数（冲击函数）形式是离散均匀分布的点，因为其他位置是 0，所以被去除）

简单来说：如果中心点在多边形内部，那么就进行上色

抗锯齿

这里面会出现一个问题：走样/锯齿（Aliasing）。因为采样的概念出自信号处理，所以就有相应的方法反走样/抗锯齿（Antialiasing）。

采样理论

本质是用时域频域的一些特性进行处理（滤波/卷积，傅里叶变换），减少图像的高频信息，避免锯齿

采样频率跟不上信号变化频率会造成锯齿，从时域频域中看就是冲击函数的间隔变小，频域卷积的函数挤在一起失真了
（像素越大锯齿就严重，因为采样稀疏了采样频率变小了）

低通滤波（模糊）后再采样的原理：

还可以对同一个像素内部做滤波（Filtered），前面根据像素中心点判断是否在三角形内部，现在对不完全在三角形内部的像素进行处理，根据不同的像素的覆盖率得到不同的深浅颜色值。

MSAA(Multi Sample AntiAliasing)

多采样抗锯齿：是反走样的近似，把一个像素内部再划分为多个像素点（不只用中心点了，添加多个点的判断）根据覆盖的数量得到像素的颜色占比。

• FXAA：快速近似抗锯齿，后期处理去除锯齿（图像处理）
• TAA：时间抗锯齿，根据上下帧的不同的像素内部点做滤波，在时间上抗锯齿，不用怎讲计算量

可见性/遮挡

油画家算法：当成绘画，由远到近，不断覆盖

3D 多边形在投影空间是被挤压拉伸的，所以很难定义远近距离的深度，特别是在有遮挡依赖的时候，说不清楚谁在前面。

所以引出了深度缓冲

深度缓冲/Z-Buffering

是一种算法，一般在硬件中实现
屏幕的像素点本质是内存的缓冲区（因为是 IO 设备），一般对于颜色的显示是放到帧缓冲中，表示每个像素的颜色，当显示器刷新时间到了，就取出显示。
现在对深度值也进行缓冲存值，（定义正值 z 越近越小，越远越大）把对多边形进行排序放到一个像素中的叠加筛选。
如果深度越近，那么就更新深度缓冲，并写入颜色值。（松弛操作）

特别好的性质：之和像素有关，先画哪个三角形无所谓，这就可以使用 GPU 加速进行并行运算

• 如果结合结合 MSAA，采样点是多个，考虑多深度的情况，算法会更复杂一些。
• 对于透明的物体需要特殊处理
  • 关闭透明物体片元的深度写入，但是打开深度测试（透明物体也要参与深度测试，只是不写入深度）

着色（Shading）

在不同情况下，同样的东西会呈现不同的颜色；比如一个绿色的的球，它本身颜色只有绿色，在二维画出来就只是一个圆，我们考虑到各种光照和环境情况就能让它更真实起来，这就是着色。

• 定义：明暗，上色
• 也可以说是把材质应用到物体上。
  • 受光照影响：对应各种光照模型
  • 可以导入纹理，简化颜色上色的定义

Shading Point：用于计算着色的点

着色模型输入有：

• 视角方向
• 表面法线：n 单位向量
• 光线方向：l 单位向量
• 表面参数
  • 颜色
  • 亮度

计算夹角直接点乘即可，因为都是单位向量

Tip：着色和阴影无关，是 Local/局部的操作

BP （Blinn-Phong） 反射模型

$$ \begin{align} L&=L_a+L_d+L_s \cr &=k_aI_a+k_d(I/r^2)max(0,n\cdot l)+k_s(I/r^2)max(0,n\cdot h)^p \end{align} $$

• Specular Highlights，高光，光滑
  • 接近镜面反射，所以取决于视线方向
  • 这里通过半程向量和法线的接近程度来描述
    • 半程向量（Half Vector）$h=bisector(v,l)=\frac{v+l}{\Vert v+l\Vert}$
• Diffuse Reflection，漫反射，粗糙
  • 散色到各个方向，各个方向都能看到
  • 光的强度和夹角有关：不同光线夹角，单位着色点得到的光强度不同
• Ambient Lighting，环境光
  • 没有环境光的情况下就当成常量

点光源

根据高斯定理或者格林公式可得不同时刻光子到达的包络面能量和来自于最内部的能量散发

• 这个内部可以是一个单位光强包络面，每个点强度为 1

越往外单位能量变少，因为总面积和曲线边长了，和距离的平方成反比关系
公式：$I_{Outside}=\frac{I_{Inside}}{r^2}$

漫反射

所以点光源的漫反射公式为：$L_d=k_d\left(I/r^2\right)max(0,n\cdot l)$

• $k_d$ 为漫反射系数（Diffuse Coefficient）表示物体吸收能量的能力，如果法线和光方向相乘小于 0 则夹角大于 90 度，那么光强为 0（因为考虑的是反射）。
• 可以观察到漫反射和视线向量无关
• l 由着色点方向减去 光源方向得到

镜面反射

使用半程向量公式：

$$ \begin{align} L_s&=k_s(I/r^2)max(0,\cos{\alpha})^p \cr &=k_s(I/r^2)max(0,n\cdot h)^p \end{align} $$

$k_s$ 为镜面反射系数，指数 p 是为了把曲线变窄，控制高光范围，正常高光只在小的区域有

使用反射向量 R 则是 Phong 模型

环境光

环境光强由物体环境光系数 $k_a$ 以及环境光强 $I_a$ 决定（这只是一个近似，常量，只有 2D 的效果）
公式：$L_a=k_aI_a$

着色频率（Shading Frequencies）

定义着色要应用在哪些点上面，随着着色点变多，渲染出来的效果就越精细

对应以下三种着色类型：

• Flat shading：只考虑三角形的法线
• Gouraud Shading：从各个三角形顶点之间插值
• Phong Shading：要先对三角形的法线向量进行插值，然后得到每个像素的法线向量

对应如下的着色频率：

• 表面
• 顶点
• 像素

在着色频率之下，增加顶点数量，能够让物体更平滑

• 复杂的顶点物体用简单的着色频率也能得到很好的效果，因为三角形面的频率以及接近像素了
• 如果三角形数量超过像素，那么用像素会更快

顶点法线定义

因为顶点不构成面，如何确定一个顶点的法线？

• 根据相邻平面的法线平均得到
  • 如果附近三角形平面大小不同，进行加权平均更精准

像素法线定义

从顶点的法线插值而来，需要归一化

拓展：

• 如何插值：重心坐标插值

图形（实时渲染）管线

输入：

• 三维模型
• 光照条件

输入根据以上的过程得到渲染的结果，中间的过程被定义为图形管线，流程：

• 根据三维空间点得到顶点在屏幕空间的位置
• 这些顶点进行连线成为三角形
  • 有顶点形成三角形的联系（分开了图形和顶点的变换处理）
    • 顶点变换后，根据顶点的三角关系再连成线
• 光栅化图形，离散化为片段
• 片段处理
  • 深度测试/可见性判断
  • 然后进行片段的着色
• 帧缓冲操作
• 最后进行显示
  
  这些图形管线的硬件实现则是 GPU，其中 GPU 有实现常用的图形接口（OpenGl，DirectX），可以对渲染管线进行操作

着色（shader）

重要：着色主要是位于顶点处理和片段处理中，是现代可编程管线中的内容

• 如果是顶点着色频率就在顶点处理器中
• 如果是像素着色则是在片段处理器中

着色程序

根据渲染管线，着色程序是位于顶点和片段处理阶段

语言类型：

• GLSL：OpenGL
• HLSL：DirectX
  着色器类型：
• 顶点着色器
• 片段/像素着色器
• 高级着色器
  • 几何着色器：动态生成三角形
  • 计算着色器：通用计算着色器， GP GPU

每一个顶点和像素都会运行一次（弄清楚着色器中的变量就能理解其作用）
着色程序中有不变的全局变量，也有每次都会变化的变量（比如对于不同顶点不同的坐标等）

根据这些输入值进行计算，然后对于一开始规定好的输出全局变量进行赋值（如果顶点的位置输出，像素颜色输出），即完成了一次着色操作

Ref：

• Shader 在线网站

三角形内部插值

• 平滑过渡
• 三角形内部纹理插值（坐标，颜色，法线）

重心坐标插值 (Barycentric Interpolation)

三角形的坐标系统（重心坐标）：使用三个顶点作为基， $(\alpha,\beta,\gamma)$ 作为坐标表示三角形内部任意一点
公式：

• 限制条件是坐标和为 1（所以只要两个值就能求出）
• 保证在三角形内部（坐标都必须非负）
• 重心坐标其实是顶点对于重心形成的三角形的面积比例
  • 重心和顶点连线就能形成三个三角形

通过重心坐标去线性组合三角形各顶点的属性（颜色，纹理坐标，法线）得到内部点插值后的属性

问题：

• 投影下，三角形重心坐标会变化
  • 所以要在投影之前做插值，逆变换回去做完插值再回来

实践：

• 在判断三角形内外用计算机浮点精度不准，应该用向量判断一边来做

纹理太大

问题更严重，需要抗锯齿

• 远处产生摩尔纹（上采样，一个像素覆盖更多纹理区域）
  • 1：包含信息多，信号频率高，所以需要更高的采样频率
  • 2：避免采样（不用点查询，用平均范围查询）：要能查询任意不同大小（纹理覆盖范围不同）
    • （可进阶）Mipmap：快速，近似，正方形查询
      • 纹理分层，卷积得到更小的纹理分辨率图，每次减少一半，log2 * 原纹理大小 = 层数
      • 可以提前计算，把纹理进行分层
        • 因为是一直缩小，所以存储量不会多很多
      • 正方形分块计算（复制三分递归放进正方形第四块）增加量增加量是原本的三分之一
    • 得到区域范围：通过附近邻居像素点在 uv 空间的距离（竖直和水平各一个，取距离最大的那个长度）找到像素的范围查询区域（正方形）
      • 
    • 通过判断范围区域的大小来使用 Mipmap 的层级
      • 如果是 1x1 说明像素和纹素基本一对一，以此类推
      • 对于层级的连续化，做两个层级的三线性插值得到
        • 先在各层的做双线性插值得到两个结果
        • 然后再进行一次线性插值
    • 问题：Overblur，远处会被模糊了，如果是非方的区域就容易模糊
      • 
      • Anisotropic Filtering（各相异性过滤）
        • 
        • MipMap 分割时长宽比是一致的，都是正方形；
        • 这里加入长和宽单独做分割，只拉伸一部分，这样就多出了不均匀的矩形的缩放情况，考虑了方向性
        • 可以解决长方形的情况
        • 常见的多少 x 就是多少层的压缩
        • 代价是增加显存的消耗，增加三倍
      • （拓展）EWA Filtering，更完善的形状考虑
• 近处产生锯齿（下采样，一个像素覆盖不了一个纹理）
  因为采样过于间断，失去了连续性，所以要增加采样点（超采样）

纹理映射

图形不只是有简单的颜色属性，还包含了图片纹理以及表面系数（漫反射系数等）

纹理：定义图形上每个点的属性参数，着色是就可以使用
方法：

• 由美工设计得到
• 参数化：能够展开为平面

通过定义三维空间到物体表面的坐标映射，完成使用二维的空间去定义物体表面每个点的属性参数

纹理采样/查询：

• 根据重心坐标能得出三角形内部点的坐标，然后再转换为纹理坐标去采样纹理属性（如颜色等）

纹理坐标：

• UV 坐标，0~1 之内，有一定的方法定义了三维空间到 UV 空间的映射
• 三角形的每个顶点都在 UV 坐标上能找到，那么就能通过 UV 纹理空间坐标所带的信息得到三角形的信息，至于三角形内部则使用插值（重心坐标）得到
• （拓展）tiled 纹理：能够重复拼接且无缝衔接，有相关算法

纹理太小

纹理分辨率过于小，texel（纹素）
需要对纹理进行一次平滑/插值，抗锯齿

• Nearest（最近采样）会出现多 pixel 对应一个 texel
• 可以用 Bilinear,Bicubic 等做插值
  • Bilinear（双线性插值）：
    • 找纹理坐标附近四个点形成一个小坐标系有坐标 s，t（0~1 之间）
    • 
    • 对任意一个坐标做双线性插值（Lerp）操作
    • 有水平和竖直的插值（因为有四个点的纹理值）
      • 第一次是/左右两个边上的插值，插值参数为 s
      • 第二次是两个插值的结果再做一次插值得到最终结果，插值参数为 t
    • 
  • （拓展）Bicubic：取周围的 16 个点进行多次插值

环境纹理

环境纹理：把不同的环境光颜色纪录在漫反射纹理上，就能表示出镜面的感觉

• 球形图：边缘处会扭曲，参考世界地图
• 立方图：曲面往外接包围正方体做射线映射，这样立方体上就能存各个方向的环境图

纹理应用

（可拓展）

• 凹凸/法线贴图：在表面用这个纹理的高度或者法线计算着色
  • 并不是真的改变了几何形状，不好计算阴影
  • 通过切线计算法线
• 位移贴图：真实改变了几何顶点位置
• （可拓展）噪声函数
• 预计算阴影，可以在美术设计阶段把阴影设计好，这样能够减少计算，的到更好的效果
• 体渲染：密度等内容作为纹理属性

几何

如何表示几何图形

隐式

• 不容易看出
• 容易验证是否在图形上

类型：

• 几何方程/代数表面
  • 如果计算特殊点，需要解方程
  • 不容易看出是什么图形
• CSG：
  • 通过基本几何进行布尔运算的到最终图形
• 距离函数（可拓展理解）
  • 说明到某个几何位置的距离，去描述几何形状
  • 定义空间任意一点的距离值
  • 做 Blend 比较方便
• 水平集方法（离散表示的距离函数）
  • 不容易用解析形式的距离函数
  • 用一个二维网格表示
  • 参考等高线
• （拓展）分形：
  • 图形频率很高，容易走样

显式

• 解析几何方程
• 容易计算出任意一点
• 判断是否在几何上很麻烦

类型：

• 多边形网格
  • obj 格式
• 纹理映射（$\mathbb{R}^2\rightarrow \mathbb{R}^3$）
  • 和方程的区别是，纹理空间是一个有限区域，可以遍历完刚刚好的到一个几何
• 贝塞尔曲线
• 贝塞尔曲面

贝塞尔曲线

可以用递归方式求出各阶的差值，阶数为线段数，控制点数加 1。

相当于对每两个控制点做 Lerp，这样会形成一个类似于杨辉三角的关系，所以最后的代数公式是二项式展开式一样的形式

公式：$b^n(t)=b^n_0(t)=\sum\limits_{j=0}^nb_jB_j^n(t)$
$b_j$ 为各个控制点向量，$B_j^n$ 为伯恩斯坦（Bernstein）多项式
$B_j^n=\left(\begin{align}&n\cr&i\end{align}\right)t^i(1-t)^{n-i}$

性质

• 曲线一定在控制点的凸包（橡皮筋 - 钉子）内
• 对于仿射变换后控制点形成的贝塞尔曲线和原本的是同态/同构的
• 可分段（piecewise）：
  • 通过各阶导数的一致保证到几阶的连续性

（可拓展）样条（Spline）

• 用一些控制点定义的
• B-Spline
• NURBS（非均匀有理）

（可拓展）贝塞尔曲面

• 通过两个时间/参数 u v 去定义二维的曲线变化，先在一个方向上找到控制点对于一个时间的公式，再 找到另一个方向的即可
  • 类似二次极限

网格操作

• 网格细分（Subdivision），上采样
• 网格简化（Simplification），下采样
• 网格正则（Regularization），改进三角形质量

细分

分为两步

• 第一步先拆分出多个三角形，此时形状为发生变化
• 第二步通过拆分的三角形更新形状

Loop Subdivision

拆分：

• 每个三角形取中点，拆分为四个新的三角形
• 需要区分新老定点

一般情况

新点更新：

• 公式：$3/8*(A+B)+1/8*(C+D)$
• 找到一个共享边的老三角形，一定会有一个新点（改变点）在共享边上
  • 共享边上旧点分别为 A、B
  • 另外两个旧点为 C、D
• 共享边新点根据公式进行移动（加权平均）

（可拓展）旧点更新：

• 先找由六个三角形构成的六边形（外边顶点为 $Q_i$），他们共享的中心旧点（P）做改变点
  • 公式：$(1-n*u)P+u\sum{Q_i}$
  • n  为度数，u 是一个数（定义：n==3 ? 3/16 : 3/(8n) 和度数有关)

Catmull-Clark Subdivision（General Mesh）

（可拓展，暂不学习理论）

• 一般网格，不一定是三角形

简化

边坍缩（Collapsing An Edge）

• Quadric Error Metrics（二次误差度量）
• 使用 L2 Distance
• 去除不那么重要的边
• 使去除后误差最小
  • 还要让受影响的边变化形成的误差也最小
  • 堆结构
  • 贪心算法

阴影

阴影映射（Shadow Mapping）：

• 阴影点的意思看成，光线不能看到这个点，而视线能看到
  • 把光源当成相机（点光源），找到光源能看到的视线内容，记录深度（深度值在不同相机都是一致？）
  • 如果视线的到的深度不一致，就说明是否有被遮挡
  • 浮点精度问题：判断距离相等
• 不需要了解场景几何的信息

阴影边界

• 硬阴影：只有本影（umbra）
• 软阴影：考虑到半阴影的情况（penumbra）