Alguns atratores enfeitiçam sua beleza mesmo em fotos estáticas. Queríamos fazer um aplicativo que fosse capaz de visualizar a maioria dos atratores em dinâmica, em 3D e sem atrasos.
Sobre nós
Somos Roman Venediktov, Vladislav Nosivskoy e Kirill Karnaukhov - alunos do segundo ano do programa de bacharelado "Matemática Aplicada e Ciência da Computação" da Escola Superior de Economia - São Petersburgo. Gostamos de programação desde os tempos de escola. Todos os três estavam engajados na programação de olimpíadas e passaram em anos diferentes para a fase final da Olimpíada de Todas as Rússias para crianças em idade escolar em ciência da computação, mas eles não tinham nenhuma experiência em programação industrial antes, e para nós este é o primeiro grande projeto em equipe. Nós o defendemos como um trabalho final em C ++.
Modelagem
Existem muitas maneiras de definir um sistema dinâmico com um atrator estranho, mas a mais comum é um sistema de três equações diferenciais de primeira ordem. Começamos com ela.
Antes de visualizar algo, você precisa simular o próprio processo e encontrar as trajetórias dos pontos. Métodos de modelagem precisos são bastante trabalhosos e gostaríamos de fazer isso o mais rápido possível.
Ao implementar a modelagem, decidimos usar metaprogramação, abandonando std :: function e outras mecânicas semelhantes. Eles poderiam ter simplificado a arquitetura e a codificação, mas teriam um desempenho bastante reduzido, o que não queríamos.
Inicialmente, o método mais simples de Runge - Kutta de 4ª ordem de precisão com passo constante foi usado para modelagem. Até agora não voltamos a aumentar o número de métodos e outros componentes matemáticos do modelo, e agora este é o único método apresentado. Na maioria dos sistemas encontrados, é preciso o suficiente para produzir imagens semelhantes a imagens de outras fontes.
O modelo aceita como entrada:
- o functor 'derivadas' para obter derivadas pelas coordenadas de um ponto;
- o functor 'observador', que é chamado a partir do ponto assim que é recebido;
- parâmetros de simulação (ponto de partida, tamanho do passo, número de pontos).
No futuro, você pode adicionar uma verificação para ver como a imagem apresentada corresponde à real, alguns métodos mais fortes de modelagem (por exemplo, conectando a biblioteca Boost.Numeric.Odeint) e alguns outros métodos de análise para os quais nosso conhecimento de matemática ainda não é suficiente.
Sistemas
Encontramos os sistemas de atratores estranhos mais populares para obter o melhor desempenho deles. Aqui queremos agradecer ao site chaoticatmospheres.com, que facilitou muito esta busca para nós.
Todos os sistemas tiveram que ser embrulhados para que, apesar de serem todos "nossos modelos", pudessem ser colocados em um contêiner e trabalhar normalmente com eles no controlador. Chegamos à seguinte solução:
- DynamicSystem ‘observer’, (, ...) std::function ‘compute’. ‘Compute’ , , ‘derivatives’ .
- std::function , DynamicSystemInternal compute .
- DynamicSystemInternal ‘observer’, ‘derivatives’. ‘derivatives’, .
Começamos a trabalhar na adição de um DynamicSystemWrapper, que seria dono do DynamicSystem e poderia fazer o pré-processamento necessário para a visualização (seleção de uma constante para normalização, erro aceitável para métodos com controle de comprimento de passo ...), mas não tivemos tempo para terminar.
Visualização
Escolhemos OpenGL como uma biblioteca de renderização por causa de seu desempenho e recursos, bem como Qt5, que tem um wrapper conveniente sobre OpenGL.
Para começar, queríamos aprender a desenhar pelo menos alguma coisa e, depois de um tempo, fomos capazes de fazer nosso primeiro cubo. Logo em seguida, uma versão simples do modelo matemático apareceu, e aqui está a primeira visualização do atrator:
Com a primeira versão da renderização, uma versão muito simples da câmera também estava pronta. Ela sabia como girar em torno de um ponto e se aproximar / se afastar. Queríamos mais liberdade no espaço: os atratores são diferentes e precisam ser explorados de maneiras diferentes. Então, uma segunda versão da câmera apareceu, que podia girar e se mover livremente em todas as direções (fomos guiados pela câmera no Minecraft). Naquela época, a álgebra linear estava apenas começando e, portanto, não havia conhecimento suficiente: tínhamos que buscar muitas informações na Internet.
Todo esse tempo as fotos eram brancas, estáticas e desinteressantes. Eu queria adicionar cores e dinâmica. Para começar, aprendemos a pintar todo o quadro com uma cor, mas isso também se revelou desinteressante. Então, descobrimos a seguinte solução:
- Pegue um monte (100–500, você pode escolher mais nas configurações, o principal é que haja desempenho suficiente) de pontos de partida próximos uns dos outros.
- Simule a trajetória de cada um deles.
- Renderize os caminhos ao mesmo tempo, colorindo-os com cores diferentes e mostrando apenas o segmento do caminho.
Descobriu-se o seguinte:
Aproximadamente esse esquema permaneceu até o fim.
Percebemos que as linhas são muito "angulares" e decidimos aprender a suavizá-las. Claro, tentamos reduzir a etapa de simulação, mas, infelizmente, mesmo os processadores modernos não são capazes de contar tal número de pontos. Era preciso procurar outra opção.
A princípio pensamos que o OpenGL deveria ter uma ferramenta de suavização de linha, mas depois de muita pesquisa, descobrimos que esse não é o caso. Então surgiu a ideia de interpolar as curvas e adicionar mais algumas entre cada par de pontos vizinhos que estão longe o suficiente. Para fazer isso, foi necessário escolher um método de interpolação de curvas, e existem muitos desses métodos. Infelizmente, a maioria deles (por exemplo, a curva de Bézier) exigia a especificação de mais alguns pontos, o que claramente não era adequado para nossa tarefa: queríamos que o resultado dependesse apenas do que o modelo matemático nos fornecesse. Depois de um tempo, encontramos uma interpolação adequada: a curva Catmull - Roma. Ficou assim:
Depois disso, decidimos que seria bom gravar vídeos dentro do aplicativo. Queríamos mantê-lo em várias plataformas, então decidimos pela biblioteca libav (quase não havia escolha entre as bibliotecas). Infelizmente, toda a biblioteca é escrita em C e tem uma interface muito inconveniente, por isso demoramos muito para aprender a escrever algo. Todos os GIFs subsequentes são feitos usando a gravação embutida.
Até este ponto, todas as cores das curvas foram especificadas explicitamente na criação. Decidimos que, para obter uma bela imagem, precisamos definir as cores de maneira diferente. Para isso, apenas as cores de controle passaram a ser indicadas, e as demais foram calculadas em gradiente linear. Essa parte foi transferida para os shaders (antes eram padrão).
Achamos interessante colorir as trajetórias de modo que cada uma delas mude de cor da cabeça à cauda. Isso permite observar o efeito da velocidade:
Então pensamos que valia a pena tentar reduzir o tempo de pré-processamento da trajetória: interpolar uma curva é uma operação "cara". Decidiu-se transferir esta parte para shaders para que a GPU calcule a interpolação toda vez que for solicitado a desenhar uma parte da trajetória. Para isso, usamos o Geometry Shader. Esta solução trouxe muitas vantagens: nenhum atraso no lado da renderização antes de desenhar, a capacidade de suavizar as curvas ainda mais (tais cálculos são realizados na GPU mais rápido do que na CPU), o uso de menos RAM (antes disso, todos os pontos interpolados tinham que ser armazenados, agora - não )
Controlador e interface do usuário
Depois de escolher o Qt5 como framework base, a questão de escolher tecnologias para a interface desapareceu imediatamente. O Qt Creator embutido satisfaz suficientemente todas as necessidades de um pequeno aplicativo.
Para responder às solicitações do usuário, um controlador teve que ser escrito. Felizmente, o Qt tem maneiras convenientes de lidar com as teclas digitadas e inserir valores nos campos. Ele usa a idéia principal do Qt - o mecanismo de sinais e slots. Por exemplo, se em nossa aplicação pressionarmos o botão responsável pela reconstrução do modelo, será gerado um sinal que será aceito pelo slot do manipulador. Ele iniciará a reconstrução propriamente dita.
Ao desenvolver quase qualquer aplicativo com uma interface, mais cedo ou mais tarde surge a ideia de tornar o aplicativo multi-threaded. Pareceu-nos necessário: construir modelos embutidos demorava vários segundos e construir um personalizado demorava 10 segundos. Ao mesmo tempo, é claro, a interface travou, porque todos os cálculos foram realizados em um segmento. Por um longo tempo, discutimos diferentes opções e pensamos sobre assincronia usando std :: async, mas no final percebemos que queríamos ser capazes de interromper cálculos em outro thread. Para fazer isso, eu tive que escrever um wrapper sobre std :: thread. Tudo é o mais simples possível: um sinalizador atômico para verificação e uma interrupção simples se a verificação falhar.
Isso deu não só o resultado desejado - a interface parou de travar - mas também acrescentou um recurso: devido às peculiaridades da arquitetura e da interação entre os dados do modelo e a visualização, tornou-se possível desenhar tudo online, logo no decorrer da contagem. Anteriormente, você tinha que esperar por todos os dados.
Sistemas personalizados
Existem muitos atratores já fornecidos no aplicativo, mas também queríamos permitir que o usuário insira as próprias equações. Para isso, escrevemos um analisador que suporta variáveis (x, y, z), operações matemáticas padrão (+ - * / ^), constantes, muitas funções matemáticas (sin, cos, log, atan, sinh, exp, etc.) e colchetes. É assim que funciona:
- A string de consulta original é tokenizada. Em seguida, os tokens são analisados da esquerda para a direita e uma árvore de expressão é construída.
- As operações possíveis são divididas em grupos. Cada grupo tem seu próprio Nó. Grupos: mais-menos, multiplicação-divisão, exponenciação, menos unário, as chamadas folhas (isso inclui constantes, variáveis, chamadas de função).
- Cada grupo tem seu próprio nível de computação. Cada nível causa cálculos recursivos nos níveis seguintes. Você pode ver que a ordem das chamadas afeta a distribuição das prioridades das operações. Nós os temos na ordem descrita acima.
Procure mais detalhes no código-fonte do analisador .
Cada nível retorna algum tipo de herdeiro do Nó. Há quatro deles:
- operador binário - armazena ponteiros para dois filhos e seu próprio tipo de operação;
- operador unário - armazena um ponteiro para o filho e seu próprio tipo de operação. Isso inclui funções, uma vez que este é um caso especial de uma operação unária;
- constante - armazena seu valor;
- variável - armazena um ponteiro para o local na memória onde está seu valor.
A estrutura Node possui apenas uma função virtual calc que retorna o valor de sua subárvore.
A saída resultante é adaptada de forma muito conveniente à arquitetura do sistema descrita anteriormente. Um lambda é simplesmente passado para DynamicSystemInternal, que armazena ponteiros para os nós raiz das três árvores obtidas e as posições de memória xyz dos valores. Quando chamado, ele altera os valores lá para aqueles fornecidos e chama calc dos vértices da raiz.
Resultado
Como resultado, temos um programa que pode visualizar sistemas definidos pelo usuário e tem uma base de um grande número de atratores. Ela faz isso muito bem e otimizada, o que é uma boa notícia.
Mas ainda há muito trabalho:
- adicione métodos mais precisos;
- adicionar mais uma camada de processamento de sistemas (normalização e seleção automática de erros em métodos mais complexos);
- melhorar o trabalho com os sistemas do usuário (suporte para variáveis, salvamento);
- otimizar seu trabalho (compilação JIT ou um utilitário que converte os sistemas salvos em código c ++ e simplesmente inicia a recompilação para que alcancem o desempenho de sistemas embarcados);
- adicionar recursos para análise de resultados ou visualização de que as pessoas que trabalham com esses sistemas realmente precisam;
- ...
Nosso repositório .
E mais alguns vídeos com atratores: