我正在尝试在 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，一个初始化为默认值的二维双精度数组，以及另一个称为迭代的变量。
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以保存新数据点。之后有两个 for 循环，一个嵌套在另一个循环中，它将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);
}
在本节中，中心的每个点，指在北、南、东、西的每个基本方向上都有一个空的相邻单元格的单元格，给定四个相邻角点的平均值，并且随机位移值添加到它。这称为钻石步骤。澄清什么是“中心”：
// 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
根据上述文章中给出的信息，变量displacementBound在上面的部分中被减少，其中包括while 循环的结束。在开始循环的另一次迭代或终止循环之前，通过将B的更新内容分配给 A 来更新A的内容。
最后，还包括了辅助方法averageFromCornersAndDisplace()、averageFromSidesAndDisplace()和wrap() ，但不需要对它们进行额外的解释。根本没有包含方法randomDisplacement() 。供您参考，它返回一个以给定数字b为界的随机浮点数x：
// The method returns a double x, where -b <= x < b
double randomDisplacement(double b);