Lecture10~12
1 几何图形的表示方式
1.1 几何的隐式表示法
- 优点
(1)容易表述(一个函数就行)，对于存储空间来说非常有利
(2)判断一个点在几何内/外特别快
(3)与光线求交点特别容易
(4)对于简单的形体，描述非常准确，不容易出现误差
(5)处理变化的拓扑结构非常容易，比如流体模拟 - 缺点：很难用函数描述一个复杂的模型，复杂的模型只能用显示表示咯
1.1.1 函数
- 不告诉点的具体位置，只描述点的关系,即只给一个函数，表示一个几何形体
- 缺点：非常抽象，不能马上知道是个什么样的几何模型。
- 如下，前两个还好，后面一个光看公式你能知道是个什么三维图形么，不知道！
1.1.2 Constructive Solid Geometry(CSG)
- 就是用布尔运算来组合模型
1.1.3 距离函数
- 不直接描述几何的表面，而是描述空间中任何一个点到该表面的最近距离(垂直)
- 有正负，0表示就在几何表面上，+表示在外部，-则在内部
- 这种表示非常适合做圆滑过度的边界
下面图：几何图形->算出俩球的距离函数->对距离函数做融合->恢复成新的几何图形。
这个图，一开始是两个球，并且也算出了距离函数
-
非常重要的解释图
输入：某种物体的边界，A图的物体覆盖屏幕的1/3，B物体覆盖屏幕2/3
希望：做个线性融合，求出中间状态
操作：
(1)求出A,B的距离函数，如A 在1/3处是边界所以边界上的点全是0；边界左边的点在物体内部，所以为负数且越远负值越大，边界右边的点则正数递增。B同理。
(2)然后对这两个函数做一个线性的融合(具体怎么操作不知道)，然后就可以找到融合的新的边界(数值为0的那些点)，并且为负数的表示物体内部，为正数表示外部，进而得到新的几何形体。
-
对任意的两个几何模型，算出其距离函数->做函数线性混合->再变回几何模型->得到混合的模型
-
太抽象，反正吧就那个意思但才疏学浅脑子不行描述不清楚。。。
-
总而言之言而总之，就是两个距离函数F1，F2混合得出新的距离函数F新，这个距离函数呢，在空间中所有为0的点就是新的边界了，为负的点就是几何内部，为正就是几何外部，从而得到新的融合之后的图形，不知道说没说清楚。。不行的话就搜索别的大佬的文章吧- - 。
-
距离函数的应用
下面这个场景的模型就是用距离函数来定义的，所以看起来才会那么的丝滑 -
如何从距离函数得到几何体的表面呢？
1.1.4 水平集(Level Set)
- 从距离函数，反求几何表面就是，类似的隐函数告诉了函数式f(x,y,z) = 0，求物体是个啥样
但是有些距离函数连写成f(x,y,z) = 0很困难咋办，用水平集 - 2D空间中
在不同的格子中心有不同的值，格子之间的值用双线性插值可以求出来；在这样一个平面中里面找函数值为0的点连起来就是物体边界了f(x,y) = 0了 - 3D空间中的水平集
跟3D纹理联系起来了，3D纹理就是描述的三维中物体的任意一个点的属性；但怎么找边界呢
定义所有点的密度，比如骨骼的密度是5，那就找到空间中所有5的点连起来就得到边界了。
1.2 几何的显式表示法
- (1)直接给出所有点在空间的位置
- (2)通过映射的方式给出、一张纹理图的每个uv坐标对应空间中一个点，遍历所有uv即得到几何形体
- 显示表示的优缺点
优点：很容易、快速得到几何模型
缺点：判断点是否在几何内/外很困难
1.2.1 点云(Point Cloud)
- 最简单的表示方法：点(x,y,z)列表
- 点云可以表示任何类型的几何体
- 很少用，一般扫描出来的原始数据是点云数据
一般会把扫描出来的点会将其转换成不同的面再计算着色
1.2.2 多边形模型
- 用得最广泛的方法，一般用三角形或者四边形来建模
- 在代码中怎么表示一个三角形组成的模型？
.obj文件：描述了“顶点、法线、纹理坐标、顶点组合关系”
比如下面代码，描述的就是个立方体
v：顶点8个
vt：纹理坐标，其中有共用的纹理坐标，下面代码是用软件生成的，会有重复问题。
vn：法线，6个面有6个法线，但vn却有8个，重复定义，3 4行、5 6行是一样的(忽略精度)
f：顶点索引，定义哪三个点组成三角形，后面分别是定义顶点对应的纹理坐标、法线。 - 对几何的处理
网格细分：增加模型面数
网格简化：减少模型面数
网格正规化：让网格大小更均匀、接近正三角形 - 游戏引擎中的LOD技术不就是动态的进行网格细分/简化么。
1.2.3 贝塞尔曲线
以三次贝塞尔曲线为例
起点P0，终点P3， 起点切线P0P1，终点切线P2P3
P1和P2其实没啥关系，但是一般还是给他们俩连个线的
- 如何用三个控制点确定一条二次贝塞尔曲线？？？————de Casteljau算法
(1)认为时间从0~1，从0开始每个时刻都找到曲线的一个点，到1时就得到整个贝斯尔曲线
(2)任取一个时刻t，根据t在时间的比例，分别插值三次(两个线段分别做一次，对得到的两个点之间再做一次插值)，最终得到的点就是曲线的一个点。 - 2次贝塞尔曲线(动图是偷来的…)
)
- 3次贝塞尔曲线
- 贝塞尔曲线的代数公式
比如2阶曲线是由3个顶点和时间t 做计算得到的，那么一定可以写出一个公式来表述。 - 更一般，给n个控制点，在t时刻的曲线点的计算公式
伯恩斯坦多项式：i = 1，2，3，…，n
最终就算是3D空间的点，只需要更改每个点为三维坐标即可
具体伯恩斯坦多项式推导可看这篇文章 - 贝塞尔曲线好用的性质
(1)首/尾两个控制点一定是起点/终点
(2)对控制点做仿射变换(投影不行)再重新画曲线，跟原来的一样，不用一直记录曲线上的每个点
(3)凸包性质：画出的贝塞尔曲线一定在控制点围成的线之内 - 请逐段使用贝塞尔曲线(一般用4个控制点、3次曲线)这在各种游戏引擎中很常见
1.2.4 Splines样条线
一条由一系列控制点控制的曲线
- B-splines 基样条
对贝塞尔曲线的一种扩展，比贝塞尔曲线好的一点是：局部性，可以更局部的控制变化。 - NURBS
比B样条更复杂的一种曲线，了解即可。
1.2.5 贝塞尔曲面
- 将贝塞尔曲线扩展到曲面
依然是用多段贝塞尔曲线对应曲面进行无缝拼接的。 - 三次贝塞尔曲面
下面这个曲面 是4x4=16个控制点应用双线性插值形成的 -
插值
很容易理解，每4个控制点可以绘制出一条贝塞尔曲线，贝塞尔曲线上时刻t的值是通过3次插值得来的，这样在t时刻一共4条贝塞尔曲线又能分别提供1个控制点，一共4个控制点，再插值画一条贝塞尔曲线(下图蓝色部分)，这条线就是t时刻的平面的线，然后每个时刻都画一条线则得到贝塞尔曲面。
容易理解
注意时间那个变量变成二维了，t1 、t2用uv表示也行
(u,v)对应两个时间，u时刻算的是4个控制点的位置，v时刻则是这四个控制点控制的贝塞尔曲线的点的位置，即最终曲面的位置。 - 因为用(u,v)表示最终位置，所以贝塞尔曲面也是一种显示的表示
2 几何的操作方式
2.1 曲面细分
2.1.1Loop细分(Loop Subdivision)
Loop是人名
两步：先增加三角形个数，后调整位置
如下图，够明显了吧，不仅仅是增加三角形的个数，还要调整新/旧顶点的位置。
-
新顶点调整方法
对于中间那个白点，处于共线的A、B顶的权重相对C、D高一些 -
旧顶点调整方法
n：旧的顶点连接的边的数量为度，度越多，则自身位置的权值越小
u：u就是个影响系数系数，n=3时，u=3/16；否则u=3/8n - loop细分的结果
很明显确实光滑了不少
2.1.2 Catmull-Clark细分
这种细分对于更一般的情况效果也很好，(全三角形、全四边形、三角形四边形混合)
-
细分步骤
1)给每个面增加1个顶点
2)给每条边增加1个中点
3)连接所有新增加的点 - 一次细分后
奇异点增加了2个(有多少个非四边形面就增加多少个)
非四边形面0个(不管多少个全部消失) - 再细分下去
奇异点不会再增加，因为首次细分后全是四边形了 顶点的度也不会变 - 顶点位置更新规则
- 新顶点，分为面新增点和边新增点
- 旧顶点，不光受8个新顶点影响还有4个旧顶点的影响
- 最终效果特别好
2.2 曲面简化
减少三角形数量的同时保持原有的基本形状
可以看到，如果离得很远3万面和3000面甚至是300面根本看不出啥区别，仅仅笑掉大牙而已
所以在大型项目中应用LOD技术是非常有必要的！
如果说MipMap是纹理上的层次结构——根据不同距离(覆盖像素区域的大小)选择不同层的纹理
那么LOD就是几何的层次结构——根据不同距离(覆盖像素区域的大小)选择不同的模型面数
2.2.1 边坍缩
- 如下图，其实是对两条边进行坍缩了
首先，三角形的任意一条边坍缩，则两个顶点合成了一个顶点
然后，只剩2个顶点1条边了，再坍缩这条边则成了右图模样
并且坍缩一条边，跟边的两个顶点相连的别的边也都会受到影响 - 新的点放哪？
-直接取平均(原本所有相邻的几个点的平均)，毫无疑问误差特别大 原本是E，现在A了，不妥！
2.2.2 二次误差网格简化
-
二次误差度量
二次误差：即新点跟原本几个相邻面的距离的平方。
找到一个位置，使得这个点到原本相邻几个面的距离平方最小 -
根据二次误差选择坍塌目标——贪心算法
(1)计算每条边的二次误差，从小到大存起来
(2)每次取二次误差最小的边，由于会影响到其他边，因此须动态更新其他边的二次误差
(3)存放每条边的二次误差的数据结构采用 小顶堆 (每次取最小，并且动态更新) -
因为每一次都坍塌局部误差最小的边，希望得到一个轮廓变化不大但是面数降低很多的模型
这就是贪心算法——希望通过对局部做最优解试图得到全局最优解 -
二次误差网格简化结果