blog · git · desktop · images · contact
2009-02-27
Gesehen hat Fraktale wohl jeder schonmal, zum Beispiel via XaoS, aber die Dinger mal zu verstehen und selbst zu machen, ist schon eine lustige Sache. Auf der anderen Seite ist es schier unglaublich, was man mit dieser - eigentlich total einfachen - mathematischen Beschreibung alles anstellen kann. Das wäre doch mal was für die Lehrer dort draußen, um ein bisschen Motivation zu streuen. ;)
Angefangen hat das Projekt mit der Mandelbrot-Menge und den Julia-Mengen. Sinn der Sache war auch, die Berechnung auf der Grafikkarte im Fragment-Shader durchzuführen, um möglichst viel Geschwindigkeit herauszuholen, denn Parallelisierung bietet sich hier natürlich an. Die ersten Ergebnisse kann man hier begutachten. Aber da geht noch viel mehr. :)
Fraktale haben nun die schöne Eigenschaft, dass man in sie hineinzoomen kann - und zwar beliebig weit. Trotzdem wird man immer wieder neue Formen entdecken, die zwar häufig Variationen von bereits bekannten Formen aber nie identisch sind. Dabei stößt man zumindest mit der heutigen Hardware aber auf ein Problem und an eine harte Grenze, die schnell den Spaß verdirbt: Pixel-Shader können nur mit float-Genauigkeit rechnen. Das heißt, mit "tief reinzoomen" war's das erstmal. In meinem Programm war etwa bei einem Zoomverhältnis von 1 zu 100'000 bis höchstens 1 zu 1'000'000 Schluss. Natürlich klingt das nach ziemlich viel, wenn man es mit alltäglichen Maßstäben vergleicht, für ein Fraktal ist es aber recht wenig.
Die erste Idee war, einen eigenen Datentyp mit den nötigen Rechenoperationen für den Shader zu bauen, was zwar funktionierte, sich aber als viel zu langsam herausgestellt hat. Also wanderte das Programm von der Grafikkarte zurück auf die CPU, denn dort gibt es den double-Typ. Aber ob das dann noch schnell genug ist?
Es ist. Zwar ist es multithreaded auf meinem alten Athlon X2 4200+ definitiv um ein paar Größenordnungen langsamer als die Pixel-Shader-Version mit floats, aber wiederum um Welten schneller als die Pixel-Shader-Version mit eigenem Datentyp. Da die float-Version dank wenig Zoom nicht wirklich Spaß macht, war also klar, wer der Gewinner ist: Die CPU. Ein bisschen schade, zeigt aber auch, dass man Shader (noch) nicht für alles missbrauchen kann. ;)
Die Frage war nun geklärt, also mussten nun so ein paar Details her wie zum Beispiel eine vom Zoom abhängige Rekursionstiefe, weiche Farbübergänge und zur Laufzeit definierbare Farben:
Das schönste Bild ist es sicher nicht, zeigt aber die Funktionen. ;) Bis auf die obligatorische Zoomfahrt natürlich, denn den Platz für ein großes Video habe ich hier leider nicht. Mehr Bilder des Programms (und ein paar früheren Versionen davon) finden sich hier oder hier:
Als Framework wird immernoch OpenGL genutzt, was sich aber in Zukunft noch ändern soll, um das Programm flexibler und portabler zu gestalten. Außerdem wird zur Darstellung noch ein texturiertes Quad benutzt, was auf älteren Grafikkarten zu Problemen bzw. Nichtdarstellbarkeit führen kann, wenn die Fenstergröße nicht 2^n x 2^n ist.
Wie sieht es jetzt eigentlich mit der Zoomtiefe aus? Nun, wäre die Mandelbrot- oder Julia-Menge in Normalansicht einen Meter breit, dann kann man in etwa auf die Größe eines Atomkerns hineinzoomen. Um es in schön großen Zahlen auszudrücken: Das entspricht einem Verhältnis von 1 zu 1'000'000'000'000'000, also einer 1 mit 15 Nullen dahinter. Wenn man sich darunter immernoch nichts vorstellen kann: Der Abstand von der Erde zur Sonne ist grob 150'000'000'000 Meter, das ist eine 150 mit gerade einmal 9 Nullen dahinter. Trotzdem ist da immernoch viel Luft für noch mehr Genauigkeit.
Damit aber erstmal genug. Anstatt den Zoomwert zu vergrößern, kann man ja auch die Anzahl der Dimensionen erhöhen. Mathematiker sind spitzfindige Menschen und so hat sich der gute Hamilton vor langer Zeit die Quaternionen ausgedacht. Als wären die Julia-Mengen über den komplexen Zahlen nicht schon erstaunlich genug, lassen sie sich mit Quaternionen dann tatsächlich vierdimensional definieren.
Ein solches 4D-Objekt kann man natürlich nur schwer visualisieren, weswegen man es zuerst in einen "normalen" 3D-Raum projizieren muss. Diesen Satz muss man sich schon ein bisschen auf der Zunge zergehen lassen, sofern man sich vorher noch nicht damit beschäftigt hat - wer kann sich schon etwas Vierdimensionales vorstellen? Hier hilft dann aber die Rückführung auf Bekanntes: Man betrachtet einfach die gewöhnliche Projektion eines 3D-Raumes auf eine 2D-Bildebene. Damit haben viele Menschen täglich zu tun, denn genau das tut eine Kamera oder unser Auge. Etwas ähnliches kann man mit den 4D-Julia-Mengen machen und erhält dann ein "3D"-Fraktal.
Damit muss man aber etwas vorsichtig sein, denn man kann sich zwar um dieses Objekt am Computer herumbewegen oder man könnte es von einem 3D-Drucker drucken lassen und dann in die Hand nehmen. Aber man muss sich der Tatsache bewusst sein, dass dies dann keineswegs die "komplette" Julia-Menge zu den gegebenen Parametern ist. Abgesehen davon, dass man eine solche Menge ohnehin schlecht irgendwann als "komplett" ansehen kann, ging bei der Projektion in den Raum Information verloren. Auf einem Foto sieht man auch immer nur eine bestimmte Perspektive, man kann sich nicht mehr in dem Raum bewegen, den dieses Foto darstellt - beispielsweise sieht man auf dem Foto immer nur die Vorderseite eines Hauses, aber was auf der Rückseite ist, kann man nicht sagen. Genauso kann eine 4D-Julia-Menge zu ein und denselben Parametern mit verschiedenen Projektionsmethoden und "Blickwinkeln" anders aussehen.
Das Verrückte ist aber sowieso, dass sich auch jetzt noch Strukturen bilden, die denen der komplexen Julia-Mengen sehr ähneln. Es ist mir ohnehin ein Rätsel, warum diese Mengen so aussehen, wie sie eben aussehen, aber dass das dann auch im Vierdimensionalen klappt, ist Wahnsinn. :eek:
Zur einfachen Visualisierung dieser Mengen bietet sich dann Raytracing an. Das klappt auch auf der Grafikkarte im Fragment-Shader erstaunlich gut und schnell, wenn man einmal vom "fancy stuff" wie Reflektionen oder Transparenz absieht (geht zwar auch, ist aber umständlich). Da ich aber vorher sowieso schon einen Raytracer für die CPU gebaut hatte, habe ich die 4D-Julia-Mengen dann auch dort noch eingebaut und bin von den Ergebnissen schon ein bisschen begeistert. ;)
Der Rest ist hier zu sehen: qjulia.
Lediglich das Finden von Normalenvektoren ist ziemlich heikel, denn wie will man eine Normale auf einer fraktalen Menge definieren? Das geht einfach nicht, also muss man es in irgendeiner Form numerisch über eine Art Gradient annähern. Leider klappt das nicht immer perfekt und es ist ziemlich frickelig, hierfür geeignete Parameter für Rekursionstiefe und Epsilon zu finden. Aber es geht halbwegs...
...und all das steckt in der einfachen Folgendefinition "z[n+1] = z[n]^2 + c". Die Welt ist seltsam. :eek:
