Hispanopedia Wiki
Articulo de referencia

Síntesis de modelos

Síntesis de modelos (también colapso de la función de onda o 'wfc' ) es una familia de algoritmos de resolución de restricciones comúnmente utilizados en la generación procedime...

Hispanopedia WikiContenido en espanolLectura gratuita

Síntesis de modelos (también colapso de la función de onda o'wfc' ) es una familia de algoritmos de resolución de restricciones comúnmente utilizados en la generación procedimental , especialmente en la industria de los videojuegos .

Síntesis del modelo/Textura generada por WFC
Un ejemplo de textura creada con WFC.
El mapa de bits de origen utilizado para generar la imagen anterior.

Algunos videojuegos que se sabe que han utilizado variantes del algoritmo incluyen Bad North , Townscaper y Caves of Qud .

El primer ejemplo de este tipo de algoritmo fue descrito por Paul Merrell, quien lo denominó «síntesis de modelos» por primera vez en su artículo de i3D de 2007 [ 1 ] y también lo presentó en la conferencia SIGGRAPH de 2008 y en su tesis doctoral de 2009. [ 2 ] El nombre « colapso de la función de onda » se popularizó posteriormente para una variante de dicho algoritmo, después de que una implementación de Maxim Gumin fuera publicada en 2016 en un repositorio de GitHub con ese nombre. [ 3 ] La implementación de Gumin popularizó significativamente este estilo de algoritmo, que fue ampliamente adoptado y adaptado por artistas técnicos y desarrolladores de juegos durante los años siguientes. [ 3 ]

La implementación de Gumin se inspiró en varias fuentes, incluyendo la tesis doctoral de Merrell y la transferencia de estilo de redes neuronales convolucionales . [ 4 ] [ 5 ] El nombre popular del algoritmo, «colapso de la función de onda», proviene de una analogía entre el método del algoritmo y el concepto de superposición y observación en mecánica cuántica . [ 6 ] [ 7 ] Algunas innovaciones presentes en la implementación de Gumin incluyeron el uso de patrones superpuestos, lo que permite usar una sola imagen como entrada para el algoritmo. [ 8 ]

Algunos han especulado que la razón por la que la implementación de Gumin resultó más popular que la de Merrell pudo deberse a la menor accesibilidad de la implementación de "síntesis de modelos", su enfoque en 3D o quizás a las limitaciones informáticas del público en general en ese momento. [ 9 ]

Una de las diferencias entre la implementación de Merrell y Gumin y el "colapso de la función de onda" radica en la decisión de qué celda "colapsar" a continuación. La implementación de Merrell utiliza un enfoque de línea de exploración, mientras que la de Gumin siempre selecciona como siguiente celda aquella con la entropía más baja. [ 10 ]

Descripción

El algoritmo WFC o de "síntesis de modelos" tiene algunas variantes. [ 6 ] Las implementaciones de Gumin y Merrell se describen a continuación, y se señalan otras variantes:

Implementación de Gumin

  1. Se lee el mapa de bits de entrada y se cuentan los patrones presentes en él.
  2. Se crea una matriz con las dimensiones de la salida deseada.
  3. Cada celda de la matriz se inicializa en un estado "no observado".
  4. Se repiten los siguientes pasos:
    1. La celda con el menor número de posibles estados de salida se encuentra
    2. 'Colapsa' esta célula en uno de sus posibles estados según las reglas.
    3. Comprueba que todas las celdas sigan siendo válidas y sigue las reglas.
  5. Una vez que todas las celdas se hayan "colapsado" en un estado definido, devuelva el resultado. Si el resultado no es válido, descártelo y repita el proceso hasta que sea válido.

La implementación de Merrell

La implementación anterior de Merrell es sustancialmente la misma que la de Gumin, con algunas diferencias menores.

(1) En la versión de Merrell, no es necesario seleccionar la celda con el menor número de estados de salida posibles para el colapso. En su lugar, se adopta un enfoque de línea de exploración. Según Merrell, esto resulta en una menor tasa de fallos del modelo sin ningún efecto negativo en la calidad. [ 10 ] Sin embargo, algunos comentaristas han señalado que el enfoque de línea de exploración para el "colapso" tiende a producir artefactos direccionales. [ 11 ]

(2) El método de Merrell ejecuta el algoritmo por partes, en lugar de hacerlo todo a la vez. Este método reduce considerablemente la tasa de fallos para muchos modelos grandes y complejos, especialmente en un espacio 3D. [ 10 ]

Desarrollos

En abril de 2023, Shaad Alaka y Rafael Bidarra, de la Universidad de Delft, propusieron el «Colapso de la función de onda semántica jerárquica». Básicamente, el algoritmo se modifica para funcionar más allá de conjuntos simples y no estructurados de teselas. Antes de su trabajo, todas las variantes del algoritmo WFC operaban sobre un conjunto plano de opciones de teselas por celda. [ 12 ]

Su enfoque generalizado organiza los conjuntos de teselas en una jerarquía, que consta de nodos abstractos llamados "meta-teselas" y nodos terminales llamados "teselas hoja". [ 13 ] Por ejemplo, en la primera pasada, WFC podría hacer que una determinada tesela sea una meta-tesela de tipo "castillo"; que en una segunda pasada se colapsará en otras teselas según una regla, por ejemplo, una tesela de "muro" o "césped".

Referencias

  1. ↑ Merrell, Paul (abril de 2007). «Síntesis de modelos basada en ejemplos». Actas del simposio de 2007 sobre gráficos y juegos 3D interactivos (PDF) . págs. 105–112 . doi : 10.1145/1230100.1230119 . ISBN  978-1-59593-628-8.
  2. ↑ Merrell, Paul (2009). Síntesis de modelos (PDF) . Chapel Hill.{{cite book}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )
  3. 1 2 Alaka, Shaad; Bidarra, Rafael (2023). "Colapso de la función de onda semántica jerárquica" . Actas de la 18.ª Conferencia Internacional sobre los Fundamentos de los Juegos Digitales . p. 2. doi : 10.1145/3582437.3587209 . ISBN  978-1-4503-9855-8En 2016 , Maxim Gumin lanzó el algoritmo WFC, publicando un repositorio con su implementación inicial. Desde entonces, WFC ha tenido un profundo impacto en artistas técnicos y desarrolladores de videojuegos, siendo adoptado, adaptado y utilizado en proyectos publicados comercialmente y en desarrollo (Caves of Qud, Townscaper, Matrix Awakens).
  4. ↑ Merrell, Paul (6 de agosto de 2023). Modelado procedimental mediante gramáticas de grafos (vídeo). El evento ocurre en el minuto 3:13.
  5. ↑ "Implementación del colapso de la función de onda y la partición binaria del espacio para la generación procedimental de mazmorras" . Shaan Khan . 21 de marzo de 2021. Consultado el 24 de marzo de 2024. En el caso de WFC , se inspira en tres algoritmos y conceptos distintos pero funcionalmente similares: síntesis de texturas (específicamente síntesis discreta), cadenas de Markov y mecánica cuántica. WFC también se inspiró adicionalmente en la transferencia de estilo de redes neuronales convolucionales (transferencia de estilo CNN).
  6. 1 2 Gumin, Maxim (septiembre de 2016), Algoritmo de colapso de función de onda , consultado el 24 de marzo de 2024
  7. ↑ "El algoritmo de colapso de la función de onda explicado con mucha claridad" . Robert Heaton . Consultado el 24 de marzo de 2024 .
  8. ↑ Gumin, Maxim (septiembre de 2016), Algoritmo de colapso de función de onda , consultado el 25 de marzo de 2024.
  9. ↑ Alaka, Shaad (2023). "Colapso de la función de onda semántica jerárquica" . Actas de la 18.ª Conferencia Internacional sobre los Fundamentos de los Juegos Digitales . p. 2. doi : 10.1145/3582437.3587209 . ISBN  978-1-4503-9855-8Años antes , Merrell había publicado el algoritmo Model Synthesis, conceptualmente idéntico, aunque no tuvo tanto éxito como WFC, posiblemente debido a su menor accesibilidad, su enfoque principal en 3D y los requisitos computacionales de la época.
  10. 1 2 3 Merrell, Paul (28 de julio de 2021). "Comparación de la síntesis de modelos y el colapso de la función de onda" (PDF) . La primera diferencia está en el paso donde elegimos una celda y seleccionamos una etiqueta. Las celdas se eligen en un orden diferente. La síntesis de modelos recorre la cuadrícula en orden de línea de exploración. El WFC elige la celda de entropía más baja.
  11. ↑ DV Gen (17 de abril de 2023). Generación procedimental con colapso de función de onda y síntesis de modelo | Unity Devlog (Vídeo). El evento ocurre a las 15:13. Lamentablemente, este método puede introducir artefactos direccionales.
  12. ↑ Alaka, Shaad; Bidarra, Rafael (abril de 2023). «Colapso de la función de onda semántica jerárquica» . Actas de la 18.ª Conferencia Internacional sobre los Fundamentos de los Juegos Digitales . págs. 1-10 . doi : 10.1145/3582437.3587209 . ISBN  978-1-4503-9855-8Sin embargo, hasta donde sabemos, todas estas variantes del algoritmo WFC operan sobre un conjunto plano de opciones de mosaico por celda.
  13. ↑ Alaka, Shaad; Bidarra, Rafael (abril de 2023). «Colapso de la función de onda semántica jerárquica» . Actas de la 18.ª Conferencia Internacional sobre los Fundamentos de los Juegos Digitales . págs. 1-10 . doi : 10.1145/3582437.3587209 . ISBN  978-1-4503-9855-8Proponemos una solución a estas deficiencias mediante la introducción de (i) la noción de meta-baldosa, una baldosa abstracta que representa un grupo semántico de baldosas, junto con (ii) una estructura similar a un grafo que es capaz de representar la jerarquía entre ellas y las restricciones entre ellas .
  • https://github.com/mxgmn/WaveFunctionCollapse