1

我有以下问题：我需要生成 3d 模型的 2d 视图。在正常情况下，这当然是微不足道的：只需使用画家算法或类似技术将所有内容渲染到屏幕上。不幸的是，输出需要是 2d 几何，以便可以发送到 CAD 包。这意味着必须在向量级别而不是像素级别上进行隐藏表面的去除，这使得大多数标准方法（画家算法、z-buffer 等）无法使用。

我发现执行对象空间隐藏表面移除的最常用技术是使用 BSP 树，理论上它工作得很好。所以我实现了它，但性能甚至无法接受，考虑到它的 O(n 2 ) 复杂性，这并不完全令人惊讶。我正在使用的测试场景在背面剔除后有大约 4800 个三角形，但我预计该算法将需要处理大约 5 或 10 倍数量的场景，当您需要对其进行平方时，它很快就会变得相当大。我们几何库的（缺乏）速度也无济于事。

从那以后，我尝试了不同的方法来解决这个性能问题，主要是基于将三角形分成较小的组以减少 O(n 2 ) 的影响，例如八叉树（超过一半的多边形是存储在根节点中）并将二维投影场景划分为 10x10 网格以减少每个正方形的三角形数量（有效，但多边形交叉点的减少被重复该过程 100 次的需要所抵消）。

今天我又进行了一次尝试，将所有三角形投影到 2D 中，并通过首先测试边界正方形是否重叠然后测试两个多边形的每个组合的每个边缘交叉点 (3x3 = 9) 来查看哪些三角形相交。对于线交点，我使用此处描述的算法绕过了几何库。总共执行了大约 1160 万个线交叉点，大约需要 30 秒，这仍然太长了（我会说绝对最大运行时间约为 5 秒），别介意这只是算法的一部分。

我开始对如何解决这个性能问题没有想法，并希望你们中的任何人都对更好的算法有一些好的想法。我能想到的都是O(n 2 )。

4

2 回答 2

1

我参加聚会有点晚了，但是如果这从未解决，我的建议是使用阴影矩阵并将几何图形投影到平面上，这样您就可以从给定方向获得 3D 场景的 2D 表示而无需去到屏幕空间/像素呢。

于 2014-02-28T13:36:11.000 回答
0

我会使用修改后的 Bresenham 算法，在其中计算所有像素交叉的线（也许这个算法有一个名字 btw）。完整的方法是：

  1. 创建一个n x m空间索引（每个网格有一个排序的多边形列表），其中 n 和 m 非常大（比如说 1000x1000 个单元格）。
  2. 对于每个投影多边形，使用上面的“修改的 Bresenham 算法”将多边形添加到它穿过的所有单元格。
  3. 通过查看每个单元格中的所有对来创建一组潜在的多边形交叉点对。
  4. 进行正确的真实相交测试，仅针对在上一步中找到的潜在对。

第 3 步应确保将潜在交叉点的数量修剪到最大。第 2 步是 O(n)，对于小多边形（少量交叉单元）应该相当快。

您甚至可以动态调整空间索引网格大小，查看以前的结果和/或基于总多边形数量、平均多边形大小等的启发式方法......

于 2012-02-04T14:54:11.167 回答