我正在编写一些代码来渲染地形数据。对于巨大的网格，我想将网格划分为子网格。为了帮助相机剔除，我想要一个算法来执行以下操作：
- 取一个网格（顶点、索引三角形）并将其分成 2 个
- 如果我们将所有点投影到 XZ 平面上并取每个网格的边界，我想最小化面积的总和它们的 2D 边界。
有谁知道这样做的快速算法？
您有几种选择可以执行此操作：
选项 1：使用图形分区算法，例如苏格兰威士忌和梅蒂斯，他们有一些选择来最小化"通信成本"，这对应于您的段之间的边界长度：
- http://www.labri.fr/perso/pelegrin/scotch/
- http://glaros.dtc.umn.edu/gkhome/metis/metis/overview
选项 2：如果可以保留次优边界长度，则可以沿希尔伯特曲线对三角形进行空间排序，然后将排序序列拆分为所需的段数。它比上面的图形分区算法快得多（但可能会生成不太紧凑的段）。您可以在 Geogram 和 CGAL 中找到空间排序的实现：
- http://alice.loria.fr/software/geogram/doc/html/mesh__reorder_8h.html
- http://doc.cgal.org/latest/Spatial_sorting/index.html