我目前正在开发第三人称建筑游戏(作为巴赫勒论文)我需要识别构造的模式,我可以将相应的结构标记为某个建筑(这样玩家就可以开始使用该建筑)。
我有以下规定:
3种积木(都是基于立方体的)(将来会有更多的类型)
在每个轴(k=20)中,任何块都可以缩放到k倍。
块可以由任意轴旋转(但保持在3D网格中)。
问题定义:
2x2网格中4个基本尺寸(1,1,1)的立方体应等于1
盒子大小(2,2,1),所以所有可能的变体(主要是旋转不同的)都可以作为有效的模式构造来评估。
我预计我的模式将是基础大小的30x30x30倍。
例如,我想识别这样的结构:(当前手动放置在水平位置)
大小为21x21x22,由多个对象构成。
作为一个限制,我将从精确的点边界模式搜索(比如说该结构的控制台)。电流限制常数约为基本立方的50x50x50倍。(根据此处的答案,限额可能会有变化。)
我搜索了20多个小时,结果只有从二维图像中识别三维结构或在二维图像中识别精确结构的论文。
我的问题是,随着K(每个X,Y,Z)的增长,结构的数量呈指数增长,这应该被认为是正确的模式构造
问题:我应该使用什么算法(+heurestic)?
以下3幅图像包含结构的可视化,这些结构在图像4中被认为是模式的正确变体,因此应该找到并接受它们。
所有这些都有相同的最终形状(在相同的地方有相同的材料)。我只把问题简化为二维形状,但在三维空间中扩展是显而易见的。
感谢您的回答/评论。
最佳答案
如果轴可以缩放的每个构建块可以细分为更小的1x1x1构建块,并且如果以下条件充分描述了构建的结构是否应与给定模板匹配:
任意细分模板构建基块不应导致不匹配
任意地“挤压”任何轴对齐的平面(想象在一些轴对齐的平面中穿过世界,然后将两个半部分开,而新的物质不断填充原来接触的点之间的间隙)不应导致不匹配。
任何其他差异都会导致不匹配
然后,应该可以在时间o(b+t^2)内有效地识别模板结构的已构建实例,其中b是已构建结构的体素体积,t是模板的体素体积(通常非常小;见下文)。其基本思想是将任何构建的结构转换为一种标准形式,在这种形式中,任何“拉伸范围”都被压缩为长度上的单个体素。
原子化然后规范化
首先,将已建结构中的所有构建块原子化为其等效的1x1x1构建块形式下一步,压缩挤出范围,本质上与从排序列表中消除重复项的算法相同,但在3d中:
对于每个轴d(x,y,z):
设置j=1。
对于I轴从1到最大坐标轴:
是在轴D上在Co ORD i上构建的结构的平面体素“切片”(例如,如果D是Y,那么所有x和z的体素(x,i,z)的集合)与紧邻的前一个“切片”在CO-ORD I-1上相同?
如果不是,则复制co ord i处的切片,并在co ord j处的切片顶部,然后递增j。
这将生成一个构建结构的规范版本,其中所有相邻的部分都是不同的;通常这个版本会小得多,因为所有“长”特性都折叠为长度1这里j的作用是指向最早的位置,在那里我们可以放置下一个不相同的切片。因为j作为预处理,相同的规范化过程应该在一开始就应用于每个模板结构现在,两种标准形式(模板和构建结构)可以通过一个强力体素逐体素比较直接进行比较(基本上类似于strstr()
,但要在一个长方体内寻找一个长方体,而不是在一个字符串中寻找一个字符串)。任何应该被视为有效转换的旋转或翻转也应该在此时尝试。
特点和注意事项
给定模板
X.X
XXX
它会将以下各项视为匹配项,
X.X
X.X XXX XX
X.X XXXXXXX
XXX XXXXXXX
但不是例如。
X..
X.X
X.X
XXX
但是,如果要检测具有不同长度支腿的此类U形结构,只需提供一个附加模板:
X..
X.X
XXX
此模板将匹配具有不同长度支腿的所有U形结构(但不匹配具有相同长度支腿的U形结构!)。根据您考虑的旋转,您可能还需要镜像。
aabbs相交的结构将无法正确处理。在前面的步骤中,这些可以很容易地分离。
有趣的是,该算法能够识别包含多个连接组件的结构。例如,模板
X.X.X
将识别一行(或列,如果允许旋转)中三个大小相等的长方体。
关于c++ - 在3D环境中识别图案,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/35048333/