假设我有一些通过面和线连接的任意点集,以形成一个封闭的多面体。有没有什么算法可以把这样的网格分成一组四面体?
最佳答案
您可以考虑为 R^3
中的点构造一个受约束的 Delaunay 三角剖分(即四面体化),其中约束是边和三角形面的列表。
但请注意——在大于二的维度中,并不总是可以直接形成这种受约束的三角剖分!一个很好的例子是 Schonhardt Polyhedron .为了处理这种多面体,有必要通过引入额外的顶点来“拆分”约束。据我了解,尽管已经提出了一系列启发式方法,但确定执行此操作的“最佳”方法仍然是一个开放的研究领域。
您可能对 Jonathan Shewchuk's 感兴趣该领域的研究/软件,特别是他的论文:
- Constrained Delaunay Tetrahedralizations and Provably Good Boundary Recovery
- Updating and Constructing Constrained Delaunay and Constrained Regular Triangulations by Flips
解决高维约束三角剖分的一些问题。
此外,我假设您的问题很重要 - 具有一组定义非凸多面体的约束。在凸约束的情况下,这些应该通过计算无约束的 Delaunay 三角剖分直接恢复,保证存在于任何维度。
关于algorithm - 将网格划分为四面体?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14367536/