网格划分的快速算法是什么？

Question

我正在写一些代码来渲染地形数据。对于巨大的网格，我想把网格划分成子网格。为了帮助相机剔除，我想要一个算法来做以下工作：

1. 取一个网格(顶点、索引三角形)并将其划分为2。
2. 如果我们把所有的点投影到XZ平面上，并取每个网格的边界面积，我想把它们的2D边界的面积之和降到最小。

有人知道这样做的快速算法吗？

Answer 1

你有几个选择可以这样做：

选项1:使用图形分割算法，例如史考奇和梅蒂斯，他们得到了一些选项来最小化“通信成本”，这对应于段之间边界的长度：

• http://www.labri.fr/perso/pelegrin/scotch/
• http://glaros.dtc.umn.edu/gkhome/metis/metis/overview

选项2:如果你可以留下一个次优的边界长度，那么你可以沿着希尔伯特曲线对你的三角形进行空间排序，然后将排序后的序列分割成你想要的片段数。它比上面的图划分算法要快得多(但可能生成较少的紧凑段)。您可以在地理图和CGAL中找到空间排序的实现：

• 8h.html
• sorting/index.html