如果有一个两个二维的宇宙,一个是球面的,另一个是甜甜圈面的,那么生活在这样的宇宙中的生物是否能够得知自己处于哪一种宇宙呢?
如果我们说一个曲面的几何形状由
- 拓扑信息(连接关系)
- 嵌入信息(空间坐标)
两方面构成,那么这个问题可以转换为
仅通过拓扑信息,是否能够得到曲面的亏格数?
说人话
好吧,上面的问题只是个楔子。下面我来简单介绍一下计算三角网格亏格的算法。在三角网格上,存在着以下两个关系:
其中,为欧拉数,、、分别代表三角网格的定点数、边数、面数,代表三角网格边界的个数,则代表三角网格的亏格。
由于、、、都是与只与拓扑有关的量,因此我们可以直接根据拓扑关系求得三角网格的亏格:
边界数
边界数可以很简单地通过洪泛法得到,相信大家都有一定的思路。在这里还是给各位摸鱼的朋友们提供一个我写的C++版本。下面的代码基于OpenMesh:
int Boundaries(const MyMesh & mesh)
{
int retval = 0;
std::vector<unsigned char> vertexFlag(mesh.n_vertices(), 0); //0 For Unvisited, 1 For Visited
while (true) {
MyMesh::VertexHandle vhStart = MyMesh::InvalidVertexHandle;
for (int i = 0; i < mesh.n_vertices(); i++) {
const auto vh = mesh.vertex_handle(i);
if (mesh.is_boundary(vh) && vertexFlag[i] == 0) {
vhStart = vh;
break;
}
}
if (!vhStart.is_valid()) break;
MyMesh::VertexHandle vh = vhStart;
while (true) {
//Mark current vertex
vertexFlag[vh.idx()] = 1;
//Find next vertex
MyMesh::VertexHandle vhNext = MyMesh::InvalidVertexHandle;
for (auto vvi = mesh.cvv_begin(vh); vvi != mesh.cvv_end(vh); ++vvi) {
if (mesh.is_boundary(*vvi) && vertexFlag[vvi->idx()] == 0) {
vhNext = *vvi;
break;
}
}
if (!vhNext.is_valid()) break;
//Move to next
vh = vhNext;
}
retval++;
}
return retval;
}