Algunos atractores hechizan con su belleza incluso en imágenes estáticas. Queríamos hacer una aplicación que fuera capaz de visualizar la mayoría de los atractores en dinámica, en 3D y sin rezagos.
Sobre nosotros
Somos Roman Venediktov, Vladislav Nosivskoy y Kirill Karnaukhov, estudiantes de segundo año del programa de licenciatura "Matemáticas aplicadas e informática" en la Escuela Superior de Economía de San Petersburgo. Nos gusta la programación desde la escuela. Los tres participaron en la programación de la Olimpiada y pasaron en diferentes años a la etapa final de la Olimpiada de toda Rusia para escolares en ciencias de la computación, pero antes no tenían experiencia en programación industrial, y para nosotros este es el primer gran proyecto de equipo. Lo defendimos como un trabajo final en C ++.
Modelado
Hay muchas formas de definir un sistema dinámico con un atractor extraño, pero la más común es un sistema de tres ecuaciones diferenciales de primer orden. Empezamos con ella.
Antes de visualizar algo, debe simular el proceso en sí y encontrar las trayectorias de los puntos. Los métodos de modelado precisos son bastante laboriosos y nos gustaría hacerlo lo más rápido posible.
Al implementar el modelado, decidimos usar metaprogramación, abandonando std :: function y otras mecánicas similares. Podrían haber simplificado la arquitectura y la codificación, pero habrían reducido considerablemente el rendimiento, lo que no queríamos.
Inicialmente, se utilizó para el modelado el método más simple de Runge-Kutta del cuarto orden de precisión con un paso constante. Hasta ahora no hemos vuelto a incrementar el número de métodos y otros componentes matemáticos del modelo, y ahora este es el único método presentado. En la mayoría de los sistemas encontrados, es lo suficientemente preciso como para producir imágenes similares a imágenes de otras fuentes.
El modelo acepta como entrada:
- el functor 'derivadas' para obtener derivadas por las coordenadas de un punto;
- el functor 'observador', que se llama desde el punto tan pronto como se recibe;
- parámetros de simulación (punto de partida, tamaño de paso, número de puntos).
En el futuro, puede agregar una verificación para ver cómo la imagen presentada coincide con la real, algunos métodos más sólidos para modelar (por ejemplo, conectando la biblioteca Boost.Numeric.Odeint) y algunos otros métodos de análisis para los cuales nuestro conocimiento de las matemáticas aún no es suficiente.
Sistemas
Encontramos los sistemas de atractores extraños más populares para obtener el mejor rendimiento de ellos. Aquí queremos agradecerle al sitio chaoticatmospheres.com, que hizo esta búsqueda muy fácil para nosotros.
Todos los sistemas tenían que estar empaquetados para que, a pesar de que todos son "nuestras plantillas", pudieran colocarse en un contenedor y trabajar normalmente con ellos en el controlador. Llegamos a la siguiente solución:
- DynamicSystem ‘observer’, (, ...) std::function ‘compute’. ‘Compute’ , , ‘derivatives’ .
- std::function , DynamicSystemInternal compute .
- DynamicSystemInternal ‘observer’, ‘derivatives’. ‘derivatives’, .
Comenzamos a trabajar en agregar un DynamicSystemWrapper, que sería propietario del DynamicSystem y podría hacer el preprocesamiento requerido para la visualización (selección de una constante para normalización, error aceptable para métodos con control de longitud de paso ...), pero no tuvimos tiempo de terminar.
Visualización
Elegimos OpenGL como la biblioteca de renderizado debido a su rendimiento y capacidades, así como Qt5, que tiene un envoltorio conveniente sobre OpenGL.
Para empezar, queríamos aprender a dibujar al menos algo, y después de un tiempo pudimos hacer nuestro primer cubo. Poco después, apareció una versión simple del modelo matemático, y aquí está la primera visualización del atractor:
Con la primera versión de la visualización, también estaba lista una versión muy simple de la cámara. Sabía rotar alrededor de un punto y acercarse / alejarse. Queríamos más libertad en el espacio: los atractores son diferentes y deben explorarse de diferentes maneras. Luego apareció una segunda versión de la cámara, que podía girar y moverse libremente en todas direcciones (nos guiaba la cámara en Minecraft). En ese momento, el álgebra lineal recién comenzaba y, por lo tanto, no había suficiente conocimiento: teníamos que buscar mucha información en Internet.
Todo este tiempo las imágenes fueron blancas, estáticas y poco interesantes. Quería agregar colores y dinámica. Para empezar, aprendimos a pintar el cuadro completo en un solo color, pero eso tampoco resultó interesante. Luego se nos ocurrió la siguiente solución:
- Tome muchos (100–500, puede elegir más en la configuración, lo principal es que haya suficiente rendimiento) de puntos de partida cercanos entre sí.
- Simula la trayectoria de cada uno de ellos.
- Renderice las trayectorias al mismo tiempo, mientras las colorea en diferentes colores, y muestre solo el segmento de la trayectoria.
Resultó lo siguiente:
Aproximadamente tal esquema se mantuvo hasta el final.
Nos sorprendió que las líneas fueran demasiado "angulares" y decidimos aprender a suavizarlas. Por supuesto, intentamos reducir el paso de simulación, pero, desafortunadamente, incluso los procesadores modernos no pueden contar tantos puntos. Había que buscar otra opción.
Al principio pensamos que OpenGL debería tener una herramienta de suavizado de líneas, pero después de muchas búsquedas, descubrimos que este no es el caso. Entonces surgió la idea de interpolar las curvas y agregar algunas más entre cada par de puntos vecinos que estén lo suficientemente lejos. Para hacer esto, fue necesario elegir un método de interpolación de curvas, y existen muchos de estos métodos. Lamentablemente, la mayoría de ellos (por ejemplo, la curva de Bezier) requirieron que se especificaran algunos puntos más, lo que claramente no era adecuado para nuestra tarea: queríamos que el resultado dependiera solo de lo que nos proporcionaba el modelo matemático. Después de un tiempo, encontramos una interpolación adecuada: la curva Catmull - Roma. Resultó así:
Después de eso, decidimos que sería bueno grabar videos dentro de la aplicación. Queríamos mantenerlo multiplataforma, por lo que nos decidimos por la biblioteca libav (casi no había elección entre las bibliotecas). Desafortunadamente, toda la biblioteca está escrita en C y tiene una interfaz muy incómoda, por lo que nos tomó mucho tiempo aprender a escribir algo. Todos los gifs posteriores se crean utilizando la grabación incorporada.
Hasta este punto, todos los colores de las curvas se han especificado explícitamente en la creación. Decidimos que para obtener una imagen hermosa necesitamos configurar los colores de manera diferente. Para ello, solo se empezaron a indicar los colores de control, y el resto se calcularon mediante un degradado lineal. Esta parte se transfirió a los sombreadores (antes eran estándar).
Nos pareció interesante colorear las trayectorias de tal manera que cada una de ellas cambie de color de la cabeza a la cola. Esto nos permite observar el efecto de la velocidad:
Entonces pensamos que valía la pena intentar reducir el tiempo de preprocesamiento de la trayectoria: interpolar una curva es una operación "cara". Se decidió transferir esta parte a los sombreadores para que la GPU calcule la interpolación cada vez que se le pida que dibuje una parte de la trayectoria. Para ello, usamos el Geometry Shader. Esta solución dio muchas ventajas: sin demora en el lado de la renderización antes de la renderización, la capacidad de suavizar las curvas aún más (tales cálculos se realizan en la GPU más rápido que en la CPU), el uso de menos RAM (antes de eso, todos los puntos interpolados tenían que ser almacenados, ahora - no ).
Controlador e interfaz de usuario
Después de elegir Qt5 como marco base, la cuestión de elegir tecnologías para la interfaz desapareció de inmediato. El Qt Creator integrado satisface suficientemente todas las necesidades de una pequeña aplicación.
Para responder a las solicitudes de los usuarios, se tenía que escribir un controlador. Afortunadamente, Qt tiene formas convenientes de manejar las pulsaciones de teclas e ingresar valores en los campos. Utiliza la idea principal de Qt: el mecanismo de señales y ranuras. Por ejemplo, si en nuestra aplicación pulsamos el botón encargado de reconstruir el modelo, se generará una señal que será aceptada por el handler slot. Comenzará la reconstrucción por sí mismo.
Al desarrollar casi cualquier aplicación con una interfaz, tarde o temprano surge la idea de hacer que la aplicación sea multiproceso. Nos pareció necesario: construir modelos incorporados tomó varios segundos y construir uno personalizado tomó 10 segundos. Al mismo tiempo, por supuesto, la interfaz se colgó, porque todos los cálculos se llevaron a cabo en un hilo. Durante bastante tiempo discutimos diferentes opciones y pensamos en la asincronía usando std :: async, pero al final nos dimos cuenta de que queríamos poder interrumpir los cálculos en otro hilo. Para hacer esto, tuve que escribir un contenedor sobre std :: thread. Todo es lo más simple posible: una bandera atómica para verificar y una interrupción ordenada si la verificación falla.
Esto dio no solo el resultado deseado, la interfaz dejó de colgarse, sino que también agregó alguna característica: debido a las peculiaridades de la arquitectura y la interacción entre los datos del modelo y la visualización, fue posible dibujar todo en línea, justo en el curso del conteo. Anteriormente, tenía que esperar todos los datos.
Sistemas personalizados
Ya hay muchos atractores proporcionados en la aplicación, pero también queríamos permitir que el usuario ingresara las ecuaciones. Para hacer esto, escribimos un analizador que admite variables (x, y, z), operaciones matemáticas estándar (+ - * / ^), constantes, muchas funciones matemáticas (sin, cos, log, atan, sinh, exp, etc.) y corchetes. Así es como funciona:
- La cadena de consulta original está tokenizada. A continuación, los tokens se analizan de izquierda a derecha y se crea un árbol de expresión.
- Las posibles operaciones se dividen en grupos. Cada grupo tiene su propio nodo. Grupos: más-menos, multiplicación-división, exponenciación, unario menos, las llamadas hojas (esto incluye constantes, variables, llamadas a funciones).
- Cada grupo tiene su propio nivel de cálculo. Cada nivel provoca cálculos recursivos en los siguientes niveles. Puede ver que el orden de las llamadas afecta la distribución de las prioridades de las operaciones. Los tenemos en el orden descrito anteriormente.
Busque más detalles en el código fuente del analizador .
Cada nivel devuelve algún tipo de heredero del Node. Hay cuatro de ellos:
- operador binario: almacena punteros a dos hijos y su propio tipo de operación;
- operador unario: almacena un puntero al niño y su propio tipo de operación. Esto incluye funciones, ya que este es un caso especial de operación unaria;
- constante: almacena su valor;
- variable: almacena un puntero al lugar en la memoria donde se encuentra su valor.
La estructura de nodo solo tiene una función de cálculo virtual que devuelve el valor de su subárbol.
La salida resultante se adapta muy convenientemente a la arquitectura del sistema descrita anteriormente. Una lambda simplemente se pasa a DynamicSystemInternal, que almacena punteros a los nodos raíz de los tres árboles obtenidos y las posiciones de memoria xyz de los valores. Cuando se llama, cambia los valores allí a los proporcionados y llama a calc desde los vértices de la raíz.
Salir
Como resultado, obtuvimos un programa que puede visualizar sistemas definidos por el usuario y tiene una base de una gran cantidad de atractores. Lo hace bastante bien y optimizado, lo cual es una buena noticia.
Pero aún queda mucho trabajo:
- agregue métodos más precisos;
- agregar una capa más de procesamiento de sistemas (normalización y selección automática de errores en métodos más complejos);
- mejorar el trabajo con los sistemas de los usuarios (soporte para variables, ahorro);
- optimizar su trabajo (compilación JIT o una utilidad que convierte los sistemas guardados a código c ++ y simplemente inicia la recompilación para que logren el rendimiento de los sistemas embebidos);
- agregar capacidades para el análisis o visualización de resultados que las personas que trabajan con tales sistemas realmente necesitan;
- ...
Nuestro repositorio .
Y algunos videos más con atractores: