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

Question

想象一下N3分辨率的体积立方体,其中充满了遮挡体素.立方体可以完全填满,或包含弯曲的"隧道",或墙壁 - 或只是一些流浪的体素; 我们现在选择边界立方体的六个面中的任意两个,并尝试找到连接这两个面的线而不击中其中的任何体素.如果存在这样的线条,则面部可以看到彼此,否则,它们将完全被遮挡.

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

Answer 1

体素立方体看起来像魔方，体素结构是块的 3D 矩阵，因此要从一侧到另一侧绘制一条线，我们需要在每个相关块内绘制连接到下一个块的线，将这些线连在一起形成一条穿过立方体的连续线。

如果实施得当，以下算法可以正常工作，因为您将在立方体内的局部坐标上工作，所以当 3D 引擎将其转换为世界坐标时，立方体本身的任何变换都将由 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