3D графична Java: Възпроизвеждане на фрактални пейзажи

3D компютърната графика има много приложения - от игри до визуализация на данни, виртуална реалност и не само. По-често скоростта е от първостепенно значение, поради което специализираният софтуер и хардуер са задължителни, за да свършите работата. Графичните библиотеки със специално предназначение предоставят API на високо ниво, но крият как се извършва истинската работа. Като програмисти от носа до метала обаче това не е достатъчно добро за нас! Ще сложим API в килера и ще разгледаме зад кулисите как всъщност се генерират изображения - от дефиницията на виртуален модел до реалното му изобразяване на екрана.

Ще разгледаме доста специфична тема: генериране и изобразяване на карти на терена, като повърхността на Марс или няколко атома злато. Изобразяването на карти на терена може да се използва не само за естетически цели - много техники за визуализация на данни създават данни, които могат да бъдат изобразени като карти на терена. Намеренията ми, разбира се, са изцяло артистични, както можете да видите от снимката по-долу! Ако желаете, кодът, който ще създадем, е достатъчно общ, че само с незначителни настройки той може да се използва и за рендиране на 3D структури, различни от терени.

Щракнете тук, за да видите и манипулирате аплета на терена.

Като подготовка за нашата днешна дискусия, предлагам да прочетете „Начертайте текстурирани сфери“ от юни, ако още не сте го направили. Статията демонстрира подход за проследяване на лъчи при изобразяване на изображения (изстрелване на лъчи във виртуална сцена, за да се получи изображение). В тази статия ще изобразяваме елементи на сцената директно върху дисплея. Въпреки че използваме две различни техники, първата статия съдържа някои основни материали на java.awt.imageопаковката, които няма да повтарям отново в тази дискусия.

Теренни карти

Нека започнем с дефиниране на a

карта на терена

. Карта на терена е функция, която картографира 2D координата

(х, у)

до височина

а

и цвят

° С

. С други думи, картата на терена е просто функция, която описва топографията на малка площ.

Нека определим нашия терен като интерфейс:

публичен интерфейс Терен {public double getAltitude (double i, double j); публичен RGB getColor (двоен i, двоен j); }

За целите на тази статия ще приемем, че 0.0 <= i, j, надморска височина <= 1.0 . Това не е изискване, но ще ни даде добра идея къде да намерим терена, който ще разглеждаме.

Цветът на нашия терен се описва просто като RGB триплет. За да създадем по-интересни изображения, бихме могли да обмислим добавяне на друга информация, като блясък на повърхността и т.н. Засега обаче ще направи следния клас:

публичен клас RGB {частен двоен r, g, b; публичен RGB (двойно r, двойно g, двойно b) {this.r = r; това.g = g; това.b = b; } публично добавяне на RGB (RGB rgb) {връщане на ново RGB (r + rgb.r, g + rgb.g, b + rgb.b); } публично изваждане на RGB (RGB rgb) {връщане на ново RGB (r - rgb.r, g - rgb.g, b - rgb.b); } обществена RGB скала (двойна скала) {връщане на нова RGB (r * скала, g * скала, b * скала); } private int toInt (двойна стойност) {return (стойност 1.0)? 255: (int) (стойност * 255,0); } публичен int toRGB () toInt (b); }

В RGBклас определя прост цвят контейнер. Ние предлагаме някои основни съоръжения за извършване на цветна аритметика и преобразуване на цвят с плаваща запетая в формат с опаковани цели числа.

Трансцендентални терени

Ще започнем с разглеждане на трансцендентален терен - fancyspeak за терен, изчислен от синуси и косинуси:

публичен клас TranscendentalTerrain внедрява Terrain {частна двойна алфа, бета; публичен TranscendentalTerrain (двойна алфа, двойна бета) {this.alpha = алфа; this.beta = бета; } public double getAltitude (double i, double j) {return .5 + .5 * Math.sin (i * alpha) * Math.cos (j * beta); } публичен RGB getColor (двоен i, двоен j) {връщане на нов RGB (.5 + .5 * Math.sin (i * alpha), .5 - .5 * Math.cos (j * beta), 0.0); }}

Нашият конструктор приема две стойности, които определят честотата на нашия терен. Използваме ги, за да изчислим надморска височина и цветове, използвайки Math.sin()и Math.cos(). Не забравяйте, че тези функции връщат стойности -1,0 <= sin (), cos () <= 1,0 , така че трябва да коригираме съответно нашите връщани стойности.

Фрактални терени

Простите математически терени не са забавни. Това, което искаме, е нещо, което изглежда поне проходимо реално. Можем да използваме реални топографски файлове като наша карта на терена (например залива на Сан Франциско или повърхността на Марс). Въпреки че това е лесно и практично, това е малко скучно. Искам да кажа, че сме

са били

там. Това, което наистина искаме, е нещо, което изглежда проходимо реално

и

никога не е виждан досега. Влезте в света на фракталите.

Фракталът е нещо (функция или обект), което показва себеподобност . Например, наборът на Mandelbrot е фрактална функция: ако увеличите значително набора на Mandelbrot, ще намерите малки вътрешни структури, които приличат на самия Mandelbrot. Планинската верига също е фрактална, поне на външен вид. Отблизо малките черти на отделна планина приличат на големи черти на планинската верига, дори до грапавостта на отделните камъни. Ще следваме този принцип на себеподобността, за да генерираме нашите фрактални терени.

По същество това, което ще направим, е да генерираме груб, първоначален произволен терен. След това ще добавим рекурсивно допълнителни случайни детайли, които имитират структурата на цялото, но във все по-малки мащаби. Действителният алгоритъм, който ще използваме, алгоритъмът Diamond-Square, първоначално е описан от Fournier, Fussell и Carpenter през 1982 г. (вж. Ресурси за подробности).

Това са стъпките, през които ще работим, за да изградим нашия фрактален терен:

  1. Първо присвояваме произволна височина на четирите ъглови точки на мрежата.

  2. След това вземаме средната стойност на тези четири ъгъла, добавяме произволно смущение и присвояваме това към средната точка на мрежата ( ii в следващата диаграма). Това се нарича диамантена стъпка, защото ние създаваме диамантена шарка върху мрежата. (При първата итерация диамантите не приличат на диаманти, защото са на ръба на мрежата; но ако погледнете диаграмата, ще разберете какво получавам.)

  3. След това вземаме всеки от диамантите, които сме произвели, осредняваме четирите ъгъла, добавяме произволно смущение и присвояваме това на средната точка на диаманта ( iii в следващата диаграма). Това се нарича квадратна стъпка, защото създаваме квадратна шарка върху мрежата.

  4. След това отново прилагаме диамантената стъпка към всеки квадрат, който сме създали в квадратната стъпка, след това отново прилагаме квадратната стъпка към всеки диамант, който сме създали в диамантената стъпка, и така, докато нашата решетка стане достатъчно плътна.

Възниква очевиден въпрос: Колко смущаваме мрежата? Отговорът е, че започваме с коефициент на грапавост 0,0 <грапавост <1,0 . При итерация n на нашия алгоритъм Diamond-Square добавяме произволно възмущение към мрежата: -roughnessn <= perturbation <= roughnessn . По същество, докато добавяме по-фини детайли към мрежата, ние намаляваме мащаба на промените, които правим. Малките промени в малък мащаб са фрактално подобни на големи промени в по-голям мащаб.

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

Може би се питате: Защо тогава триъгълници, а не квадрати? Проблемът с използването на квадратите на мрежата е, че те не са равни в триизмерното пространство. Ако вземете предвид четири произволни точки в пространството, е изключително малко вероятно те да бъдат съвместни. Затова вместо това ние разлагаме терена си на триъгълници, защото можем да гарантираме, че всякакви три точки в пространството ще бъдат копланарни. Това означава, че няма да има пропуски в терена, които в крайна сметка ще нарисуваме.