Games101-lecture 12 几何

将上一讲的曲面内容移到这一讲

曲面

贝塞尔曲面

u方向上画出四条贝塞尔曲线后，在这四个线上再取四个点，并认为这是个点是一组新的贝塞尔曲线的控制点，这些

点在空间内向v方向扫描，便形成了贝塞尔曲面

动画请见lecture11　55:14-56:07

求贝塞尔平面

几何处理

曲面细分

Loop细分（涡轮平滑）

连接各边中点，并重新改变各个顶点位置，从而创造出更多三角形面，使得表面更加光滑（命名并不是因为算法与循环有关，而是该算法创始人的名字叫loop）

该算法规定，一般情况下（不考虑边缘情况）分为两类顶点进行考虑--新顶点与旧顶点

旧顶点，需要由原顶点和周围顶点位置共同确定

其中n为该顶点的度（依附于某个顶点的边的条数--数据结构），u为一个和n有关的数

Catmull-Clark 细分

loop细分有一个前提，即只适用于三角形网格，而对于非三角形网格的细分，就需要借助catmull-clark算法

该算法定义面分为两种——四边面和非四边面，并定义度为4的顶点为非奇异点，其余点均为奇异点

Non-quad face非四边形面

具体做法是，对每个非四边面都取其中的一个点（重心或者其他点），将其与该面的其他顶点分别连接，在这个过程中，会引入一个新的奇异点，并且在一次细分后，所有非四边面都变为了四边面，在后续的细分中，将不会引入新的奇异点（但也不会减少-见下图）

对于细分后顶点位置的调整，先将顶点分为三大类

①新的在面上的点；②新的在边上的点；③旧的点

如下计算：

loop细分与catmull-clark细分不同的处理效果：

可参考https://blog.csdn.net/McQueen_LT/article/details/106102609

网格简化

边坍缩

如何保证坍缩前后轮廓基本保持一致？ ——二次误差（机器学习中的L2距离相似）

二次误差度量：坍缩后的点和原本几个边（面）的距离的平方和最小

对每一条边都先计算一下二次误差，随后从二次误差最小的开始坍缩，由小到大

但这么做会引入一些问题：做一次坍缩后，其他边也跟着变了，他们的二次误差必须被重新计算

所以需要从二次度量误差中选最小的，取完最小的之后，我们要对它们的二次误差做一次更新，于是我们就要用到优先队列 / 堆这种数据结构，这种数据结构能让我们能取得二次误差最小值的同时也能动态更新其他受影响的元素

另外，这种通过对局部计算最优解，试图找到全局的最优解，是一个典型的贪心算法

注：本节开始讲了光线追踪，放在下一笔记中