在体素空间上的正则表达式

Question

有没有办法在3d体素网格中松散地描述一个对象(例如通过模式匹配有限自动机),就像我们可以用regexp松散地描述一维字符串中的模式一样？

假设我想要描述具有下部小平面的"A"型体素的长方体,其由具有高度3和宽度5的"B"或"C"型体素组成,并且将该描述与体素场匹配以找到图案的示例.我可以搜索精确模型(类似Boyer-Moore-in-3D),但我需要为某些对象指定可变尺寸(如上述长方体的可变长度).

Answer 1

正则表达式是表达有限（并且仍然是无限）语言集的语法的一种紧凑方式。使用正则表达式，你不需要告诉在哪里寻找下一个符号，因为众所周知你正在处理一个字符串并迭代它的字符，将它们作为语言的符号......但在 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 型体素相同，更好的是允许在语言中描述它。

现在，如果体素是节点，那么描述路径非常相似，我已经做了一种语言来描述二维路径作为私有项目的一部分（将它们存储在数据库中，去图......），它非常简单，它为每个方向保留一个字符，并为步数使用一个数字，例如：“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}

Answer 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>

您的正则表达式可以查找同一立方体内共享边框的面。正则表达式最适合文本，因此您的第一步应该是找到一种“扁平化”文本的方法。