3D Graphic Java: Fraktale Landschaften rendern

3D-Computergrafiken haben viele Verwendungsmöglichkeiten - von Spielen über Datenvisualisierung bis hin zur virtuellen Realität und darüber hinaus. In den meisten Fällen ist Geschwindigkeit von größter Bedeutung, sodass spezielle Software und Hardware ein Muss sind, um die Arbeit zu erledigen. Spezielle Grafikbibliotheken bieten eine API auf hoher Ebene, verbergen jedoch, wie die eigentliche Arbeit erledigt wird. Als Nose-to-the-Metal-Programmierer ist das für uns jedoch nicht gut genug! Wir werden die API in den Schrank stellen und einen Blick hinter die Kulissen werfen, wie Bilder tatsächlich generiert werden - von der Definition eines virtuellen Modells bis zu seiner tatsächlichen Darstellung auf dem Bildschirm.

Wir werden uns mit einem ziemlich spezifischen Thema befassen: dem Generieren und Rendern von Geländekarten wie der Marsoberfläche oder einigen Goldatomen. Das Rendern von Geländekarten kann nicht nur für ästhetische Zwecke verwendet werden. Viele Datenvisualisierungstechniken erzeugen Daten, die als Geländekarten gerendert werden können. Meine Absichten sind natürlich völlig künstlerisch, wie Sie auf dem Bild unten sehen können! Wenn Sie dies wünschen, ist der Code, den wir erstellen, allgemein genug, dass er mit nur geringfügigen Änderungen auch zum Rendern anderer 3D-Strukturen als Terrains verwendet werden kann.

Klicken Sie hier, um das Gelände-Applet anzuzeigen und zu bearbeiten.

In Vorbereitung auf unsere heutige Diskussion schlage ich vor, dass Sie Junis "Zeichnen strukturierter Kugeln" lesen, falls Sie dies noch nicht getan haben. Der Artikel zeigt einen Raytracing-Ansatz zum Rendern von Bildern (Abfeuern von Strahlen in eine virtuelle Szene, um ein Bild zu erzeugen). In diesem Artikel werden Szenenelemente direkt auf dem Display gerendert. Obwohl wir zwei verschiedene Techniken verwenden, enthält der erste Artikel Hintergrundmaterial zu dem java.awt.imagePaket, das ich in dieser Diskussion nicht noch einmal aufbereiten werde.

Geländekarten

Beginnen wir mit der Definition von a

Geländekarte

. Eine Geländekarte ist eine Funktion, die eine 2D-Koordinate abbildet

(x, y)

zu einer Höhe

ein

und Farbe

c

. Mit anderen Worten, eine Geländekarte ist einfach eine Funktion, die die Topographie eines kleinen Gebiets beschreibt.

Definieren wir unser Terrain als Schnittstelle:

öffentliche Schnittstelle Terrain {public double getAltitude (double i, double j); öffentliches RGB getColor (double i, double j); }}

Für den Zweck dieses Artikels nehmen wir an, dass 0,0 <= i, j, Höhe <= 1,0 . Dies ist keine Voraussetzung, gibt uns aber eine gute Vorstellung davon, wo wir das Terrain finden, das wir sehen werden.

Die Farbe unseres Geländes wird einfach als RGB-Triplett beschrieben. Um interessantere Bilder zu erstellen, sollten Sie andere Informationen wie den Glanz der Oberfläche usw. hinzufügen. Im Moment reicht jedoch die folgende Klasse aus:

öffentliche Klasse RGB {privates Doppel r, g, b; öffentliches RGB (doppeltes r, doppeltes g, doppeltes b) {this.r = r; this.g = g; this.b = b; } public RGB add (RGB rgb) {neues RGB zurückgeben (r + rgb.r, g + rgb.g, b + rgb.b); } public RGB subtrahieren (RGB rgb) {neues RGB zurückgeben (r - rgb.r, g - rgb.g, b - rgb.b); } öffentliche RGB-Skala (doppelte Skala) {neues RGB zurückgeben (r * Skala, g * Skala, b * Skala); } private int toInt (doppelter Wert) {return (Wert 1.0)? 255: (int) (Wert * 255,0); } public int toRGB () toInt (b); }}

Die RGBKlasse definiert einen einfachen Farbcontainer. Wir bieten einige grundlegende Funktionen zum Durchführen von Farbarithmetik und zum Konvertieren einer Gleitkommafarbe in ein Ganzzahlformat.

Transzendentale Gebiete

Wir beginnen mit einem transzendentalen Terrain - Fancyspeak für ein Terrain, das aus Sinus und Cosinus berechnet wird:

öffentliche Klasse TranscendentalTerrain implementiert Terrain {private double alpha, beta; public TranscendentalTerrain (doppeltes Alpha, doppeltes Beta) {this.alpha = alpha; this.beta = beta; } public double getAltitude (double i, double j) {return .5 + .5 * Math.sin (i * alpha) * Math.cos (j * beta); } public RGB getColor (double i, double j) {neues RGB zurückgeben (.5 + .5 * Math.sin (i * alpha), .5 - .5 * Math.cos (j * beta), 0.0); }}

Unser Konstruktor akzeptiert zwei Werte, die die Häufigkeit unseres Geländes definieren. Wir verwenden diese, um Höhen und Farben mit Math.sin()und zu berechnen Math.cos(). Denken Sie daran, dass diese Funktionen Werte -1,0 <= sin (), cos () <= 1,0 zurückgeben . Daher müssen wir unsere Rückgabewerte entsprechend anpassen.

Fraktales Gelände

Einfache mathematische Terrains machen keinen Spaß. Was wir wollen, ist etwas, das zumindest passabel real aussieht. Wir könnten echte Topografiedateien als Geländekarte verwenden (zum Beispiel die Bucht von San Francisco oder die Marsoberfläche). Dies ist zwar einfach und praktisch, aber etwas langweilig. Ich meine, wir haben

gewesen

Dort. Was wir wirklich wollen, ist etwas, das passabel real aussieht

und

wurde noch nie gesehen. Betreten Sie die Welt der Fraktale.

Ein Fraktal ist etwas (eine Funktion oder ein Objekt), das Selbstähnlichkeit aufweist . Zum Beispiel ist das Mandelbrot-Set eine fraktale Funktion: Wenn Sie das Mandelbrot-Set stark vergrößern, finden Sie winzige interne Strukturen, die dem Haupt-Mandelbrot selbst ähneln. Eine Bergkette ist zumindest fraktal, zumindest optisch. Aus der Nähe ähneln kleine Merkmale eines einzelnen Berges großen Merkmalen des Gebirges, bis hin zur Rauheit einzelner Felsbrocken. Wir werden diesem Prinzip der Selbstähnlichkeit folgen, um unser fraktales Terrain zu erzeugen.

Im Wesentlichen werden wir ein grobes, anfängliches zufälliges Terrain erzeugen. Dann werden wir rekursiv zusätzliche zufällige Details hinzufügen, die die Struktur des Ganzen nachahmen, jedoch in immer kleineren Maßstäben. Der eigentliche Algorithmus, den wir verwenden werden, der Diamond-Square-Algorithmus, wurde ursprünglich 1982 von Fournier, Fussell und Carpenter beschrieben (Einzelheiten siehe Ressourcen).

Dies sind die Schritte, die wir durcharbeiten werden, um unser fraktales Terrain aufzubauen:

  1. Wir weisen den vier Eckpunkten eines Gitters zunächst eine zufällige Höhe zu.

  2. Wir nehmen dann den Durchschnitt dieser vier Ecken, fügen eine zufällige Störung hinzu und weisen diese dem Mittelpunkt des Gitters zu ( ii im folgenden Diagramm). Dies wird als Diamantschritt bezeichnet , da wir ein Rautenmuster auf dem Gitter erstellen. (Bei der ersten Iteration sehen die Diamanten nicht wie Diamanten aus, weil sie sich am Rand des Gitters befinden. Wenn Sie sich jedoch das Diagramm ansehen, werden Sie verstehen, worauf ich hinaus will.)

  3. Wir nehmen dann jeden der Diamanten, die wir produziert haben, mitteln die vier Ecken, fügen eine zufällige Störung hinzu und ordnen diese dem Diamantmittelpunkt zu ( iii im folgenden Diagramm). Dies wird als quadratischer Schritt bezeichnet, da wir ein quadratisches Muster auf dem Raster erstellen.

  4. Als nächstes wenden wir den Diamantschritt erneut auf jedes Quadrat an, das wir im Quadratschritt erstellt haben, und wenden dann den Quadratschritt erneut auf jeden Diamanten an, den wir im Diamantschritt erstellt haben, und so weiter, bis unser Gitter ausreichend dicht ist.

Es stellt sich die offensichtliche Frage: Wie stark stören wir das Netz? Die Antwort ist, dass wir mit einem Rauheitskoeffizienten von 0,0 <Rauheit <1,0 beginnen . Bei der Iteration n unseres Diamond-Square-Algorithmus fügen wir dem Gitter eine zufällige Störung hinzu: -roughnessn <= Störung <= Rauheitn . Wenn wir dem Raster feinere Details hinzufügen, reduzieren wir im Wesentlichen den Umfang der Änderungen, die wir vornehmen. Kleine Änderungen in kleinem Maßstab sind fraktal ähnlich wie große Änderungen in größerem Maßstab.

If we choose a small value for roughness, then our terrain will be very smooth -- the changes will very rapidly diminish to zero. If we choose a large value, then the terrain will be very rough, as the changes remain significant at small grid divisions.

Here's the code to implement our fractal terrain map:

public class FractalTerrain implements Terrain { private double[][] terrain; private double roughness, min, max; private int divisions; private Random rng; public FractalTerrain (int lod, double roughness) { this.roughness = roughness; this.divisions = 1 << lod; terrain = new double[divisions + 1][divisions + 1]; rng = new Random (); terrain[0][0] = rnd (); terrain[0][divisions] = rnd (); terrain[divisions][divisions] = rnd (); terrain[divisions][0] = rnd (); double rough = roughness; for (int i = 0; i < lod; ++ i) { int q = 1 << i, r = 1 <> 1; for (int j = 0; j < divisions; j += r) for (int k = 0; k  0) for (int j = 0; j <= divisions; j += s) for (int k = (j + s) % r; k <= divisions; k += r) square (j - s, k - s, r, rough); rough *= roughness; } min = max = terrain[0][0]; for (int i = 0; i <= divisions; ++ i) for (int j = 0; j <= divisions; ++ j) if (terrain[i][j]  max) max = terrain[i][j]; } private void diamond (int x, int y, int side, double scale) { if (side > 1) { int half = side / 2; double avg = (terrain[x][y] + terrain[x + side][y] + terrain[x + side][y + side] + terrain[x][y + side]) * 0.25; terrain[x + half][y + half] = avg + rnd () * scale; } } private void square (int x, int y, int side, double scale) { int half = side / 2; double avg = 0.0, sum = 0.0; if (x >= 0) { avg += terrain[x][y + half]; sum += 1.0; } if (y >= 0) { avg += terrain[x + half][y]; sum += 1.0; } if (x + side <= divisions) { avg += terrain[x + side][y + half]; sum += 1.0; } if (y + side <= divisions) { avg += terrain[x + half][y + side]; sum += 1.0; } terrain[x + half][y + half] = avg / sum + rnd () * scale; } private double rnd () { return 2. * rng.nextDouble () - 1.0; } public double getAltitude (double i, double j) { double alt = terrain[(int) (i * divisions)][(int) (j * divisions)]; return (alt - min) / (max - min); } private RGB blue = new RGB (0.0, 0.0, 1.0); private RGB green = new RGB (0.0, 1.0, 0.0); private RGB white = new RGB (1.0, 1.0, 1.0); public RGB getColor (double i, double j) { double a = getAltitude (i, j); if (a < .5) return blue.add (green.subtract (blue).scale ((a - 0.0) / 0.5)); else return green.add (white.subtract (green).scale ((a - 0.5) / 0.5)); } } 

In the constructor, we specify both the roughness coefficient roughness and the level of detail lod. The level of detail is the number of iterations to perform -- for a level of detail n, we produce a grid of (2n+1 x 2n+1) samples. For each iteration, we apply the diamond step to each square in the grid and then the square step to each diamond. Afterwards, we compute the minimum and maximum sample values, which we'll use to scale our terrain altitudes.

To compute the altitude of a point, we scale and return the closest grid sample to the requested location. Ideally, we would actually interpolate between surrounding sample points, but this method is simpler, and good enough at this point. In our final application this issue will not arise because we will actually match the locations where we sample the terrain to the level of detail that we request. To color our terrain, we simply return a value between blue, green, and white, depending upon the altitude of the sample point.

Tessellating our terrain

We now have a terrain map defined over a square domain. We need to decide how we are going to actually draw this onto the screen. We could fire rays into the world and try to determine which part of the terrain they strike, as we did in the previous article. This approach would, however, be extremely slow. What we'll do instead is approximate the smooth terrain with a bunch of connected triangles -- that is, we'll tessellate our terrain.

Tessellate: to form into or adorn with mosaic (from the Latin tessellatus).

To form the triangle mesh, we will evenly sample our terrain into a regular grid and then cover this grid with triangles -- two for each square of the grid. There are many interesting techniques that we could use to simplify this triangle mesh, but we'd only need those if speed was a concern.

The following code fragment populates the elements of our terrain grid with fractal terrain data. We scale down the vertical axis of our terrain to make the altitudes a bit less exaggerated.

double exaggeration = .7; int lod = 5; int steps = 1 << lod; Triple[] map = new Triple[steps + 1][steps + 1]; Triple[] colors = new RGB[steps + 1][steps + 1]; Terrain terrain = new FractalTerrain (lod, .5); for (int i = 0; i <= steps; ++ i) { for (int j = 0; j <= steps; ++ j) { double x = 1.0 * i / steps, z = 1.0 * j / steps; double altitude = terrain.getAltitude (x, z); map[i][j] = new Triple (x, altitude * exaggeration, z); colors[i][j] = terrain.getColor (x, z); } } 

Sie fragen sich vielleicht: Warum also Dreiecke und keine Quadrate? Das Problem bei der Verwendung der Quadrate des Gitters besteht darin, dass sie im 3D-Raum nicht flach sind. Wenn Sie vier zufällige Punkte im Raum betrachten, ist es äußerst unwahrscheinlich, dass sie koplanar sind. Stattdessen zerlegen wir unser Gelände in Dreiecke, weil wir garantieren können, dass drei beliebige Punkte im Raum koplanar sind. Dies bedeutet, dass es keine Lücken im Gelände gibt, die wir am Ende zeichnen.