Recognize pattern in 3D environment

Question

I'm currently developing 3rd person building game (as bacheleor thesis). I need to recognize constructed patterns co I can mark corresponding structure as some building (so player can start using that building).

I have folowing rules:

• 3 types of building blocks (all based on cube) (and in future there will be more types)
• any block can be scaled up to k multiple in each axis (k = 20)
• blocks can be rotated by any axis (but stays in 3D grid)

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.

I expect that my patterns will be up to 30x30x30 multiple of base size.

For example, I'd like to recognize structure like this: (currently placed in level by hand) Size is 21x21x22 and it is constructed from multiple objects.

As a limitation, I will border pattern search from exact point (lets say control console for that structure). Current limitation constant is around 50x50x50 multiple of base cube. (Limit is subject to change based on answers here.)

I searched over 20hrs and result was only papers to recognize 3D structure from 2D image or recognize exact structure in 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?

Following 3 images contains visualization of structures, that are considered as correct variant of pattern at image 4, thus they should be found and accepted.

All together has same final shape (and has same material at same places). I simplified the problem only to 2D shape, but extending in 3D space is obvious.

Thank you for all answers / comments.

Answer 1

If every building block whose axes can be scaled can be subdivided into smaller 1x1x1 building blocks, and if the following conditions adequately describe whether a built structure should match a given template:

• Arbitrarily subdividing a template building block should not cause a mismatch
• Arbitrarily "extruding through" any axis-aligned plane (imagine slicing through the world in some axis-aligned plane and then pulling the two halves apart, while new matter continuously fills in the gaps between points that were originally touching) should not cause a mismatch
• Any other difference forces a mismatch

then it should be possible to efficiently recognise built instances of a template structure in time O(b + t^2), where b is the voxel volume of the built structure and t is the (typically very small; see below) voxel volume of the template. The basic idea is to transform any built structure into a canonical form in which any "extruded range" is compacted down to a single voxel in length.

Atomise then canonicalise

First, atomise all building blocks in the built structure down to their equivalent 1x1x1-building-block forms. The next step, compacting extruded ranges, is essentially the same algorithm as for eliminating duplicates from a sorted list, but in 3D:

• For each axis d (X, Y, Z):
  • Set j = 1.
  • For i from 1 to the maximum co-ord in axis d:
    • Is the planar voxel "slice" of the built structure at co-ord i on axis d (e.g., if d is Y, then the set of voxels (x, i, z) for all x and z) identical to the immediately preceding "slice" at co-ord i-1?
      • If not, copy the slice at co-ord i on top of the slice at co-ord j, and then increment j.

This will produce a canonical version of the built structure in which all adjacent slices are different; typically this version will be much smaller, since all "long" features are collapsed to length 1. The role of j here is to point to the earliest location where we can put the next non-identical slice. Since j <= i always, we never have to worry about overwriting a slice we haven't processed yet. Also note that it doesn't matter in which order the directions are processed, the final result is the same.

The same canonicalisation process should have been applied to each template structure at the outset as preprocessing. Now the two canonical forms (template and built structure) can be compared directly via a brute-force voxel-by-voxel comparison (basically like strstr(), but looking for a cuboid inside a cuboid instead of a string inside a string). Any rotations or flips that should be considered valid transformations should also be tried at this point.

Features and caveats

Given the template

X.X
XXX

it will recognise e.g. the following as matches,

X.X
X.X   XXX  XX
X.X   XXXXXXX
XXX   XXXXXXX

but not e.g.

X..
X.X
X.X
XXX

But if you want to detect such U-shaped structures with different-length legs, you need only supply an additional template:

X..
X.X
XXX

This template will match all U-shaped structures with different-length legs (but not U-shaped structures with equal-length legs!). Depending on which rotations you consider, you may also need the mirror image.

---

Structures whose AABBs intersect won't be handled correctly. These can be separated easily enough in a prior step.

---

Interestingly enough, this algorithm is capable of recognising structures that comprise more than one connected component. For example, the template

X.X.X

will recognise three equal-size cuboids in a row (or column, if rotations are allowed).