Die Technik der Computergrafik ist komplex. Zum Einstieg in die Thematik verzichten wir zunächst auf die Ansteuerung von Grafiksystemen und ihrer Hardwarebeschleunigung bis wir Grundwissen darüber erlangt haben, wie Computer Grafiken erzeugen und verarbeiten.
Das einfachst mögliche Grafiksystem ist ein eigens definierter Grafikpuffer. Zur Betrachtung schreiben wir diesen in eine Bilddatei im PPM-Format, die dann mit externen Programmen in ein komprimiertes Bildformat umgewandelt werden kann.
Eine typische geeignete Aufgabe ist die Erzeugung so eines Bildes der Mandelbrotmenge. Der Programmieraufwand dafür ist recht gering.
Zunächst steht die Überlegung an, wie die Darstellung von Farben erfolgen soll. Üblicherweise geschieht dies mit dem RGB-Farbraum, wo jede Farbe ein Tripel aus Rot-, Grün- und Blau-Anteil ist, die jeweils Werte von 0 bis 255 annehmen. Alle Farben sind additiv aus diesen drei Anteilen zusammengesetzt. Die Farbe Schwarz ist (0, 0, 0) und Weiß ist (255, 255, 255). Man kann sich jetzt darüber streiten, ob Schwarz, Weiß und die Grautöne dazwischen zu den Farben zu zählen sind. Da diese aber auch im Farbraum liegen, liegt mir das nahe.
Weil Lese- und Schreiboperationen in den Speicher langsam sind,
reduziert man deren Anzahl am besten durch Zusammenfassung der
Bytes zu einer u32-Zahl. Hierbei bleibt ein Byte unbesetzt, das
später für den Alpha-Wert benutzt wird. Die Definition eines
neuen abstrakten Datentyps Color sorgt dafür, dass wir
uns um die interne Bit-Arithmetik keine Gedanken mehr machen müssen.
Die interne Reihenfolge kann man dann später ggf. leicht an die
genutzte Binärschnittstelle eines weiteren Grafiksystems adaptieren.
#[derive(Clone,Copy)]
struct Color(u32);
impl Color {
pub fn rgb(r: u8, g: u8, b: u8) -> Self {
Color(u32::from(b)<<16 | u32::from(g)<<8 | u32::from(r))
}
pub fn to_rgb(self) -> (u8, u8, u8) {
(self.0 as u8, (self.0>>8) as u8, (self.0>>16) as u8)
}
}
Zum Setzen von Pixeln wird eine Funktion pset(x,y)
dienen, wobei x,y die nichtnegativen ganzzahligen
Koordinaten sind. Es ist üblich, dass man in der linken oberen
Ecke des Bildes startet, x nach rechts zählt und
y nach unten. Hat das Bild eine Größe von
width*height Pixeln, ist
0 ≤ x < width
und 0 ≤ y < height.
Da der Computer die Pixel sequenziell im Speicher anordnet
und nichts von der zweidimensionalen Struktur weiß, bedarf es
einer Speicherabbildungsfunktion index(x,y), die
die beiden Koordinaten in einen Index eines eindimensionalen Feldes
data überführt. Das ist
index(x,y) = width*y + x.
Ein neuer abstrakter Datentyp Canvas (Leinwand)
schafft wieder eine Abstraktion von den internen Details.
struct Canvas {
width: u32, height: u32,
data: Box<[Color]>
}
impl Canvas {
pub fn new(width: u32, height: u32, color: Color) -> Self {
let data = Box::from(vec![color; (width*height) as usize]);
Self {width, height, data}
}
pub fn pset(&mut self, x: u32, y: u32, color: Color) {
self.data[(self.width*y + x) as usize] = color;
}
pub fn width(&self) -> u32 {self.width}
pub fn height(&self) -> u32 {self.height}
}
Schließlich braucht es noch Funktionalität zur Umwandlung des Puffers in eine PPM-Datei und eine Funktion zum Speichern der Datei.
struct PPM {data: Vec<u8>}
impl Canvas {
fn encode(&self) -> PPM {
let cap = 3*self.data.len() + 20;
let mut buffer: Vec<u8> = Vec::with_capacity(cap);
buffer.append(&mut format!("P6 {} {} 255\n",
self.width, self.height).into_bytes());
for color in self.data.iter() {
let (r, g, b) = color.to_rgb();
buffer.push(r);
buffer.push(g);
buffer.push(b);
}
PPM {data: buffer}
}
pub fn save(&self, path: &str) -> Result<(), std::io::Error> {
use std::io::Write;
let ppm = self.encode();
let mut file = std::fs::File::create(path)?;
file.write_all(&ppm.data)
}
}
Benötigt ist nun ein Übergang von Pixelkoordinaten zu einer
vektoriellen Beschreibung. Hierfür definieren wir ein
Koordinatensystem System, das auch gleich die Information
über die Position und Skalierung in der komplexen Zahlenebene
enthält. Jedem Pixel wird damit eine komplexe Zahl zugeordnet.
Die Pixelkoordinaten seien (px,py). Wir wollen jetzt
haben, dass der Koordinatenursprung in der Bildmitte liegt. Das wird
Erreicht durch Subtraktion der halben Breite bzw. Höhe:
px' = px - 0.5*width, py' = py - 0.5*height.
Bei Einheitsskalierung soll bei x = 1 die rechte Bildkante erreicht werden. Wir wollen haben:
x = 1 => px = width.
Keine komplizierte Mathematik, nur ein paar proportionale und lineare Gleichungen. Das macht
x = 1/(0.5*width)*(px - 0.5*width), y = 1/(0.5*width)*(py - 0.5*height).
Zu beachten ist nun noch, dass y in spiegelverkehrte
Richtung läuft, was durch die Substitution
y := -y beseitigt wird.
Hinzufügen von Skalierung scale und Position
(x0,y0) bringt schließlich
x = x0 + scale/(0.5*width)*(px - 0.5*width), y = y0 - scale/(0.5*width)*(py - 0.5*height).
Definieren wir kurz die Arithmetik von komplexen Zahlen.
mod complex {
#[derive(Clone,Copy)]
pub struct C64 {pub re: f64, pub im: f64}
impl C64 {
pub fn abs_sq(self) -> f64 {
self.re*self.re + self.im*self.im
}
}
impl std::ops::Add<C64> for C64 {
type Output = Self;
fn add(self, y: Self) -> Self {
Self {re: self.re + y.re, im: self.im + y.im}
}
}
impl std::ops::Sub<C64> for C64 {
type Output = Self;
fn sub(self, y: Self) -> Self {
Self {re: self.re - y.re, im: self.im - y.im}
}
}
impl std::ops::Mul<C64> for C64 {
type Output = Self;
fn mul(self, y: Self) -> Self {
Self {
re: self.re*y.re - self.im*y.im,
im: self.re*y.im + self.im*y.re
}
}
}
}
Für die Funktion
fc(z) = z2 + c
mit festem c = x + yi nimmt man nun eine Iteration
zn+1 = fc(zn)
mit Startwert z0 = 0 vor. Den Startwert machen wir am besten gleich zu einer Funktion von c, damit man mit dem Programm auch Julia-Mengen zeichnen lassen kann. Die Iteration geht solange wie |zn|2 < 4 ist.
use complex::C64;
fn sigmoid(x: f64) -> f64 {
x/(x + 1.0)
}
fn choose_color(i: u32, gradient: f64) -> Color {
let t = (255.0 - 255.0*sigmoid(gradient*f64::from(i))) as u8;
Color::rgb(t, t, t)
}
struct System {
canvas: Canvas, scale: f64, pos: (f64,f64),
gradient: f64, max_iter: u32
}
impl System {
fn new(canvas: Canvas, scale: f64, pos: (f64,f64)) -> Self {
Self {canvas, scale, pos, gradient: 0.04, max_iter: 1000}
}
fn fractal(&mut self,
f: &dyn Fn(C64,C64) -> C64,
z0: &dyn Fn(C64) -> C64
) {
let w = self.canvas.width();
let h = self.canvas.height();
let w2 = 0.5*f64::from(w);
let h2 = 0.5*f64::from(h);
let scale = self.scale/w2;
let (x0, y0) = self.pos;
let max = self.max_iter;
let gradient = self.gradient;
let canvas = &mut self.canvas;
for py in 0..h {
for px in 0..w {
let x = x0 + scale*(f64::from(px) - w2);
let y = y0 - scale*(f64::from(py) - h2);
let c = C64 {re: x, im: y};
let mut z = z0(c);
let mut count: u32 = 0;
while count < max {
z = f(z, c);
if z.abs_sq() > 4.0 {break;}
count += 1;
}
if count < max {
canvas.pset(px, py, choose_color(count, gradient));
}
}
}
}
}
Nun endlich die Berechnung. Für die Bildmaße benutze ich gerne hochzusammengesetzte Zahlen. Als Seitenverhältnis benutze ich oft 3/2 in Form von 360/240 und Vielfachen oder 8/5 in Form von 480/300 und Vielfachen, das kommt dem goldenen Schnitt einigermaßen nahe.
fn main() -> Result<(), std::io::Error> {
let canvas = Canvas::new(720, 480, Color::rgb(0, 0, 0));
let mut s = System::new(canvas, 2.0, (-0.5, 0.0));
s.fractal(&|z, c| z*z + c, &|_| C64 {re: 0.0, im: 0.0});
s.canvas.save("Fraktal.ppm")?;
Ok(())
}
Das Resultat:
Die Datei ist etwas über 1 MB groß. Mit pnmtopng
aus Netpbm kann man die in eine schon stark komprimierte PNG-Datei
umwandeln. Mit optipng und zopflipng lässt
sich diese anschließend auf ca. 20 KB komprimieren.
pnmtopng Fraktal.ppm > Fraktal.png optipng Fraktal.png zopflipng -ym Fraktal.png Fraktal.png