CODEWITHSUNDEEP
javaterrainfractalslighthouse
Joshua S.
Joshua S.

Reputation: 31

Midpoint Displacement Terrain Artifacts

I am trying to implement the midpoint displacement algorithm in Java. It's also called the diamond square algorithm. My reference is http://www.lighthouse3d.com/opengl/terrain/index.php3?mpd. It seems to work correctly except on the right and bottom edges.

See Midpoint Displacement Results

Upon close inspection, the "rough" edges can be seen. Could anyone point out what is wrong? This effect hasn't been observed in other online implementations of this algorithm.

Code

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

Annotations

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;

This part defines a variable displacementBound, a 2D array of doubles initialized to default values, and another variable called 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];                  
        }

This part is where the loop is declared. It will run for mPDIterations loops. A makeshift array B is created to hold an updated version of A, making B larger than A to hold new data points. After that there are two for loops, one nested inside another, which places the current values of A into the temporary B, taking care to leave every other row and every other column blank. Take a look at this example:

// 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.
* _ * 
_ _ _ 
* _ *

Now for the next bit of code:

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

            }

In this section, every point at a center, which refers to a cell that has an empty adjacent cell in every cardinal direction of north, south, east, and west, is given a value averaged from the four adjacent corner points and with a random displacement value added to it. This is called the diamond step. To clarify what a 'center' is:

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

And the next code section:

//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;

This part does is analogous to the previous section of code. It assigns to each non-center and empty point a new value; this value is the average of the adjacent elements in the cardinal directions north, south, east, and west, with another random displacement value added to it. This is called the square step. The code above assures that only the non-center and empty points are given new values; these points being equivalent to side points, which are clarified below:

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

The section that concludes the while loop is given below:

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

        // assign B to A            
        A = B;

        iterations++;
    } // end of while loop

The variable displacementBound is reduced in the section above, which comprises the end of the while loop, according to the information given in the aforementioned article. The contents of A are renewed by assigning the updated contents of B to A prior to beginning another iteration of the loop or terminating it.

Lastly, the ancillary methods averageFromCornersAndDisplace(), averageFromSidesAndDisplace(), and wrap() have been included but additional explanations for them are unnecessary. The method randomDisplacement() has not been included at all. For your information, it returns a random floating-point number x bounded by the given number b:

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

Upvotes: 2

Views: 1535

Answers (2)

Joshua S.
Joshua S.

Reputation: 31

The wrap() function is the culprit. It wraps indexes around when they exceed the boundaries of the array, so that on the edges two (often disparate) values are averaged together. Which lead to the weird incompatibility. I deleted all calls to wrap() and chose to average three adjacent points instead of four whenever wrapping was necessary.

The method wrap() was meant to provide seamless tiling, but in this case seems to have caused a problem. And the tiling doesn't even look seamless.

Upvotes: 1

Mikola
Mikola

Reputation: 9326

I just saw your post pop up, and I guess you've already sorted it out. Anyway, if you want to do a wrap like that, there is a neat trick to fix the fact that negative mods don't work right in C/Java. What you do is just add some multiple of the modulus (being careful not to overflow) back to the number to ensure that it is non-negative. Then you can mod out as usual without it breaking. Here is an example:

private int wrap(int n, int lowerBound, int upperBound) {
    int lengthOfInterval = upperBound - lowerBound;
    return lowerBound + ((n - lowerBound + lengthOfInterval) % lengthOfInterval);
}

Upvotes: 1

Related Questions