2

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

  1. 取一个网格（顶点，索引三角形）并将其划分为 2
  2. 如果我们将所有点投影到 XZ 平面上并获取每个网格的边界区域，我想最小化它们的 2D 边界区域的总和。

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

4

1 回答 1

0

你有几个选项可以做到这一点：

选项 1：使用图形分区算法，例如 Scotch 和 Metis，他们有一些选项可以最小化“通信成本”，这对应于您的段之间边界的长度：

选项 2：如果您可以离开次优边界长度，那么您可以沿希尔伯特曲线对三角形进行空间排序，然后将排序后的序列拆分为所需的段数。它比上面的图形分区算法快得多（但可能会生成不太紧凑的段）。您可以在 Geogram 和 CGAL 中找到空间排序的实现：

于 2015-07-14T10:58:41.517 回答