5

有没有办法在 3d 体素网格中松散地描述对象（例如，通过模式匹配有限自动机），就像我们可以用正则表达式松散地描述一维字符串中的模式一样？

假设我想描述一个“A”型体素的长方体，其下侧面由“B”或“C”型体素组成，高度为 3，宽度为 5，并将此描述与体素字段匹配以查找模式示例。我可以对精确模型进行一些搜索（类似于 Boyer-Moore-in-3D），但我需要为某些对象指定可变尺寸（例如上述长方体的可变长度）。

4

2 回答 2

5

正则表达式是一种简洁的方式来表达有限（并且仍然是无限）语言集的语法。使用正则表达式，您不需要告诉在哪里寻找下一个符号，因为众所周知，您正在处理一个字符串并迭代其字符，将它们作为语言的符号......但在 3D 中，您将需要告诉走什么路。

您可以将其视为 3D 图灵机，即具有内部状态并可以从 3D“磁带”读取符号的图灵机，因为我们只是验证让我们忽略写入磁带。然后，这台图灵机将走 3D“磁带”，也就是 3D 体素网格，读取体素作为符号，在读取每个符号后，图灵机的内部状态会根据一定的规律发生变化。一旦执行结束，机器的最终状态会告诉您它是否匹配。现在，冯纽曼架构中的这些定律是将磁带中的数据解释为指令，但我们想要一个哈佛架构，即指令与数据分离。现在你想要的是一种描述图灵机指令的方法。

遵循正则表达式的精神，我们更喜欢一种类似于实际结构的语言。如果我们让它基于文本，它将是一种描述性语言（因为命令式语言并不比你最喜欢的图灵完备的语言更好），它必须例如（用英语）说：

There is a voxel type A and then moving (x1, y1, z1) from that there is a voxel of type B or C and then moving (x2, y2, z3) from that there is a voxel type D

这描述了图灵机正在寻找的东西，使用回溯算法测试所有可能的匹配，它将按预期工作。

请注意，我不知道体素的可能值集。也就是说，我不知道字母表。所以我刚才说了A型、B型、C型和D型作为例子，其中一个可能是没有体素的表示，其他的可能是颜色或你正在使用的任何东西。可以根据需要有多种类型的体素。如果体素的类型很复杂，则必须在其中插入对它的描述。

我一直在考虑实际使用这种语言，一个很快出现的问题是旋转，我必须决定 X 轴上的三个体素类型 A 被认为与 Z 轴上的三个体素类型 A 相同，更好的是允许用语言来描述。

如果体素是节点，现在描述路径非常相似，我已经做了一种语言来描述 2D 路径作为私有项目的一部分（将它们存储在数据库中，去图......），非常简单，它为每个方向保留一个字符，并为步骤使用一个数字，例如：“2d5l1u”。对 3D 做同样的事情并添加一种分组和匹配的方式就可以了。为了解决旋转问题，有必要扩展方向以允许析取来表达匹配的替代配置。在我想到的一些关于它如何工作的例子中，这将变得更加清晰（我没有在 EBNF 或类似中使用过正式的语法）：

在 X 轴上匹配一条由三个体素类型 A 组成的线：

(A1X){3}

这里我插入匹配“A”与运动“1X”，使用括号“（”和“）”进行分组，并使用大括号“{”和“}”进行量化。这展开为：

A1XA1XA1X

最后一个“1X”不影响结果，所以也可以是：

A1XA1XA

它清楚地表明：匹配 A 型体素，在 X 上移动 1 并匹配 A 型体素，在 X 上移动 1 并匹配 A 型体素。

在 X 轴或 Z 轴上匹配由三个体素类型 A 组成的线：

(A1X){3}|(A1Z){3}

选择：

(A1[X|Z]){3}

这里我使用括号“[”和“]”来创建一个“类”，它的位置告诉它方向，它只包括可能的轴，不要混淆：

[(A1X)|(A1Z)]{3}

这将匹配三个体素类型 A，但它们可能不在同一轴上，它们只需要连续并与其邻居共享 X 轴或 Z 轴。

在平面 X、Y 上匹配一组 3x3 体素类型 a：

(((A1X){3})1Y){3}

这匹配 X 轴上的一条线，并在 Y 轴上移动 1 以匹配另一条线，依此类推。这意味着在对重复“（[（A1X）]{16}）”进行分组后，我们会回溯到比赛开始执行以下移动“1Y”的位置。展开它将是：

(A1XA1XA1X)1Y(A1XA1XA1X)1Y(A1XA1XA1X)1Y

看剩下的括号，那些意味着回溯到比赛开始的地方。所以程序将检查组内的内容，完成后它将回到进入组之前的位置并在之后继续执行。

匹配由忽略类型的体素分隔的一对体素类型 A（在任何轴上）：

A1(X|Y|Z).1(X|Y|Z)A1(X|Y|Z)

受正则表达式的影响，我们使用点“.”。表示任何类型的体素。

我仍然不决定使用负值是否比其他轴使用其他字母更好，而且我认为数字 1 可能是可选的。还有正则表达式语法的其他部分，例如“+”、“*”和“?” 必须更加小心。在证明没有歧义之前，对任何量化强制执行“{”和“}”可能会很好。

您可能已经注意到，添加另一个运动方向或完全是另一个轴不会有问题，所以这个端口很好地说是四个维度，如：

(A1[X|Y|Z|W]){3}

使用点“。”也可能很好。代表任何方向：

(A1.){3}

在未指定时假设任何方向存在一个问题，即定义此语言以识别什么是方向并根据表达式内部的位置将它们与体素类型区分开来。所以“(A1B1){3}”不会映射到“(A1.B1.){3}”，因为它会以“B”作为移动方向，或许可以通过后面的数字来推断含义结束，但我不知道它是否会明确。

最后，这将匹配由 A 型体素组成的平面 X、Y 中的任何有效俄罗斯方块：

(A1[X|Y]){4}

如果我们假设世界只是二维的并且我们允许忽略第一个，它会简化为：

(A.){4}

我对此很满意。不过，对于复杂结构，您应该考虑使用更复杂、更简洁、更易读的符号。

这就是我将正则表达式推广到两个、三个或更多维度的理论。

编辑：

如果体素的类型很复杂或引起歧义，我建议用尖括号“<”和“>”来编写它，例如，您可以使用原始体素数据的十六进制值：

(<0088FF>.){4}
于 2012-01-09T04:20:28.713 回答
2

我对 3D 或体素了解不多，但如果您可以使用标记将 3D 空间转换为一维表示，那么您可以在其上使用正则表达式。

简化示例：

对于具有蓝色面、红色面、绿色面和其他 3 个我们不关心的立方体：

<object>
    <cube>
        <faces>
            <face orientation="up" color="blue">
                <border neighborOrient="west">
                <border neighborOrient="south">
            <face orientation="west" color="red">
            <face orientation="south" color="green">
            ...
        </faces>
    </cube>
</object>

您的正则表达式可以在同一个多维数据集中查找共享边界的面孔。正则表达式最适合文本，因此您的第一步应该是找到一种“扁平化”为文本的方法。

于 2011-12-22T20:03:36.537 回答