Высота ландшафта.

Автор: Shuher

Одна из важных задач, которую необходимо решить при программировании ландшафта: определение его высоты в какой-то конкретной точке. Это необходимо, например, для того, чтобы камера всегда находилась на определенном расстоянии от ландшафта; чтобы дерево уходило корнями именно в ландшафт, а не висело над ним, а ракета, пущенная сверху вниз, взрывалась при ударении о ландшафт, а не о Sky-box :)

Есть несколько способов определения высоты на ландшафте. Рассмотрим 3 из них.

Первый довольно очевидный. Находим самую высокую вершину в заданном радиусе от точки и определяем ее, как текущую. Этот способ применим на тех картах, где разброс высот не очень большой, и может применяться для определения позиции камеры.

Второй недалеко ушел от предыдущего. Вместо самой высокой точки можно взять среднее арифметическое от ближних высот. А это уже, хоть какой-то, да расчет. Он может применяться для грубых расчетов, где не нужна большая точность (например, для вычисления положения здания на ландшафте).

Однако, есть третий способ, с помощью которого можно точно рассчитать высоту точки на ландшафте. Его реализацией мы сейчас и займемся.

Для начала, необходимо определить, что же у нас есть. А есть у нас, собственно, карта высот (height_map[n][n]), размер тайла (TileSize) и точка с координатами A=(X,Z). Нам необходимо найти высоту ландшафта в точке A, то есть, фактически, Y-координату точки A. Вот как это выглядит, если смотреть на ландшафт сверху вниз:

Для определения высоты нам необходимо знать, над(под) каким тайлом находится точка. Ищется это просто:

I=(int)(X/TileSize);
J=(int)(Z/TileSize);

, где I и J - координаты тайла на карте высот.

Для следующего шага нам понадобится тот факт, что, на самом деле, каждый тайл карты высот - это 2 треугольника, которые имеют общую грань. Это сильно облегчит нам задачу, так как работать с треугольниками гораздо проще, чем, например, с квадратами.

Для определения высоты необходимо узнать в каком из треугольников лежит точка. Для этого мы перенесем тайл в начало системы координат и найдем координаты X и Z точки А уже в новой системе. Для этого достаточно сделать следующие преобразования:

X0=int(X)%TileSize;
Z0=int(Z)%TileSize;

, где X0 и Z0 - координаты точек в новой системе координат:

Я неслучайно пронумеровал вершины квадрата. У треугольника (1,2,4) есть особенность по отношению к (2,3,4). Все дело в том, что если точка лежит в (1,2,4), то сумма координат X и Z будет меньше, чем TileSize. Вот таким простым методом можно определить к какому треугольнику принадлежит точка.

Теперь мы знаем в каком треугольнике лежит точка. Осталось вывести уравнение плоскости, в которой он находится, и по нему определить координату Y точки А.

Для вершин 2 и 4 все считается просто. Их координаты нам хорошо известны:

//точка 2
X2= I*TileSize;
Z2= (J+1)*TileSize;
Y2=height_map[I][J+1];
//точка 4
X3= (I+1)*TileSize;
Z3= J*TileSize;
Y3=height_map[I+1][J];

А вот 3-ю точку необходимо искать уже с учетом проверки на принадлежность к одному из треугольников:

//точка 1 или 3
if  (X0+Z0>=TileSize)
{
       X1= I*TileSize;
       Z1= J*TileSize;
       Y1=height_map[I][J];
}
else
{
       X1= (I+1)*TileSize;
       Z1=(J+1)*TileSize;
       Y1=height_map[I+1][J+1];
}

Теперь у нас есть 3 точки, по которым можно вывести уравнение плоскости (Ax+By+Cz+D=0), в которой лежит наша точка:

double a=-(z3*y2-z1*y2-z3*y1+y1*z2+y3*z1-z2*y3);
double b= (z1*x3+z2*x1+z3*x2-z2*x3-z1*x2-z3*x1);
double c= (y2*x3+y1*x2+y3*x1-y1*x3-y2*x1-x2*y3);
double d=-a*x1-b*y1-c*z1;

Из уравнения плоскости видно, что y=-(Ax+Cz+D)/B. Подставив в эту формулу данные, которые у нас есть, получим: Y=-(a*X+c*Z+d)/b

Вот и все! Теперь у нас есть координата Y точки A. Осталось добавить к ней рост человека, и у нас получится координата положения камеры над ландшафтом.

Если что, я всегда на связи.

#ландшафт

23 июня 2002

Комментарии [23]