Я пытаюсь реализовать алгоритм смещения средней точки *1002* в 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, инициализированный значениями по умолчанию, и другую переменную, называемую 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 для хранения новых точек данных.После этого есть два цикла 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 *
Раздел, завершающий цикл , в то время как приведен ниже:
displacementBound *= Math.pow(2, -Constants.DEFAULT_ROUGHNESS_CONSTANT);
// assign B to A
A = B;
iterations++;
} // end of while loop
Переменная displacementBound уменьшается в приведенном выше разделе, который включает в себя конец цикла while, в соответствии с информацией, приведенной в вышеупомянутой статье.Содержимое A обновляется назначением обновленного содержимого B на A до начала другой итерации цикла или его завершения.
Наконец, вспомогательные методы averageFromCornersAndDisplace () , averageFromSidesAndDisplace () и wrap () были включены, но дополнительные объяснения для них не нужны.Метод randomDisplacement () вообще не был включен.Для вашей информации, он возвращает случайное число с плавающей точкой x , ограниченное данным числом b :
// The method returns a double x, where -b <= x < b
double randomDisplacement(double b);