3D 体积的数据结构和算法？

Question

我一直在修补一些 Minecraft Bukkit 插件开发，目前正在研究一些东西，我需要能够定义空间“体积”并确定实体（玩家）何时从该体积外部移动到内部（或反之亦然）。

如果我将“体积”限制为盒子，那么它应该很简单。 数据结构可以只维护 X/Y/Z 边界整数（因此总共 6 个整数），并且计算给定两个点（从移动开始和移动到）的进入/退出应该只是确定是否 A) 所有三个 To 值都为问题在所有三个范围内，并且 B) 至少有一个 From 值超出其相应范围。

（尽管如果有更好、更高效的方法来存储和计算它，我洗耳恭听。）

但是，如果“体积”不是一个简单的盒子怎么办？ 假设我有一个形状奇怪的房间，并且想要封闭该房间的体积。 我可以单独安排多个“卷”来填充整个空间，但是当一个实体从一个实体移动到另一个实体时，这会导致误报。

之前没有从事过游戏或 3D 引擎工作，我对如何构建这样的东西一无所知。 但我突然想到，这可能是一个已经解决的问题，并且已经确定了既定的模式。 本质上，我正在尝试：

1. 定义一个可以表示奇特形状的空间体积的数据结构（尽管至少基于块坐标）。
2. 定义一种算法，在给定移动源和目的地的情况下，可以确定移动是否跨越了定义空间的边界。

这方面有既定的模式和实践吗？

Answer 1

我不知道这是否曾在任何类型的视频游戏中使用过，但首先想到的是经典的Eratosthenes实现的筛子，唯一的变化是使

boolean

数组为3D ，并使用按键作为坐标。显然，虽然

x

和

y

值在 Minecraft 中可能很大，但您可能希望通过保存世界

0,0

位置和您的选择之间的偏移量来节省空间，如下所示：

class OddArea
{
    static final int MAX_SELECTION_SIZE = 64; //Or whatever

    public final int xOffset, yOffset;

    // 256 = Chunk height
    public final boolean[][][] squares = new boolean[MAX_SELECTION_SIZE][MAX_SELECTION_SIZE][256];

    OddArea()
    {
        this(0, 0);
    }

    OddArea(final int xOffset, final int yOffset)
    {
        this.xOffset = xOffset;
        this.yOffset = yOffset;
    }

    void addBlock(final int x, final int y, final int z)
    {
        this.squares[x - this.xOffset][y - this.yOffset][z] = true;
    }

    boolean isInsideArea(final int x, final int y, final int z)
    {
        return this.squares[x - this.xOffset][y - this.yOffset][z];
    }
}

z

不需要偏移，因为 Minecraft 世界只有 256 个方块高。

我能想到的此设置的唯一问题是，在开始填充对象之前，您必须知道最低的

x

,

y

坐标

Answer 2

一般来说，您应该使用类似于 kd 树 的数据结构。您可以将体积表示为立方体或球体的联合，并且应该很容易评估对象是否进入体积。

顺便说一句，要计算两个球体是否相交，请检查中心之间的距离是否小于半径之和。

Answer 3

使用基于体素的方法是在 Minecraft 中定义复杂的非矩形体积的一种方法。为此，体积被表示为稀疏数据结构或 3D 数组，其中每个元素表示某个体素（块）是在体积内部还是外部。将检查移动之前和之后的体素坐标，以确定实体何时跨越边界。如果起始位置 ({From}) 指示为外部且结束位置 ({To}) 标记为内部（反之亦然），则实体已越过边界。对于大型或高度复杂的体积，此技术可能会占用大量内存，但它很准确，并且可以直接映射到基于网格的 Minecraft 世界。