学完代数拓扑已经有一段时间了, 尽管内容已经忘了不少了, 但一直心心念念将代数拓扑的思想应用至游戏开发中. 终于在前段时间, 自己完成了一个名为Auto LOD Group的UE5插件初版, 利用闭曲面分类定理设置游戏开发过程中使用到的Mesh的LOD Group. 由于不同美术同学设置Mesh的LOD Group的标准可能是不一致的, 会使得游戏开发过程中对于LOD Group的管理变得十分混乱, 而Auto LOD Group便可以帮助实现LOD Group的自动化设置, 严格保证了LOD Group的设置标准的一致性. 限于所在项目的保密性, 接下来仅简单介绍一下Auto LOD Group的算法思想.
参考材料
1. 闭曲面分类定理
2. 如何直观，准确地解释＂亏格＂。？
3. 几何处理和模型简化课程笔记
1. 闭曲面分类定理
首先复习一下闭曲面分类定理.
$\\$ 闭曲面分类定理 一个二维闭曲面, 它是且只能是以下三种类型之一:
$\\$ 1) 球面: $\mathbb{S}^2$, 这时为可定向闭曲面.
$\\$ 2) $n$个环面作连通和: $n \mathbb{T}^2$型, 这时为可定向闭曲面.
$\\$ 3) $m$个射影平面作连通和: $m \mathbb{P}^2$型, 这时为不可定向闭曲面.
$\\$ 这个定理蕴含了对任意的正整数$m$, $n$, 这些不同类型的闭曲面是不交的, 这个不交性的证明需要用到基本群的相关理论. 可定向性是拓扑不变量.
上述三类曲面的Euler示性数和亏格如下:
$\\$ 1) $\mathbb{S}^2$, Euler示性数是2, 亏格是0.
$\\$ 2) $n \mathbb{T}^2$, Euler示性数是$2 – 2n$, (可定向) 亏格是$n$.
$\\$ 3) $m \mathbb{P}^2$, Euler示性数是$2 – m$, (不可定向) 亏格是$m$.
$\\$ Euler示性数和亏格是拓扑不变量.
注: 一个曲面做连通和被视为还是这个曲面自身.
2. 亏格计算
一般来说, 游戏开发所使用的Mesh的连通分支数(即第0个Betti数) 不一定为1, 且可能是带洞的. 此处洞的数量不一定为亏格, 因为亏格对应的洞必须是穿透型的, 不穿透的洞再深也不行(详见参考材料2). 因此, 在计算亏格时, 必须考虑第0个Betti数与边界的连通分支数(即洞的数量). 笔者所使用的计算亏格的公式为:
$\\$ 1) 当Mesh的隐藏曲面为可定向曲面时, $$v – e + f = 2s – 2g – h.$$$\\$ 2) 当Mesh的隐藏曲面为不可定向曲面时, $$v – e + f = 2s – g – h.$$其中, $s$为第0个Betti数, $g$为亏格, $h$为边界的连通分支数.
$\\$ 证: 仅证1). 不妨设Mesh的所有连通分支的顶点数分别为$v_1$, $\cdots$, $v_s$, 边数分别为$e_1$, $\cdots$, $e_s$, 面数分别为$f_1$, $\cdots$, $f_s$, 边界的连通分支数分别为$h_1$, $\cdots$, $h_s$, 考虑连通分支$C_i$, 其亏格计算公式为$$v_i – e_i + f_i = 2 – 2g_i – h_i,$$其中, 用该连通分支$C_i$的欧拉示性数$v_i – e_i + f_i$加上边界的连通分支数$h_i$的操作可视为仅用一个面进行补洞. 又Mesh的亏格$g$为其所有连通分支$\{ C_i \}_{i = 1}^s$的亏格$\{ g_i \}_{i = 1}^s$之和, 故其亏格计算公式为$${\textstyle \sum_{i = 1}^{s}} v_i – {\textstyle \sum_{i = 1}^{s}} e_i + {\textstyle \sum_{i = 1}^{s}} f_i = 2s – 2{\textstyle \sum_{i = 1}^{s}} g_i – {\textstyle \sum_{i = 1}^{s}} h_i,$$上式可简记为$$v – e + f = 2s – 2g – h.$$从而, 命题得证. 类似可得2).
$\\$ 此外, 借助并查集这个强有力的数据结构, 也可以较快速度地计算出Mesh的第0个Betti数, 边界的连通分支数与可定向性.
3. 亏格到LOD Group的映射
实际上, 各个项目组对于LOD Group的设置规则可能是各不相同的. 笔者将Mesh的亏格$g$到其LOD Group的映射定义如下:$$f: (g, b, s) \mapsto LOD \ Group,$$其中, $b$为Mesh的的Bounding Sphere的半径, $s$为Mesh采用的Shading Model. 之所以还需要考虑Mesh采用的Shading Model, 是因为上述的亏格计算是不考虑材质产生的亏格的. 目前, 笔者观察到Two Sided Foliage Shading Model会产生一定数量的亏格, 对于采用了Two Sided Foliage Shading Model的Mesh, 会直接将其LOD Group设置为Foliage相关的LOD Group.
4. 应用
分类问题一直是数学研究的基本问题之一, 在利用闭曲面分类定理与LOD Group对游戏开发过程中使用到的Mesh进行分类后, 我们便可以针对每一类Mesh进行特定的优化. 如
$\\$ 1) 对于高亏格, LOD Group为Foliage, Deco或Small Prop的Mesh, 由于其很难在遮挡剔除中发挥作用, 那么可以关闭对应的Actor Settings上的Use as Occluder选项. 尤其是对于LOD Group为Foliage的Mesh, 还可以启用Nanite进行渲染(分Cluster渲染, 剔除效率更高).
$\\$ 2) 对于LOD Group为Vista的Mesh, 可以将其绘制到天空盒上(待验证…).
5. 未来工作
目前Auto LOD Group算法已经在笔者项目内顺利落地, 也取得了还算不错的自动化效果. 但依旧存在一些不足等待解决, 如:
$\\$ 1) 实际上, 目前计算得到的Mesh的总亏格数量区分意义不大. 尤其是对于非流形的Mesh, 必须对其进行Manifold-Connected(MC) 分解得到MC复形(参考论文Hui A, De Floriani L. A two-level topological decomposition for non-manifold simplicial shapes[C]//Proceedings of the 2007 ACM symposium on Solid and physical modeling. 2007: 355-360.), 比较其每一个MC Component的亏格(参考论文Heisserman J A. A generalized Euler-Poincaré equation[J]. 1991.), 这样在Mesh的分类问题上才更具区分价值.
$\\$ 2) 计算Mesh的材质产生的亏格.
$\\$ 3) 计算Mesh的Handle与Tunnel(参考论文Dey T K, Fan F, Wang Y. An efficient computation of handle and tunnel loops via Reeb graphs[J]. ACM Transactions on Graphics (TOG), 2013, 32(4): 1-10. 或许可以用至Portal Culling中?).
$\\$ 最后, 也希望能够将代数拓扑更深层次的思想应用至游戏开发中. 不忘初心, 以学术之心应工业之事(ง •_•)ง~