2

Java で中点変位アルゴリズムを実装しようとしています。ダイアモンド スクエア アルゴリズムとも呼ばれます。私の参照はhttp://www.lighthouse3d.com/opengl/terrain/index.php3?mpdです。右端と下端以外は正しく動作しているようです。

中点変位の結果を見る

よく見ると、「粗い」エッジが見られます。誰が間違っているのか指摘できますか？この効果は、このアルゴリズムの他のオンライン実装では観察されていません。

コード

private void generateWorldMPD() {               
    /* The following is my first attempt at the MDP algorithm. */       

    // displacement boundary.
    double displacementBound = Constants.DEFAULT_ROUGHNESS_CONSTANT;
    double[][] A = Utilities.get2DDoubleArray(Constants.MPD_PRESET_HEIGHT, 2, 2);
    int iterations =0;
    while (iterations < mPDIterations) {

        // create a new array large enough for the new points being added.
        double [][] B = new double[A.length * 2 - 1][A[0].length * 2 - 1];

        // move the points in A to B, skipping every other element as space for a new point
        for (int i = 0; i < B.length; i +=2) 
            for (int j = 0; j < B[i].length; j+=2) {
                B[i][j] = A[i / 2][j / 2];                  
            }

        //calculate the height of each new center point as the average of the four adjacent elements  
        //(diamond step) and add a random displacement to each
        for (int i = 1; i < B.length; i+= 2)
            for (int j = 1; j < B[i].length; j+=2)  {
                averageFromCornersAndDisplace(B, i, j, displacementBound);

            }

        //calculate the height of each new non-center point (square step) and add a random displacement to each
        for (int i = 0; i < B.length; i ++)
            for (int j = 0; j < B[i].length; j++)
                if (i % 2 == 0)         //on every even row, calculate for only odd columns
                    if (j % 2 == 0) continue;
                    else
                        averageFromAdjAndDisplace( B , i, j, displacementBound );

            else                                //on every odd row, calculate for only even columns
                    if (j % 2 == 0)
                        averageFromAdjAndDisplace( B , i, j, displacementBound );
                    else
                        continue;

        displacementBound *= Math.pow(2, -Constants.DEFAULT_ROUGHNESS_CONSTANT);

        // assign B to A            
        A = B;

        iterations++;
    }
}

private void averageFromCornersAndDisplace(double[][] A, int i, int j, double displacementBoundary) {
    double nw = A[ wrap(i - 1, 0, A.length - 1) ][ wrap(j - 1, 0, A[i].length - 1) ];
    double ne = A[ wrap(i + 1, 0, A.length - 1) ][ wrap(j - 1, 0, A[i].length - 1) ];
    double sw = A[ wrap(i - 1, 0, A.length - 1) ][ wrap(j + 1, 0, A[i].length - 1) ];
    double se = A[ wrap(i + 1, 0, A.length - 1) ][ wrap(j + 1, 0, A[i].length - 1) ];
    A[i][j] = (nw + ne + sw + se) / 4;  
    A[i][j] += randomDisplacement(displacementBoundary);
}

private void averageFromAdjAndDisplace(double[][] A, int i, int j, double displacementBoundary) {
    double north = A[i][ wrap(j - 1, 0, A[i].length - 1)];
    double south = A[i][ wrap(j + 1, 0, A[i].length - 1)];
    double west  = A[ wrap(i - 1, 0, A.length - 1) ][j];
    double east  = A[ wrap(i + 1, 0, A.length - 1) ][j];
    A[i][j] = (north + south + east + west) / 4;    
    A[i][j] += randomDisplacement(displacementBoundary);
}

// This function returns a value that is wrapped around the interval if
// it exceeds the given bounds in the negative or positive direction.
private int wrap(int n, int lowerBound, int upperBound) {

    int lengthOfInterval = upperBound - lowerBound;

    if (n < lowerBound) 
        return (lowerBound - n) % lengthOfInterval;
    else
        return (n - upperBound) % lengthOfInterval; 
}

注釈

private void generateWorldMPD() {               
    /* The following is my first attempt at the MDP algorithm. */       

    // displacement boundary.
    double displacementBound = Constants.DEFAULT_ROUGHNESS_CONSTANT;
    double[][] A = Utilities.get2DDoubleArray(Constants.MPD_PRESET_HEIGHT, 2, 2);
    int iterations =0;

この部分では、変数displacementBound、デフォルト値に初期化されたdoubleの2D配列、およびiterationsと呼ばれる別の変数を定義します。

while (iterations < mPDIterations) {

    // create a new array large enough for the new points being added.
    double [][] B = new double[A.length * 2 - 1][A[0].length * 2 - 1];

    // move the points in A to B, skipping every other element as space for a new point
    for (int i = 0; i < B.length; i +=2) 
        for (int j = 0; j < B[i].length; j+=2) {
            B[i][j] = A[i / 2][j / 2];                  
        }

この部分でループが宣言されます。mPDIterationsループに対して実行されます。その場しのぎの配列Bを作成してAの更新バージョンを保持し、BをAより大きくして新しいデータ ポイントを保持します。その後、2 つの for ループがあり、1 つは別の内部にネストされています。これは、Aの現在の値を一時的なBに配置し、他のすべての行と他のすべての列を空白のままにします。次の例を見てください。

// The '*'s represent a cell in an array that is populated with a value.
// The '_'s represent a cell in an array that is empty.

// This is 'A'.
* *
* *

// This is 'B'. At the moment, completely empty.
_ _ _ 
_ _ _ 
_ _ _ 

// The elements of 'A' are tranferred to 'B'.
// Blank cells are inserted in every other row, and every other column.
* _ * 
_ _ _ 
* _ *

次のコードは次のとおりです。

        //calculate the height of each new center point as the average of the four adjacent elements  
        //(diamond step) and add a random displacement to each
        for (int i = 1; i < B.length; i+= 2)
            for (int j = 1; j < B[i].length; j+=2)  {
                averageFromCornersAndDisplace(B, i, j, displacementBound);

            }

このセクションでは、中心のすべての点 (北、南、東、西のすべての基本方向に空の隣接セルがあるセルを参照) に、隣接する 4 つの角点から平均化された値が与えられます。変位値がそれに追加されます。これをダイヤモンドステップと呼びます。「センター」とは何かを明確にするには:

// The big "O" indicates the 'center' in this 2D array.
* _ *
_ O _
* _ *

そして、次のコード セクション:

//calculate the height of each new non-center point (square step) and add a random displacement to each
for (int i = 0; i < B.length; i ++)
    for (int j = 0; j < B[i].length; j++)
        if (i % 2 == 0)         //on every even row, calculate for only odd columns
            if (j % 2 == 0) continue;
            else
                averageFromAdjAndDisplace( B , i, j, displacementBound );

    else                                //on every odd row, calculate for only even columns
            if (j % 2 == 0)
                averageFromAdjAndDisplace( B , i, j, displacementBound );
            else
                continue;

この部分は、コードの前のセクションに類似しています。中心ではない空の点にそれぞれ新しい値を割り当てます。この値は、北、南、東、西の基本方向に隣接する要素の平均であり、別のランダムな変位値が追加されます。これをスクエアステップと呼びます。上記のコードは、非中心点と空の点のみに新しい値が与えられることを保証します。これらのポイントは、以下で明確にされるサイド ポイントと同等です。

// The big 'O's indicate the 'side points' in this 2D array.
* O *
O * O
* O *

whileループを終了するセクションを以下に示します。

        displacementBound *= Math.pow(2, -Constants.DEFAULT_ROUGHNESS_CONSTANT);

        // assign B to A            
        A = B;

        iterations++;
    } // end of while loop

上記の記事に記載されている情報によると、変数の変位バウンドは、while ループの最後を構成する上記のセクションで削減されます。Aの内容は、ループの別の反復を開始または終了する前に、Bの更新された内容をAに割り当てることによって更新されます。

最後に、補助的なメソッドaverageFromCornersAndDisplace()、averageFromSidesAndDisplace()、およびwrap()が含まれていますが、それらの追加の説明は不要です。メソッドrandomDisplacement()はまったく含まれていません。参考までに、指定された数値bによって境界付けられたランダムな浮動小数点数xを返します。

// The method returns a double x, where -b <= x < b
double randomDisplacement(double b);
4

2 に答える 2

1

あなたの投稿がポップアップ表示されるのを見たところですが、すでに整理されていると思います。とにかく、そのようなラップを行いたい場合は、C/Java でネガティブ mod が正しく機能しないという事実を修正するための巧妙なトリックがあります。あなたがすることは、モジュラスの倍数を（オーバーフローしないように注意して）数値に戻して、それが負でないことを確認することです。その後、壊れることなく通常どおり改造できます。次に例を示します。

private int wrap(int n, int lowerBound, int upperBound) {
    int lengthOfInterval = upperBound - lowerBound;
    return lowerBound + ((n - lowerBound + lengthOfInterval) % lengthOfInterval);
}
于 2011-06-25T07:58:10.110 に答える
1

wrap()関数が原因です。インデックスが配列の境界を超えるとラップアラウンドするため、エッジで 2 つの (多くの場合異なる) 値が平均化されます。これは奇妙な非互換性につながります。wrap()へのすべての呼び出しを削除し、ラップが必要な場合は常に 4 つではなく 3 つの隣接するポイントを平均化することを選択しました。

メソッドwrap()は、シームレスなタイリングを提供することを意図していましたが、この場合、問題が発生したようです。また、タイルはシームレスに見えません。

于 2011-06-25T07:38:10.757 に答える