计算机图形学笔记整理（部分）

xiaozongpeng

目录
第 1 章 引言        3
一、什么是计算机图形学？        3
二、计算机图形学包括哪些领域？        3
三、计算机图形学的应用方向有哪些？        3
第 2 章 数学知识&线性代数        5
一、向量之间点乘和叉乘的计算公式？        5
二、如何求两个向量之间的夹角？        5
三、怎样判断一个点是否在三角形内？（同五2、3）        5
四、向量点乘的几何意义？        6
五、向量叉乘的几何意义？        6
补充一、向量叉乘的性质        7
补充二、矩阵形式的向量乘法        8
第 6 章 矩阵变换 & 第 7 章 观察        9
一、矩阵变换的基本形式：        9
二、哪些是线性变换？        11
三、哪些是仿射变换？        12
四、什么是齐次坐标系，有何作用？        12
五、用齐次坐标系表示点和方向的区别：        14
六、变换是怎么样组合（分解）的（旋转和平移顺序的影响）：        15
七、什么是模型视图变换？        16
八、什么是投影变换？        17
九、正交投影和透视投影的区别？        21
十、什么是视口变换？        22
十一、定义cuboid和视椎体（frustum）需要那些参数？        23
十二、对三维空间中的物体可视化需要依次经过哪些矩阵变换？        23
第 3 章 光栅算法        25
一、什么是光栅化？        25
二、bresenham算法        27
三、三角形光栅化算法（逐点检测是否在三角形内、扫描线法、重心坐标法）的伪代码描述。        28
四、什么是走样？走样的原因是什么？        30
五、缓解走样有哪些方法？（Reduce Aliasing Error）选择一种简要说明其原理、过程和优缺点（MSAA）        30
六、先平滑再采样，为什么能够缓解走样现象？        33
第 8 章 隐藏面消除        34
一、什么是画家算法？该方法在实践中存在哪些问题？        34
二、可见性判断/遮挡关系的处理方法有哪些？        34
三、深度缓冲的算法原理？（伪代码）        36
四、三角形内部点的深度如何计算？        36
第 9 章 表面明暗处理        37
一、Blinn-Phong 反射模型的基本原理？        37
二、Blinn-Phong 反射模型中漫反射/高光/环境光的计算方法和公式？        38
三、什么是着色频率？有哪几种着色频率？        41
四、逐像素着色一定比逐顶点着色好吗？为什么？        43
补充一、不同着色频率当中法向量的获取        44
补充二：图形学实时渲染管线(Realtime pipeline)&Shader        44
第 11 章 纹理映射        46
一、什么是纹理坐标？光栅化过程中，三角形内部的纹理坐标如何计算？        46
二、纹理图像的分辨率太低会产生什么问题？有什么解决方法？        48
三、纹理图像太大（分辨率高）会产生什么问题？有什么解决方法？        48
四、最近邻/双线性插值/双三次插值：        49
五、Mipmap 技术的基本原理和过程？        50
补充一、纹理的应用        54
第 15 章 曲线        57
一、什么是几何建模的显式表示/隐式表示？        57
二、什么是贝塞尔曲线？分段贝塞尔曲线？        61
三、贝塞尔曲线的构造算法（伪代码）        63
四、贝塞尔曲线有什么特点？        65
五、贝塞尔曲面如何构造？        65
六、Loop 细分方法的原理和流程？        66
七、Catmull-Clark 细分方法的原理和流程？        67
八、网格化简的目的是什么？简述一种网格化简方法的原理        68
补充一、在图形学中如何表示用三角形面形成的物体？（obj文件）        70
补充二、面片操作（网格细分、化简、规则化）        71

第 1 章 引言

一、什么是计算机图形学？

虎书P1；
计算机图形学是一种使用数学算法将二维或三维图形转化为计算机显示器的栅格形式的科学。简单地说，计算机图形学的主要研究内容就是研究如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法。

二、计算机图形学包括哪些领域？

虎书P1；

三、计算机图形学的应用方向有哪些？

虎书P1；
计算机图形学的应用领域有以下几个：
1、计算机辅助设计与制造(例如：CAD/CAM)
这是计算机图形学最广泛、最重要的应用领域。它使工程设计的方法发生了巨大的改变，利用交互式计算机图形生成技术进行土建工程、机械结构和产品的设计正在迅速取代绘图板加工字尺的传统手工设计方法，担负起繁重的日常出图任务以及总体方案的优化和细节设计工作。
2、计算机辅助教学(例如：CAI)
在这个领域中，图形是一个重要的表达手段，它可以使教学过程形象、直观、生动，激发学生的学习兴趣，极大地提高了教学效果。随着微机的不断普及，计算机辅助教学系统已深入到家庭。
3、计算机动画（例如：flash、Premiere）
通过计算机制作动画，只需生成几幅被称作“关键帧”的画面，然后由计算机对两幅关键帧进行插值生成若干“中间帧”，连续播放时两个关键帧被有机地结合起来。这样可以大大节省时间，提高动画制作的效率。
4、管理和办公自动化
计算机图形学在管理和办公自动化领域中应用最多的是绘制各种图形，所有这些图形均以简明形式呈现出数据的模型和趋势，加快了决策的制定和执行。
5、国土信息和自然资源显示与绘制
国土信息和自然资源系统记录全国的大地和重力测量数据、高山和平原地形、河流和湖泊水系、道路桥梁、城镇乡村、农田林地植被、国界和地区界以及地名等。利用这些存储的信息不仅可以绘制平面地图，而且可以生成三维地形地貌图，为高层次的国土整治预测和决策、综合治理和资源开发研究提供科学依据。
6、科学计算可视化领域
科学计算可视化是利用计算机图形学方法将科学计算的中间或最后结果以及通过测量得到的数据以图形形式直观地表示出来。科学计算可视化广泛应用于气象、地震、天体物理、分子生物学、医学等诸多领域。
7、计算机游戏方面
计算机游戏目前已成为促进计算机图形学研究特别是图形硬件发展的一大动力源泉。计算机图形学为计算机游戏开发提供了技术支持，如三维引擎的创建。建模和渲染这两大图形学主要问题在游戏开发中的地位十分重要。
8、虚拟现实领域
虚拟现实技术的应用非常广泛，可以应用于军事、医学、教育和娱乐等领域，通过带上具有立体感觉的眼睛、头盔或数据手套，通过视觉、听觉、嗅觉、触觉以及形体或手势，整个融进计算机所创造的虚拟氛围中，从而取得身临其境的体验。
第 2 章 数学知识&线性代数

一、向量之间点乘和叉乘的计算公式？

虎书P17，P18
二、如何求两个向量之间的夹角？

虎书P17
三、怎样判断一个点是否在三角形内？（同五2、3）



利用向量叉乘：
1、原理：若点O在三角形内部，则沿着三角形的边逆时针走，点O一定保持在边的左侧。如图示，点在逆时针行走时，在AB，BC，CA的左侧：
2、如何判断点在一个边的左侧呢？
可以借助向量叉乘来判断O是否在向量AB的哪一侧。通过计算向量AO与向量AB的叉乘的值为正，则表示O在AB的左侧，反之为右侧。
3、顺时针转换为逆时针：
上图中如果依次输入的是A,C,B的坐标（顺时针），怎么解决呢？假设依次输入的点分别是p1,p2,p3.我们判断若p3在p1p2的右侧，则表示输入的点的顺序是顺时针的，即A,C,B式的输入，将p2,p3调换位置即可保证顺序是逆时针。


四、向量点乘的几何意义？

虎书P17；
几何意义：
1、向量点乘的几何意义是向量的点乘可以用来计算两个向量之间的夹角，进一步判断这两个向量是否正交或垂直等方向关系；
2、同时，还可以用来计算一个向量在另一个向量方向上的投影长度，在数学中，向量也称为矢量，指具有大小和方向的量，它可以形象化地表示为带箭头的线段；
3、Decompose a Vector向量分解（根据投影）；
4、Determine Forward / Backward：两个向量点乘结果>0，则两个向量同向；两个向量点乘结果<0，则两个向量反向；
5、Measure How Close Two Directions：若两个向量越近，则点乘结果越接近于1，直到两个向量完全平行，此时点乘结果为1；若两个向量越远，则点乘结果越接近于0，直到两个向量完全相反，此时点乘结果为-1；当两个向量垂直时，点乘结果为0；

五、向量叉乘的几何意义？

虎书P18
几何意义：
1、叉积的长度|a×b|可以解释成这两个叉乘向量a，b共起点时，所构成平行四边形的面积。据此有：混合积[abc]=（a×b）·c，可以得到以a，b，c为棱的平行六面体的体积。
2、Determine left / right：（同三，判断向量a和向量b的位置关系）：
用向量a叉乘向量b，即a×b，若得到的结果为正（说明叉乘的结果向量（z）向外，如果用右手系去判断，则b在a的左侧；若得到的结果为负（说明叉乘的结果向量（z）向内，则a在b的左侧；同理，还可以用向量b叉乘向量a，即b×a，若得到的结果为正，则b在a的右侧，若得到的结果为负，则a在b的右侧。
3、Determine inside / outside：（同三）
判断点P在三角形ABC内部，默认组成三角形的三个点是逆时针方向排列，首先用向量AB与向量AP叉乘，若结果为正，说明向量AP（点p）在向量AB的左侧，然后用向量BC与向量BP叉乘，若结果为正，说明向量BP（点p）在向量BC的左侧，最后用向量CA与向量CP叉乘，若结果为正，说明向量CP（点p）在向量CA的左侧，若以上三个式子都成立，则说明点p在AB、BC、CA的左侧，则点p在三角形ABC内。
4、Orthonormal Bases / Coordinate Frames（坐标正交基/坐标轴框架）：


用向量叉乘可以定义一些相互垂直的轴，这些轴就会形成一个坐标系。
上式中定义了u、v、w三个单位向量，且相互点乘都为0（即互相垂直），w即可通过u×v得到（右手系）。这样定义的好处是可以把任意一个向量分解到三个轴上。

补充一、向量叉乘的性质

叉乘的性质：
1、Cross product is orthogonal to two initial vectors （外积正交于两个初始向量）
2、Direction determined by right-hand rule （通过右手定则判断叉乘结果向量的方向）
3、Useful in constructing coordinate systems （在构建空间坐标系的时候很有用）
4、一些公式：







补充二、矩阵形式的向量乘法



第 6 章 矩阵变换 & 第 7 章 观察

一、矩阵变换的基本形式：

1、缩放与镜像：
虎书P93，P101




用齐次坐标系后：




2、错切/切变：
虎书P94，P101


3、旋转：
虎书P95,P101


用齐次坐标系后：


绕x、y、z轴旋转：


欧拉角：


绕任意轴旋转：（Rodrigues’ Rotation Formula）


4、平移：
虎书：P104
(1)仿射变换（线性变换+平移）：


齐次坐标形式：


(2)纯平移（齐次坐标）(2D&3D)：




5、逆变换：
逆变换在数学运算中即为逆矩阵

二、哪些是线性变换？

缩放、错切、旋转、镜像/反射；






三、哪些是仿射变换？

(1)平移、缩放、错切、旋转、镜像/反射；


(2)仿射变换=线性变换+平移：




(3)仿射变换的矩阵表示：



四、什么是齐次坐标系，有何作用？

虎书P104
1.定义：
齐次坐标就是将一个原本是n维的向量用一个n+1维向量来表示，是指一个用于投影几何里的坐标系统，如同用于欧氏几何里的笛卡儿坐标一般。
2.应用背景：
在欧氏几何空间，两条平行线不能相交；然而，在透视几何空间里面，两条平行线可以相交。欧氏空间描述正投影非常适合，但是这种方法却不适合处理透视空间的问题。例如：2维笛卡尔坐标（x,y），当该点在无穷远处时，这个点的坐标将是(∞,∞)，在欧氏空间，这变得没有意义；平行线在透视空间的无穷远处交于一点，但是在正投影却不能，于是数学家发明了齐次坐标来解决这个问题。
3.齐次坐标：
(1)从欧式几何坐标点转换成透视几何齐次坐标时：
（x，y）→（x，y，w）
(2)注意：
投影平面上的任何点都可以表示成一三元组 (x, y, w)，称之为该点的齐次坐标或投影坐标，其中 x、y 及 w 不全为 0;
Ⅰ.当w 不为 0，则该点表示欧氏平面上的 (x/w, y/w)；
Ⅱ.当w 为 0，则表示无穷远点/向量；
(3)从透视几何齐次坐标转换成欧式几何坐标点
（x，y，w）->（x/w，y/w）
注意：
Ⅰ.以齐次坐标表表示的点，若该坐标内的数值全乘上一相同非零实数，仍会表示该点；
Ⅱ.相反地，两个齐次坐标表示同一点，当且仅当其中一个齐次坐标可由另一个齐次坐标乘上一相同非零常数得取得；
Ⅲ.三元组 (0, 0, 0)不表示任何点。原点表示为 (0, 0, 1)；
4.齐次坐标的应用：
4.1用来区分向量和点
(1)从普通坐标转换成齐次坐标时
如果(x,y,z)是个点，则变为(x,y,z,1);
如果(x,y,z)是个向量，则变为(x,y,z,0)
(2)从齐次坐标转换成普通坐标时
如果是(x,y,z,1)，则知道它是个点，变成(x,y,z);
如果是(x,y,z,0)，则知道它是个向量，仍然变成(x,y,z)
4.2易于进行仿射几何变换：
引入齐次坐标的目的主要是合并矩阵运算中的乘法和加法。齐次坐标的作用，把各种变换都统一了起来，即把缩放，旋转，平移等变换都统一起来，都表示成一连串的矩阵相乘的形式。保证了形式上的线性一致性。
5、仿射变换：



五、用齐次坐标系表示点和方向的区别：

虎书P104
1、为什么要区分点和向量？


2、区别：
(1)从普通坐标转换成齐次坐标时
如果(x,y,z)是个点，则变为(x,y,z,1);
如果(x,y,z)是个向量，则变为(x,y,z,0)
(2)从齐次坐标转换成普通坐标时
如果是(x,y,z,1)，则知道它是个点，变成(x,y,z);
如果是(x,y,z,0)，则知道它是个向量，仍然变成(x,y,z)
3、向量具有平移不变性（“0”）

六、变换是怎么样组合（分解）的（旋转和平移顺序的影响）：

虎书P97、P98
1、为什么先缩放，再旋转，最后平移（先线性变换，后平移）？
矩阵乘法不满足交换律！
变换一般出现在物体从一个坐标系向另一个坐标系转换的过程，坐标系转换就是变换的目的。比如在个人坐标系向世界坐标系转换的过程，首先要明白缩放、旋转和平移都是针对个体而言，在世界坐标系下进行的。此时物体的个人坐标系和世界坐标系重合；
如果先旋转后缩放，那么旋转后的个人坐标轴就不再与世界坐标轴重合，那么利用原先定义的缩放方向在此时进行缩放就会出错。比如原先定义的沿x轴缩放2倍，那么此时进行缩放2倍的物体部位就不再是我们想要缩放的物体部位（被旋转走了）了；
如果先平移，那么接下来的旋转和缩放就不再以原点为中心进行变换了，这不是我们想要的效果，我们想要的是原点进行缩放和旋转。
2、向量组合：
(1)在一个组合变换中，虽然矩阵乘法不满足交换律，但是依然满足结合律；
(2)矩阵乘法是从右向左相乘的；
(3)无论经历了多少次变换，总能把所有变换计算出来写成一个总的变换矩阵，优化性能；
(4)复杂变换可由简单变换得到，变换的顺序很重要；
3、分解复杂的变换：



七、什么是模型视图变换？

虎书P112
1、前言：模型视图变换主要是为了让摄像机回归到世界坐标的原点并且和拍摄物体一起进行变换，便于计算。模型视图变换的根据就是物体和相机的相对位置不变，那么，投影得到的图片也是不变的。


2、目的：为了投影变换
3、首先定义相机：拍摄方向朝向g，相机的位置位于e，相机的正上方可以用向量t来表示：


4、将相机移动到世界坐标的原点的过程如下图：Transform objects together with the camera物体和相机的相对位置不变；
平移矩阵就可以写成：


然后分别需要将e变换到坐标原点（0,0,0），g旋转到-Z，将t旋转到Y，将g叉积t的方向旋转到X，然而，这个旋转对应的旋转矩阵并不容易写出，但是如果将Z旋转到-g，将Y旋转到t，将X旋转到g叉积t的方向，这个逆向的旋转矩阵就可以写成：


之所以可以这样写，是因为旋转矩阵是正交矩阵，其列向量或列向量可以构成一组正交基向量，而t, -g以及g与t的叉积可以构成一组正交基，所以直接将g与t的叉积方向、t方向与-g方向的三个向量填入旋转矩阵，并且这三个向量可以表示旋转后的向量。于是就有了逆向旋转矩阵。
因为旋转矩阵是正交矩阵，所以逆矩阵也是矩阵的转置，就可以得到原来的旋转矩阵。


所以，模型视图变换矩阵最终的结果就是：



八、什么是投影变换？

虎书P111、P114
1、投影变换：
在计算机图形学中，投影变换分为正交投影和透视投影，目的就是把场景世界中的3D物体转换为2D平面图形的过程，转换后降了一维，相对于前面的绘图装置，线末端固定点的可以认为是观察者的视点或者摄像机的位置。依据这个目的，我们的目标本质上就是已知物体表面的点坐标(x,y,z)计算出投影的某个固定面的2D坐标(x',y',1)，可以根据三角形的比例关系轻松的计算出x'=x/z,y'=y/z.
2、正交投影：
(1)正交投影坐标的相对位置都不会改变，所有光线都是平行传播，只需将物体（可视部分）全部转换到一个[l,r]*[b,t]*[f,n]大小的[-1,1]3的空间（标准立方体）之中即可。对于正交投影，最简单的理解方式就是将所有三维空间的物体挤压到一个二维的平面，也就是将所有物体的z坐标直接去掉，也就实现了从三维到二维平面的映射。
(2)步骤1：Translate (center to origin) first先通过一个位移矩阵将长方体中心移动到原点；


(3)步骤2：then scale (length/width/height to 2)再通过一个缩放矩阵将长方体压缩成一个立方体：


(4)注意：沿着-Z看，近处和远处就不直观了（n>f），这也是为什么OpenGL（一个图形API）使用左手系坐标的原因。
3、透视投影：
(1)透视投影的目的就是将上面的棱台转换为一个立方体（cuboid），转换后，棱台的前剪裁平面的右上角点变为立方体的前平面的中心（下图中弧线所示）。由图可知，这个变换的过程是将棱台较小的部分放大，较大的部分缩小，以形成最终的立方体。这就是投影变换会产生近大远小的效果的原因。变换后的x坐标范围是[-1, 1]，y坐标范围是[-1, 1]，z坐标范围是[0, 1]（OpenGL略有不同，z值范围是[-1, 1]）。
(2)特点：
在计算机图形学、艺术、视觉系统中最为常见；远小近大；平行线不平行，最终收敛于单点；




(3)步骤1：First “squish” the frustum(视锥体) into a cuboid(长方体) (n->n,f->f) ()


相似三角形关系：,



所以：

而且：近平面上的任何点都不会改变；任何点在远平面上的z都不会改变；




所以：

(4)步骤2：Do orthographic projection()

九、正交投影和透视投影的区别？

虎书P111、P114
Ⅰ.正交投影变换用一个长方体来取景，并把场景投影到这个长方体的前面。这个投影不会有透视收缩效果（远些的物体在图像平面上要小一些），因为它保证平行线在变换后仍然保持平行，也就使得物体之间的相对距离在变换后保持不变。简单的说， 正交投影变换忽略物体远近时的大小缩放变化，将物体以原比例投影到截面（如显示屏幕）上，实现这样效果的照相机叫做正交投影照相机，也称正交照相机。
Ⅱ.透视投影变换跟正交投影一样，也是把一个空间体（指的是以投影中心为顶点的透视四棱锥）投影到一个二维图像平面上。然而，它却有透视收缩效果：远些的物体在图像平面上的投影比近处相同大小的物体的投影要小一些。跟正交投影不同的是，透视投影并不保持距离和角度的相对大小不变，所以平行线的投影并不一定是平行的了。换言之，透视投影变换能够实现一个物体在玩家近距离比较大，远距离比较小，那么实现这样的效果的照相机就叫做远景照相机。远景照相机常用来开发3D游戏，它的工作原理是根据照相机和物体之间的距离缩放投影的比例（也就是截面的大小）。透视投影跟人的眼睛或相机镜头产生三维世界的图像的原理还是很接近的。
Ⅲ.两种投影法的本质区别在于透视投影的投影中心到投影面之间的距离是有限的，而平行投影的投影中心到投影面之间的距离是无限的。
Ⅳ.透视投影的步骤中包含正交投影；
十、什么是视口变换？

虎书P109
1、屏幕定义：
①An array of pixels （像素组成的数组）
②Size of the array: resolution （数组的大小:分辨率）
③A typical kind of raster display （一种典型的光栅显示）
2、像素定义：
一个像素是一个具有统一颜色的小正方形；一个像素是由红绿蓝三种颜色混合而成。
3、视口变换：主是将视景体内投影的物体显示到二维的视口平面上. 在计算机图形学中,它的定义是将经过几何变换, 投影变换和裁剪变换后的物体显示于屏幕指定区域内。
4、步骤：
①与z无关
②把标准立方体转换到屏幕空间：[-1,1]2 to [0,width]*[0,height]


③公式：

若y轴向下：

十一、定义cuboid和视椎体（frustum）需要那些参数？

1、cuboid参数：top、bottom、left、right、near、far
2、视锥体是一个三维体，他的位置和摄像机相关，视锥体的形状决定了模型如何从camera space投影到屏幕上。最常见的投影类型-透视投影，使得离摄像机近的物体投影后较大，而离摄像机较远的物体投影后较小。透视投影使用棱锥作为视锥体，摄像机位于棱锥的椎顶。该棱锥被前后两个平面截断，形成一个棱台，叫做View Frustum，只有位于Frustum内部的模型才是可见的。

3、通常我们通过两个量来定义这个视锥：


①垂直可视角度（field-of-view，FovY）：如上图中红色虚线，摄像机到近平面上下中点所连成的线的夹角，即为垂直可视角度。
②宽高比（ aspect ratio）：width/height。


4、如何将刚刚定义的垂直可视角度（fovY）和宽高比（aspect）转化为已经定义好的 l, r, b, t？我们从侧面去看这个视锥，假设最右边垂直的线是近平面，那么到摄像机的距离就是|n|，这时我们可以根据三角函数得出：宽高比即为左右的宽度与上下的高度的比值：

十二、对三维空间中的物体可视化需要依次经过哪些矩阵变换？

模型视图变换→投影变换→视口变换；
(1)模型变换(modeling tranformation)：这一步的目的是将虚拟世界中或者更具体点，游戏场景中的物体调整至他们应该在的位置
(2)摄像机变换(camera tranformation)：在游戏中我们真正在乎的是摄像机(或者说眼睛)所看到的东西，也就是需要得到物体与摄像机的相对位置
(3)投影变换(projection tranformation)：根据摄像机变换得到了所有可视范围内的物体对于摄像机的相对位置坐标(x,y,z)之后，便是根据是平行投影还是透视投影，将三维空间投影至标准二维平面([-1,1]^2)之上 （tips：这里的z并没有丢掉，为了之后的遮挡关系检测）
(4)视口变换(viewport transformation)：将处于标准平面映射到屏幕分辨率范围之内，即[-1,1]2→[0,width]*[0,height], 其中width和height指屏幕分辨率大小
第 3 章 光栅算法

一、什么是光栅化？

虎书P35


1、定义屏幕空间：
我们定义每一个像素位置都以该像素左下角的点的坐标来表示，定义屏幕左下角的点（原点）坐标为（0,0），那么上图中蓝色像素的坐标应为（2,1）。如果整个屏幕的分辨率是width×height，那么整个屏幕中的像素位置从（0,0）到（width-1, height-1）。虽然我们用整数的坐标来描述坐标的位置，但是每个像素实际中心准确来讲在（x+0.5，y+0.5）上。一个像素会覆盖1的宽度，整个屏幕覆盖的像素应该从（0,0）到（width, height）
2、光栅设备：
①电视：一条条画水平的线，当线足够密集的时候，就覆盖了整个屏幕。由于人眼有视觉暂留现象，而画面的切换速度又很快，因此为了让成像更快一点，可以隔一行画一条线，比如在当前时刻，只画奇数行的线，在下一时刻（或者下一张图）的时候，只画偶数行的线。这种技术就被称为隔行扫描技术。隔行扫描现在在一些视频压缩技术里依然存在。但是当画面高速运动的时候，隔行扫描可能会造成画面撕裂。
②Frame buffer帧缓冲器：显示的图像就是内存中的一块区域；
③LCD：液晶通过自己的不同排布影响光的极化（光的偏振方向），通过液晶的扭曲，将光的振动方向渐渐调整过来；
3、三角形的特点：
三角形是最常用的建模模型。
(1)Most basic polygon （三角形是最基本的多边形）
(2)Break up other polygons （其他多边形都可以分解为三角形）
(3)Unique properties （三角形有其独特的属性）
(4)Guaranteed to be planar （确保是平面，三点确定一个唯一的平面）
(5)Well-defined interior （三角形的内部外部定义的非常清楚）
(6)Well-defined method for interpolating values at vertices over triangle (barycentric interpolation) （定义良好的三角形顶点插值方法(重心插值)，定义了三角形三个顶点的属性，其内部任意一个点都可以根据三个顶点的属性而定义出来）
4、光栅化（Rasterization）：绘制到光栅显示。
光栅化是把顶点数据转换为片元的过程，具有将图转化为一个个栅格组成的图象的作用，特点是每个元素对应帧缓冲区中的一像素。
光栅化是将一个图元转变为一个二维图像的过程。二维图像上每个点都包含了颜色、深度和纹理数据。将该点和相关信息叫做一个片元（fragment）。光栅化的目的，是找出一个几何单元（比如三角形）所覆盖的像素。粗略地讲：模型的顶点在经过各种矩阵变换后也仅仅是顶点。而由顶点构成的三角形要在屏幕上显示出来，除了需要三个顶点的信息以外，还需要确定构成这个三角形的所有像素的信息。光栅化就是干这个的：光栅化会根据三角形顶点的位置，来确定需要多少个像素点才能构成这个三角形，以及每个像素点都应该得到哪些信息，比如uv坐标该是什么...等。这是通过对顶点数据进行插值来完成的。
光栅化是将几何数据经过一系列变换后最终转换为像素，从而呈现在显示设备上的过程，光栅化的本质是坐标变换、几何离散化。在Unity3D中，每一个美术模型由顶点和顶点构成的三角面来确定。将3D模型绘制到屏幕上时，根据每个三角面的三个顶点，将这个三角面所覆盖的每一个像素(栅格)进行填充的过程，就叫做光栅化。其实，三维物体绘制到屏幕上的过程大多都是采用的这种光栅化方式。
总结：光栅化，就是将几何信息转换成一个个的栅格组成的图像的过程。
5、实现光栅化的方法（采样sample，函数离散化）：
1、最简单的方法就是通过采样来实现光栅化。什么是采样？通俗的解释是，给你一个函数，在不同的地方（x），我去问：这个函数的值（y）是多少。采样即为把一个函数离散化的过程。
2、采样=重复频率内容
3、采样是图形的核心思想，应用在各个领域、各个维度。如time (1D), area (2D), direction (2D), volume (3D)
4、采样函数（1D）：


（2D）


如果一个像素中心在形体内，则进行采样。通过遍历整个屏幕空间中的所有像素，来判断哪些像素的中心点在如三角形的内部。我们可以利用三个叉乘来判断一个点是否在三角形的内部。如果一个点在两个三角形的边界上，只要自己定义一个标准可以说通就好。
5、其中遍历所涉及的范围的方法：
①bounding box；②lncremental Triangle Traversal增量三角形遍历




二、bresenham算法














三、三角形光栅化算法（逐点检测是否在三角形内、扫描线法、重心坐标法）的伪代码描述。

逐点检测是否在三角形内：
1、use a Bounding box or Incremental triangle traversal；
2、叉乘判断是否在三角形内
扫描线填充算法：
1. 按三角形的y坐标对三角形的顶点进行排序;
2. 同时栅格化三角形的左右两边;
3. 在左右边界点之间绘制水平线段。
重心坐标法：
1、use a bounding box；
2、迭代给定三角形边界框的所有像素，对于每个像素，计算其重心坐标（三角形所在平面上任意一个点（x，y）都可以用三个顶点A、B、C坐标的线性组合来表示，线性组合的系数α、β、γ之和等于1。如果系数都为非负数，则表示这个点在三角形内部；如果知道被某点（x，y）与三个顶点连接将这个三角形划分成三个小三角形各自的面积，那么也可以求出系数α、β、γ），如果它至少有一个负分量，则像素位于三角形之外。
3、重心坐标的计算：


①三角形所在平面上任意一个点（x，y）都可以用三个顶点A、B、C坐标的线性组合来表示，线性组合的系数α、β、γ之和等于1。如果系数都为非负数，则表示这个点在三角形内部。（实际上只有两个基）
②顶点处：


③α、β、γ计算:




如果知道被某点（x，y）与三个顶点连接将这个三角形划分成三个小三角形各自的面积，那么也可以求出系数α、β、γ。
④质心坐标：


四、什么是走样？走样的原因是什么？

虎书P46
1、走样=频率内容混合，混叠错误
2、走样的原因：因为对函数（信号）的采样频率不足，或者说信号的变化速率远大于采样的频率。
3、简单来说，在图形学中无法呈现所设想的效果，即称为走样。在计算机渲染中，由于绘制的图形在数学上是连续的，而渲染的像素点是离散的，从而导致在光栅化的三角形遍历阶段，将图形打散为像素时，会不可避免的产生锯齿（Jaggies），这种现象不可避免，只能减轻。主要通过硬件（像素点数量加倍）和软件（各种算法，如超级采样算法等）来减轻走样。
4、走样主要有：
①锯齿（Jaggies，对空间进行采样）；
②摩尔纹（Moire，对图像进行采样，采样时跳过了图像中的奇数行和奇数列，例如手机拍电视）；
③转轮效应（一块转轮上产生视觉上的不同转速，对时间进行采样）。

五、缓解走样有哪些方法？（Reduce Aliasing Error）选择一种简要说明其原理、过程和优缺点（MSAA）

1、提高采样率：
本质上是增加傅里叶域中复制体之间的距离；更高分辨率的显示器、传感器、帧缓冲器。但是：成本高，可能需要非常高的分辨率
2、反走样（Antialiasing）：


在重复（repeating）之前使傅里叶内容 "更窄"。即在采样前过滤掉高频。（限制，然后重复）
①先平滑再采样（先把一个信号的高频信息抹除再采样）


②计算平均像素值实现反走样：
对于任何一个像素，被三角形覆盖的情况只有三种：1.完全被覆盖 2. 完全不被覆盖 3.部分被覆盖；
③超级采样反走样方法(Super-Sampled Anti-Aliasing ,SSAA)：
通过以更高的分辨率来采样图形，然后再显示在低分辨率的设备上，从而减少失真的方法。例如下面的图形表示了增加分辨率后，绘制直线的差别。通过将高分辨率的图像，显示在低分辨率的设备上，确实能有效减轻走样现象，但是存在的弊端就是，要为这些多出来的像素，进行更多的计算，以及内存开销很大。这是一种比较传统的方法。


超级采样抗锯齿（Super Sampling Anti-Aliasing）的原理是把当前分辨率成倍提高,然后再把画缩放到当前的显示器上。这样的做法实际上就是在显示尺寸不变的情况提高分辨率，让单个像素变得极小，这样就能够大幅减轻画面的锯齿感了。不过是由于对整个显示画面的放大，因此它消耗的显示资源也是非常大的。
④多重采样反走样方法(Multi-Sampled Anti-Aliasing, MSAA)：
按照上面的那种求每个像素中的区域百分比十分困难，所以就有了MSAA这种反走样的方法，其思想也是如上面的那种方法，但是取的是一个近似的求区域像素平均值的方法。具体的做法如下：


Ⅰ.将一个像素划分为 N*N个小像素，每一个小像素都有一个像素中心，然后可以对这个小像素进行采样，判断这些小像素在不在三角形内，然后将最后的结果平均起来，就能够求的三角形对一个像素的区域的近似的覆盖。
Ⅱ.假如把一个像素分为四个小像素，


在像素内部多加一些采样点；
Ⅲ.然后每个点都可以判断是否在三角形内，如果四个点都在三角形内就是100%覆盖，如果只有三个点在三角形内，则三角形对这个像素就是75%覆盖。于是就可以得出每个像素的覆盖结果；
注意：MSAA通过更多的样本，来近似的进行反走样的第一步：模糊，这个过程之后就相当于每一个像素内部都已经知道了三角形的覆盖率，求了平均之后是什么，就会得到上图的结果。MSAA不是增加分辨率，而是检测三角形覆盖。
MSAA的过程：
Ⅰ.将每个像素划分为多个小像素
Ⅱ.判断每个小像素的中心是否在三角形内部，从而得到三角形在该像素的覆盖率
Ⅲ.得到覆盖率之后对这个像素的像素值进行平均，得到上图的结果
Ⅳ.然后采样
注意： MSAA并不是通过提高采样率而完成的，对更多的点进行采样是为了得到三角形在一个像素上的覆盖比率而已。
MSAA原理：
原理是寻找出物体边缘部分的像素，然后再把画缩放到当前的显示器上。
MSAA优点：
不过MSAA是寻找出物体边缘部分的像素，然后对它们进行缩放处理。由于只是物体的外层像素进行缩放处理，忽略掉了不会产生锯齿的内部像素，所以显卡不会像处理SSAA（超级采样抗锯齿）那样需要庞大的计算量，因此MSAA比起SSAA来更有效。
MSAA的缺陷：
MSAA提高了计算的量，将一个像素划分为多个区域，就要对每个区域进行多次计算，最后就提高了计算的成本。
⑤其他反走样方法：FXAA (Fast Approximate AA)、TAA (Temporal AA)等
六、先平滑再采样，为什么能够缓解走样现象？

先filter后sample：在采样之前，先用滤波器（虚线框）抹除掉高频率的信息，也就是通过滤波器先做一个模糊操作，砍掉高频，减少了频谱复制的面积。可见，这样采样后就不会发生走样（混叠错误）的现象了。
先sample后filter：因为采样之后，信号已经产生了堆叠，模糊（卷积取均值）后仍然是堆叠的。

第 8 章 隐藏面消除

一、什么是画家算法？该方法在实践中存在哪些问题？

虎书P121
1、“画家算法”表示头脑简单的画家首先绘制距离较远的场景，然后用绘制距离较近的场景覆盖较远的部分。画家算法首先将场景中的多边形根据深度进行排序，然后按照顺序进行描绘。这种方法通常会将不可见的部分覆盖，这样就可以解决可见性问题。


2、画家算法无法处理相互重叠的多边形在有些场合下，画家算法可能无法解决可见性问题。在这个例子中，多边形 A、B、C 互相重叠，我们无法确定哪一个多边形在上面，哪一个在下面，我们也无法确定两个多边形什么时候在三维空间中交叉。在这种情况下必须用一些方法对这些多边形进行切分、排序。1972年提出的Newell算法就是切分类似多边形的一种方法，在计算几何领域人们已经提出了许许多多的解决方法。会有不可解的深度顺序：
3、一些基本的画家算法实现方法也可能效率很低，因为这将使得系统将可见多边形集合中的每个点都进行渲染，而没有考虑这些多边形在最终场景中可能被其它部分遮挡。这也就是说，对于细致的场景来说，画家算法可能会过度地消耗计算机资源。
4、时间复杂度：对于n个三角形来说，O(nlogn)；

二、可见性判断/遮挡关系的处理方法有哪些？

概述：
由于投影变换失去了深度信息，往往导致图形的二义性。要消除二义性，就必须在绘制时消除被遮挡的不可见的线或面，习惯上称作消除隐藏线和隐藏面(或可见线判定、可见面判定)，或简称为消隐。经过消隐得到的投影图称为物体的真实感图形。

两种基本算法：
1、以构成图像的每一个像素为处理单元，对场景中的所有表面，确定相对于观察点是可见的表面，用该表面的颜色填充该像素.适于面消隐。
算法步骤：
a.在和投影点到像素连线相交的表面中，找到离观察点最近的表面；
b.用该表面上交点处的颜色填充该像素；
2、以三维场景中的物体对象为处理单元，在所有对象之间进行比较，除去完全不可见的物体和物体上不可见的部分.适于面消隐也适于线消隐。
算法步骤：
a.判定场景中的所有可见表面；
b.用可见表面的颜色填充相应的像素以构成图形；
提醒注意:
1.假定构成物体的面不能相互贯穿，也不能有循环遮挡的情况。
2.假定投影平面是oxy平面，投影方向为z轴的负方向。
如果构成物体的面不满足该假定，可以把它们剖分成互不贯穿和不循环遮挡的情况。

可见面判断的有效技术：
Z缓冲器算法：
算法描述：z缓冲器算法是最简单的隐藏面消除算法之一。
基本思想：需要一个额外的深度值的缓冲区深度缓冲区(z-buffer)存储深度，存储每个样本(像素)的当前最小z值，假设z为正，初始时设为无穷大，z越小越靠近。帧缓冲器每个单元存放对应像素的颜色值；z缓冲器每个单元存放对应像素的深度值;
算法实现：时间复杂度：n个三角形O(n)，在GPU实现；
优缺点：
z-Buffer算法没有利用图形的相关性和连续性，这是z-Buffer算法的严重缺陷，更为严重的是，该算法是像素级上的消隐算法。
三、深度缓冲的算法原理？（伪代码）

1.首先分配一个数组buffer，数组的大小为像素的个数，数据中的每个数据都表示深度，初始深度值为无穷大
2. 随后遍历每个三角形上的每个像素点[x,y]，如果该像素点的深度值z<zbuffer[x,y]中的值，则更新zbuffer[x,y]值为该点深度值z，并更新该像素点[x,y]的颜色为该三角形上像素点上的颜色。
3、伪代码：



四、三角形内部点的深度如何计算？

重心坐标插值（？）

光栅化：
1、根据透视变换后的三角形三个顶点求出bounding box，简化计算
2、对bounding box的每个像素进行遍历，先进行插值的系数计算，求出z值，进行z-buffer计算
3、对于需要绘制的像素点，利用上一步计算的插值系数，分别插值出颜色、法向量、UV坐标值、没有经过透视变换的真实3D坐标，初始化结构体fragment_shader_payload。
4、把fragment_shader_payload的数据传进shader里，即可求出该点的颜色。
5、然后调用设置颜色的函数，渲染完成。
6、三维空间的属性在三维空间中插值
第 9 章 表面明暗处理

一、Blinn-Phong 反射模型的基本原理？

虎书P132
1、前言：在这一章中，实现光线与对象表面之间的相互作用。目的是在渲染流水线中增加着色功能，所以这里只讨论最基础的局部光照模型。与全局光照不同，在局部光照模型中，着色点的颜色值只取决于着色点表面的材质属性、表面的局部几何性质以及光源的位置与属性，而与场景中其他的表面无关。
2、渲染流程与场景定义：
因为不考虑全局光照，只考虑从光源发出的光线，具体来说只考虑光源和表面之间的一次单独的相互作用。所以这个问题可分解为两个独立的部分：
①定义场景中的光源（这里只介绍点光源）
②定义一个描述材质和光线之间相互作用的反射模型（phong与Blinn-Phong反射模型）。
首先从一个点光源发出的光线中，由于观察者只看到从光源出发后最终到达他眼睛的那些光线。也就是说可以分两种情况：
要么这条光线从光源出发后直接进入观察者的眼睛，这时候看到的就是光源的颜色。要么这条光线经过一条复杂的路线并且与场景中的对象发生多次相互作用（这里只考虑一次），之后进入观察者的眼睛，这时候看到的是光源与表面材质之间的相互作用。
3、Blinn-Phong 反射模型分为三个部分：specular highlights、diffuse reflection、ambient lighting；环境光：它的特点是使场景获得均匀的照明，是光线与场景对象的多次相互作用的结果。这里简单的设置为一个常数来模拟。漫反射光：它的特点是把入射光线向各个方向散射，而且向各个方向散射的光线的强度都相等，因此不同位置的观察者看到的反射光线都是一样的。镜面反射光：它的特点是看起来有光泽，因为被反射出去的大多数光线的方向都是和反射角的方向很接近。反射光线的方向服从入射角等于反射角这一规律；
4、Blinn-Phong 反射模型计算在一个特定的着色点（shading point，物体表面）向相机反射的光线；
5、定义的单位向量：
着色点的法线n；光照方向l；摄像机观测方向v；物体表面的一些参数
6、根据光的传播与能量守恒，光在传播过程中是会有衰减的。
7、着色和阴影是两个概念。着色时只考虑每个物体接收光源而被照亮了多少，不考虑模间的遮挡，也不考虑物体间因为遮挡而投射的阴影（阴影单独生成）。

二、Blinn-Phong 反射模型中漫反射/高光/环境光的计算方法和公式？

虎书P132
1、环境光Ambient lighting：
①不依赖任何因素
②添加恒定的颜色，以考虑到被忽略的光照和填充黑色的阴影（近似）
③
2、漫反射光diffuse reflection(Lambertian Shading)：
①当光线照射到一个点时，该光线会被均匀的反射到各个方向，这种反射称为漫反射。也就是说，在漫反射中，视角的位置是不重要的，因为反射是完全随机的，因此可以认为漫反射光在任何反射方向上的分布都是一样的（与v无关）；


②光线到达：


③光线衰减falloff：


④Lambertian Shading的结果与视线方向无关：


⑤Kd及其影响：


对于一个点来说会吸收一部分能量（颜色），那么剩下不吸收的能量被反射出来，我们就看到了这个点的颜色。不同的点有不同的吸收率，那么不同的点就产生了不同颜色。那么我们定义一个系数kd。如果kd=1，说明完全不吸收，所有光都被反射了，如果kd=0说明所有能量都被吸收了，没有能量反射出来，就是黑色。如果把这个数值表示成向量，表示一个有三通道的RGB颜色的值，每个通道都是从0到1，那么在一个点上就可以定义这个点上的颜色。
3、高光反射specular highlight：
①我们能看到高光的原因是镜面反射的方向和观察方向大致重合。也就是说当v和R足够接近的时候，就会看到高光。


②半程向量（h）：入射方向l和出射方向v的角平分线 （h的方向很好算，由于l和v都是单位向量，根据平行四边形法则，h=l+v，再将h归一化将长度变成1即可）
Ⅰ.为什么要引入半程向量？因为好算，而反射向量R不好算；
Ⅱ.v和R接近反应相当于就是n和h接近。
Ⅲ.如何衡量两个向量接近？还是利用点乘。
Ⅳ.通常来将认为高光是白色的，所以这里的镜面反射系数一般认为是白色。


③为什么max0,cos要引入一个指数？


上图我们可以看出，如果是cos，随着夹角变大，由1变到0非常缓慢，假设当n和h夹角在45°时，感觉上这两个向量夹角已经离得很远了，但是在夹角余弦中，仍然告诉我们有一个较大的值，此时高光就会非常大，但是实际上在n和h夹角这么大的时候高光没有这么大。于是我们引入指数，可以看到随着指数的增大，n和h夹角余弦的指数倍的值减小的会越来越快，也就达到了我们的目的。正常情况下指数会用到100~200这个范围。
④ks和p对其影响：


4、Blinn Phong反射模型：





三、什么是着色频率？有哪几种着色频率？

着色模型(频率）就是指把着色应用到那些点上面，就是如何运用（也可以不用）光照模型计算的结果显示由多边形表示的曲面。着色模型(频率）和光照模型是不同的概念，着色模型(频率）考虑的是面，着色模型(频率）会使用到光照模型的计算结果，当然也有不使用光照模型的情况，例如：固定着色（constant shading）。而光照模型指的是模型某一点如何与光交互的，是为了计算某一点最终颜色的。


着色频率分为：
1、flat shading（面片着色，逐面片）：
对于每一个四边形面进行一次着色，一个法向量，这个面上的像素都是同一个颜色；
逐面片着色指的是根据多边形上某个像素的光照情况对整个多边形着色。换句话说，假设多边形是由一种材质构成的。
缺点：对于平面组成的物体，这种方法是可行的;但是对于由曲面组成的物体，使用多边形近似，这种方法导致物体看起来是由多边形组成的。不适于平滑的表面；
2、Gouraud 着色（逐顶点）：
对于每一个平面的三个顶点，都计算它的法线然后对每一个顶点都做一次着色，而平面内部的点使用插值来确定颜色；
Gouraud 着色是分别计算三角形三个顶点的光照情况，然后通过重心坐标插值的方式来决定三角形内每一点的颜色。
缺点：对高光的插值不好，因为高光往往比较锐利，如果本该面上有高光，但是顶点处没有高光，那么插值后，这个面就没有高光。
优点：效果不错，计算量小
3、Phong 着色（逐像素）：
对于每一个三角形的平面求出一个法线然后把这些法线在三角形平面内部进行插值就得到了任何一个像素自己的法线方向，然后再进行着色；
phong着色只得是通过插值计算屏幕空间多边形每个点的法线，然后根据法线来执行光照计算。
优点：它对每个像素执行光照计算，真实感比gouraud着色强些，提高了镜面反射效果。
缺点：计算量比较大
4、顶点数/三角形面片数对三者的影响：



四、逐像素着色一定比逐顶点着色好吗？为什么？

不一定；
不同的着色方式会随着三角形面片的增加， Gouraud shading 也可以有很好的效果，而此时逐顶点开销更小。
每种着色方式各有利弊。上图中每一行的模型都是一样的，行与行之间的模型面数增加，几何形体本身定义的更加密集（光滑）。
我们可以看出，当几何的形体足够复杂（细分曲面的面数足够多）时，其实就可以用一些相对简单的着色模型，效果与利用复杂的着色模型的效果几乎没有差别。
因此，着色频率取决于面（或者顶线、像素）出现的频率。当这些因素出现的频率很高时，就不再需要用很高的着色频率去着色了。（着色频率越高计算量越大，所以需要跟面（或者顶线、像素）之间做一个权衡，两者结合达到一个合理的开销）
补充一、不同着色频率当中法向量的获取





虎书P134
1、逐顶点：
最好从底层几何得到顶点法线：例如，考虑一个球体；


否则必须从三角形面推断顶点法线简单的方案:平均周围的面的面积以获取法线：


2、逐像素：
重心坐标插值并将其单位化：

补充二：图形学实时渲染管线(Realtime pipeline)&Shader

1、Pipeline：


①Vertex Processing: Model, View,Projection transforms
②Rasterization: Sampling triangle coverage     ③Fragment Processing:Z-Buffer;




④Fragment Processing + Vertex Processing:
Blinn Phong;                                                    Texture Mapping：




⑤实现：GPU（单指令流，多数据流）
2、Shader：
①对顶点(vertex)和片段(fragment)进行程序处理的阶段
②描述对单个顶点(或片段)的操作

第 11 章 纹理映射

一、什么是纹理坐标？光栅化过程中，三角形内部的纹理坐标如何计算？

虎书P169
1、引入：假设有两个光源照到一个球上，这个球上面有不同的颜色，也就是说kd的值不同，我们希望能用一种方式，定义这个球上每一个顶点的属性。因此引入纹理映射。
2、任何一个三维物体的表面其实都是二维的，如对地球仪的拆解即可以解释这个现象。通过对二维纹理的拉伸、变换等一系列操作，将其能蒙到三维物体上，我们称这个过程即为纹理映射。纹理映射使物体表面任何一个点和纹理上一个点产生一一对应关系。三角形三个顶点，每个顶点都对应一个uv。
3、纹理映射（Texture Mapping）是将纹理空间中的纹理像素映射到屏幕空间中的像素的过程。
4、纹理坐标就是纹理与图形的映射关系，图形中每个顶点都会关联一个纹理坐标，表示顶点需要从该位置读取纹理图像的数据。纹理坐标实际上是一个二维数组，它的元素是一些颜色值。单个的颜色值被称为纹理元素或纹理像素。我们通常用（u，v）坐标来表示纹理上任意一个点，一般u和v的范围都从0到1.
5、纹理可以重复，也可以做到无缝衔接；
6、插值：
为什么插值？
确定顶点处的值；得到三角形内部平滑变化的值；
插值的对象？
纹理坐标、颜色、法向量等
怎样插值？
重心坐标插值；
7、三角形内部的纹理坐标如何计算？
当一个点的重心坐标（α，β，γ）求出来以后，就可以将任意属性V在此点的插值求出来，此时只需要将三个顶点的该属性和系数做乘法再相加，即


可求出在该点插值出来的属性。
但是要注意，重心坐标在投影过后会发生变化，这时候三角形已经投影到屏幕上了，尤其对于在三维空间中的属性（比如深度信息），应该找到像素中心点对应三角形的位置的三维空间坐标，然后在三维空间中将A、B、C的深度（属性）插值好，再放回来。这个过程需要做一次逆变换就可以了。
屏幕上任何一个采样点（像素中心）的位置，我们可以求出在这个位置上插值出来的uv（纹理坐标）的位置。
原来纹理坐标定义在三角形的顶点上，现在对于任何一个三角形内的点，我们都知道其在三角形中的位置，然后用重心坐标做一个插值，可以算出这一个点的uv。算出来这个点的uv以后，在纹理上查询一下这个uv的值，我们就知道对应纹理的颜色了，然后就可以拿来用了（比如用作漫反射的系数kd）。
三维空间的属性在三维空间中插值。


二、纹理图像的分辨率太低会产生什么问题？有什么解决方法？

问题：纹理放大（多个像素被映射到了一个texel上）
在高分辨率下（比如4k），如果纹理的分辨率比较低（比如256×256），那么在任意一个点上去查纹理，可能会查到一些非整数的值。纹理分辨率小了，就需要将其拉大。当查询纹理的时候，如果给了一个非整数的坐标，如何得到它的值？
解决方法：
最近邻插值：第一种方法是取就近的像素，四舍五入，比如0.4就认为是0,0.6就认为是1，如上图左侧Nearest。但是这个样子很难看。
双线性插值；
双三次插值；

三、纹理图像太大（分辨率高）会产生什么问题？有什么解决方法？

问题：一个pixel被映射到了多个texel上，会产生走样。当一张uv纹理的分辨率过大，大于屏幕像素的时候，就会出现这样的情况，近处锯齿远处摩尔纹。原因是近处一个像素覆盖的纹理区域相对较小，远处一个像素覆盖了很大一片纹理。屏幕上各个像素覆盖的纹理区域各不相同。如果一个像素覆盖的纹理区域较小，用这个像素的中心查询一下纹理的值，没有什么问题。但是一旦一个像素覆盖了很大一片区域的纹理（比如远处接近地平线的纹理），现在我还用一个像素的中心去查这块儿区域，用一个点的值去认为是这一个区域的值，那显然是不对的。用一个点的值无法代表一块纹理区域的颜色变化。


解决方法：
超采样去做，质量高，但是开销极大；当高度精简时，在像素范围内有许多 texels；一个像素中的信号频率太大；需要更高的采样频率；

如果不采样，只是去得到一个范围内的平均值呢？
1、点查询：以纹理为例，给你一个点，它的值是多少，可以用双线性插值来解决，这是点查询。
2、范围查询：给你任何一个区域，你立刻可以得到这个范围内的平均值，这是范围查询。（范围查询还有查询一个范围内最大值和最小值，这类问题跟现在所说的完全不一样）以实际的渲染图为例，近处的圆圈（右下方）一个像素覆盖的纹理区域较小，远处的圆圈（中上方）一个像素覆盖的纹理区域非常大。假设用同一个纹理，不同像素有不同的在纹理上覆盖的大小，所以范围查询应该能查询任意范围的大小。
3、Mipmap范围查询；

四、最近邻/双线性插值/双三次插值：

最近邻插值：第一种方法是取就近的像素，四舍五入，比如0.4就认为是0,0.6就认为是1，如上图左侧Nearest。但是这个样子很难看；
双线性插值：
红点并没有落在像素中心（非整数的值），我们想得到此时红点处的值。首先，找到这个红点临近的四个像素点的中心。这四个点总有一个左下角，可以找到这个红点离左下角的水平距离（s）和垂直距离（t）。s和t的值肯定都是在0到1之间的，因为两个像素之间的距离是1。首先我们定义一个操作：线性插值。如上图公式。定义v0是0，v1是1，那么x就是位于0到1上的值。当x=0时，lerp的值为v0=0，x=1时，lerp的值为v1=1，x=0.5时，lerp的值为0.5. 左下角和右下角可以用s做一次线性插值： 左下角u00有一个颜色，右下角u10有一个颜色，又知道u0离左边的距离是s，所以可以用s对这两个点进行一次线性插值。
左上角和右上角也可以用s做一次线性插值： 左上角u01有一个颜色，右上角u11有一个颜色，又知道u1离左边的距离是s，所以可以用s对这两个点进行一次线性插值。上一步已经通过插值得到了 u0和u1，但是最后我们想得到的是红点的值。那么我们再做一次竖直方向的插值即可。知道u0和u1，又知道红点离u0的距离t，所以可以用t对u0和u1做一次线性插值，即可得到红点的值。
整个过程做了两种插值：第一种插值是水平方向的点的插值，做了两个点（一对点），第二种插值是竖直方向的点的插值，做了一个点。这时红点的颜色就综合了u00, u10，u01, u11四个点，得到了一种平滑过渡的颜色。这个进行了两种插值的方法，就是双线性插值。（这里水平和竖直的先后顺序可以反过来）。


双三次插值：
这种操作取的是周围16个像素而非4个像素（非线性），虽然效果好但是同时带来的弊端就是开销会很大。

五、Mipmap 技术的基本原理和过程？

MipMap（mipmapping）多级渐远纹理技术，又被称为“纹理贴图金字塔”，多级渐远纹理技术原理：提前用滤波处理来得到很多更小的图像，形成一个图像金字塔，每一层都是对上一层降采样的结果。这样在实际运行时，就能快速得到结果像素。当物体原理摄像机时，可以直接使用较小的纹理（纹理质量稍差，模糊感较强），当物体靠近时适当替换较大纹理（纹理质量好，模糊感较少），以便给玩家呈现更精致的画面。
Mipmap的范围查询三个特点：快（查询速度非常快）、大约（是查询的近似值）、方形（查询区域仅可以是方形）
优点：当物体远离时，无需高精度纹理展示时，则替换低精度纹理，降低了显存带宽，减少了渲染。如果原图存储开销是1，因为每一层图分辨率都缩小一半，所以每一层的存储量都是上一层的四分之一。计算下来，总存储量开销是4/3，额外开销仅仅是1/3.
缺点：为了适配多场景（远近个不同的场景）提前生成八张精度不同的纹理，使用一定的空间用用于存储这些多级渐远纹理，通常会多占用33%的内存空间，典型的利用空间换取时间的办法。
概述：


Mipmap其实就是从一张图生成一系列图。如上图，原始图是第0层，每升高一层，图像的分辨率都缩小一半。如果原图存储开销是1，因为每一层图分辨率都缩小一半，所以每一层的存储量都是上一层的四分之一。计算下来，总存储量开销是4/3，额外开销仅仅是1/3.
过程：
①任何一个像素都可以映射到纹理上的一个区域，想算一个像素的覆盖面积，可以让该像素中心和其相邻像素中心分别映射到纹理上去，然后做一个近似。我们知道相邻两个像素中心的距离是1，那么对应到右边纹理上占有多远的距离L也就可以求出，这时我们就可以求出一个像素映射到纹理上占据多大的面积。
我们可以用如图所示的一个正方形框来近似这样一个不规则的区域。当我们把一个像素在纹理上覆盖区域近似成一个正方形时，如何根据我刚刚已经算好的Mipmap，去查询这样一个边长为L正方形的区域的平均值是多少？如果这个正方形区域就是1×1，那么就表明一个像素正好对应一个边长为L的正方形区域，也就可以直接在最原始（第0层，D=0）的纹理上找对应的像素，就是它的值。如果这个正方形区域是2×2，那么这个区域会在第1层（D=1）上对应一个像素。如果这个正方形区域是4×4，那么这个区域会在第2层（D=2）上对应一个像素。对于L×L大小的正方形，一定会在D=log2L层上对应到一个像素。因此我们只需要算出D，即在第几层正方形的区域对应一个像素，就可以得出这个区域内平均值是多少。






②但是会发现，两层之间有很明显的边界，那么在实际纹理映射的过程中可能会出现一些缝。在此处我们的解决方法是，先找D层，再找D+1层，这两层内部分别用双线性插值把对应的在这两层上的查询做出来，做出来之后把这两个双线性插值的值合到一起，然后在层与层之间再做一次插值。总共做了三步插值，在双线性插值上又加了一步插值，这就是三线性插值。这样我就可以在任意层，无论是整数层还是浮点数层（例如第1.8层，D=1.8）。可以看到，三线性插值处理后的层级可视化出来，就是一个很漂亮的连续渐变的层级了。
③在这里我们可以看到，如果假设用高开销的超采样得到的结果是相对准确的，那么用Mipmap得到的图，很明显在远处过于模糊，远处的所有细节全部糊掉。出现这个问题的原因就在于Mipmap只能查询一个正方形方块的范围。




解决方法：
Anisotropic Filtering（开销是原来的3倍）
各向异性：在不同的方向上表现各不相同（考虑方向性）
各向同性：各个方向上表现完全相同（如刚刚的正方形，水平竖直表现完全相同）
Mipmap操作的相当于是上图的对角线图片，每次长宽各缩小一半，而各向异性可以用不同的长宽比进行缩小（上图除了对角线以外的图片），也就是可以用矩形区域做范围查询（总共开销是原来的三倍）。反映到映射关系上即为上图。但是，对于一些斜着的图形，依然没有很好的方法去查询。
解决方法：EWA filtering；对于任何一个形状，都可以拆成很多不同的圆形去覆盖这个形状。如上图查询一个椭圆，将其拆成三个圆形，每次去查询一个圆形，多次查询自然就可以得到一个区域，但是代价是“多次查询”。可见质量越高的效果，性能开销越大。

补充一、纹理的应用

虎书P172
1、环境贴图，制造环境光，描述来自不同方向的光照信息，照亮整个环境中的物体，也可以被环境中的物体反射。环境光只记录光的方向，即假设环境光来自无限远处，从同一个方向照过来的光强度都是一样的。
①可以把整个环境光记录在球上，用球去存储环境光的信息。但是我们来看一个环境光球展开后的顶部和底部，可以发现出现了不同程度的变形。
②也可用一个立方体盒子，把这个球包围起来。当光从中心打到包围的球上时，我们不管，让光继续走，直到碰到立方体的一个面，记录下来信息。那么展开后的图像有六个面，就不存在刚刚球展开后产生的大面积扭曲了。
2、凹凸贴图/法线贴图、位移贴图（更现代化）：
贴图不光可以表示颜色信息，还可以表示高度信息和法线。高度贴图可以定义任意一个点，沿着他的法线向上向下走的相对高度。如右图，原本就是一个很普通的球，可以用很少的三角形来表示，如果想通过直接改变模型的方法得到右边那种凹凸不平的效果，会用很多三角形，开销会很大，那么在这里通过凹凸（高度）贴图，改变高度信息，高度信息变化，就会使法线信息变化，从而使着色结果发生变化（人们看到的明暗对比一定程度上就是因为法线变化），得到右图的效果。


如下图，假设黑色的线是原本一个比较光滑的面，在这里应用了一个凹凸贴图，凹凸贴图告诉我们一个相对高度如何变化，得到了黄色的线，那么原来点的位置会认为被凹凸贴图改变，那么法线也会改变。凹凸贴图改变相对高度，从而改变法线。


在不增加三角形的情况下增加表面细节，扰乱每个像素的表面法线(仅用于着色计算)。由纹理定义的每一个texel的 "高度偏移"。如何修改法线向量？
①原始表面法线n(p)=(0, 1)
②在p处的导数是dp = c * [h(p+1) - h(p)] 。
③被扰动的法线是 n(p) = (-dp, 1).normalized
在这里我们将复杂问题简单化，首先来看在一维上如何计算。
我们认为，某点p原来的法线n为(0, 1) ，我们要求出改变后的法线，首先就要求出切线，设切向量为（x，y）由于点p内存储着这一点的高度信息，因此会改变p点的高度，为h（p），利用微分的思想，我们再去找相邻像素点的位置，即p+1处，也有一个高度h（p+1），通过这两点的高度差，就可以算出切向量的y值，即为dp，x的值就是相邻两个像素的x，为1，因此切向量即为（1，dp），所以法向量就是（-dp，1），即法线为（-dp，1）。


所以将刚刚一维上一条线的思维推广到二维上uv平面内的操作，我们即可得出下面的公式。
①原始表面法线n(p) = (0, 0, 1)
②在p处的导数是：
dp/du = cl * [h(u+1) - h(u)]
dp/dv = c2 * [h(v+1) - h(v)]
③扰动的法线是n = (-dp/du, -dp/dv, 1).normalized()
请注意，这是在本地坐标中!
总结：复杂了纹理属性，但不改变任何几何信息，即不改变三角形数量；通过纹理（具有属性）→改变高度（相对属性）→改变法线→改变着色（height→normal→shading）
3、下面是Displacement Mapping，他与bump mapping运用了相同的纹理，但它挪动了顶点。
通过法线贴图改变模型表面细节对于边界和阴影是有破绽的，而位移（置换）贴图，直接通过贴图改变模型各个三角形的顶点位置。但是位移贴图要求三角形数量足够多，否则精度会非常低。
4、还可以定义三维纹理，如果把这个球砍一半，可以看到其内部的纹理，这里实际定义了空间中任何一点的值，这种纹理实际没有真的生成纹理的图片，而是定义了一个在三维空间中的噪声函数，对于空间中任意一点都有一个解析式可以算出在该点的值。
5、纹理贴图还可以记录一些提前算好的信息，比如模型自己本身互相遮挡产生的阴影（环境光遮蔽）。

第 15 章 曲线

一、什么是几何建模的显式表示/隐式表示？

虎书P206
隐式Implicit：
隐式几何表示：不表达点的具体位置，不给实际的点，而表示点与点的关系（这些点的排列满足一定的函数关系）。
已知：更通用来讲，定义一个函数f(x,y,z) = 0，只要满足这个式子，就认为这个（x，y，z）是我定义的表面上的一个点，如果能找到所有点就能把这个表面画出来。
缺点：找寻所有在物体上的点很困难；隐式几何很难看出函数所表示的几何的“真容”。难以描述复杂几何（比如给你一个奶牛去描述）。仅根据表达式F(x,y,z)很难直接看出来是是什么样子，面上都有哪些点也不容易知道，面上采样起来比较困难（找到所有点）
优点：方便判断点是否在物体内外；
1.通常表示出来很容易（例如用一个函数就能表示）
2.做某些查询容易(判断在物体里面还是外面，计算到表面的距离等)。给你一个点，判断在里面还是外面是很简单的。将点代入F(x,y,z)，如果小于零在里面，大于零在外面，等于零在面上。
3.很容易对光线与表面求交的
4.对于简单的物体们，用隐式的表示方法是很精确的，没有采样错误
5.易于处理拓扑结构（比如流体）
例子：algebraic surface(方程式)；


distance functions(距离函数)；取代布尔运算，逐渐将表面混合在一起，使用距离函数，给出最小距离从任何地方到物体（可以是有符号的距离）；距离函数：空间中任意一点到你想要表述的几何形体上任意一点，他们之间的最小距离。这个距离有正负。如果有一个点在几何形体外面，则最小距离算出来之后加个正号，如果在内部最小距离加符号。把这两个物体各自的距离函数都算出来之后，把两个距离函数做一个融合（blend）再把他恢复成原来的物体，就可以得到下图的效果。


如下图，A表示距离左侧1/3面积都是黑色，B表示距离左侧2/3面积都是黑色，A和B做一次blend，得到的结果就是1/3黑色（左侧），1/3灰色（中间），1/3白色（右侧）。


对A单独做一次SDF（SDF（A）），那么就可以得到A上任意一点的距离函数。我们认为A的黑白分界线为0，若一个点越接近于黑白分界线，距离函数的值越小，越接近于0，向右（白）为正，向左（黑）为负。
同理对B也单独做一次SDF（SDF（B））。
将SDF（A）和SDF（B）做一次blend，得到blend（ SDF（A），SDF（B））。那么这个blend后的图像中间即为0，向右（白）为正向左（黑）为负。把这个blend（ SDF（A），SDF（B））通过SDF再恢复成原来的形状，就可以知道，0的地方就是他们的边界，非0的地方不是。也就是说，blend两个对应的SDF，实际就是在blend他们的边界。
隐式几何之间，如果要实现比较圆滑的过度，就是通过距离函数来实现的。
level sets(水平集)：
封闭式方程很难描述复杂的形状 ，替代方案：存储一个近似于函数的数值网格 。
Ⅰ.f(x)=0 在内插值等于0的地方找到表面
Ⅱ.对形状提供更明确的控制（就像一个纹理)
距离函数blend出来之后得到的函数，如何再把它恢复成表面？我们只需要把距离函数对应的0的位置全部找出来（ f（x）=0 ）。
但是当距离函数不太好通过式子表示出来时，可以通过其他方法表示出来，如上图，通过水平集的方法表示。把函数的表述写在了格子上，只需要在格子上找到值为0的那条线，即为表面。（和等高线类似，在不同位置有相同值）至于在什么地方应该等于0？前面已经学过双线性插值了，可以解决这个问题。
应用：人体组织密度，水花四溅的效果（空气与液体的距离，水平集+距离函数）。
Constructive Solid Geometry(构造实体几何，布尔运算)。


Fractals(分形)：
如雪花：每个边上都有六边形，在看更小的地方又有六边形，再看更小的地方又有一个个六边形（递归）。
植物（西蓝花的一种），看这个植物，有很多凸起，看一个凸起上又有很多凸起，再去看一个小的凸起又有很多凸起…
还有例如遥感影像海岸线；
分形在渲染的时候会引起强烈的走样，因为物体变化的频率实在是太高。

显式Explicit：
显式几何：把所有点都直接表示出来，如三角形，把面上的点确确实实都表示出来。或通过参数映射。定义一个uv空间，上面有任意一个点用坐标uv表示，对应每一个uv值都可以映射到三维空间上的某一个点，把uv上所有的点都遍历一遍，就可以得到所有点的xyz，在三维空间中得到一个完整的几何体。


优点：显式几何可以很容易地看出几何图形的“真容”
缺点：但是显式几何对于判断一个点与几何的相对位置（在几何内还是在几何外还是在几何上）就很困难，通过式子无法得到。
例子：
point cloud点云，
最简单的显式几何。点的集合，模型由一个个点点组成。很容易表示任何类型的几何图形。当点云的密度非常大的时候，模型看起来没有什么问题，但是点云密度逐渐稀疏时，整个模型也就看不出来了。因此如果想用点云表示物体需要点云的密度非常大，适用于大数据集（>>1点/像素）。一般在扫描模型的时候会用到（然后还会再转化为一个个面，经常转换为多边形网格），难以在采样不足的区域进行绘制。
polygon mesh多边形网格：triangle meshes三角形面片：
①存储顶点和多边形（通常是三角形或四边形）。
②更容易做处理/模拟，自适应采样
③更复杂的数据结构
④也许是图形中最常见的表示方法


subdivision surfaces曲面细分,
NURBS(曲面建模方式)，
Curce曲线（Bézier curve贝塞尔曲线、spline（样条曲线）、B-splines）

二、什么是贝塞尔曲线？分段贝塞尔曲线？

虎书P222
贝塞尔曲线(Bézier curve)，是应用于二维图形应用程序的数学曲线。Bézier曲线由线段与节点组成，节点是可拖动的支点，线段像可伸缩的皮筋，我们在绘图工具上看到的钢笔工具就是来做这种矢量曲线的。
构造过程：递归线性插值：
首先这条线一定要从b0开始，到b3结束。b1、b2决定了整条线要向哪个方向弯曲。


以三点的贝塞尔曲线举例：


给定一个时间t，从0开始到1结束。
三个输入的点b0、b1、b2确定了两条线段b0b1、b1b2，在b0b1上认为b0是0，b1是1，那么在这个线段上，找一个点t。假设此时t=1/3，这个点记为b10。同样的，在b1b2上，认为b1是0，b2是1，也找这样一个点t=1/3，这个点记为b11。
到此我们通过三个点b0、b1、b2得到了两个点b10、b11。把刚刚得到的两个点b10、b11连起来，再认为这条线段又是从0到1，b10是0，b11是1，再取同样的t=1/3，这时我们找到了1个点b20，这个点即为由b0、b1、b2三点确定的一条贝塞尔曲线在时间t=1/3上的点。t的取值从0到1，每取一个值都重复上述步骤，然后得到了一系列点，将所有的点连起来就得到了一条贝塞尔曲线。
四个点确定的一条贝塞尔曲线同理，只不过这次的操作需要先由4个点b0、b1、b2、b3组成的3条线段b0b1、b1b2、b2b3确定3个点b10、b11、b12，再由3个点b10、b11、b12确定的2条线段b10b11、b11b12确定2个点b20、b21，再由2个点b20、b21确定的1条线段b20b21确定一个点b30。然后再对t取从0到1的所有值，重复上述步骤画出贝塞尔曲线。

分段贝塞尔曲线：
当控制点的数量过多，就可能导致某些地方弯曲不到我想要的程度，很难去控制局部。


第一段的终点等于第二段的起点，这种点叫连续。
continuity：=
连续:公共点相邻的左右两个控制点和这个公共点之间距离相等且三点共线（方向相反、等距、共线）。
continuity：==()


应用广泛：（字体、路径、插图、Keynote...）

三、贝塞尔曲线的构造算法（伪代码）

虎书P225




Bernstein多项式：
以三点的贝塞尔曲线为例：


其中：


，且


例如：b0 = (0, 2, 3), b1 = (2, 3, 5), b2 = (6, 7, 9), b3 = (3, 4, 5)
bn(t) = b0(1-t)3+ b13t(1-t)2+ b23t2(1-t)2 + b3t3


四、贝塞尔曲线有什么特点？

虎书P223
1.在贝塞尔曲线中，只有起点和终点在曲线上，其他点均为调整曲线形状和结束的控制点；


2.贝塞尔曲线通过起始点和终止点，并与起始点和终止点的折线相切，在对自车路径规划过程中可根据曲线的起始点和终止点的切线方向确定自车起始点姿态和目标点姿态；


3、Affine transformation property通过变换控制点来变换曲线；
4、Convex hull property曲线位于控制点的凸壳内
凸包：能够包围一系列给定的几何形体的最小的凸多边形，贝塞尔曲线一定在原来控制点的凸包里。更直观来讲，如上图，在一个板子上打好多钉子，用一个橡皮筋拉大包住所有钉子后放手，让橡皮筋自然收缩，被卡在的一圈钉子组成的多边形即为凸包。
5.至少需要三阶贝塞尔曲线（四个控制点）才能生成曲率连续的路径；
6.若要求两端弧线拼接在一起依然是曲率连续的，必须要求两段弧线在连接处的曲率是相等的；
7.贝塞尔曲线中的一个控制点改变，曲线的形状都会随之改变。

五、贝塞尔曲面如何构造？

贝塞尔曲面以Bernstein基函数的张量积为加权系数对控制顶点进行线性组合所构造的参数曲面。曲面具有端点和边界线插值性质。类似于双线性插值。
构造方法：在两个方向上分别运用贝塞尔曲线。
首先在一个方向上做贝塞尔曲线，然后把得到的点作为控制点，再做一次贝塞尔曲线即可。
例如：
对于双立方贝塞尔曲面补丁。输入：4x4个控制点 ；输出是以[0,1]2中的(u,v)为参数的2D曲面。目标：评估对应于(u,v)的表面位置 ：也即(u,v)- de Casteljau算法的可分离应用 。使用de Casteljau来评估点u在4条贝塞尔曲线中的每一条上的位置。这就得到了 "移动 "贝塞尔曲线的4个控制点。再使用1D de Casteljau来评估 "移动 "曲线上的点v.



六、Loop 细分方法的原理和流程？

loop细分的基本思想就是把一个三角形分成四个三角形，区分新顶点和老顶点分别进行位置的改变，最终让模型表面变得更加光滑。只针对三角形。
对于Loop细分其实就是两步：先细分（增加三角形面片数），再调整（位置）


①将每个三角形分成四个
②根据权重分配新的顶点位置，新/旧顶点的更新方式不同：
New vertex：(A+B)+(C+D)
对于新的顶点（如上图白色点），会被两个三角形所共享，将共享顶点所在的这条公共边两端的两个公共顶点分别定义为A、B，然后把这两个三角形非公共的两个顶点分别定义为C、D，然后将共享顶点（上图白色点）的位置调整为3/8 * (A + B) + 1/8 * (C + D)即可（这个式子其实就是一个简单的加权平均，A和B离共享顶点近一些，所以占的比例相对较大，而C和D离共享顶点远一些，所以占的比例相对较小）。
对于老的顶点（如上图白色点），周围的老顶点会对这个顶点有一定的影响。Loop细分规定这个要计算的老顶点（上图白色点）一部分受周围老顶点的影响，一部分保持自己的位置属性。在这里我们定义一个n，为顶点的度（这个顶点连接的边的数量），再定义一个u，这个u仅仅是一个与顶点的度有关的数。得到以下公式：(1 - n*u) * original_position + u * neighbor_position_sum。从这个式子可以看到，当顶点的度很大（连了好多三角形），那么这个顶点基本就可以由周围的老顶点决定位置，当顶点的度很小（连接的三角形很少），那么这个顶点由自己原来位置决定更新后位置的比重就会增大。



七、Catmull-Clark 细分方法的原理和流程？

Catmull-Clark细分是一种四边形网格的细分法则，每个面计算生成一个新的顶点，每条边计算生成一个新的顶点，同时每个原始顶点更新位置。
刚刚的Loop Subdivision仅仅可以针对全部都是三角面的网格。而Catmull-Clark Subdivision适用于更普遍的情况，无论是四边面还是三角面都可以很好地进行细分处理。


首先我们定义Non-quad face，所有不是四边面的网格形状都被称作非四边形面。
其次我们再定义奇异点（极点），所有度不为4的点都被称为奇异点。
对于每一个面，首先取这个面中心的点，然后取这个面的各个边的中点，最后把边上的中点和面中心的点连起来。原来是度是5的奇异点现在的度还是5，新引入的奇异点由于要与三角面上的每一条边的中点相连，因此度为3




没有非四边形面了，全部都为四边形面（细分的过程中每一个非四边形面都会引入一个奇异点，然后非四边形面就消失了）再次细分后，面会越来越光滑。
Catmull-Clark细分后对点的位置的更新分三种：


第一种是对于面的中心点f的更新，第二种是对于边的中心点e的更新，第三种是对于老的顶点v的更新。公式如上图所示。

八、网格化简的目的是什么？简述一种网格化简方法的原理

网格简化其实是利用尽可能少的三角面片来呈现所要展示的模型信息。但是简化不能太过，太过了就没法实现建模的目的，我们希望尽量保持住网格的几何信息或其它属性（如纹理），起码做到建模神似。
网格简化可以减少网格的三角片数量，同时尽量保持住网格的几何信息或其它属性（如纹理）。它是网格处理里的经典问题，
广泛应用于各个领域：游戏领域：游戏场景里的网格都很简单，适合快速渲染；简单的模型也适合快速的物理碰撞检测；多分辨率加载模型（Level of Detail）

！！！基于二次度量误差的边坍缩算法。
边坍缩：形象的说明的话，即为一条边两端连着两个顶点，将这两个顶点往中间一捏，变成一个点，这个操作即为边坍缩。
边坍缩算法是一个迭代算法，通过不断迭代进行边坍缩操作达到简化模型的目的。


边坍缩具有一个非常好的性质——边坍缩的过程是可逆的。边坍缩操作以及代价计算都是局部的。


假设要简化上面三个顶点，变成一个顶点，该把这个顶点放在哪里，才能保证简化后的蓝色三角形与原本灰色多边形基本保持轮廓的一致？这里引入二次误差度量概念：我们希望把这个顶点放某个位置上，可以最小化二次误差。在此处的意思就是：把这个顶点放置在某个位置上，使得这个顶点到各个面（如上图右图，在这里看上去像是边）的距离的平方和达到最小。


对于整个模型有很多条边，假设如果坍缩一条边，并且算出把这个坍缩后的点放在最佳的位置上会得到一个多大的二次度量误差。对于整个模型而言，每次肯定都是要坍缩二次度量误差最小的边。
先给每个边打上一个分数，这个分数就是这个边的二次度量误差，从小的开始一个个进行坍缩。
但是问题是，如果坍缩了一条边，有一些其他的边的位置要跟着这条坍缩的边变化，那么这些边的二次度量误差就会随之发生变化。
因此这里我们要通过一种数据结构，既可以每次取到二次度量误差的最小值的边，又可以动态地以最小的代价去更新其他的受影响的元素。那么这里要使用的数据结构就是堆（优先队列）。

补充一、在图形学中如何表示用三角形面形成的物体？（obj文件）



Obj文件常用于图形研究，它只是一个文本文件，指定顶点、法线、纹理
坐标和它们的关联性
将.obj文件拓展名改为文本文件，就会得到上图的一系列数据。v开头的是记录的顶点信息，vt记录的是纹理信息，vn记录的是面法线信息，f记录的是由哪三个（顶点/纹理/面法线）组成一个三角形。上图记录的是一个立方体的模型数据，有一些多余的数据是由于自动建模中数据冗杂造成的。

补充二、面片操作（网格细分、化简、规则化）

Mesh Operations: Geometry Processing
@ Mesh subdivision (increase resolution增加分辨率)
@ Mesh simplification(decrease resolution,try to preserve shape / appearance降低分辨率)
@ Mesh regularization(Modify sample distribution to improve quality修改样本分布以提高质量)


<hr/>PS：文中截图大部分来自闫令琪老师的GMAES101