Schön? Sehr! Wie wir eine Anwendung zur Visualisierung von Attraktoren geschrieben haben

Seltsame Attraktoren sind Bereiche, die häufig in verschiedenen physikalischen Systemen auftreten. Wir können sagen, dass dies eine Region der Anziehung ist, zu der Flugbahnen aus einer bestimmten Nachbarschaft tendieren. Im Gegensatz zu einigen Grenzzyklen oder von einem Gleichgewichtspunkt in gedämpften Schwingungen sind sie nicht periodisch. In solchen Systemen manifestiert sich der Schmetterlingseffekt: Die minimalen Abweichungen der Ausgangspositionen nehmen mit der Zeit exponentiell zu.



Einige Attraktoren verzaubern mit ihrer Schönheit auch in statischen Bildern. Wir wollten eine Anwendung entwickeln, mit der die meisten Attraktoren in der Dynamik, in 3D und ohne Verzögerungen visualisiert werden können.

Über uns

Wir sind Roman Venediktov, Vladislav Nosivskoy und Kirill Karnaukhov - Studenten im zweiten Studienjahr des Bachelor-Studiengangs "Angewandte Mathematik und Informatik" an der Hochschule für Wirtschaft in St. Petersburg. Wir programmieren seit Schulzeiten gern. Alle drei beschäftigten sich mit der Programmierung von Olympiaden und gingen in verschiedenen Jahren in die Endphase der Allrussischen Olympiade für Schüler der Informatik über, hatten jedoch zuvor keine Erfahrung mit industrieller Programmierung, und für uns ist dies das erste große Teamprojekt. Wir haben es als Hausarbeit über C ++ verteidigt.

Modellieren

Es gibt viele Möglichkeiten, ein dynamisches System mit einem seltsamen Attraktor zu definieren. Am häufigsten wird jedoch ein System aus drei Differentialgleichungen erster Ordnung verwendet. Wir haben mit ihr angefangen.

$$

$$\begin{cases} x' = f(x,y,z) \\ y' = f(x,y,z) \\ z' = f(x,y,z) \\ \end{cases}$$

Bevor Sie etwas visualisieren, müssen Sie den Prozess selbst simulieren und die Trajektorien der Punkte ermitteln. Genaue Modellierungsmethoden sind ziemlich mühsam und wir möchten dies so schnell wie möglich tun.



Bei der Implementierung der Modellierung haben wir uns für die Metaprogrammierung entschieden und dabei auf std :: function und andere ähnliche Mechanismen verzichtet. Sie hätten die Architektur und die Codierung vereinfachen können, aber sie hätten die Leistung stark reduziert, was wir nicht wollten.



Für die Modellierung wurde zunächst die einfachste Runge-Kutta-Methode 4. Genauigkeitsordnung mit konstantem Schritt verwendet. Bisher haben wir die Anzahl der Methoden und anderer mathematischer Komponenten des Modells nicht wieder erhöht, und jetzt ist dies die einzige vorgestellte Methode. Auf den meisten gefundenen Systemen ist es genau genug, um Bilder zu erzeugen, die Bildern aus anderen Quellen ähneln.



Das Modell akzeptiert als Eingabe:

• der 'Derivate'-Funktor zum Erhalten von Derivaten durch die Koordinaten eines Punktes;
• der "Beobachter" -Funktor, der von dem Punkt an aufgerufen wird, sobald er empfangen wird;
• Simulationsparameter (Startpunkt, Schrittweite, Anzahl der Punkte).

In Zukunft können Sie eine Überprüfung hinzufügen, um festzustellen, wie das dargestellte Bild mit dem tatsächlichen Bild übereinstimmt, einige stärkere Methoden zur Modellierung (z. B. durch Verbinden der Boost.Numeric.Odeint-Bibliothek) und einige andere Analysemethoden, für die unsere mathematischen Kenntnisse noch nicht ausreichen.

Systeme

Wir haben die beliebtesten seltsamen Attraktorsysteme gefunden, um die beste Leistung zu erzielen. An dieser Stelle möchten wir uns bei der Website chaoticatmospheres.com bedanken, die uns diese Suche sehr erleichtert hat.



Alle Systeme mussten so verpackt werden, dass sie trotz der Tatsache, dass sie alle "unsere Vorlagen" sind, in einen Container gestellt werden und normal mit ihnen in der Steuerung arbeiten können. Wir sind zu folgender Lösung gekommen:

• DynamicSystem ‘observer’, (, ...) std::function ‘compute’. ‘Compute’ , , ‘derivatives’ .
• std::function , DynamicSystemInternal compute .
• DynamicSystemInternal ‘observer’, ‘derivatives’. ‘derivatives’, .

Wir haben mit dem Hinzufügen eines DynamicSystemWrapper begonnen, dem das DynamicSystem gehören würde und der die für die Visualisierung erforderliche Vorverarbeitung durchführen könnte (Auswahl einer Konstante für die Normalisierung, akzeptabler Fehler für Methoden mit Schrittlängensteuerung ...), hatten aber keine Zeit zum Abschluss.

Visualisierung

Wir haben OpenGL aufgrund seiner Leistung und Funktionen als Rendering-Bibliothek ausgewählt sowie Qt5, das einen praktischen Wrapper über OpenGL bietet.



Zunächst wollten wir lernen, wie man zumindest etwas zeichnet, und nach einer Weile konnten wir unseren ersten Würfel herstellen. Kurz danach erschien eine einfache Version des mathematischen Modells, und hier ist die erste Visualisierung des Attraktors:







Mit der ersten Version der Visualisierung war auch eine sehr einfache Version der Kamera fertig. Sie wusste, wie man sich um einen Punkt dreht und sich nähert / wegbewegt. Wir wollten mehr Freiheit im Weltraum: Attraktoren sind unterschiedlich und müssen auf unterschiedliche Weise erforscht werden. Dann erschien eine zweite Version der Kamera, die sich drehen und frei in alle Richtungen bewegen konnte (wir wurden in Minecraft von der Kamera geführt). Zu dieser Zeit hatte die lineare Algebra gerade erst begonnen, und daher gab es nicht genügend Wissen: Wir mussten im Internet nach vielen Informationen suchen.







Die ganze Zeit waren die Bilder weiß, statisch und uninteressant. Ich wollte Farben und Dynamik hinzufügen. Zunächst haben wir gelernt, wie man das ganze Bild in einer Farbe malt, aber das hat sich auch als uninteressant herausgestellt. Dann haben wir folgende Lösung gefunden:

• Nehmen Sie eine Menge (100–500, Sie können mehr in den Einstellungen auswählen, Hauptsache, dass es genügend Leistung gibt) Startpunkte nahe beieinander.
• Simulieren Sie die Flugbahn von jedem von ihnen.
• Rendern Sie die Trajektorien gleichzeitig, während Sie sie in verschiedenen Farben färben, und zeigen Sie nur das Segment der Trajektorie an.

Es stellte sich Folgendes heraus:







Ungefähr ein solches Schema blieb bis zum Ende bestehen.



Es fiel uns auf, dass die Linien zu "eckig" sind, und wir beschlossen zu lernen, wie man sie glättet. Natürlich haben wir versucht, den Simulationsschritt zu reduzieren, aber leider können selbst moderne Prozessoren eine solche Anzahl von Punkten nicht zählen. Es war notwendig, nach einer anderen Option zu suchen.



Zuerst dachten wir, dass OpenGL ein Linienglättungswerkzeug haben sollte, aber nach langem Suchen stellten wir fest, dass dies nicht der Fall ist. Dann kam die Idee auf, die Kurven zu interpolieren und zwischen jedem Paar benachbarter Punkte, die weit genug entfernt sind, einige weitere hinzuzufügen. Zu diesem Zweck musste eine Methode zum Interpolieren von Kurven ausgewählt werden, und es gibt viele solcher Methoden. Leider mussten für die meisten von ihnen (z. B. die Bezier-Kurve) einige weitere Punkte angegeben werden, was für unsere Aufgabe eindeutig nicht geeignet war: Wir wollten, dass das Ergebnis nur von dem abhängt, was uns das mathematische Modell gab. Nach einer Weile fanden wir eine geeignete Interpolation: die Catmull-Roma-Kurve. Es stellte sich so heraus:







Danach haben wir beschlossen, dass es schön wäre, Videos in der App aufzunehmen. Wir wollten es plattformübergreifend halten, also haben wir uns für die libav-Bibliothek entschieden (es gab fast keine Wahl unter den Bibliotheken). Leider ist die gesamte Bibliothek in C geschrieben und hat eine sehr umständliche Oberfläche, so dass wir lange gebraucht haben, um zu lernen, wie man etwas schreibt. Alle nachfolgenden Gifs werden mithilfe der integrierten Aufzeichnung erstellt.







Bis zu diesem Punkt wurden alle Kurvenfarben bei der Erstellung explizit angegeben. Wir haben beschlossen, dass wir für ein schönes Bild die Farben anders einstellen müssen. Zu diesem Zweck wurden nur Kontrollfarben angezeigt, und der Rest wurde unter Verwendung eines linearen Gradienten berechnet. Dieser Teil wurde an Shader übertragen (vorher waren sie Standard).



Wir fanden es interessant, die Flugbahnen so zu färben, dass jede von ihnen ihre Farbe von Kopf bis Schwanz ändert. Dies ermöglicht es uns, den Effekt der Geschwindigkeit zu beobachten:







Dann dachten wir, dass es sich lohnt, die Vorverarbeitungszeit für die Trajektorie zu reduzieren: Das Interpolieren einer Kurve ist eine "teure" Operation. Es wurde beschlossen, diesen Teil an Shader zu übertragen, damit die GPU die Interpolation jedes Mal berechnet, wenn sie aufgefordert wird, einen Teil der Flugbahn zu zeichnen. Dafür haben wir den Geometry Shader verwendet. Diese Lösung bot viele Vorteile: Keine Verzögerung auf der Rendering-Seite vor dem Zeichnen, die Möglichkeit, Kurven noch mehr zu glätten (solche Berechnungen werden auf der GPU schneller als auf der CPU durchgeführt), die Verwendung von weniger RAM (vorher mussten jetzt alle interpolierten Punkte gespeichert werden - nein ).

Controller und Benutzeroberfläche

Nach der Auswahl von Qt5 als Basis-Framework verschwand die Frage nach der Auswahl der Technologien für die Schnittstelle sofort. Der integrierte Qt Creator erfüllt alle Anforderungen einer kleinen Anwendung ausreichend.





Um auf Benutzeranfragen zu antworten, mussten Sie einen Controller schreiben. Glücklicherweise bietet Qt bequeme Möglichkeiten, Tastenanschläge zu verarbeiten und Werte in Felder einzugeben. Dies nutzt die Hauptidee von Qt - den Signal- und Slot-Mechanismus. Wenn wir beispielsweise in unserer Anwendung die Taste drücken, die für die Neuerstellung des Modells verantwortlich ist, wird ein Signal generiert, das vom Handler-Slot akzeptiert wird. Es wird der Wiederaufbau selbst starten.







Bei der Entwicklung fast jeder Anwendung mit einer Schnittstelle kommt früher oder später die Idee auf, die Anwendung multithreaded zu machen. Es schien uns notwendig: Der Bau eingebauter Modelle dauerte einige Sekunden, und der Bau eines benutzerdefinierten Modells dauerte 10 Sekunden. Gleichzeitig hing natürlich die Schnittstelle, da alle Berechnungen in einem Thread durchgeführt wurden. Lange haben wir verschiedene Optionen diskutiert und über Asynchronität mit std :: async nachgedacht, aber am Ende wurde uns klar, dass wir in der Lage sein wollten, Berechnungen in einem anderen Thread zu unterbrechen. Dazu musste ich einen Wrapper über std :: thread schreiben. Alles ist so einfach wie möglich: ein Atom-Flag zur Überprüfung und ein ordentlicher Interrupt, wenn die Überprüfung fehlschlägt.



Dies ergab nicht nur das gewünschte Ergebnis - die Benutzeroberfläche blieb hängen -, sondern fügte auch einige Funktionen hinzu: Aufgrund der Besonderheiten der Architektur und der Interaktion zwischen Modelldaten und Visualisierung wurde es möglich, alles während des Zählens online zu zeichnen. Bisher mussten Sie auf alle Daten warten.

Kundenspezifische Systeme

Die Anwendung enthält bereits viele Attraktoren, aber wir wollten dem Benutzer auch ermöglichen, die Gleichungen selbst einzugeben. Zu diesem Zweck haben wir einen Parser geschrieben, der Variablen (x, y, z), mathematische Standardoperationen (+ - * / ^), Konstanten und viele mathematische Funktionen (sin, cos, log, atan, sinh, exp usw.) unterstützt. und Klammern. So funktioniert es:

• Die ursprüngliche Abfragezeichenfolge ist mit einem Token versehen. Als nächstes werden Token von links nach rechts analysiert und ein Ausdrucksbaum erstellt.
• Mögliche Operationen sind in Gruppen unterteilt. Jede Gruppe hat ihren eigenen Knoten. Gruppen: Plus-Minus, Multiplikationsteilung, Potenzierung, unäres Minus, sogenannte Blätter (dazu gehören Konstanten, Variablen, Funktionsaufrufe).
• Jede Gruppe hat ihre eigene Berechnungsebene. Jede Ebene führt zu rekursiven Berechnungen auf den nächsten Ebenen. Sie können sehen, dass die Reihenfolge der Aufrufe die Verteilung der Prioritäten von Vorgängen beeinflusst. Wir haben sie in der oben beschriebenen Reihenfolge.

Weitere Details finden Sie im Parser-Quellcode .



Jede Ebene gibt eine Art Erbe des Knotens zurück. Es gibt vier davon:

• binärer Operator - speichert Zeiger auf zwei untergeordnete Elemente und seine eigene Art von Operation;
• unärer Operator - speichert einen Zeiger auf das untergeordnete Element und seinen eigenen Operationstyp. Dies schließt Funktionen ein, da dies ein Sonderfall einer unären Operation ist;
• konstant - speichert seinen Wert;
• Variable - speichert einen Zeiger auf die Stelle im Speicher, an der sein Wert liegt.

Die Knotenstruktur verfügt nur über eine virtuelle Berechnungsfunktion, die den Wert ihres Teilbaums zurückgibt.



Die resultierende Ausgabe ist sehr bequem auf die zuvor beschriebene Systemarchitektur zugeschnitten. Ein Lambda wird einfach an DynamicSystemInternal übergeben, das Zeiger auf die Wurzelknoten der drei erhaltenen Bäume und die xyz-Speicherpositionen der Werte speichert. Beim Aufruf werden die dortigen Werte in die angegebenen Werte geändert und calc von den Stammscheitelpunkten aufgerufen.

Ergebnis

Als Ergebnis haben wir ein Programm erhalten, das benutzerdefinierte Systeme visualisieren kann und auf einer großen Anzahl von Attraktoren basiert. Sie macht es ganz nett und optimiert, was eine gute Nachricht ist.



Aber es gibt noch viel Arbeit:

• präzisere Methoden hinzufügen;
• Hinzufügen einer weiteren Ebene der Systemverarbeitung (Normalisierung und automatische Fehlerauswahl bei komplexeren Methoden);
• Verbesserung der Arbeit mit Benutzersystemen (Unterstützung von Variablen, Speichern);
• Optimierung ihrer Arbeit (JIT-Kompilierung oder ein Dienstprogramm, das die gespeicherten Systeme in C ++ - Code konvertiert und einfach die Neukompilierung startet, damit sie die Leistung eingebetteter Systeme erreichen);
• Hinzufügen von Funktionen zur Ergebnisanalyse oder -visualisierung, die Personen, die mit solchen Systemen arbeiten, wirklich benötigen;
• ...

Unser Repository .



Und noch ein paar Videos mit Attraktoren: