senäh

17senäh und so…

WebGL Thumb

HTML/CSS/JS
17. Mrz 2012
Kommentare: 5

Make some (Perlin) Noise!

Kategorien: HTML/CSS/JS | 17. Mrz 2012 | Kommentare: 5

Serie: Landschaften generieren

  • Teil 1: Make some (Perlin) Noise!

Prozedurale Synthese. Habt ihr schon einmal davon gehört? Darüber wollte ich ursprünglich mal meine Bachelorarbeit schreiben. Prozedurale Synthese bedeutet, dass Daten (Grafiken, Musik oder was auch immer) durch einen speziellen Algorithmus generiert werden. Das heißt, dass euer Computer bestimmte Inhalte generiert und ihr als Programmierer könnt diese Inhalte beeinflussen. Je nach Daten/Inhalte, die generiert werden sollen, funktioniert das unterschiedlich gut/einfach. So gibt es noch kein Computerprogramm, welches euch einen Beststeller-Roman entwirft. Aber es gibt andere ziemlich beeindruckende Dinge, die ihr damit tun könnt. Ihr könnt euch zum Beispiel eure eigene Welt generieren lassen! Glaubt ihr nicht? In dieser Serie erfahrt ihr, wie es geht! 😛

Anforderungen

Was wollen wir am Ende erreichen? Wir werden eine Landschaft mit Bergen und Tälern erstellen. Diese Landschaft werden wir mit three.js darstellen und sie soll begehbar sein. Zuvor müssen wir jedoch eine Möglichkeit finden, wie wir unsere „Landschaftsdaten“ generieren. Ohne diese können wir three.js nicht sagen, wie die Landschaft aussehen soll. Wir bedienen uns deswegen eines im Grafikbereich bekannten Verfahrens: Noise und Heightmaps. Klären wir der Reihe nach, was diese Begriffe bedeuten.

Noise

Noise ist das englische Wort für Rauschen. Wow! 😉 Ihr kennt das z.B. von eurem Fernseher, wenn ihr einen Kanal einschaltet, auf welchem kein Sender einprogrammiert wurde. Dann seht ihr schwarz-weißes Rauschen, welches durch „Störungen“ im Fernsehsignal entsteht. Das sieht ungefähr so aus (und ja – irgendwer stellt sowas auf YouTube):

Nun kann man aus diesem Rauschen bestimmte Daten ableiten und sie für eigene Zwecke weiterverwenden. Welche Daten meine ich? Die weißen und schwarzen Punkte! Ihr wisst ja als gute Programmierer, dass euer Computer in 1 und 0 denkt und ihr mit diesem Binärsystem jede Art von Daten darstellen könnt, die ihr wollt. Das Rauschen funktioniert ganz ähnlich. So kann ein schwarzer Punkt eine 1 darstellen und ein weißer Punkt eine 0. Ihr könnt aber noch viel mehr damit anfangen. So besitzt jeder Punkt eine x- und eine y-Position. Zusätzlich könntet ihr – wenn ihr wollt und ich sage euch: wir wollen! – Werte dazwischen interpolieren, also bspw. grau mit 0,5 darstellen.

Diese Art von Rauschen ist vollkommen willkürlich und deswegen schlecht manipulierbar. Wir benötigen ein manipulierbares Rauschen. Dieses gibt es u.a. in der Form des „Perlin Rauschens“ bzw. Perlin Noise, benannt nach seinem Erfinder Ken Perlin. Glücklicherweise hat der Programmier Kas Thomas Ken Perlins Algorithmus zur Erzeugung des Rauschens nach JavaScript portiert. Wir werden seinen portierten Code auch in unserem Beispiel verwenden. Für nähere Informationen über die genaue Implementierung solltet ihr euch seinen Artikel ruhig einmal durchlesen.

Wunderbar. Wir haben manipulierbares Rauschen. Aber wozu genau benötigen wir das…?

Heightmaps

Heightmaps to the rescue! Mit einer Heightmap kann die Oberflächenstruktur einer Ebene beschrieben werden. Dazu werden die „Daten“ der Heightmap auf eine ursprünglich flache Ebene übertragen, um sie so zu manipulieren. Typischerweise ist eine Heightmap schwarz-weiß, wobei dunkle Punkte eine „Vertiefung“ repräsentieren und helle Punkte eine „Erhöhung“. Wir verwenden unser Rauschen als Fundament für eine Heightmap, wobei hier das gleiche Prinzip besteht: der Grauton eines Punktes im Rauschen beschreibt die Vertiefung/Erhöhung eines Punktes auf einer Landschaft. Das sieht dann ungefähr so aus (Quelle):

Heightmap (Source: http://en.wikipedia.org/wiki/File:Heightmap_rendered.png)

Heightmap (Source: http://en.wikipedia.org/wiki/File:Heightmap_rendered.png)

Cool oder? Lasst uns nun zu Anschauungszwecken ein Rauschen ertsellen.

Das Praxisbeispiel

Um ein Rauschen zu Erzeugen benötigen wir drei Schritte:

1. Wir müssen über die Pixel eines Canvas Elements loopen.
2. Jeder Pixel muss an eine Shader-Funktion übergeben, dort manipuliert und dann wieder zurückgegeben werden.
3. Die Shader-Funktion greift auf den Perlin Noise Algorithmus zu um die Pixeldaten zu manipulieren.

Hier seht ihr die Funktion, welche über die Pixel eines Canvas Elements loopt. Ich nenne sie manipulateImageData und sie benötigt als Parameter eine Referenz auf das Canvas-Element sowie die Shader-Funktion:

var manipulateImageData = function(canvas, shader) {
var w = canvas.width;
var h = canvas.height;
var context = canvas.getContext("2d");

var imageData = context.createImageData(w, h);

for (var i = 0, l = imageData.data.length; i < l; i += 4) {
var x = (i / 4) % w;
var y = Math.floor(i / w / 4);

var r = imageData.data[i + 0];
var g = imageData.data[i + 1];
var b = imageData.data[i + 2];
var a = imageData.data[i + 3];

var pixel = shader(r, g, b, a, x, y, w, h);

imageData.data[i ] = pixel.r;
imageData.data[i + 1] = pixel.g;
imageData.data[i + 2] = pixel.b;
imageData.data[i + 3] = pixel.a;
}

context.putImageData(imageData, 0, 0);
};

Die Shader-Funktion kann je nach Beispiel anders aussehen. Sie dient dazu die Rot, Grün, Blau und Alpha-Werte eines Pixels zu verändern. Der Wertebereich für alle vier Parameter liegt zwischen 0 und 255. Pro Pixel kann die Manipulation auf den vorigen R, G, B und A Werte des Pixels, aber auch auf dessen Lage (x, y) und die Größe des Canvas (w, h) basieren. Meine Shader-Funktion orientiert sich an einem Beispiel von Kas Thomas. Überhaupt orientiert sich dieses Beispiel sehr an seiner Vorgehensweise:

var shader = function(r, g, b, a, x, y, w, h) {
x /= w;
y /= h; // normalize
var size = 10; // pick a scaling value
var n = PerlinNoise.noise(size * x, size * y, 0.8);
r = g = b = Math.round(255 * n);

return {r:r, g:g, b:b, a:255};
};

Und natürlich benötigen wir die PerlinNoise.noise() Funktion von Kas Thomas (siehe hier).

Heraus kommt folgendes Rauschen:

Fazit

Es war ganz schön schwer eine Implementation von Perlin Noise in JavaScript zu finden. Der Umweg über die Shader-Funktion ist zwar sehr flexibel, aber (wie ihr vielleicht auch schon bemerkt habt) sehr unintuitiv. Ich weiß noch von meinen ActionScript-Zeiten, dass Flash eine sehr flexible API für eine eingebaute Perlin Noise Implementation besaß und kann dieser Variante deswegen nur sehr wenig abgewinnen. Aber wir haben hier ein Proof-of-concept, dass Perlin Noise keine Probleme in JavaScript bereitet.

Eventuell setz ich mich beim nächsten Teil dieser Serie mal ran und baue mir eine eigene komfortablere Perlin Noise API. Wenn nicht, dann seht ihr beim nächsten Mal wie wir aus den oben beschriebenen Rauschen eine Landschaft generieren 🙂

PS: Falls ich euch etwas zu schnell durch den Stoff gegangen bin, könnt ihr gerne Fragen im Kommentarbereich hinterlassen 🙂

 Update vom 12.05.2012

Mittlerweile habe ich eine neue Artikel-Serie angefangen in der ich erkläre, wie ich meine eigene Bibliothek für Rauschfunktionen baue. Die Bibliothek wird Noizy heißen und soll eine etwas benutzerfreundlichere API erhalten. Hier gelangt ihr zur Serie.

Autor: Pipo

...kommt ursprünglich aus der Designerecke, ist aber im Laufe seines Studiums in die Webentwicklung gestolpert. Kann sich seit dem nicht so richtig entscheiden wo er hingehört und wagt deswegen vielleicht die Flucht nach vorne in ein komplett neues Gebiet. Vielleicht Management? Niemand weiß es. Auch er nicht.