3DグラフィックJava:フラクタル地形をレンダリングする

3Dコンピュータグラフィックスには、ゲームからデータの視覚化、バーチャルリアリティなど、さまざまな用途があります。多くの場合、速度が最も重要であり、特殊なソフトウェアとハ​​ードウェアが仕事を成し遂げるために必須になります。専用のグラフィックライブラリは高レベルのAPIを提供しますが、実際の作業がどのように行われるかを隠します。しかし、ノーズツーザメタルのプログラマーとしては、それだけでは十分ではありません。APIをクローゼットに入れて、仮想モデルの定義から画面への実際のレンダリングまで、画像が実際にどのように生成されるかを舞台裏で見ていきます。

かなり具体的なテーマを見ていきます。火星の表面や数個の金の原子などの地形マップの生成とレンダリングです。地形図のレンダリングは、見た目の美しさだけでなく、多くのデータ視覚化手法を使用して、地形図としてレンダリングできるデータを生成できます。下の写真でわかるように、私の意図はもちろん完全に芸術的です!必要に応じて、作成するコードは十分に一般的であるため、わずかな調整を加えるだけで、地形以外の3D構造のレンダリングにも使用できます。

テレインアプレットを表示および操作するには、ここをクリックしてください。

今日の議論の準備として、6月の「テクスチャ球を描く」をまだ読んでいない場合は読むことをお勧めします。この記事では、画像をレンダリングするためのレイトレーシングアプローチ(画像を生成するために仮想シーンに光線を発射する)について説明します。この記事では、シーン要素をディスプレイに直接レンダリングします。2つの異なる手法を使用していますが、最初の記事にはjava.awt.image、この説明では再ハッシュしないパッケージの背景資料が含まれています。

地形マップ

を定義することから始めましょう

地形図

。地形図は、2D座標をマッピングする関数です。

(x、y)

高度に

a

と色

c

。言い換えれば、地形図は、単に小さな領域の地形を記述する関数です。

地形をインターフェースとして定義しましょう。

パブリックインターフェイスTerrain {public double getAltitude(double i、double j); public RGB getColor(double i、double j); }

この記事では、0.0 <= i、j、altitude <= 1.0と仮定します。これは必須ではありませんが、表示する地形をどこで見つけるかについての良いアイデアが得られます。

地形の色は、単にRGBトリプレットとして記述されます。より興味深い画像を作成するために、表面の光沢などの他の情報を追加することを検討する場合があります。ただし、今のところ、次のクラスで実行できます。

パブリッククラスRGB {プライベートダブルr、g、b; public RGB(double r、double g、double b){this.r = r; this.g = g; this.b = b; } public RGB add(RGB rgb){新しいRGBを返す(r + rgb.r、g + rgb.g、b + rgb.b); } public RGB減算(RGB rgb){新しいRGBを返す(r-rgb.r、g-rgb.g、b-rgb.b); } public RGB scale(double scale){return new RGB(r * scale、g * scale、b * scale); } private int toInt(double value){return(value 1.0)?255:(int)(値* 255.0); } public int toRGB()toInt(b); }

このRGBクラスは、単純なカラーコンテナを定義します。色演算を実行し、浮動小数点色をパックド整数形式に変換するための基本的な機能をいくつか提供します。

超越的な地形

まず、超越的な地形を見てみましょう。正弦と余弦から計算された地形については、fancyspeakを参照してください。

パブリッククラスTranscendentalTerrainはTerrainを実装します{プライベートダブルアルファ、ベータ; public TranscendentalTerrain(double alpha、double beta){this.alpha = alpha; this.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){return new RGB(.5 + .5 * Math.sin(i * alpha)、. 5-.5 * Math.cos(j * beta)、0.0); }}

コンストラクターは、地形の頻度を定義する2つの値を受け入れます。これらを使用して、とを使用して高度と色を計算Math.sin()Math.cos()ます。これらの関数は値-1.0 <= sin()、cos()<= 1.0を返すため、それに応じて戻り値を調整する必要があることに注意してください。

フラクタル地形

単純な数学的地形は楽しいものではありません。私たちが望んでいるのは、少なくともまずまず本物に見えるものです。実際の地形ファイルを地形図として使用できます(たとえば、サンフランシスコ湾や火星の表面)。これは簡単で実用的ですが、やや鈍いです。つまり、私たちは

されている

そこ。私たちが本当に望んでいるのは、まあまあ本物に見えるものです

そして

これまでに見たことがありません。フラクタルの世界に入ります。

フラクタルは、自己相似性を示すもの(関数またはオブジェクト)です。たとえば、マンデルブロ集合はフラクタル関数です。マンデルブロ集合を大きく拡大すると、メインのマンデルブロ自体に似た小さな内部構造が見つかります。山脈も、少なくとも見た目はフラクタルです。クローズアップから、個々の山の小さな特徴は、個々の岩の粗さまで、山脈の大きな特徴に似ています。この自己相似性の原則に従って、フラクタル地形を生成します。

基本的に、私たちが行うことは、粗い初期のランダムな地形を生成することです。次に、全体の構造を模倣するランダムな詳細を再帰的に追加しますが、スケールはますます小さくなります。使用する実際のアルゴリズムであるDiamond-Squareアルゴリズムは、1982年にFournier、Fussell、Carpenterによって最初に記述されました(詳細については、「参考文献」を参照してください)。

これらは、フラクタル地形を構築するために実行する手順です。

  1. まず、グリッドの4つのコーナーポイントにランダムな高さを割り当てます。

  2. 次に、これらの4つのコーナーの平均を取り、ランダムな摂動を追加して、これをグリッドの中点に割り当てます(次の図のii)。グリッド上にひし形パターンを作成しているため、これはひし形ステップと呼ばれます。(最初の反復では、ダイヤモンドはグリッドの端にあるため、ダイヤモンドのようには見えませんが、図を見ると、私が何をしているのかがわかります。)

  3. 次に、生成した各ダイヤモンドを取得し、4つのコーナーを平均して、ランダムな摂動を追加し、これをダイヤモンドの中点に割り当てます(次の図のiii)。グリッド上に正方形のパターンを作成しているため、これは正方形のステップと呼ばれます。

  4. 次に、正方形のステップで作成した各正方形にダイヤモンドのステップを再適用し、次に、グリッドが十分に密になるまで、ダイヤモンドのステップで作成した各ダイヤモンドに正方形のステップを再適用します。

明らかな疑問が生じます:グリッドをどの程度混乱させるのでしょうか?答えは、粗さ係数0.0 <粗さ<1.0から始めることです。Diamond-Squareアルゴリズムの反復nで、グリッドにランダムな摂動を追加します。- roughnessn<=摂動<= 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); } } 

あなたは自分自身に問いかけているかもしれません:では、なぜ正方形ではなく三角形なのですか?グリッドの正方形を使用する際の問題は、3D空間でそれらが平坦ではないことです。空間内の4つのランダムな点を考慮すると、それらが同一平面上にある可能性はほとんどありません。したがって、代わりに、空間内の任意の3つのポイントが同一平面上にあることを保証できるため、地形を三角形に分解します。これは、最終的に描画する地形にギャップがないことを意味します。