Expresión regular en voxel space

Question

¿Existe alguna manera de describir un objeto de forma más vaga (mediante un patrón que coincida con autómatas finitos, por ejemplo) en una red vóxel 3D de la misma manera que podemos describir patrones en cadena unidimensional con expresiones regulares?

Digamos que quiero describir un cuboide de voxels de tipo "A" con faceta inferior compuesta de voxels de tipo "B" o "C" con altura 3 y ancho 5, y hacer coincidir esta descripción con el campo de vóxel para encontrar ejemplos de patrón. Puedo hacer una búsqueda de modelos exactos (tipo-de-como-Boyer-Moore-en-3D) pero necesito especificar dimensiones variables para algunos objetos (como la longitud variable para el cuboide mencionado anteriormente).

Answer 1

No sé mucho sobre 3D o vóxeles, pero si puede transformar su espacio tridimensional en una representación unidimensional con un marcado, entonces puede usar una expresión regular en él.

ejemplo simplificado:

Para un cubo con una cara azul, cara roja, la cara verde, y 3 otros que no se preocupan por:

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

Su expresión regular podría buscar caras dentro del mismo cubo que comparte un borde. Las expresiones regulares funcionan mejor con texto, por lo que su primer paso debe ser encontrar una forma de "aplanar" hacia abajo al texto.

Answer 2

Las expresiones regulares son una forma compacta de expresar la sintaxis de un conjunto de idiomas limitado (y aún infinito). Con las expresiones regulares no necesita indicar dónde buscar el siguiente símbolo, ya que se sabe que está trabajando en una cadena e iterando sobre sus caracteres tomándolos como símbolos del idioma ... pero en 3D lo hará necesito decir qué camino tomar.

Puede pensarlo como una máquina 3D de Turing, que es una máquina de Turing que tiene un estado interno y puede leer símbolos de una "cinta" 3D, ya que solo estamos verificando ignoremos la escritura en la cinta. Luego, esta máquina de Turing recorrerá la "cinta" 3D, también conocida como la red vóxel 3D, y leerá los vóxeles como símbolos. Después de leer cada símbolo, el estado interno de la máquina Turing cambiará de acuerdo con ciertas leyes. Una vez que finaliza la ejecución, el estado final de la máquina le indica si se trata de una coincidencia o no. Ahora estas leyes en una arquitectura de Von Newman son una interpretación de los datos de la cinta como instrucción, pero queremos una arquitectura de Harvard, es decir, las instrucciones están separadas de los datos. Ahora lo que quiere es una forma de describir esas instrucciones para la máquina de Turing. [Puedes pensar en esto como la tortuga de Logo pero en 3D].

Siguiendo el espíritu de las expresiones regulares, preferiríamos un lenguaje que se asemeje a la estructura real. Si lo hacemos texto basado será un lenguaje descriptivo (porque uno imperativo no es mejor que el de Turing preferido termina uno), se tendrá que decir por ejemplo (en Inglés):

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 

Esto describe lo la máquina de Turing está buscando, con un algoritmo de retroceso que pruebe todas las coincidencias potenciales, funcionará como se espera.

Tenga en cuenta que no conozco el conjunto de posibles valores de los vóxeles. Es decir, no sé el alfabeto. Así que acabo de decir tipo A, tipo B, tipo C y tipo D como ejemplos, uno de ellos puede ser la representación de no voxel, y los otros pueden ser colores o lo que sea que esté usando. Puede haber tantos tipos de vóxeles como sea necesario. Si el tipo de vóxel es complejo, la descripción debe insertarse allí.

He estado pensando en el uso práctico de este tipo de lenguaje y un problema que surge muy rápidamente son las rotaciones, tengo que decidir que tres vóxeles tipo A sobre el eje X se consideran iguales a tres vóxeles tipo A sobre el Eje Z, mejor es permitir describir eso en el lenguaje.

Ahora es muy similar describir una ruta si los vóxeles son nodos, hice un lenguaje para describir caminos 2D como parte de un proyecto privado (para almacenarlos en una base de datos, vaya a la figura ...), es muy simple, reserva un personaje para cada dirección y usa un número para los pasos, por ejemplo: "2d5l1u". Hacer lo mismo para 3D y agregar una forma de agrupar y combinar hará. Para resolver el problema de rotación, será necesario ampliar la dirección para permitir disyunciones para expresar configuraciones alternativas para el partido. Esto quedará más claro en algunos ejemplos de cómo puede funcionar que he pensado (no he trabajado una sintaxis formal en EBNF o similar):

Coincidencia de una línea de tres vóxeles tipo A sobre el eje X:

(A1X){3} 

Aquí se intercalan a juego "a" con el movimiento "1X", utilice paréntesis "(" y ")" para la agrupación y las llaves "{" y "}" de cuantificar. Esto se desenrolla a esto:

A1XA1XA1X 

El último "1X" no afecta el resultado, por lo que puede ser también:

A1XA1XA 

Y dice claramente: partido de un tipo de un voxel, mover 1 sobre la X y hacer coincidir un voxel tipo A, mover 1 sobre la X y hacer coincidir un voxel tipo A.

Coincidencia de una línea de tipo tres voxels a sobre el eje X o el eje Z:

(A1X){3}|(A1Z){3} 

alternativa:

(A1[X|Z]){3} 

Aquí uso corchetes "[" y "]" para hacer una 'clase', la ubicación de ella dice que es sobre la dirección y solo incluye el eje posible, no confunda con:

[(A1X)|(A1Z)]{3} 

Esto coincidirá con tres vóxeles tipo A pero no pueden estar en el mismo eje, solo tienen que ser contiguos y compartir el eje X o el eje Z con el vecino.

a juego un conjunto de 3x3 de tipo voxels a sobre el plano X, Y:

(((A1X){3})1Y){3} 

Esto coincide con una línea sobre el eje X y los movimientos 1 sobre el eje Y para que coincida con otro y así sucesivamente. Implica que después de agrupar una repetición "([(A1X)] {16})" volvemos al punto donde la partida comenzó a ejecutarse con el siguiente movimiento "1Y". Para desenrollarlo sería:

(A1XA1XA1X)1Y(A1XA1XA1X)1Y(A1XA1XA1X)1Y 

Mira el paréntesis restante, esos medios para retroceder al lugar donde comenzó la coincidencia. Entonces, el programa verificará qué hay dentro del grupo y, cuando lo haga, volverá a estar donde estaba antes de ingresar al grupo y continuará ejecutándolo después.

Coincidencia de un par de tipo A voxels separadas por un voxel de tipo ignorado (sobre cualquier eje):

A1(X|Y|Z).1(X|Y|Z)A1(X|Y|Z) 

Bajo la influencia de las expresiones regulares que utilizamos el punto "" para representar cualquier tipo de vóxel.

Todavía no decido si es mejor usar valores negativos que usar otras letras para otros ejes, también considero que el número 1 podría ser opcional. También otras partes de la sintaxis de expresiones regulares como "+", "*" y "?" tiene que ser más cuidadoso. Puede ser bueno aplicar "{" y "}" para cualquier cuantificación hasta que se demuestre que no hay ambigüedad.

Como es posible que tenga cuenta de que no será un problema para agregar otra dirección del movimiento o totalmente otro eje, por lo que este puerto muy bien decir cuatro dimensiones, como en:

(A1[X|Y|Z|W]){3} 

También puede ser bueno usar el punto "." para representar cualquier dirección:

(A1.){3} 

Hay un problema con el supuesto de cualquier dirección cuando no está especificado y es que este lenguaje se define para identificar lo que es una dirección y distinguirlos de los tipos de voxel basado en la ubicación dentro de la expresión. Entonces "(A1B1) {3}" no se correlacionará con "(A1.B1.) {3}" porque tomará "B" como la dirección para moverse, puede ser posible inferir el significado por el número final en al final, pero no sé si será inútil.

Por último esta coincidirá con cualquier pieza de Tetris válido en el plano X, Y hecha de tipo voxels A:

(A1[X|Y]){4} 

Si asumimos que el mundo es sólo bidimensional y que nos permiten ignorar el número uno, se reduce a esto:

(A.){4} 

Y estoy contento con eso. Sin embargo, debería considerar una notación más compleja, menos compacta y más legible para estructuras complejas.

Y esa es mi teoría para generalizar expresiones regulares a dos, tres o más dimensiones.

EDIT:

Si el tipo de voxel es complejo o provoca ambigüedad propongo a escribir con soportes angulares "<" y ">", así que por ejemplo se puede utilizar el valor hexadecimal de la prima datos de voxel:

(<0088FF>.){4}