Graphs
变换
MVP变换
-
模型变换(Model):通过平移(Translate)、旋转(Rotate)和缩放(Scale)矩阵将物体摆放到场景中;
Translate Matrix :
Scale Matrix :
Rotate Matrix:
- x轴旋转:
- y轴旋转:
- z轴旋转:
罗德里格旋转公式:
-
视点变换(View) : 首先定义一个相机,有Position(相机位置)符号为e,Look-at direction(相机视野朝向)符号为g和判断相机的倾向角度的Up dirction(向上方向)符号记为t
视点变换需要将相机位置摆放到坐标系原点,之后相机朝向-Z轴,相机的向上方向指向Y轴,此时需要两个步骤:- 将摄像机位置平移至原点,矩阵如下:
- 将g(相机朝向方向)旋转到-Z轴方向,t(向上方向)旋转的Y轴方向,旋转到x轴方向。矩阵如下:
最后矩阵相乘得到
-
投影变换(Projection)
投影变换将三维物体映射到二维屏幕,有正交投影和透视投影,其中透视投影更接近人肉眼所见
- 正交投影 前面变换中相机在原点, 相机面朝-Z轴方向,去掉Z坐标轴,将物体平移缩放到内矩阵如下
- 透视投影
光栅化
将物体画在屏幕上
视口变换
视口变换将剪裁空间映射到屏幕空间。在图形学中,抽象的认为屏幕是一个二维数组,数组中每一个元素为一个像素(pixel),而这个数组的大小就是“分辨率”。
- 像素(Pixel) 先暂时将像素理解为屏幕上显示的最小单元,是一个内部颜色唯一的方块;像素的颜色可以由RGB三个值表示。
- 屏幕空间
图中蓝色像素坐标的位置为,像素都是以的形式表示的,其中x,y 都是整数;像素坐标的范围为到,像素的范围从到;蓝色像素的中心为,像素的中心在;屏幕的覆盖范围到。

- 视口变换 忽略z轴坐标;将原本的平面变换到;视口变换矩阵为
光栅化
将屏幕空间映射到像素
-
三角形(Triangles)

-
为什么会是三角形? 三角形是最基础的多边形,所有的多边形都可以拆成三角形。三角形具有独特的性质,1. 除非拆成两个三角形,否则永远是一个平面;2. 三角形内外明确;3. 在三角形顶点处插值的方法明确(重心插值)
-
采样(Sampling) 在一个函数上求不同位置上的对应值,这个过程称为采样;采样是一个将函数离散化的过程;
c++for (int x = 0; x < xmax; x += 1) { output[x] = f(x); }采样是图形学中的一个核心概念。
-
inside函数 光栅化就是对一个二维函数进行采样的过程;一个点是否在三角形内可以靠叉乘判断;
如果这个点在三角形的边界,要么不进行处理,要么进行特殊处理,这在图形API中由严格规定。
定义一个二元函数:inside(tri, x, y);
c++for (int x = 0; x < xmax; x += 1){ for (int y = 0; y < ymax; y += 1){ image[x][y] = inside(tri, x + 0.5, y + 0.5); } }
-
包围盒优化 AABB包围盒是对于沿着斜对角放置的瘦长型形优化效果并不好;

-
-
采样 采样在图形学中非常常见,光栅化就是采样二维屏幕上的点;摄影就是采样感光元件上的信息;视频是在时间时钟采样。 采样会出现失真现象比如:锯齿,由于 采样率对于信号来说不够高,造成了信号的走样也就形成了锯齿;
摩尔纹,左边跳过奇数行和奇数列得到右图;
车轮效应,对高速旋转物体采样可能出现视觉上的倒转现象。
反走样(抗锯齿)
反走样主要技术
物体遮挡
-
画家算法 Painter’s Algorithm 先绘制较远物体,再绘制较近物体覆盖先前位置上的物体。
这个算法在一定程度上可行,有相互遮挡关系是无法正确解决问题。
-
深度测试
-
原理 在相机视角看向场景,存储每个距离相机最近的像素的深度信息。
每个像素最后输出的颜色存储到帧缓冲中,深度信息存储为深度缓冲。

-
深度缓冲算法

-
Shader
Blinn-Phong模型
通过计算物体表面的高光(Specular highlights),漫反射(Diffuse reflection), 环境光(Ambient lighting)确定物体着色点的颜色 着色点是一个平面,在此平面定义观察方向(Viewer direction)、法线方向(Surface normal)、光照方向(Light direction)、和物体表面参数
着色频率
纹理
纹理贴图
- 纹理贴图实现: 3d模型文件(.obj)中存有纹理坐标用于纹理映射。通过将纹理贴图通过纹理坐标,计算给每个像素点的纹理颜色,再将该像素点的颜色信息进行phong shading计算。
- 纹理映射问题: 变换后分辨率太小—> 使用双线性插值 变换后分辨率太大—> 使用mipmap结构
几何
有些图形适合隐式实现,有些则适合使用显示实现
隐式几何
隐式几何 —> 代数曲面、水平集、分形几何
- 代数曲面,使用数学公式表述,但是不够直观
- CSG(Constructive Solid Geometry 构造实体几何)通过基本几何的基本运算定义新的几何 belike:


- 距离函数几何,使用距离函数做融和,空间的点到想到的形体的最小距离


- 水平集,得到融合的距离函数,通过这个距离函数为0来确定物体表面。
- 分形几何,自相似的,常用于描述自然现象但是极难控制形状。

显示几何
- 多边形面(Explicit Surface)
- 点云(Point Cloud)
贝塞尔曲线
平滑曲线的数学描述方式,通过一系列控制点定义一条曲线。
Example: 定义三个控制点,取区间内任意值t,根据t值插值出两点,连接两点再次根据t插值出一点,这个点就是整个贝塞尔曲线在t时间上的一点,在范围不断进行插值,最终得到的点即为贝塞尔曲线
几何处理
-
曲面细分
-
loop细分:loop细分只应用于由三角形构成的物体之上。loop细分具体步骤1. 计算三角形各个边中点。三角形被分为了四个。
步骤2.根据新旧顶点计算更新后顶点位置。新顶点的位置计算公式为
老顶点的位置计算公式为 其中n为当前顶点的度,u是n决定的权重系数,so,这个权重如何取值呢?????
loop细分的结果如图:
-
catmull-clark细分:适应于四边形和非四边形的物体细分。其中度不等于4的顶点称为奇异点,图中的奇异点数量为2。
细分时,将面上的中点和边上的中点连接,细分结束后引入了两个度为3的奇异点。之前的两个非四边形面消失了,也就是说一次catmull_clark细分后会将非四边形转换为四边形,每转换一个非四边形就多引入了一个新奇异点。之后继续细分奇异点数量不变。
具体计算:
-
-
曲面简化 有时我们反而用不到过于复杂精细的模型,或者受限于设备性能。此时我们需要对模型的网格进行简化。如图30000个顶点和3000个顶点其实表现没有太大差别,而且如果从远距离看过去两个模型几乎没有差别。

- Edge Collapse(边坍缩):边坍缩是一种网格的简化方法。找到一条边,将它的两个顶点捏成一个顶点,边消掉。哪么具体要坍缩哪些边呢?这个问题可以通过其中一种方法Quadirc Error Metrics(二次度量误差)解决,二次误差度量用于估算简化操作的代价,其中二次误差可以用“简化后的点与原表面相应局部的距离的平方”作为误差值。
假设每个顶点坍缩的二次误差值,依此坍缩二次误差最小的顶点。坍缩一个顶点后会改变其余顶点的位置,导致需要重新计算其他顶点的二次误差,所以每次坍缩一个顶点后,更新受到此次坍缩影响的顶点的二次误差。此时优先队列或堆是改算法最契合的数据结构。
通过局部的最优解,推出全局的最优解,所以此算法属于贪心算法。
边坍缩后的模型belike:

- Edge Collapse(边坍缩):边坍缩是一种网格的简化方法。找到一条边,将它的两个顶点捏成一个顶点,边消掉。哪么具体要坍缩哪些边呢?这个问题可以通过其中一种方法Quadirc Error Metrics(二次度量误差)解决,二次误差度量用于估算简化操作的代价,其中二次误差可以用“简化后的点与原表面相应局部的距离的平方”作为误差值。
光线追踪
阴影
此前的着色解决不了阴影问题,在光栅化着色中实现阴影的方法是使用Shadow Mapping。Shadow Mapping本质是一种图像空间的做法,在生成阴影这一步不需要知道场景的几何信息,该方法会出现走样现象,经典的shadow mapping只能处理点光源的情况。原理是相机可以看到这个点,光源也可以看到这个点,固这个点不在阴影中。
shadow mapping的具体做法(目前只考虑点光源): 从点光源位置看向场景,生成一幅图,但不着色,只记录深度。再从摄像机位置看向场景,把从摄像机看见的点投影到光源视角。比较两个深度值,如果深度值相等,这个点可以被光线照射到,如果深度值不想动,那么该点不能被光线照射到。
- 硬阴影 硬阴影有锐利边缘,非0既1;
- 软阴影
光线追踪
光栅化最大的问题是不好表示全局的效果(global effect)比如Soft shadows(软阴影)、Glossy reflection、Indirect illumination。 
-
光线定义
- 光线沿直线传播。
- 光线和光线不会发生碰撞。
- 光线从光源出发最终反射到眼睛。(根据光的可逆性,实现光线追踪也就从相机视角出发,所谓光线追踪就是从光的终点也就是人眼或相机开始)
-
Example
假设眼睛是一个摄像机,先不考虑实际相机处理,镜头等。从眼镜开始,穿过成像平面上的像素向场景抽射eye ray,记录与场景最近的交点,这一步解决了深度测试的问题?

接着从交点向光源连线,判断该点是否被光源照亮,如果该连线中间没有物体阻挡,则说明该点可以被光源照亮。再根据法线、出射光、入射光这些数据,带入着色模型计算该点的着色,写入该像素。

-
Whitted-Style风格光线追踪(递归)
前面的光线追踪只考虑了光线值反射一次,实际光线是会弹射多次的。

假设场景中圆形为玻璃球,光线从眼镜出发穿过一个像素,光线接触物体表面会发生折射(Refraction)和反射(Reflection)。在Whitted-Style风格光线追踪中,光线进行多次弹射,每个弹射点都去计算着色值,在最后将所有的值加到该像素中。

-
光线和物体表面的交点 光线在数学上就是一条射线,由起点(Origin)和方向(Direcion)确定。光线上的任意一点可以由一个以为自变量的函数来表示。
-
光线和隐式表面求交点 光线与隐式表面相交,则交点p既满足射线方程,又满足表示隐式表面的函数。 如光线和球体表面相交,
公式为

-
光线和显示表面求交点 对于显示表面,问题变为光线如何与三角形相交。 最简单的做法就是遍历整个三角形,计算光线与三角形所在平面的交点,最后判断交点是否在三角形内。 计算光线与三角形所在平面相交的方法:一个平面由它的法向量和平面内一点定义。只有射线交点在平面内时,平面内点与交点线段与法线垂直,故推出一下公式: Ray equation: Plane equation: Solve :

-
mt算法 一种求交点更快的方法,能够更快的求出光线与三角形所在平面交点的重心坐标,并通过重心坐标判断光线是否在三角形内。

-
-
包围盒 遍历所有三角形求交的方式速度上非常之慢,所以使用一种将复杂物体包裹进简单形状内,以达到加速光线与表面求交的方法叫做“包围盒”。

-
轴对齐包围 盒包围盒是三组对面组成的交集,而轴对称包围盒的每个轴都沿着坐标轴,简称为(AABB)。

-
光线与轴对齐包围盒求交点 对于二维示例(三维包围盒同理,取用二维示例方便理解),分别记录光线进入平面和离开平面的时间、和光线进入平面和离开平面的时间、。所以光线在这个两组对面形成的矩形内的位置为前两段的交集。
Key ideas:1. 光线只有进入所有对面时,才算是进入这个盒子。2. 只要光线离开任意一个对面,就算离开这个盒子。
因此对于三维包围盒,当,我们就能知道光线在包围盒内传播了一段时间。
考虑到光线是一条射线而不是一条直线。
如果,则包围盒在光线后面,所以没有交点。
如果 and ,则光线在包围盒内,所以有交点。
总结: 且 ,光线对于包围盒有交点 为什么会选择轴对齐包围盒(Axis-Aligned)?因为平面沿轴放置的情况下求的时候只需要某一个轴的信息,而不用整个坐标,计算量更小。

- 轴对齐包围盒加速光线追踪
-
均匀空间划分
在做光线追踪之前,先对场景进行预处理,1. 找到场景的包围盒;2. 在场景里划分格子;3. 标记与物体相交的各自。
在光线追踪过程中,只需要判断光线是否和含有物体表面的格子相交,如果没有的话跳过,有的话和其中的物体求交点。
不同格子数的加速效果是不同的,不能太疏也不能太密,经过实际应用#cells = C * #objs,其中在三维中时的加速效果最好。
这种使用格子划分的方法在大量均匀分布的物体的场景是比较有效的。比如:
但是,此方法在物体分布不均匀的、有大量空旷场景中表现不好,导致出现“体育场找水壶”问题。比如:
-
空间划分(Spatial Partitions)
空间划分结构: Oct-Tree,KD-Tree,BSP-Tree()
八叉树将空间分为八份(如果是四维空间则为四份),对于每个子节点再次切割一次,一次类推。指定停止规则时一般规定划分到有多少格子内为空或有足够少的问题时停止。八叉树太复杂一般不会使用。
KD树空间划分的复杂程度和维度没有关系,KD树和八叉树的划分方式几乎完全相同,只不过它每次沿着某个轴切开,并且只砍一下。空间就被划分成了类似二叉树的结果,每次节点划分都有两个子节点,划分时为了均匀,xyz轴依此划分。
BSP树是一种对空间二分的划分方法,它每次选一个方向切开,它不是横平竖直划分的,而且位数越多计算越复杂。

-
KD树 之前三种空间划分方法中KD树是被广泛使用的结构。 预处理之后所有物体分布在叶子节点上
适合KD树的数据结构该如何设计,区分中间节点和叶子节点:1. 中间节点存储沿哪一个轴划分、划分平面的位置、两个子节点的指针;2. 叶子节点存储物体。 KD树遍历

当然KD树也暴露了一些问题:1. 给出一个包围盒很难判定它和哪些三角形有交集;2. 一个物体和很多包围盒都有交集的情况下会存在多个叶子节点。
-
基于物体划分BVH BVH不同于空间划分,采用物体划分空间。从物体划分可以避免空间划分的一些问题。比如它不涉及三角形和包围盒求交,避免了一个物体存在于多个叶子节点内。 BVH的预处理流程: 1. 找到场景的包围盒;
2. 递归地将对象集拆分为两个子集;3. 重新计算子集的边界
4. 根据一定条件停止划分(分到每个子集中不多于五个三角形);5. 每个叶子节点存储物体
如何划分节点:1.选择一个维度进行划分->总是选择节点中最长的轴;2. 取中间物体(第n / 2个三角形,可以使用快速选择算法)
那么BVH适合什么数据结构?1. 由中间节点存储包围盒、叶子节点的指针;2. 由叶子节点存储包围盒、物体。
辐射度量学
辐射度量学表示如何表述光照,它定义了一系列的方法和一系列的单位;它能给我门光各种各样不同的属性。 New terms: 【Radiant flux】, 【intensity】, 【irradiance,】 【radiance】 Radiant flux: Radiant Energy -> 辐射能,是单位时间的能量;flux -> 单位时间内通过传感器的光子的数量。 Radiant intensity: 光源发出的每单位立体角的能量; 什么是立体角?
irradiance: radiance: