3
\$\begingroup\$

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) target pattern structure 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?

EDIT: 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. enter image description here enter image description here enter image description here enter image description here

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.

\$\endgroup\$
10
  • \$\begingroup\$ Just to make sure, you have 1 type of cube, that can be placed into patterns 30x30x30, that you need to recognize? Something like building a structure in Minecraft of a single block type and figuring out what it is? \$\endgroup\$ Commented Jan 27, 2016 at 16:49
  • \$\begingroup\$ @PearsonArtPhoto No, I have 3 types of building block, each of them is based on cube and curently it is not allowed to have multiple blocks overlaping (if you look at the picture, corners looks cutted, but edges are different block and cube vertex is another block.) And each of this shape can be modified by multiplying base size ( maximum is 20x20x20), so potentialy you can get 20^3 variants. (Visually there aren't this number of combinations, you can imagine that cube (1,1,10) differs only in rotation from cube (10,1,1) or (1,10,1)) \$\endgroup\$ Commented Jan 27, 2016 at 17:02
  • \$\begingroup\$ What would be an example of the type of pattern you are looking for? Exact pattern matching, pattern matching with some errors? You might even get better answers at dsp.stackexchange.com \$\endgroup\$ Commented Jan 27, 2016 at 17:06
  • \$\begingroup\$ @PearsonArtPhoto: I extended my Q, I hope it will be much clearer now. \$\endgroup\$ Commented Jan 27, 2016 at 17:36
  • \$\begingroup\$ I feel stupid, but I don't understand what you are trying to do, you want to extract a 3D re-usable pattern from a 2D visualization ? is that it ? \$\endgroup\$ Commented Jan 28, 2016 at 10:24

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.