Высота ландшафта.
Автор: 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