algorithm - 找到连接立方体两个面的线

Question

想象一个 N³ 分辨率的立方体，其中充满了遮挡体素。立方体可以被完全填满，或者包含弯曲的“隧道”，或者墙壁——或者只是一些杂散的体素；我们现在选择边界立方体的六个面中的任意两个，并尝试找到一条连接这两个面的线，而不触及其中的任何体素。如果存在这样一条线，则面可以看到彼此，否则，它们将完全被遮挡。

我的问题是:是否存在 O(n)(或更好)的算法来快速辨别是否可以绘制这样的线？线路的确切参数无关紧要。

Answer 1

我不太清楚在这个(连续的？离散的？)空间中成为直线的确切参数，但我想知道您是否正在寻找动态规划解决方案？

也许让我们限制为从左到右的二维情况来构建算法然后概括:

遍历数组的第一列，对于每个不透明的正方形，标记不可能构建到达该正方形的射线对于每个非不透明方 block ，标记它可以到达这个方 block - 并且 - 跟踪斜坡范围可以到达这个方 block 。您可以通过可能到达体素体积另一端的一组斜率来限制此初始化中的一组斜率。

然后遍历下一列每个方格都可能被前一列中的任何方格到达，但前提是可以到达前一列中的方格的坡度范围与从前一列中的方格到达当前方格所需的坡度范围相交.
因此，您将当前方 block 中的有效斜率范围设置为先前方 block 的有效范围与当前方 block 的有效范围的交集的并集。

您继续遍历列，直到到达远端，远端的任何可到达条目将报告允许到达该方 block 的向量斜率范围。

算法的速度在很大程度上取决于您合并和交叉斜率范围(或者在 3D 情况下，任意范围的 UV 坐标)的速度。在 2D 连续空间中，可以通过排序快速完成此操作，在 3D 离散空间中，您可以根据体素空间的维度在 X、Y 中使用一组可能的矢量斜率。在 3D 连续空间中，某种类型的四叉树可能会接近通过在 2D 中排序可以实现的效果。

该算法在您输入的每个单元格上循环一次(您认为这是 O(n) 还是 O(n^3)？)，并且所花费的时间将受交集调用乘以元素数的并集限制在你的空间中(我相信离散情况下的最坏情况 O(n^2)，但如果体积的另一端很远，在初始化步骤中会急剧收缩，并且在许多不透明单元格和适当的情况下可能会快速收缩数据结构)

据我所知，体积切片的处理顺序实际上并不重要，因此如果您知道某些点非常不透明(通过不透明单元的总和或其他)，您可以使用启发式方法重新排序路口操作。