计算三角网格的亏格(Genus)

三角网格的亏格数可以直接从它的的拓扑关系得到,而与其在空间中的嵌入方式无关。

如果有一个两个二维的宇宙,一个是球面的,另一个是甜甜圈面的,那么生活在这样的宇宙中的生物是否能够得知自己处于哪一种宇宙呢?

如果我们说一个曲面的几何形状由

两方面构成,那么这个问题可以转换为

仅通过拓扑信息,是否能够得到曲面的亏格数?


说人话

好吧,上面的问题只是个楔子。下面我来简单介绍一下计算三角网格亏格的算法。在三角网格上,存在着以下两个关系:

其中,e为欧拉数,|V||E||F|分别代表三角网格的定点数、边数、面数,B代表三角网格边界的个数,G则代表三角网格的亏格。

由于|V||E||F|B都是与只与拓扑有关的量,因此我们可以直接根据拓扑关系求得三角网格的亏格G

G = \frac{2-B-e}{2} = \frac{2-B-|V|+|E|- |F|}{2}


边界数

边界数可以很简单地通过洪泛法得到,相信大家都有一定的思路。在这里还是给各位摸鱼的朋友们提供一个我写的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;
}

 

称谓(*)
邮箱
留言(*)