闫令琪教授计算机图形学

概述

Implicit（隐式几何）

定义：不会具体告诉点的位置，只给出几何中的点的关系，满足该关系的就是该几何图形，这样的方式就是隐式几何。
例如下图中f=0,指f(x,y)满足等于0时候的点就是该几何中的点：

劣势难以根据方程式推断出几何图形的位置样貌，如下图：

优势可以很方便推出一个点和几何图形的关系，如下图：

Explicit（显式几何）

定义：方法一，直接给出几何的位置；方法二，通过via parameter mapping（参数映射）的方式给出：

优势易于根据公式推出几何图形的样貌，如下图中，只需要将所有对应的u,v代入即可知道所有位于图形上的点的坐标：

劣势不易于判断一个点和几何图形之间的关系：

Implicit（隐式几何）表示方法

数学公式表示

CSG表示法

Distance Functions（距离函数）
为空间中的任意一点到几何中的点定义一个最小距离（该距离可+可-），就是将两个图先逐渐融合之后，再恢复到原图像空间：


例如：下图需要求A和B的融合空间，最终需要的效果图blend(A,B)是从左到右依次呈现黑、灰、白三种颜色。那么可以先以A图的边界为原点线做图SDF(A)，该线上值为0；同理做图SDF(B)，以SDF(A)中心（红色箭头所指）为例，值应该为1/6，SDF(B)中心（红色箭头所指）为例，值应该为-1/6，则blend(SDF(A),SDF(B))中点位置也应该为0；以此类推图blend(SDF(A),SDF(B))的值区域应该分成了三块负值、零区域、正值各占1/3：

Level Set Methods（水平集表示法）

思想和距离函数其实是一致的，只不过使用了网格图的形式来表示，其中f(x)=0的地方就是表示物体的表面，同理可以寻找f(x)=0.3等等的边界线，只不过表示的不是物体表面，即也就是地理上的等高线思想相一致：

Fractals（分形）
即物体的一部分和整体十分相似（可以理解成递归操作，亦或是雪花的构成，细看六边形的雪花的其中一边，其仍然是较小的六边形构成的，再细看仍然由由更小的六边形构成

Explicit（显式几何）表示方法

point clouds（点云）
即使用一堆点，只要点与点之间密度足够大，致使最终看不到点之间的空隙，那么这些点就可以构成一个物体的表面（注意：使用的是一个列表保存这些点的坐标）：

Polygon Mesh（多边形网格）
存储顶点和多边形（通常是三角形或四边形），易于处理/模拟，自适应采样，并且有着更复杂的数据结构，是图形中最常见的表示形式，如下图胶囊状物体：

The Wavefront Object File (.obj) Format波阵面对象文件（.obj）格式
注意：区别于编译软件编译出来的.obj文件。在3D中的.obj文件是一个文本文件，只是把一堆点、法线、纹理坐标分开表示，然后再组织起来形成的模型。
例如下图：定义的是一个立方体，有8个顶点（V表示），6个面的法线向量（Vn表示，其中Vn有两个冗余，例如29，30行的法线实际代表的是同一个法线），一堆纹理坐标（Vt表示），之间的相互关系（f V/Vt/Vn表示）。
注意 ：例如关于f的36行表示从上到下数第5个点（使用第1个纹理坐标和第1个法线向量）和第1个点、第4个点之间的关系：

Curves（曲线）

Bézier Curves(⻉塞尔曲线)

特点：如下图的字母Q，采用的就是⻉塞尔曲线，可以做到不管放大多少倍都不会看到锯齿状，显现的就是一根平滑的曲线：

定义：只经过起、止点，中间不管是否通过别的点的一条任意光滑的曲线（注意：中间的点的作用是告知在这附近曲线应该往哪个方向弯曲）：

⻉塞尔曲线的画法-----de Casteljau算法

如下图，假设三个点连成两条线段，每两个点间距离假设为1，则在第一条线段中找0~1中任意一点t（假设为1/3），第二条线段也同样找到1/3这一点：

将这两点连接起来获得新的线段，该线段长度也假设为1，则同样取其1/3的点，那么最终的贝塞尔曲线也一定通过这一点，画一条曲线就是枚举所有可能的点t位置对应找出其在贝塞尔曲线上的位置，最终连接起来：

而对于n个点来说，每一次找都需要进行n-1 趟 查找：

注意：下图中右上角的标是第n趟画的点的意思（即第n层）：

使用线性代数表示 其中t虽然是指到前一个点的距离（如：b0到b1中t代表距b0的距离，但是代数式却是要写成(1-t)b0+tb1），验证可以令t=0和1分别代入验证求的的点是不是分别为b0和b1：

伯恩斯坦多项式实质就是描述二项分布的多项式

Convex hull（凸包性质）

空间中有若干个点，连接最外围的几个点形成一个封闭空间那么遍历所有点画出的贝塞尔曲线一定在这个封闭空间中（如空间中所有点都在一条直线上，那么其封闭空间就是这一条直线，那么根据凸包性质贝塞尔曲线不能超过该凸包包围的空间，那么就可以确定贝塞尔曲线就是这一条直线）：

Piecewise Bézier Curves（逐段贝塞尔曲线）

引出原因 贝塞尔曲线可以很好的表示全部点位于起终点一侧的曲线，但是对于中间点散列分布在两侧的情况：

在使用逐段贝塞尔曲线时一般都是使用Piecewise cubic Bézier（逐段三次贝塞尔曲线），即每4个控制点定义一条贝塞尔曲线（即每一段起点终点和空间中的两个控制点）：

Surfaces（曲面）

Bezier surfaces（贝塞尔曲面）

一般来说，也是运用的三次贝塞尔曲面。和二维空间到三维空间中的插值思考方式相同，三次贝塞尔曲面就是对三次贝塞尔曲线在竖直方向上再进行了一次三次贝塞尔曲线运算得到的结果。下图是三次贝塞尔曲面，即4X4个控制点得到的平面：

对于水平方向上先遍历得到每一个t，在这记作u,然后对于遍历得到的一个u再在竖直方向上遍历每一个t，在这记作v，可以理解成两层for循环外层u内层v:

Mesh（网格）

Subdivision（细分）

Loop Subdivision(loop细分）

将每个三角形从各边中点划分成四个三角形，不断重复步骤，最终得到的结果将无限接近于理想中的物体：


如何调整细分了的三角形位置
对于 新的顶点（图中白点），对于它所在边两头的点设为A、B，该两个三角形的非共享点设为D、C，则这个白点的新位置取A、B的3/8加上C、D的1/8位置（加权平均），因为一般认为在该点所在共享边上的点对该点的影响较大，而其它的两个顶点影响较小：

而对于 旧的顶点 （下图白点）以自身原来的位置和周围其它点的位置来决定自己的新位置，其中n是本身的度（度即边的数量，如下图中白点度为6），u是某个和度相关的数，那么最终式子为图中右上角的式子，可以看出当度小的时候自身原位置占的比重较大，而度大的时候（如度为20，则周围三角形也有20个），自身原始位置所占比重就显得没那么重要了：

Catmull-Clark Subdivision（Catmull-Clark细分）

loop细分只是针对三角形构成的图形，而如果遇到了其它形状组成的图形时，则Catmull-Clark做的更加优秀。
步骤 取出各个点的中点和每一个面的中点，并且将这些点连接起来（注意：奇异点指度不为4的点；non-quad faces指非四边形面）：

例如，将上图邻近边的中点连接到每个面的中点（橙色三角形）得到下图，因此此时多出来两个度为3的奇异点（紫色圆点），同时所有的非四边形面都消失了：

而再做一次细分，会增加更多的奇异点数，但是非四边形面数量则始终为0：

点的更新

性质

在进行第一次Catmull-Clark细分时，会产生n个奇异点（n为细分前非四边形面的数量），而这n个非四边形面都会消失，此后无论经过多少次细分都不会增加减少非四边形面

Simplification（简化）

Collapsing An Edge（边坍缩）

边坍缩简单理解就是将一个边的两个顶点用手捏到一起，那么这一条边就不存在了，应用到总体来看效果就是实现了三角形的删减：

Quadric Error Metrics（二次度量误差）

即需要寻找到一个点，使这个点到与他邻近的面的距离平方和最小，则该点就是坍缩到的点：

步骤
先为每一条边打分（赋值标明优先度）；然后从最低分开始进行坍缩操作，坍缩完后同时对它所影响到的边进行重新赋值操作（更新优先度）；不断重复上诉操作。（注意：以上操作明显是一个动态操作，并且涉及到优先级，因此使用的是优先级队列/堆的数据结构）。

Shadows（阴影）

Shadow Mapping

原理 ：对于一个点来说，如果它位于阴影中，则说明摄像机能看到这个点，但是光源无法看到这个点；如果位于阴影外，则说明摄像机能看到这个点，同时光源也能看到这个点。
注意 ：该方法只能处理点光源中的阴影；在形成的阴影中经常会看到有走样现象发生；这是一种 硬阴影（对于空间中的点非0即1，没有平滑过渡）。
步骤 ：
首先从点光源的位置看向整张图，记录下所有像素点对应的深度（Z-Buffer）：

之后再回到真正摄像机的视角看向整张图，遍历所有像素点，从该像素点重新投影回到点光源生成的深度图上，看上面记录的该点的深度和实际的深度是否一致（一致则说明点光源能看到该点：不位于阴影中；反之位于阴影中）：

软阴影

实际上人眼看到的阴影是有一个渐变的过程，如以下右图中，软阴影区域实质上就是位于penumbra（半影）区域中，针对于非点光源（即该光源实际上是一个有范围大小的光如下图的太阳），半影区域是被物体遮蔽了一部分光而并非所有光的像素点的集合：