Basic
通过定义点的位置和点之间的连续关系,来描述一个曲面。
在mesh上的操作有:
- 网速细分:引入更多三角形,并调整顶点坐标。使表面更光滑
- 网格简化:在保持基本形状的情况下,用更少的三角形
- 网格 Regularization:使网格更接近正三角形,这样对渲染更友好
网格细分 [09:26]
目的:引入更多三角形,并调整顶点坐标。使表面更光滑
基本方法都是通过平均的方式让平面的局部得到平滑,类似图像的模糊操作。
✅ 立方体不断细分后会变成球体,因为细分的目的是变光滑。
Loop 细分算法
[11:30] (loop 是人名,不代表循环)
第一步: 划分三角形
第二步:更新new顶点的位置
new顶点被两个old三角形共享,更新公式为:
\[ p = \frac{3}{8}(A+B) + \frac{1}{8}(C+D) \]
第三步:更新old顶点的位置
old 顶贞被多个 old 三角形共享
更新公式为:
\[ p = (1 - n * u) * pos + n * neighbor \]
n:与old顶点连接的边数
u:一个经验值
pos: old顶点更新前的位置
neighbor: old顶点的所有邻居的位置之和
Catmull-Clark 细分
loop 细分只能用于三角形面片,而此算法则更通用
定义
Quad face:四边形面片
Non-quad face:非四边形面片
奇异点: degree不为4的点,degree 表示与点相邻的边数
第一步:取所有边上的中点与面上的中点
把边中点与面中总用一条线连起来
操作后,增加的奇异点个数与 操作前的non-quad face 数相同,且所有的面都变为 quad face
第二步: 更新面中心的新增点,
更新公式为:
\[ f = \frac{v_1 + v_2 + v_3 + v_4}{4} \]
❓ 如果是在一个三角形面片的中心呢?
第三步: 更新边中心的新增点
更新公式为:
\[ e = \frac{v_1 + v_2 + f_1 + f_2}{4} \]
更新 old 顶点
更新公式为:
\[ p' = \frac{f_1 + f_2 + f_3 + f_4 + 2(e_1 + e_2 + e_3 + e_4) + 4p}{16} \]
💡 以上这些方法都是基于经验估计。
new point的位置不是该是由邻居点使用固定加权值得到,这个权值应该是不固定的,与old point和neighbour的距离有关。
这些都是local细分方法,要想细分后与原mesh形状接近,应该使用global方法。
同时,mesh细分是对丢失信息的补全,要想猜丢失的信息,还需要从其它mesh的统计规律、物理意义、人为知识中得到先验信息。
Mesh 简化
- 由于计算能力不足,需要简化模型
- 有些场景中,不需要足够精细的模型
边坍缩 Edge Collapse
- 原理:
- 选择一条边,把边坍缩成点
- 建立边周围的点到新点之间的边
- 使坍缩后的形状与坍缩前尽量接近
- 要解决的问题:
- 要坍缩哪些边?
- 边坍缩成点以后,这个点应该放在什么位置?
- 怎么衡量坍缩后的形状与坍缩前的接近程度?
衡量坍缩后的形状与坍缩前的接近程度
Quadris Error Matrics 二次误差度量
二次误差度量用于衡量“坍缩后的形状与坍缩前的接近程度”,使算法可以基于此标准选择要坍缩的边及确定坍缩点的位置。
二次误差来度量[41:17] = new point 到 old edge(或old face) 的距离平方和。
❓ 为什么以这种方式定义距离。不太直观。
✅ 这种度量也是local度量,大部分情况下local就够用了。
确定坍缩点的位置
例子:
坍缩点的位置应该在使二次度量误差最小的地方。
找到坍缩点转化为一个优化问题。
选择要坍缩的边
把所有边都尝试坍缩,评估一下每条边如果要做坍缩并选择了最好的坍缩点位置,会得到多少误差。最后选择造成误差最少的边。
即:遍历-计算-排序-选择-坍缩
每次选择当前最优,这是贪心的思想。不一定最终是最优,但是至少效果可用。
- 存在的问题:
计算一条边的坍缩点及坍缩误差是一个优化问题,用迭代法来解。因此“遍历-计算”是一个比较耗时的过程。
尤其是使用“遍历-计算-排序-选择-坍缩”的过程坍缩了一条边之后,坍缩过程对被坍缩的边周围的边造成影响,上一轮的“遍历-计算”的结果已经不适用了,不能直接基于此结果做排序和选择。
- 解决方法:
优先队列。动态更新受影响的边。
预处理:遍历-计算-生成队列
循环:取队列top - 坍缩 - 部分点重新计算 - 更新队列部分点
💡 计算出new point的位置后可以再调整一下old point的位置。
网格 Regularization
本文出自CaterpillarStudyGroup,转载请注明出处。
https://caterpillarstudygroup.github.io/GAMES101_mdbook/