今年年初开始, 我的研究重心便从对于单个游戏模型的拓扑分析转移到对于整个游戏世界的拓扑分析. 前段时间偶然淘到一本书《数字图像的计算几何、拓扑和物理及其应用》, 作者是来自加拿大马尼托巴大学的James Peters教授, 其Erdos数为3, 是一位挺强的研究计算拓扑的学者. 冥冥中觉得能从该书中获取如何去研究计算拓扑在游戏世界中的应用的灵感, 目前也已经粗略阅读了三分之二的内容了, 但收获不算太多, 让我有些失望的点主要在于大部分定理的证明有点循环论证的味道. 尽管如此, 我依旧想记录下读罢该书的一些收获, 本文便是一篇关于游戏世界的计算几何、拓扑及其应用的前言.
Edelsbrunner的网格生成几何和Ziegler的多胞形几何为我们所研究的三角化场景的几何结构提供了计算几何学方法的坚实基础. 三维多胞形由覆盖游戏模型内部的闭合半空间相交所定义的填充多面体. 由Edelsbrunner和Harer提出的单元复合型拓扑结构以及由Munch在持久性同源性方面的工作为游戏场景的计算拓扑学的介绍性研究提供了坚实的基础. 这种拓扑形式探索了游戏场景中常见的构造、形状和结构.
$\\$ 研究游戏模型目标形状在游戏帧序列以及记录游戏场景中表面形状变化的帧序列中的持久性非常重要. 表面形状会出现出现、经历各种光线和表面条件的变化、并最终消失. 玩家通常倾向于在游戏场景中寻找不寻常的物体(自然的和人工的), 这是一种对游戏场景中连续变化和观察到的成分的瞬间持久性的默认认识. 换句话说, 重要的是需考虑游戏场景形状的时空特性. 这指对游戏场景的理解包括对游戏场景的几何和拓扑的研究.
$\\$ 计算几何学有助于捕获嵌入在游戏模型目标形状中的细粒度结构. 计算拓扑学能够捕捉和分析嵌入在三角化游戏场景几何结构中的单元复合形(顶点、线段、填充三角形、循环、涡旋、神经的集族) 里发现的近邻. 单元复合形的同源性(亚历山德罗夫拓扑学方法的后代) 在这里是一个重要的组成部分. 同源性是一个数学框架, 它关注空间是如何连通的, 并利用代数结构, 如群和映射, 将空间中具有拓扑意义的子集相互联系起来.
$\\$ 实际上, 同源性是洞察游戏场景中的各个部分如何相互连通的来源. 循环群有助于以简洁的方式表示游戏场景中的各个部分是如何相互连通并接合在一起的. 具有多个生成元的循环群也是指定感兴趣表面形状的重要特征的一个来源, 该特征即贝蒂数(Betti number, 自由阿贝尔群中生成元数量的计数). H. Poincare为纪念Enrico Betti命名了这个数. 游戏世界的计算几何学、拓扑学的重点是有限空间.
$\\$ 贝蒂观察到, 有限空间具有与其维度大小和元素形状无关的属性. 这些属性仅指其各部分的连通方式…… 有限有界空间区域的特性倾向于通过覆盖空间的单元复合形中的通道所连通的顶点来揭示.
$\\$ Kaczynski、Mischaikov和Mrozek对同源性的计算方法进行了深入研究. 这里的重点是辨别和跟踪、分析和表达以及近似移动表面形状的接近性. 为了应对一个游戏场景中(从一个游戏帧到另一个游戏帧) 的连续形状变化, 描述性邻近空间上的特征矢量为我们提供了一种表示形状变化的方法, 这些变化要么彼此靠近, 要么有时相距很远.
$\\$ 在欧氏空间中, 几何结构包括顶点、线段、实心三角形(三边多面体) 和空心四面体. 三维多胞形是封闭半空间的交集. 单个三维多胞形是一个空间区域, 内部充满, 四周都有边界. 在拓扑设置中, 重点是将游戏场景区域分解为非常简单的三维多胞形, 例如易于测量和分析的空心四面体. 这种拓扑的基本成分是单纯复合形、形状理论和持久同源性.
$\\$ 这项工作背后的秘密是将封闭的游戏场景区域分解成一组形状复合形, 这些形状复合形为形状分析提供了基础. 形状复合形用嵌套的, 通常不重叠的涡旋集族对形状进行覆盖. 在每个复合形中构成神经结构的三角形集族具有共同的顶点. 一般来说, 形状分析的目标是分类、比较、量化异同, 并测量形状之间的距离. 我们的研究重点是计算拓扑在游戏场景形状分析中的应用.
$\\$ 对于三角化游戏场景中的单元复合形, 场景形状被称为神经复合形的填充三角形簇所覆盖. 设$K$是点集的有限集族. 集族$K$的神经(用Nrv $K$表示) 由$K$的所有非空子集族组成, 这些子集族具有非空交集. 每条神经都有其独特的形状. 在三角化表面上, 亚历山德罗夫神经复合形$A$(用Nrv $A$表示) 是具有公共顶点的三角形集族.