Grafis 3D Java: Menampilkan lanskap fraktal

Grafik komputer 3D memiliki banyak kegunaan - dari game hingga visualisasi data, realitas virtual, dan seterusnya. Lebih sering daripada tidak, kecepatan adalah yang terpenting, membuat perangkat lunak dan perangkat keras khusus menjadi suatu keharusan untuk menyelesaikan pekerjaan. Pustaka grafik tujuan khusus menyediakan API tingkat tinggi, tetapi menyembunyikan bagaimana pekerjaan sebenarnya dilakukan. Namun, sebagai programmer hidung-ke-logam, itu tidak cukup baik bagi kami! Kami akan meletakkan API di lemari dan melihat di balik layar bagaimana gambar sebenarnya dibuat - dari definisi model virtual hingga rendering aktualnya ke layar.

Kita akan melihat subjek yang cukup spesifik: membuat dan menampilkan peta medan, seperti permukaan Mars atau beberapa atom emas. Perenderan peta medan dapat digunakan lebih dari sekadar tujuan estetika - banyak teknik visualisasi data menghasilkan data yang dapat dirender sebagai peta medan. Niat saya, tentu saja, sepenuhnya artistik, seperti yang Anda lihat pada gambar di bawah ini! Jika Anda menginginkannya, kode yang akan kami hasilkan cukup umum sehingga hanya dengan sedikit penyesuaian, kode ini juga dapat digunakan untuk membuat struktur 3D selain medan.

Klik di sini untuk melihat dan memanipulasi applet medan.

Sebagai persiapan untuk diskusi kita hari ini, saya sarankan Anda membaca "Gambar bulatan bertekstur" bulan Juni jika Anda belum melakukannya. Artikel ini mendemonstrasikan pendekatan ray-tracing untuk merender gambar (menembakkan sinar ke dalam pemandangan virtual untuk menghasilkan gambar). Dalam artikel ini, kami akan merender elemen pemandangan langsung ke layar. Meskipun kami menggunakan dua teknik yang berbeda, artikel pertama berisi beberapa materi latar belakang pada java.awt.imagepaket yang tidak akan saya ulas dalam pembahasan ini.

Peta medan

Mari kita mulai dengan mendefinisikan a

peta medan

. Peta medan adalah fungsi yang memetakan koordinat 2D

(x, y)

ke ketinggian

Sebuah

dan warna

c

. Dengan kata lain, peta medan hanyalah sebuah fungsi yang mendeskripsikan topografi suatu area kecil.

Mari kita tentukan medan kita sebagai sebuah antarmuka:

antarmuka publik Terrain {public double getAltitude (double i, double j); public RGB getColor (double i, double j); }

Untuk keperluan artikel ini, kami akan mengasumsikan bahwa 0,0 <= i, j, ketinggian <= 1,0 . Ini bukan persyaratan, tetapi akan memberi kita ide yang baik di mana menemukan medan yang akan kita lihat.

Warna medan kami dijelaskan hanya sebagai triplet RGB. Untuk menghasilkan gambar yang lebih menarik, kami dapat mempertimbangkan untuk menambahkan informasi lain seperti kilau permukaan, dll. Untuk saat ini, kelas berikut akan melakukannya:

kelas publik RGB {private double r, g, b; RGB publik (r ganda, g ganda, b ganda) {this.r = r; ini.g = g; this.b = b; } public RGB add (RGB rgb) {return RGB baru (r + rgb.r, g + rgb.g, b + rgb.b); } pengurangan RGB publik (RGB rgb) {return RGB baru (r - rgb.r, g - rgb.g, b - rgb.b); } skala RGB publik (skala ganda) {kembalikan RGB baru (skala r *, skala g *, skala b *); } private int toInt (nilai ganda) {return (nilai 1.0)? 255: (int) (nilai * 255.0); } publik int toRGB () toInt (b); }

The RGBkelas mendefinisikan wadah warna yang sederhana. Kami menyediakan beberapa fasilitas dasar untuk melakukan aritmatika warna dan mengubah warna floating-point menjadi format integer yang dikemas.

Medan transendental

Kita akan mulai dengan melihat medan transendental - fancyspeak untuk medan dihitung dari sinus dan cosinus:

public class TranscendentalTerrain mengimplementasikan Terrain {private double alpha, beta; public TranscendentalTerrain (double alpha, double 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); } getColor RGB publik (double i, double j) {return RGB baru (.5 + .5 * Math.sin (i * alpha), .5 - .5 * Math.cos (j * beta), 0.0); }}

Konstruktor kami menerima dua nilai yang menentukan frekuensi medan kami. Kami menggunakan ini untuk menghitung ketinggian dan warna menggunakan Math.sin()dan Math.cos(). Ingat, fungsi-fungsi tersebut mengembalikan nilai -1.0 <= sin (), cos () <= 1.0 , jadi kita harus menyesuaikan nilai yang dikembalikan sesuai.

Medan fraktal

Medan matematika sederhana tidak menyenangkan. Apa yang kita inginkan adalah sesuatu yang terlihat sangat nyata. Kami dapat menggunakan file topografi nyata sebagai peta medan kami (Teluk San Francisco atau permukaan Mars, misalnya). Meskipun ini mudah dan praktis, ini agak membosankan. Maksudku, kita sudah

telah

sana. Yang kita inginkan sebenarnya adalah sesuatu yang terlihat sangat nyata

dan

belum pernah terlihat sebelumnya. Masuki dunia fraktal.

Fraktal adalah sesuatu (fungsi atau objek) yang menunjukkan kemiripan diri . Misalnya, set Mandelbrot adalah fungsi fraktal: jika Anda memperbesar set Mandelbrot secara signifikan, Anda akan menemukan struktur internal kecil yang mirip dengan Mandelbrot utama itu sendiri. Pegunungan juga merupakan fraktal, setidaknya dalam penampilannya. Dari dekat, fitur-fitur kecil dari sebuah gunung menyerupai fitur-fitur besar pegunungan, bahkan hingga ke permukaan batu-batu besar yang kasar. Kami akan mengikuti prinsip kesamaan diri ini untuk menghasilkan medan fraktal kami.

Pada dasarnya apa yang akan kita lakukan adalah menghasilkan medan acak awal yang kasar. Kemudian kita akan secara rekursif menambahkan detail acak tambahan yang meniru struktur keseluruhan, tetapi pada skala yang semakin kecil. Algoritma aktual yang akan kita gunakan, Algoritma Diamond-Square, awalnya dijelaskan oleh Fournier, Fussell, dan Carpenter pada tahun 1982 (lihat Resources untuk detailnya).

Ini adalah langkah-langkah yang akan kami lakukan untuk membangun medan fraktal kami:

  1. Kami pertama kali menetapkan ketinggian acak ke empat titik sudut dari sebuah kotak.

  2. Kami kemudian mengambil rata-rata dari keempat sudut ini, menambahkan gangguan acak dan menetapkannya ke titik tengah kisi ( ii dalam diagram berikut). Ini disebut langkah berlian karena kami membuat pola berlian di kisi. (Pada iterasi pertama, berlian tidak terlihat seperti berlian karena berada di tepi kisi; tetapi jika Anda melihat diagram, Anda akan memahami apa yang saya maksud.)

  3. Kami kemudian mengambil masing-masing berlian yang telah kami hasilkan, rata-rata empat sudut, menambahkan gangguan acak dan menetapkan ini ke titik tengah berlian ( iii dalam diagram berikut). Ini disebut langkah persegi karena kita membuat pola persegi pada kisi.

  4. Selanjutnya, kami menerapkan kembali langkah berlian ke setiap kotak yang kami buat di langkah persegi, kemudian menerapkan kembali langkah persegi tersebut ke setiap berlian yang kami buat di langkah berlian, dan seterusnya hingga kisi-kisi kami cukup padat.

Sebuah pertanyaan yang jelas muncul: Seberapa banyak kita mengganggu jaringan? Jawabannya adalah kita mulai dengan koefisien kekasaran 0.0 <kekasaran <1.0 . Pada iterasi n algoritma Diamond-Square kami, kami menambahkan gangguan acak ke kisi: -roughnessn <= perturbation <= roughnessn . Pada dasarnya, saat kami menambahkan detail yang lebih halus ke kisi, kami mengurangi skala perubahan yang kami buat. Perubahan kecil pada skala kecil hampir sama dengan perubahan besar pada skala yang lebih besar.

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); } } 

Anda mungkin bertanya pada diri sendiri: Jadi mengapa segitiga dan bukan kotak? Masalah dengan menggunakan kotak dari kisi-kisi adalah bahwa mereka tidak rata dalam ruang 3D. Jika Anda mempertimbangkan empat titik acak di luar angkasa, sangat kecil kemungkinannya mereka akan menjadi coplanar. Jadi sebagai gantinya kami menguraikan medan kami menjadi segitiga karena kami dapat menjamin bahwa tiga titik di luar angkasa akan menjadi coplanar. Ini berarti tidak akan ada celah di medan yang akhirnya kita gambar.