寻找连接正方体两个面的线。

Question

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

我的问题是：是否存在O(n)（或更好）的算法来快速确定是否可以画出这样的线路？该线路的确切参数并不重要。

- paniq

---

直线，对吧？ - David Eisenstat

是的。我先写了直线，然后想到这可能是多余的提及。 - paniq

O(n) 对我来说有点乐观了；你最多能接受什么样的最坏复杂度？ - G. Bach

也许这里有一些可以帮助你入门的东西：每个被阻挡的体素都会遮挡通过两个类似于双锥形状的金字塔树桩的路径。如果你能有效地合并所有被阻挡的空间，你可以尝试推导出一个允许这样一条线的未被遮挡空间的特征描述。 - G. Bach

如果我理解正确，那么对于一层的相对面而言，一条线可以穿过最多三个体素吗？ - Yola

Answer 1

对于这个（连续的？离散的？）空间中成为直线的确切参数，我有点不清楚，但我想知道你是否在寻找一种动态规划解决方案？

也许我们可以限制为二维左右的情况来构建算法，然后再进行概括：

循环遍历数组的第一列， 对于每个不透明的正方形，标记无法建立连接到该正方形的光线 对于每个非透明正方形，标记可以到达该正方形，并跟踪可到达该正方形的斜率范围。您可以通过可能到达体素体积另一端的斜率集来限制此初始化中的斜率集。

然后循环下一列 每个正方形可能被前一列中的任何正方形到达，但只有当可以到达前一列中的正方形的斜率范围与从前一列中的正方形到达当前正方形所需的斜率范围相交时才能到达当前正方形。
因此，您将当前正方形的有效斜率范围设置为先前正方形的有效范围与到当前正方形的有效范围的交集的联合。

继续循环列，直到达到远端，任何可到达远端的条目都将报告允许命中该正方形的向量斜率范围。

该算法的速度严重依赖于您如何快速地联合和交叉斜率范围（或在3D情况下，UV坐标的任意范围）。在2D连续空间中，可以通过排序来快速完成此操作，在3D离散空间中，可以使用一组可能的矢量斜率，在X、Y上依赖于您的体素空间的尺寸。在3D连续空间中，某种四叉树可能会接近2D排序所能实现的内容。

该算法对输入中的每个单元格循环一次（您是否认为这是O(n)还是O(n^3)?），并将时间限制为交集调用时间与空间元素数量的并集（在离散情况下最坏情况是O(n^2)，但如果体积的相反端点远离，则初始化步骤中将大大缩小，并且在许多不透明单元和适当的数据结构的情况下，可能会迅速缩小）。

据我所知，卷的处理顺序实际上并不重要，因此，如果您知道某些位置非常不透明（通过不透明单元的总和或其他方式），则可以使用启发式方法重新排列交集操作。

- dhakim

Answer 2

一个体素立方体看起来像一个魔方，体素结构是一个由块组成的三维矩阵，所以要从一侧画一条线到另一侧，我们需要在每个相关的块内绘制连接到下一个块的线条，这些线条共同形成了一个穿过立方体的连续线。

如果实现得好，以下算法可以正常工作，因为您将在立方体的局部坐标系中工作，任何对立方体本身的变换都将在3D引擎将其转换为世界坐标时自动应用。 时间复杂度

MATRIX.MAX_Z * (
                   Time(MATRIX.GET_VOXEL(x,y,z))
                 + Time(VOXEL.DRAW-LINE(0,0,0, 0,0,VOXEL_DEPTH))
               )

算法

FUNCTION DRAW (INTEGER X, INTEGER Y)

    INTEGER VOXEL_X = X / MATRIX.VOXEL_WIDTH
    INTEGER VOXEL_Y = Y / MATRIX.VOXEL_HEIGHT

    FOR i = 0 .. (MATRIX.MAX_Z-1)

        VOXEL V = MATRIX.GET_VOXEL(VOXEL_X, VOXEL_Y, i)

        INTEGER X_0 = X % MATRIX.VOXEL_WIDTH
        INTEGER Y_0 = Y % MATRIX.VOXEL_HEIGHT
        INTEGER Z_0 = 0

        INTEGER X_1 = X_0
        INTEGER Y_1 = Y_0
        INTEGER Z_1 = (MATRIX.VOXEL_DEPTH-1)

        V.DRAW-LINE(X_0,Y_0,Z_0, X_1,Y_1,Z_1)

    END-FOR

END-FUNCTION

- Khaled.K

Answer 3

将问题分解为二维，很明显有些体素配置是无法从左到右穿透的：

    +-+-+-+          +-+-+-+-+-+
    | |#| |          |#| | | | |
    +-+-+-+          +-+-+-+-+-+
    | |#| |          |#| | |#| |
    +-+-+-+          +-+-+-+-+-+
    | |#| |          |#| | |#| |
    +-+-+-+          +-+-+-+-+-+
                     |#| | |#| |
                     +-+-+-+-+-+
                     | | | |#| |
                     +-+-+-+-+-+

...但这可能不是不可渗透的，这取决于您如何处理角落：

  +-+-+-+-+-+
  |#| | | |/|
  +-+-+-+-+-+
  |#| | |/| |
  +-+-+-+-+-+
  |#| |/|#| |
  +-+-+-+-+-+
  |#|/| |#| |
  +-+-+-+-+-+
  |/| | |#| |
  +-+-+-+-+-+

... 这绝对是可能的：

  +-+-+-+-+-+
  |#| | | | |
  +-+-+-+-+-+
  |#| | | | |
  +-+-+-+-+-+
  |#| | | | |
  +-+-+-+-+-+
  | | | |#| |
  +-+-+-+-+-+
  | | | |#| |
  +-+-+-+-+-+

现在，如果你能想到任何方法来区分上面的2D立方体和下面的立方体，那么可能会消除一些不可能的像素/体素配置 - 但我担心你需要测试目标侧的每个像素是否从任何角度透过光线从源侧穿过，这听起来非常像一个n平方问题（2D），或者在3D中是n的四次方。

在2D中，我会从左侧顶部开始，检查连接我的体素中心到右上角的线是否击中了遮挡像素：如果没有，我们就完成了；如果有，您需要调整角度，使射线通过遮挡物的左下角并继续检查，直到找到通道或到达右侧的末端。

继续处理源侧的每个像素，直到完成 - 无论如何都要这样做。

但这是蛮力法，我很想看到更优雅的解决方案，也许由G. Bach提供...？

- Christian Severin

Answer 4

因此，进行此测试的一种简单方法是以任意分辨率从源立方体渲染到目标立方体的视图（正交）。如果还剩下任何背景像素，则存在两个矩形之间的线。因此，复杂性归结为两件事：

• 您渲染的分辨率
• 您可以多快地呈现正交二进制视图

现在对于二进制渲染，您唯一需要知道的是覆盖/未覆盖。这归结为两个八叉树，一个用于最小值，一个用于最大值。最小树跟踪“是否有任何打开的子节点（或）”，最大树跟踪“是否有任何关闭的子节点（和）”。构建这些树是n log（n），但查询仅为log（n）。

对于目标分辨率m，它应该只是log（m）。即使您将其提高到float大小的m = 2 ^ 23。

- starmole

---

很抱歉，我不明白您所说的“源立方体”和“目标立方体”，也不了解开放或关闭的子节点。如果您从光线追踪的角度来考虑这个问题，仍然需要检查目标立方体上每个像素是否有来自任何角度的光线，即源立方体上的任何像素。听起来对我来说是O(n^4)的复杂度... - Christian Severin