在立方体网格上进行光线投射？

Question

我正在 Unity 中编写一个体素游戏。

游戏世界是一个 3D 阵列体素（立方体）。

每个体素可能是空的或被占用的。

我需要从世界上的任何一点投射光线，并找出它将首先击中占据的体素表面的位置。

public struct Vector3 {
    public float x, y, z;
}

public struct Vector3Int {
    public int x, y, z;
}

public enum Voxel {
    Empty,
    Occupied,
}

public struct RaycastResult {
    public bool success;  // whether any block was hit by raycast
    public Vector3 point;  // point where ray hits the surface of first solid voxel
    public Vector3Int block;  // what block was hit by raycast
}

public class World {
    public Voxel[,,] voxels;

    public Voxel GetVoxel(Vector3Int position) {
        return voxels[position.x, position.y, position.z]
    }

    public RaycastResult Raycast(Vector3 origin, Vector3 direction) {
        // What to do here?
    }
}

我使用什么算法来确定这一点？

是否有一种（有效的）方法可以统一执行此操作，而无需编写自己的光线投射器？请注意，世界的大小可能非常大。

如果没有好的内置解决方案，有通用算法吗？

Answer 1

以下是一些基本原则。您需要对线性代数相当熟悉才能尝试此操作，并阅读并理解射线平面相交如何工作。

您的光线将从立方体内部开始，在离开立方体时会击中 6 个面之一。在正常情况下，我们只需检查射线方向是否与立方体面指向同一方向，就可以快速消除其中三个面。这是通过检查向量之间的点积的符号来完成的。为了找到剩余三个面中的第一个击中，我们对相应的平面进行相交测试，并选择最接近的一个，如果你知道击中的面，你就知道它击中了哪个立方体。如果该立方体是空的，则重复该过程，直到找到非空的立方体。您还可以添加一些检查以避免边缘情况，例如尽早消除与光线平行的所有平面。

但是，要获得真正的速度，您确实需要某种树结构来减少检查的数量。有很多替代方案，kd 树、r 树等，但在这种特定情况下，我可能会考虑稀疏八叉树。这意味着您的立方体将成为更大的 2x2x2 部分的一部分，其中整个部分可以标记为空、填充、部分填充等。这些部分也将被分组为更大的 2x2x2 部分等等，直到您达到某个最大尺寸包含您的整个游乐区域，或游乐区域的一个独立可加载单元，并具有一些逻辑来测试多个单元（如果需要）。

光线投射的完成方式或多或少与简单情况下的八叉树相同，只不过您现在拥有可变大小的立方体。当你击中一个面时，你需要遍历树来找到下一个要测试的立方体。

但是要真正对此进行良好的优化实现，需要大量的经验，无论是在所涉及的概念方面，还是在语言和硬件方面。您可能还需要深入了解实际游戏世界的结构，因为您可能可以采取一些不明显的捷径来显着提高性能。因此，不能保证您的实施会比内置的 Unity 更快。