PHP: Mandelbrot Programmering

Limited edition

Trådstarter

22. juli 2011

2 - Programmering

Så over til det som har med programmering å gjøre: Hvordan skriver vi et program som kan tegne Mandelbrot-figuren? Jeg har skrevet det i PHP - kanskje ikke det mest optimale språket å bruke - men det er nå en gang det jeg kan best. Det hadde vært spennende å se kreative bidrag fra andre språk; kanskje aller mest spesielt vakre bilder, optimalisert kode eller utgaver med ASCII-art (for eksempel i kommandolinje).

Jeg bruker ganske mange variabler og det er en del tricky matematikk ute og går. Som jeg har prøvd å forklare over, så skjønner jeg ikke alle prinsippene som er i sving her - men det må gjerne de som kan utdype. Variablene er som følger:

iterations
Det maksimale antallet iterasjoner vi tillater. Jeg har forklart smått tidligere hva dette dreier seg om, men i all korthet - et høyere tall krever mer ressurser og vil gi et bedre resultat. Kan sammenlignes med oppløsning på et bilde, eller nøyaktighet i utregningen.

width
height
Dimensjonene på det ferdige bildet vi skal lage, i pixler. I dette eksemplet bruker jeg 500 på begge.

x_min
x_max
y_min
y_max
Minimum- og maksimal-verdier for koordinatsystemet vårt. Det er ganske små verdier vi jobber med, og for et bilde av hele figuren bruker jeg verdier fra -2 til +1 på X-aksen og +1,5 til -1,5 på Y-aksen. Når vi jobber med koordinater så er det viktig å huske på at Y-aksen er omvendt fra det logikken i datamaskiner tilsier - positive verdier er øverst, og negative verdier er nederst. For å unngå at bildet blir strukket, bruker jeg en formel for å beholde proposjonene når jeg allerede har definert størrelse på bildet. Det kommer jeg tilbake til.

x_coordinate_factor
y_coordinate_factor
Her begynner moroa. Disse variablene beskriver forholdet mellom koordinatene i det tenkte koordinatsystemet vårt og de faktiske pixlene på dataskjermen. Det vil være ganske opplagt når regnestykkene dukker opp, hvorfor det er lurt å lagre disse to verdiene (for X og Y) på forhånd.

x
y
Dette er de kuleste variablene - rett og slett hvilken pixel vi jobber med. Disse bruker vi i loopene når vi går gjennom alle pixlene i bildet.

x_complex
y_complex
Nå blir det enda mer moro. Disse verdiene er de komplekse tallene for koordinatet vi jobber med og nå nærmer vi oss det punktet hvor jeg bare aksepterer at det er sånn det må være - ikke nødvendigvis fordi jeg forstår hvorfor. Som vi skal se snart i utregningen, er disse variablene aksens minsteverdi (x_min) pluss koordinatet vi er på (x) ganger forholdet mellom koordinater og pixler (x_coordinate_factor). Igjen, husk på at formelen for Y-aksen må snus litt på hodet fordi Y-aksen blir negativ når vi beveger oss nedover. Mer om det senere, altså.

a
b
Dette er midlertidige variabler jeg bruker i utregningen. Som sagt, så må vi kjøre Mandelbrot-funksjonen opptil 50 ganger (avhengig av hvor mange iterasjoner vi har), og vi må mellomlagre resultatet fra hver utregning et sted. A og B starter med samme verdi som x_complex og y_complex, men endrer seg etter hvert som vi kjører Mandelbrot-funksjonen. Vi kunne ha brukt x_complex og y_complex i denne loopen også, og resatt den til originalverdien i neste koordinat ved å regne ut forrige avsnitt på nytt - men det er jo ikke optimalt i forhold til ressursbruk. Vi sparer krefter på å regne minst mulig. X_complex endres altså bare én gang per x-verdi (variabelen x).

is_zero
Dette er en boolean vi bruker til å sjekke om koordinatet tilhører Mandelbrot-mengden eller ei (uendelig eller 0).

i
Dette er den iterasjonen vi jobber med akkurat nå; brukes i en for-løkke mens iterasjonene pågår. Denne variabelen bruker i i kalkulasjonen for farger.

a2
b2
Dette er kvadratet av a og b. Dette er tall vi trenger i Mandelbrot-formelen, og det er like greit å lagre dem i egne variabler for å gjøre selve regnestykket mer lettfattelig. For oss ikke-matematikere, kvadratet av et tall får du om du ganger tallet med seg selv. Det omvendte av kvadratroten, altså.

That's it!

Nå skal jeg begynne å snakke konkret kode. For å produsere et bilde i PHP trenger vi noen funksjoner til;

header("Content-type: image/png");
Sender beskjed om at output fra koden er et bilde, ikke en nettside.

imagecreatetruecolor();
Lager en ressurs (PHP-begrep) som basically er en variabel som er et bilde.

imagecolorallocate();
Oppretter en farge som kan brukes i en bilderessurs.

imagesetpixel();
Overfører en farge til en spesifikk pixel i bildet.

imagepng();
Sender bildet fra server til nettleser, litt som bildeutgaven av echo eller print.

Logikken er forholdsvis enkel (i psuedokode):

Kode

Sett opp variablene iterations, width, height, x_min, x_max, y_min, y_max, x_coordinate_factor og y_coordinate_factor
for(Y) {
	Regn ut y_complex
	for(X) {
		Regn ut x_complex
		Regn ut a, b og sett is_zero
		
		for(i) {
			Regn ut a2 og b2
			if(kvadratrot av a2 + b2 > 2) {
				is_zero = false
				bryt for(i)-løkken (break)
			}
			
			Neste iterasjon:
			Regn ut a og b på nytt
		}

		if(is_zero) {
			svart pixel (innenfor Mandelbrot-figuren)
		} else {
			ikke-svart pixel (utenfor figuren)
		}
	}
}

Enda en optimaliseringsgreie jeg plukket opp i artikkelen jeg lenket tidligere, er if-løkken innerst:
kvadratrot av a2 + b2 > 2

Denne kan forenkles ved å opphøye begge sider i andre, slik:
(kvadratrot av a2 + b2)² > 2²

... og da kan vi utrykke akkurat det samme på denne måten (kvadratroten nøytraliseres):
a2 + b2 > 4

Det gjør utrykket enklere og bidrar til å optimalisere prosessen bittelitt. Denne sjekken kan tross alt utføres opptil 50 ganger per pixel i mitt tilfelle.

Grunnen til at jeg forklarer logikken i psuedokode er, som noen kanskje skjønner, at det lettere kan overføres til et hvilken som helst annet programmeringsspråk. Det er nå i utgangspunktet bare én del som mangler for den komplette koden, og det er kodeblokken for å regne ut fargekodene for feltene på utsiden av Mandelbrot-mengden. Det foregår på følgende måte:

Fargeverdiene setter jeg med RGB, tre tall mellom 0 og 255. Det er henholdsvis rød, grønn og blå. Det mest stilige resultatet, slik jeg ser det, får vi ved å ha en gradient som går fra svart, til en farge, og videre til hvit nærmest Mandelbrot-figuren. Det betyr at vi må ha en dobbel if-løkke, en for å behandle verdier fra svart til en farge, for eksempel grønn, og én som behandler fra grønn til hvit. Det kan vi utrykke på denne måten:

Kode

Recap: "i" er antallet iterasjoner vi har brukt for dette koordinat-settet, og "iterations" er det største antallet iterasjoner vi tillater.

if(i >= 0 OG i < iterations / 2) {
	Fra svart til grønn:
	color = (255 / iterations) * i;
} else if(i >= iterations / 2 OG i <= iterations) {
	Fra grønn til hvit:
	color = (255 / iterations) * i;
}

"Color" vil nå være et tall fra 0 til 255. Det fine med å gjøre det sånn er at fargene blir jevnere i overgangene, jo flere iterasjoner du bruker. Dynamikk, altså. Smoothie.

Når vi da setter sammen alt dette her, så ender vi opp med noe sånt:

Kode

<?php

// For lange kalkulasjoner kan det være greit å skru av execution time limit for skriptet. 0 er uendelig:
set_time_limit(0);

// Maks antall iterasjoner:
$iterations = 50;

// Høyde og bredde:
$width = 500;
$height = 500;

// Rammekoordinater:
$x_min = -2.0;
$x_max = 1.0;
// Kalkulasjon: Lengden på X-aksen delt på to med omvendt fortegn. It makes sense if you don't think about it.
$y_min = (($x_max - $x_min) / 2) * -1;
// Mer kalkulasjon: Minste Y-verdi pluss lengden av X-aksen ganger forholdet mellom høyde og bredde:
$y_max = $y_min + ($x_max - $x_min) * $height / $width;

// Forholdet mellom koordinater og pixler:
$x_coordinate_factor = ($x_max - $x_min) / ($width - 1);
$y_coordinate_factor = ($y_max - $y_min) / ($height - 1);

// Send header og sett opp bilderessursen:
header("Content-type: image/png");
$image = imagecreatetruecolor($width, $height);
// Opprett en svart fargevariabel:
$black = imagecolorallocate($image, 0, 0, 0);

// Start loopen for Y-aksen:
for($y = 0; $y < $height; $y++) {
	// Regn ut første del av det komplekse tallet; husk at Y-aksen er omvendt av det vi kanskje finner logisk:
	$y_complex = $y_max - $y * $y_coordinate_factor;
	
	// Start loopen for X-aksen:
	for($x = 0; $x < $width; $x++) {
		// Regn ut andre del av det komplekse tallet:
		$x_complex = $x_min + $x * $x_coordinate_factor;
		
		// Overfør variablene til mellomlagringsvariablene våre:
		$a = $x_complex;
		$b = $y_complex;
		// Sett opp booleanen:
		$is_zero = true;
		
		// Start iterasjonsloopen:
		for($i = 0; $i < $iterations; $i++) {
			// Regn ut kvadratet av de komplekse tallene:
			$a2 = $a * $a;
			$b2 = $b * $b;
			
			// Sjekk om tallene nærmer seg uendelig store:
			if($a2 + $b2 > 4) {
				// På dette punktet kan vi fastslå at tallet blir uendelig stort.
				$is_zero = false;
				// Regn ut fargeverdi for denne pixelen:
				if($i >= 0 && $i < $iterations / 2) {
					// Gradient fra svart til grønn:
					$color = (255 / $iterations) * $i;
					// Opprett farge:
					$color = imagecolorallocate($image, 0, $color, 0);
				} else if($i >= $iterations / 2 && $i <= $iterations) {
					// Gradient fra grønn til hvit:
					$color = (255 / $iterations) * $i;
					// Opprett farge:
					$color = imagecolorallocate($image, $color, 255, $color);
				}
				// Bryt iterasjonsloopen:
				break;
			}
			
			// Neste iterasjon, regn ut på nytt:
			$b = 2 * $a * $b + $y_complex;
			$a = $a2 - $b2 + $x_complex;
		}
		
		// Iterasjonsloopen er ferdig, sjekk om vi er innenfor Mandelbrot-mengden:
		if($is_zero) {
			// Innenfor, bruk svart farge:
			imagesetpixel($image, $x, $y, $black);
		} else {
			// Utenfor, bruk grønn farge (kan også være svart, avhengig av avstand fra sentrum):
			imagesetpixel($image, $x, $y, $color);
		}
	}
}

// Skriv ut resultatet:
imagepng($image);

?>

Om du har et sted å kjøre PHP-kode, så kan du faktisk kopiere alt inni boksen over og kjøre i gang. Resultatet skal bli circa slik:

http://www.kiwhen.com/resources/nff/mandelbrot2.jpg

Dette er altså med 50 iterasjoner. For å sammenligne, her er samme bilde med 10 iterasjoner:

http://www.kiwhen.com/resources/nff/mandelbrot3.jpg

Hvis du ser nøye etter, så er det altså ikke nyansene som sådan som er forskjellen, men heller nøyaktigheten av selve figuren. Den vil fremdeles ha et uendelig spekter med detaljer, men fordi datamaskinen avbryter utregningen tidligere, vil den ikke klare å mappe alle punktene like nøyaktig. Derfor vil den i noen tilfeller tro at pixler utenfor Mandelbrot-mengden er en del av figuren, rett og slett fordi det tar for lang tid å regne ut at de vokser over 2.

Jeg synes som sagt at dette her er skikkelig spennende, og håper det er flere som blir litt fascinert av konseptet. Det er fullt mulig å modifisere koden til å rendre et mindre område av figuren. Et populært område som er spesielt vakkert heter "Sea horse valley", og befinner seg i kløften mellom den største og den nest største delen av figuren:

http://www.kiwhen.com/resources/nff/mandelbrot4.jpg

Å komme seg inn dit er et spørsmål om å tweake koordinatsystemet. Matematikken er allerede på plass, så det eneste vi trenger å gjøre er å endre verdiene på koordinatsystemet slik at det blir større. Det er her det blir kjekt å ha variabler på minimum og maksimum på begge aksene. Hvis vi endrer verdiene til dette:

Kode

$x_min = -0.8;
$x_max = -0.7;
$y_min = 0.1;
$y_max = $y_min + ($x_max - $x_min) * $height / $width;
// Det siste er den samme linja som før - du trenger strengt tatt ingen nye verdier for den siden den regner ut forholdene på egenhånd

... så ser vi dette:

http://www.kiwhen.com/resources/nff/mandelbrot5.jpg

Her har jeg guffet på med 100 iterasjoner for å få frem litt mer av de bittesmå detaljene. Se på den øverste av de røde pilene på det forrige bildet; det er der vi befinner oss. Årsaken til at "plassen" kalles "Sea horse valley" blir litt mer åpenbar jo flere iterasjoner du tør å prøve. Igjen, det er et spørsmål om prosessorkraft.

Så there's that, Mandelbrot-mengden i PHP. Neste steg for min del er å skrive et utrykk for å kunne zoome inn på et spesifikt område uten å måtte kløne med grensetallene til koordinatsystemet, og ikke minst ta det et skritt videre med en lignende fraktal, kalt "The Julia set". Dette er skremmende likt, men med Julia-formelen kan man produsere et uendelig antall unike bilder - i motsetning til Mandelbrot-figuren som alltid er den samme. Det er selvsagt et ganske flytende begrep, siden figuren er uendelig stor.

En liten fotnote til de som ikke er alt for stødige i PHP og bare kopierer koden min; pass på at du ikke har tekstbryting, ettersom det kan hende at noen av kommentarene blir brutt opp og havner over flere linjer. Det kan føre til at skriptet krasjer. Eksempelvis:

Kode

// Dette er en kommentar som
har blitt brutt opp over to linjer

Noen ganger kan det også dukke opp mellomrom (whitespace) i kodeboksene som messer opp, de er litt vanskeligere å oppdage. Så får jeg bare håpe at det ikke har havnet alt for mange copy/paste- eller faktafeil inni her - jeg har som sagt to mål med dette innlegget; å vise folk hvor awesome fraktaler er og kanskje få tak i litt mer info om matematikken som er involvert. Lag Mandelbrot i ditt favorittspråk og post et bilde!