在 3D 环境中识别模式
Recognize pattern in 3D environment
我目前正在开发第三人称建筑游戏（作为学士或论文）。我需要识别构造模式，因为我可以将相应的结构标记为某个建筑物（这样玩家就可以开始使用该建筑物）。
我有以下规则：
- 3种积木（均以立方体为基础）（以后还会有更多种类）
- 任何块都可以在每个轴上放大到 k 倍数 (k = 20)
- 方块可以通过任何轴旋转（但保持在 3D 网格中）
Problem definition:
4 cubes of base size (1,1,1) in a grid 2x2 should be equivalent to 1
box size (2,2,1), so all possible variants (mainly different in rotation) could be evaluated as valid pattern construction.
我预计我的图案将达到基本尺寸的 30x30x30 倍数。
例如，我想识别这样的结构：（当前手动放置在关卡中）
大小为 21x21x22，由多个对象构成。
作为限制，我将从确切的点开始搜索边界模式（比如说 控制台 该结构）。限流常数约为基本立方体的 50x50x50 倍数。 （限制可能会根据此处的答案发生变化。）
我搜索了 20 多个小时，结果只有从 2D 图像识别 3D 结构或在 2D 中识别精确结构的论文。
My problem is that with growing K( each X,Y,Z) there is exponencially growing number of structures, which should be accepted as correct pattern construction.
Question: What algorithm (+ heurestic) should I use?
以下 3 张图像包含结构的可视化，被认为是图像 4 中图案的正确变体，因此应该找到并接受它们。
全部具有相同的最终形状（并且在相同的地方具有相同的 material）。我只将问题简化为 2D 形状，但在 3D 中延伸 space 是显而易见的。
感谢您的所有回答/评论。
我会编写一个函数来检查 1x1x1 区域是否具有特定形状（完整块、半块 + 旋转、边缘块 + 旋转），然后以这种方式定义和检查图案。
如果每个轴可以缩放的构建块都可以细分为更小的 1x1x1 构建块，并且如果以下条件充分描述了构建结构是否应与给定模板匹配：
- 任意细分模板构建块不应导致不匹配
- 任意 "extruding through" 任何 axis-aligned 平面（想象在某个 axis-aligned 平面切开世界，然后将两半拉开，同时新物质不断填充点之间的间隙最初是接触的）不应导致不匹配
- 任何其他差异都会造成不匹配
那么应该可以在时间 O(b + t^2) 内有效地识别模板结构的构建实例，其中 b 是构建结构的体素体积，t 是（通常非常小；参见下面）模板的体素体积。基本思想是将任何构建结构转换为规范形式，其中任何 "extruded range" 都被压缩到长度上的单个体素。
原子化然后规范化
首先，将构建结构中的所有构建块原子化为等效的 1x1x1-building-block 形式。下一步，压缩扩展范围，本质上与从排序列表中消除重复项的算法相同，但在 3D 中：
- 对于每个轴 d (X, Y, Z)：
- 设 j = 1。
- 对于 i 从 1 到轴 d 中的最大值 co-ord：
- 是在 co-ord i 处的建筑结构的平面体素 "slice" 在轴 d 上（例如，如果 d 是 Y，则所有体素的集合 (x, i, z) x 和 z) 与 co-ord i-1 处的 "slice" 相同？
- 如果不是，则将 co-ord i 处的切片复制到 co-ord j 处切片的顶部，然后递增 j。
这将生成构建结构的规范版本，其中所有相邻切片都不同；通常这个版本会小得多，因为所有 "long" 特征都折叠到长度 1。这里 j 的作用是指向我们可以放置下一个 non-identical 切片的最早位置。由于 j <= i 总是，我们永远不必担心覆盖我们尚未处理的切片。另请注意，路线的处理顺序无关紧要，最终结果是相同的。
在一开始就应该对每个模板结构应用相同的规范化过程作为预处理。现在可以通过 brute-force voxel-by-voxel 比较直接比较两种规范形式（模板和构建结构）（基本上类似于 strstr()，但在长方体内部寻找长方体而不是在长方体内部寻找字符串一个字符串）。此时也应尝试应被视为有效转换的任何旋转或翻转。
特点和注意事项
给定模板
X.X
XXX
它将识别例如以下为匹配项，
X.X
X.X XXX XX
X.X XXXXXXX
XXX XXXXXXX
但不是例如
X..
X.X
X.X
XXX
但是如果你想检测这种有different-length条腿的U-shaped结构，你只需要提供一个额外的模板：
X..
X.X
XXX
此模板将匹配所有具有 different-length 分支的 U-shaped 结构（但 不会 U-shaped 具有 equal-length 分支的结构！ ).根据您考虑的旋转方式，您可能还需要镜像。
AABB 相交的结构将无法正确处理。这些可以在前面的步骤中很容易地分开。
有趣的是，该算法能够识别包含多个连接组件的结构。例如，模板
X.X.X
将识别三个 equal-size 排成一行（或列，如果允许旋转）的长方体。
我目前正在开发第三人称建筑游戏（作为学士或论文）。我需要识别构造模式，因为我可以将相应的结构标记为某个建筑物（这样玩家就可以开始使用该建筑物）。
我有以下规则：
- 3种积木（均以立方体为基础）（以后还会有更多种类）
- 任何块都可以在每个轴上放大到 k 倍数 (k = 20)
- 方块可以通过任何轴旋转（但保持在 3D 网格中）
Problem definition: 4 cubes of base size (1,1,1) in a grid 2x2 should be equivalent to 1 box size (2,2,1), so all possible variants (mainly different in rotation) could be evaluated as valid pattern construction.
我预计我的图案将达到基本尺寸的 30x30x30 倍数。
例如，我想识别这样的结构：（当前手动放置在关卡中）
作为限制，我将从确切的点开始搜索边界模式（比如说 控制台 该结构）。限流常数约为基本立方体的 50x50x50 倍数。 （限制可能会根据此处的答案发生变化。）
我搜索了 20 多个小时，结果只有从 2D 图像识别 3D 结构或在 2D 中识别精确结构的论文。
My problem is that with growing K( each X,Y,Z) there is exponencially growing number of structures, which should be accepted as correct pattern construction.
Question: What algorithm (+ heurestic) should I use?
以下 3 张图像包含结构的可视化，被认为是图像 4 中图案的正确变体，因此应该找到并接受它们。
全部具有相同的最终形状（并且在相同的地方具有相同的 material）。我只将问题简化为 2D 形状，但在 3D 中延伸 space 是显而易见的。
感谢您的所有回答/评论。
我会编写一个函数来检查 1x1x1 区域是否具有特定形状（完整块、半块 + 旋转、边缘块 + 旋转），然后以这种方式定义和检查图案。
如果每个轴可以缩放的构建块都可以细分为更小的 1x1x1 构建块，并且如果以下条件充分描述了构建结构是否应与给定模板匹配：
- 任意细分模板构建块不应导致不匹配
- 任意 "extruding through" 任何 axis-aligned 平面（想象在某个 axis-aligned 平面切开世界，然后将两半拉开，同时新物质不断填充点之间的间隙最初是接触的）不应导致不匹配
- 任何其他差异都会造成不匹配
那么应该可以在时间 O(b + t^2) 内有效地识别模板结构的构建实例，其中 b 是构建结构的体素体积，t 是（通常非常小；参见下面）模板的体素体积。基本思想是将任何构建结构转换为规范形式，其中任何 "extruded range" 都被压缩到长度上的单个体素。
原子化然后规范化
首先，将构建结构中的所有构建块原子化为等效的 1x1x1-building-block 形式。下一步，压缩扩展范围，本质上与从排序列表中消除重复项的算法相同，但在 3D 中：
- 对于每个轴 d (X, Y, Z)：
- 设 j = 1。
- 对于 i 从 1 到轴 d 中的最大值 co-ord：
- 是在 co-ord i 处的建筑结构的平面体素 "slice" 在轴 d 上（例如，如果 d 是 Y，则所有体素的集合 (x, i, z) x 和 z) 与 co-ord i-1 处的 "slice" 相同？
- 如果不是，则将 co-ord i 处的切片复制到 co-ord j 处切片的顶部，然后递增 j。
- 是在 co-ord i 处的建筑结构的平面体素 "slice" 在轴 d 上（例如，如果 d 是 Y，则所有体素的集合 (x, i, z) x 和 z) 与 co-ord i-1 处的 "slice" 相同？
这将生成构建结构的规范版本，其中所有相邻切片都不同；通常这个版本会小得多，因为所有 "long" 特征都折叠到长度 1。这里 j 的作用是指向我们可以放置下一个 non-identical 切片的最早位置。由于 j <= i 总是，我们永远不必担心覆盖我们尚未处理的切片。另请注意，路线的处理顺序无关紧要，最终结果是相同的。
在一开始就应该对每个模板结构应用相同的规范化过程作为预处理。现在可以通过 brute-force voxel-by-voxel 比较直接比较两种规范形式（模板和构建结构）（基本上类似于 strstr()，但在长方体内部寻找长方体而不是在长方体内部寻找字符串一个字符串）。此时也应尝试应被视为有效转换的任何旋转或翻转。
特点和注意事项
给定模板
X.X
XXX
它将识别例如以下为匹配项，
X.X
X.X XXX XX
X.X XXXXXXX
XXX XXXXXXX
但不是例如
X..
X.X
X.X
XXX
但是如果你想检测这种有different-length条腿的U-shaped结构，你只需要提供一个额外的模板：
X..
X.X
XXX
此模板将匹配所有具有 different-length 分支的 U-shaped 结构（但 不会 U-shaped 具有 equal-length 分支的结构！ ).根据您考虑的旋转方式，您可能还需要镜像。
AABB 相交的结构将无法正确处理。这些可以在前面的步骤中很容易地分开。
有趣的是，该算法能够识别包含多个连接组件的结构。例如，模板
X.X.X
将识别三个 equal-size 排成一行（或列，如果允许旋转）的长方体。