Inledning
I denna artikel kommer vi att visa att matematik kan vara snyggt och fascinerande rent bildmässigt. Du kanske har hört talas om fraktaler någon gång? Fraktaler är matematiska mönster som kommer från enkla formler.
Fokus kommer inte ligga på att förklara fraktaler utan istället kommer vi att visa olika optimeringstekniker samtidigt som vi skapar ett Windows Forms program som renderar en fraktal.
Mandelbrotfraktal
Fraktalen har fått sitt namn efter Benoît Mandelbrot som var en forskare som jobbade för IBM. Han intresserade sig för fraktaler och problem som hör samman med dessa. I början av 1980-talet så publicerade han en skrift med en samling fraktaler som han upptäckt, bl.a. den fraktal som kom att kallas Mandelbrotmängden. Det var först på 60-talet och framåt som man kunde visualisera fraktaler med hjälpa av datorer.
Det som fascinerar med fraktaler är den till synes enkla formel som ligger bakom mönstret. Mandelbrotmängden använder sig av komplexa tal och har formeln:
Vad säger denna formel egentligen? Jo om vi väljer värdet c = 1 som startpunkt och utgår från att z0 = 0 så får vi mängden {0, 1, 2, 5, 26, ...}. Denna mängd begränsas ej utan kommer att gå mot oändligheten. Vi säger då att 1 inte tillhör Mandelbrotmängden.
Om vi istället väljer c = -1 och z0 = 0 så får vi mängden {0, -1, 0, -1, 0, ...}. Denna mängd är begränsad och kommer inte att skena iväg mot oändligheten. Vi säger då att -1 tillhör Mandelbrotmängden.
I bilden ovan så använder vi istället det komplexa talplanet och låter punkten c vara ett komplext tal. Punkter som, i det komplexa talplanet, tillhör mängden färgar vi svarta. Övriga punkter ritas med en färg som indikerar hur snabbt mot oändligheten de är på väg. Gränsen mellan området som tillhör mängden och de som inte gör det bildar ett fantastiskt oändligt mönster. Vi använder färgskalan vit-gul-röd-svart för att illustrera hastigheten mot oändligheten. För vit så rör sig punkten långsamt och för gul lite snabbare etc.
Implementation
Vi börjar med att skapa ett Windows Application Program och döper det till "Mandelbrot". Vi döper sedan om "Form1.cs" till "Mandelbrot.cs".
Den enda extra komponent som vi lagt in är en PictureBox som vi döpt till "pictureBox". Vi sätter "Dock = Fill" i egenskaper för pictureBox för att bilden skall fylla hela programmet automatiskt. Själva renderingen måste vi sköta själva. Vi hoppar direkt på koden och tar en diskussion efteråt.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Drawing.Imaging;
using System.Linq;
using System.Runtime.InteropServices;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace Mandelbrot
{
public partial class Mandelbrot : Form
{
private Bitmap _image = null;
private double _startX = -2.4;
private double _startY = -1.3;
private double _stopX = 1.3;
private double _stopY = 1.3;
private readonly Color[] _colors = new Color[100];
public Mandelbrot()
{
InitializeComponent();
}
private void Mandelbrot_Load(object sender, EventArgs e)
{
CreateColors(new[] { Color.Black, Color.Red, Color.Yellow, Color.White },
new [] {0, 50, 80, 100});
RenderMandelbrot();
}
private void CreateColors(Color[] colors, int[] steps)
{
int index = 0;
for (int i = 0; i < colors.Length - 1; i++)
{
int range = steps[i+1] - steps[i];
Color start = colors[i];
Color destination = colors[i + 1];
for (int j = 0; j < range; j++)
{
_colors[index] = Color.FromArgb(
(int)(start.R + (destination.R - start.R) / (double)range * j),
(int)(start.G + (destination.G - start.G) / (double)range * j),
(int)(start.B + (destination.B - start.B) / (double)range * j));
index++;
}
}
}
private void RenderMandelbrot()
{
if (pictureBox.Height == 0 || pictureBox.Width == 0)
return;
var startTime = DateTime.Now;
_image = new Bitmap(pictureBox.Width, pictureBox.Height);
var xmin = _startX;
var ymin = _startY;
var xmax = _stopX;
var ymax = _stopY;
double stepX = (xmax - xmin) / _image.Width;
double stepY = (ymax - ymin) / _image.Height;
int height = _image.Height;
for (int screenX = 0; screenX < _image.Width; screenX++)
{
double x = xmin + stepX * screenX;
double y = ymin;
for (int screenY = 0; screenY < height; screenY++)
{
double x1 = 0.0, y1 = 0.0, xx = 0.0;
int looper = 0;
while (looper < 100 && ((x1*x1) + (y1*y1)) < 4)
{
looper++;
xx = (x1*x1) - (y1*y1) + x;
y1 = 2*x1*y1 + y;
x1 = xx;
}
int val = (looper == 100) ? 0 : looper;
var color = _colors[val];
_image.SetPixel(screenX, screenY, color);
y += stepY;
}
}
var timeSpan = DateTime.Now - startTime;
Debug.WriteLine(timeSpan.TotalMilliseconds + " ms");
pictureBox.Image = _image;
pictureBox.Invalidate();
}
private void Mandelbrot_Resize(object sender, EventArgs e)
{
RenderMandelbrot();
}
}
}
På rad 17 till 20 deklarerar vi variabler som bestämmer det "fönster" vi tittar på. Mandelbrotmängden befinner sig ungefär inom -2 < x < 1 och -1,3 < y < 1,3. Vi deklarerar också en Bitmap som vi renderar till och sedan sätter till vår pictureBox.
Vi deklarerar 100 färger som vi kommer att använda för att illustrera hastigheten mot oändligheten. Vi hakar på eventet "Form Load" och skapar färgerna samt renderar fraktalen (rad 32).
Skapandet av färger är i sig lite avancerat. Tanken är att vi skickar in ett fält med önskade färger samt ett motsvarande fält för index som bestämmer var i färglistan vi vill ha dessa färger. Metoden CreateColors ser sedan till att fältet _colors fylls med toningar mellan dessa färger. På index 0 blir det svart, på index 50 rött, index 80 gult och index 99 vitt (vi kommer inte nå index 100).
I RenderMandelbrot sker all magi. Här skapar vi först en Bitmap som fyller hela pictureBox. Därefter itererar vi över varje pixel i x-led (rad 71) och y-led (rad 76). stepX och stepY bestämmer hur varje pixel-steg i x och y-led påverkar variablarna x och y (punkten c i formeln för fraktalen).
I den inre loop'en på rad 80 så upprepas formeln för fraktalen. För att begripa denna till fullo så bör man vara införstådd i hur komplexa tal fungerar och kvadraten av ett sådant tal. Detta tar vi inte upp. Den inre loop'en körs max 100 ggr om inte den avbryts p.g.a. | zn | har blivit för stor.
När den inre loop'en avbryts så håller variabeln looper information om vilken färg som skall användas. Har vi kört 100 ggr så sätter vi färg 0 (=svart) på rad 88. Sedan fyller vi en pixel med korrekt färg.
Vi har också hakat på eventet "Resize" för formuläret så att vi kan rita om fraktalen i rätt storlek, rad 105.
Förbättringar
Visst hade det varit skoj att zoom'a in och ut också! Det löser vi genom att använda eventet "Mouse Click" på pictureBox. Där vi klickar zoom'ar vi in.
Vi börjar med att skapa en struct som innehåller koordinater för ett fönster så att vi kan "backa" vår zoom.
struct ZoomCoordinate
{
public double StartX;
public double StopX;
public double StartY;
public double StopY;
public ZoomCoordinate(double startX, double stopX , double startY , double stopY )
{
StartX = startX;
StopX = stopX;
StartY = startY;
StopY = stopY;
}
}
Vi kompletterar sedan Mandelbrot.cs med Click-eventet.
private readonly List<ZoomCoordinate> _positions = new List<ZoomCoordinate>();
private void pictureBox_MouseClick(object sender, MouseEventArgs e)
{
if (e.Button == MouseButtons.Left)
{
// Zoom in
double diffX = _stopX - _startX;
double diffY = _stopY - _startY;
double cX = _startX + (diffX) * (e.X / (double)this.Width);
double cY = _startY + (diffY) * (e.Y / (double)this.Height);
_positions.Add(new ZoomCoordinate(_startX, _stopX, _startY, _stopY));
_startX = cX - diffX / 4.0;
_stopX = cX + diffX / 4.0;
_startY = cY - diffY / 4.0;
_stopY = cY + diffY / 4.0;
RenderMandelbrot();
}
else if (e.Button == MouseButtons.Right)
{
// Zoom out
if (_positions.Count > 0)
{
var pos = _positions.Last();
_startX = pos.StartX;
_stopX = pos.StopX;
_startY = pos.StartY;
_stopY = pos.StopY;
_positions.RemoveAt(_positions.Count - 1);
RenderMandelbrot();
}
}
}
Vänsterklick zoom'ar in genom att beräkna om _startX, _startY, _stopX, _stopY samtidigt som vi sparar undan värdena som en ZoomCoordinate.
Vid högerklick kolla vi om det finns någon tidigare koordinat i listan att återgå till. Vi kan på så vis hoppa tillbaka dit vi var innan.
Optimera bort SetPixel
Metoderna GetPixel och SetPixel i klassen Bitmap är ökänt långsamma. Vi kan få bättre prestanda genom att undvika dessa metoder.
Genom att använda LockBits kan vi få en BitmapData med "rådata". Utifrån denna kan sedan alla bytes som bygger upp bilden kopieras ut till en buffer. Vi kan sedan manipulera buffern genom att beräkna index för ett visst x och y-värde och sedan skriva in det ARGB-värde (alpha, röd, grön, blå) som är vår färg.
Bara 1 CPU?
I dagens datorer sitter det oftast 2-6 kärnor (CPU), eller ännu fler. Det vore ju dumt att bara använda 1 kärna eller hur?
Ett program körs alltid i en process/tråd. Programmet kan inte automatiskt dela upp sig och köras på flera kärnor. För att kunna dela upp arbete måste vi programmerare hjälpa till. Samtidigt måste uppgiften kunna gå att delas upp, vi kan inte t.ex. dela upp en uppgift vars arbete hela tiden bygger på tidigare arbeten.
I .Net sedan version 4 (VS 2010) så har man lagt in stöd för att dela upp arbete i parallella trådar. Namnutrymmet heter passande nog Parallel. Den vanligaste varianten är att parallellisera loop'ar. Det betyder att istället för att 1 tråd kör alla iterationer så delas iterationerna upp mellan flera trådar.
Vi kommer att använda oss av Parallel.For och ersätta den yttre loop'en i RenderMandelbrot. De vertikala linjerna kommer då att renderas i olika trådar. Vanligtvis skapas det fler trådar än vad man har kärnor. När for-loop'en är klar så synkroniseras alla trådar så att allt arbete är klar innan exekveringen fortsätter som vanligt i 1 tråd.
Vi presenterar nu en optimerad variant av RenderMandelbrot med de två ändringar som diskuterats:
private void RenderMandelbrot()
{
if (pictureBox.Height == 0 || pictureBox.Width == 0)
return;
var startTime = DateTime.Now;
_image = new Bitmap(pictureBox.Width, pictureBox.Height);
BitmapData bData = _image.LockBits(new Rectangle(0, 0, _image.Width, _image.Height),
ImageLockMode.ReadWrite, _image.PixelFormat);
int size = bData.Stride * bData.Height;
byte[] data = new byte[size];
System.Runtime.InteropServices.Marshal.Copy(bData.Scan0, data, 0, size);
var xmin = _startX;
var ymin = _startY;
var xmax = _stopX;
var ymax = _stopY;
double stepX = (xmax - xmin) / _image.Width;
double stepY = (ymax - ymin) / _image.Height;
int height = _image.Height;
Parallel.For(0, _image.Width, screenX =>
{
double x = xmin + stepX * screenX;
double y = ymin;
for (int screenY = 0; screenY < height; screenY++)
{
double x1 = 0.0, y1 = 0.0;
int looper = 0;
while (looper < 100 && ((x1*x1) + (y1*y1)) < 4)
{
looper++;
double xx = (x1*x1) - (y1*y1) + x;
y1 = 2*x1*y1 + y;
x1 = xx;
}
int val = (looper == 100) ? 0 : looper;
var color = _colors[val];
data[(screenX*4 + screenY*bData.Stride) + 0] = color.B;
data[(screenX*4 + screenY*bData.Stride) + 1] = color.G;
data[(screenX*4 + screenY*bData.Stride) + 2] = color.R;
data[(screenX*4 + screenY*bData.Stride) + 3] = color.A;
y += stepY;
}
});
System.Runtime.InteropServices.Marshal.Copy(data, 0, bData.Scan0, data.Length);
_image.UnlockBits(bData);
var timeSpan = DateTime.Now - startTime;
Debug.WriteLine(timeSpan.TotalMilliseconds + " ms");
pictureBox.Image = _image;
pictureBox.Invalidate();
}
Resultat av optimering
Att rendera en bild på 1366x706 pixlar tog 1063 ms på min dator. Datorn är en laptop med i5-processor.
Att undvika SetPixel sänkte renderinstiden till 499 ms. Nästan en halvering! Där kan vi också nämna att det finns ytterligare förbättringar att göra genom att använda pekare och unsafe. Troligtvis går det att sänka renderingstiden med ytterligare 20%.
När vi införde Parallel så sänktes renderingstiden till 124 ms! Det skalar rätt väl med det faktum att datorn har 4 kärnor. En fjärdedel så långt tid.
Avslutning
Detta var en kort introduktion till fraktaler och optimering, främst då Parallell programmering något som efterfrågas mer och mer. Att förstå problematiken med flertrådade applikationer och de fällor man kan hamna i är inget man lär sig på några timmar. För vidare läsning rekommenderar vi Threading in C#, en gratis e-bok.
Koden till projektet finns nedan samt en kort video som visar hur programmet fungerar.