Heute schreibe ich mal ein bisschen was dazu, wie man ein Fraktal implementieren kann. Ich werde hierbei einfach eine Java-Klasse für ein Projekt schreiben, dass ich zusammen mit einem Freund gemacht habe. Die Erklärungen lassen sich aber auch auf andere Programmiersprachen anwenden. Ich werde hier einfach Schritt für Schritt beschreiben wie ich eine Version des Newton-Fraktals implementiere. Wenn man die Schritte selber nachmachen will kopiert man am besten einfach das Git-Repository und fügt es in ein Eclipse Java-Projekt ein.

Die Java Klasse erzeugen

Als erstes wird mit Eclipse die Klasse erstellt. Diese Klasse erbt von der Oberklasse Fraktalprogramm. Ein Fraktalprogramm hat eine Hauptmethode nähmlich calcPixel. calcPixel bekommt als eingabe vom Renderer den Punkt der berechnet werden soll. Dann berechnet calcPixel die Farbe die der Pixel bekommen soll und gibt sie zurück damit der Renderer den entschprechenden Pixel einfärben kann. Das kann man natürlich auch anders realiesieren, aber so bleibt der Code vielleicht noch am übersichtlichsten. So sieht in diesem Fall also meine Klasse aus:

package de.a.newton; //Das eigene Package
import java.awt.Color; // Benötigt um Farben auszugeben

import de.otori.engine.FraktalProgram; // die Eltern-Klasse
import de.otori.engine.Point2F; // Format der Koordinate die übergeben wird

public class Newton extends FraktalProgram{

public Newton() {
// TODO Auto-generated constructor stub
}

@Override
public Color calcPixel(Point2F coordinate) {
// TODO Auto-generated method stub
return null;
}

}

Damit man die Klasse dem Renderer als Objekt übergeben werden kann erstellen wir noch ein generisches Objekt der Klasse welches dann schon voreingestellt ist.

public static final Newton GenerischeEinstellungen = new Newton();

Dann erstellen wir den Konstruktor:

/**
* Konstruktor
*/
public Newton() {
zoom = 1.; //Das Zoomlevel und der Mittelpunkt gehören zur Oberklasse
center = new Point2F(0, 0);
}

Jetzt kann amn schnell testen ob bis hier schon alles klappt. Wir schreiben einfach eine kleine Testfunktion die einen Sinus malen soll.

@Override
public Color calcPixel(Point2F coordinate) {
double sin = Math.sin(coordinate.x); //den Sinus von x berechnen
if(coordinate.y < sin + 1 && coordinate.y>sin-1) //wenn der wert des Sinus 
{return Color.black;}// in etwa der y Koordinate gleicht wird der Punkt schwarz

return Color.white; // ansonsten bleibt er weiss
}

Jetzt muss noch in engine/Programm.java das entsprechende Programm aufgerufen werden

private FraktalProgram[] fraktals = {  Newton.GenerischeEinstellungen};

Wenn man jetzt das Gesamte Programm neu kompiliert und ausführt sollte man etwas wie das hier erreichen:

 

Wenn man doppel Rechtsklickt erkennt man schon die Sinuskurve

Die Regeln für die Erzeugung programmieren

Die Berechnung eines Pixels soll solange andauern bis die Folge die das Fraktal beschreibt konvergiert (sich also irgendwann nicht mehr groß verändert sondern nur noch in einem bestimmten Bereich bleibt). Wenn sie aber einfach nicht konvergieren will müssen wir irgendwann einfach abbrechen. Dies machen wir nach einer willkürlich festgelegten Anzahl von Schritten (Iterationen). Die Anzahl der Iterationen sollte möglichst nah an Unendlich liegen. Also eine möglichst große Zahl sein. Dieses mal wählen wir 42.

/**
* The Maximum number of iterations determines the Quality of the computation:
* A high number results in longer computation time, a low in less quality
*/

private int MAX_ITER = 42;

Um dem Pixel später eine Farbe geben zu können lassen wir uns einfach ausgeben ab wann die Folge konvergiert dazu geben wir einfach den Itterationschritt mit.

Die Folge auf der das Newtonfraktal aufbaut ist laut Wikipedia  [latex]z_{n+1} := z_{n} – \dfrac{p(z_{n})}{p'(z_{n})}[/latex]. Wobei [latex]p[/latex] hier eine Funktion ist die auf [latex]z[/latex] angewendet wird. Man denkt vielleicht , das es einfacher ist die Formel einfach rekursiv zu implementieren. Das Lohnt sich aber aus Performance-Gründen nicht. Denn in einer imperativen Implementierung können wir immer so früh wie möglich abbrechen. Das wird hoffentlich klar sobald der Code geschrieben wird.

Unser ausgegebenes Bild wird die Komplexe Ebene darstellen weil unsere Folge auf Komplexen Zahlen definiert ist müssen wir auch mit Komplexen Zahlen rechnen die sind praktischer Weise schon einmal für die Mandelbrotmenge implementiert worden. Also werden wir sie hier einfach importieren. Die Funktion die wir als nächstes implementieren bekommt dannn als Eingabe eine Komplexe Zahl und wird uns eine Farbe zurückgeben. Hier bekommen wir erstmal eine Zahl zurück die wir dann später in eine Farbe umwandeln können. Die Komplexe Zahl erhalten wir einfach aus den Koordinaten underes Pixels. So kann zum Beispiel die X-Koordinate den Imaginäranteil und die Y-Koordinate den Realanteil darstelllen. Später werden wir die Funktion einfach mit einer aus den Pixeln erzeugten komplexen Zahl aufrufen. Die Zahl die wir dann bekommen wandeln wir dann in eine Farbe um.

Die Methode sieht also erstmal so aus:

public int calcConvergence(ComplexNumber startValue) {
return null;
}

Jetzt kann man sich etwas konkreter überlegen was berechnet werden soll. Auf dem Deutschen Wikipedia wird die Funktion [latex]p(z)=z^{3}-1[/latex] vorgeschlagen wenn man von dieser Funktion ausgeht und dies in die Ursprungsdefinition des Newtonfraktals([latex]z_{n+1} := z_{n} – \dfrac{p(z_{n})}{p'(z_{n})}[/latex]) einsetzt erhält man folgende Folge [latex]z_{n+1} := z_{n} – \dfrac{(z_{n})^{3}-1}{3*(z_{n})^{2}}[/latex].

Das kann man jetzt versuchen in Code umzusetzen.

public int calcConvergence(ComplexNumber startValue) {

int iteration = 1; // die Anzahl der Itterationen soll gezählt werden

ComplexNumber aktuellerWert = new ComplexNumber(startValue); //mit dem startValue fängt die Folge an

while(iteration < MAX_ITER)
{

//divident berechnen
ComplexNumber divident = new ComplexNumber(aktuellerWert); 
divident.pot(3); //z³
divident.sub(1);//-1

//divisor 
ComplexNumber divisor = new ComplexNumber(aktuellerWert); 
divisor.quad(); // z²
divisor.mul(3.);//*3

//Subtrahend
ComplexNumber subtrahend = new ComplexNumber(divident);
subtrahend.div(divisor); // quotient = dividend/ divisor

//Differenz Berechnen
aktuellerWert.sub(subtrahend);
iteration++;
if(aktuellerWert.absSqr() > 4.0){
//nach http://de.wikipedia.org/wiki/Julia-Menge#Graphische_Darstellung_der_Julia-Mengen
break;
}
}
return iteration;

}

Danach ruft man calcConvergence in  calcPixel auf. Dabei kann man sich eine fast belibige Farb-Funktion schreiben. Ich habe einfach große Teile von der Implementierung des Mandelbrot Fraktals übernommen.

public Color calcPixel(Point2F coordinate) {

int iter = calcConvergence( new ComplexNumber(coordinate.x,coordinate.y));//Die Nummer holen auf der die Farbe beruht 
if(iter == MAX_ITER)
{
return Color.black;
}
else
{ double near = Math.sqrt(iter) / Math.sqrt((double)MAX_ITER);
return ColorFun.farbVerlauf(Color.getHSBColor((float) (((coordinate.x / 3) + 0.5f) % 1.f), 1.f, 1.f), Color.getHSBColor((float) (coordinate.x / 3), 1.f, 1.f), near);}
}

}

Wenn man das Programm jetzt wieder ausführt sollte man etwas wie das hier erhalten:

Ich bekomme leider nur das hier :

 

naja, vermutlich habe ich bei der implementierung von den komplexen Zahlen zu viel gefuscht aber was auch immer ich da jetzt erhalten habe. Es scheint immerhin ein Fraktal zu sein….

Quellcode

Wenn man sich den Code genauer ansehen will oder es einfach ausprobieren will kann man hier das Projekt anschauen. Vielleicht sagt mir ja jemand was noch nicht stimmt.