Недавно возникла необходимость в «реальном времени» увеличивать разрешение карты высот для одной разрабатываемой игры. По существу, задача сводится к трёхмерной линейной интерполяции: берем уравнение плоскости, выражаем высоту (Z), т.е. приводим уравнение к виду z = f(x_1, y_1, z_1, x_2, y_2, z_2, x_3, y_3, z_3, x, y), подставляем туда координаты трёх известных точек и две координаты искомой и получаем результат.

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

\begin{vmatrix}x-x_1&y-y_1&z-z_1\\ x_2-x_1&y_2-y_1&z_2-z_1\\ x_3-x_1&y_3-y_1&z_3-z_1\end{vmatrix}=0

Как видно, чтобы привести этот вид уравнения плоскости к виду z=f(...) необходимо по-честному взять длиннющий определитель. Результат этой нехитрой операции таков:

z=\frac{1}{x_2y_3-x_1y_3-x_2y_1-x_3y_2+x_1y_2+x_3y_1}[z_1(x_2y_3-x_1y_3-x_2y_1-x_3y_2+x_1y_2+x_3y_1)+(y-y_1)(x_2z_3-x_1z_3-x_2z_1-x_3z_2+x_1z_2+x_3z_1)-(x-x_1)(y_2z_3-y_1z_3-y_2z_1-y_3z_2+y_1z_2+y_3z_1)].

Собственно, это выражение и есть формула трёхмерной линейной интерполяции. Несмотря на свою длину, вычисляется оно довольно быстро. Предлагаю готовый метод на C#, реализующий эту формулу.


static float InterpolateHeight(Point3D p1, Point3D p2, Point3D p3, float selfX, float selfY)
{
	var tz = (p2.X * p3.Y - p1.X * p3.Y - p2.X * p1.Y - p3.X * p2.Y + p1.X * p2.Y + p3.X * p1.Y);
	var tx = (p2.Y * p3.Z - p1.Y * p3.Z - p2.Y * p1.Z - p3.Y * p2.Z + p1.Y * p2.Z + p3.Y * p1.Z);
	var ty = (p2.X * p3.Z - p1.X * p3.Z - p2.X * p1.Z - p3.X * p2.Z + p1.X * p2.Z + p3.X * p1.Z);
	return (1 / tz) * (((selfY - p1.Y) * ty) + p1.Z * tz - (selfX - p1.X) * tx);
}

Здесь Point3D — простейшая структура, содержащая тройку (X, Y, Z) координат точки.

Как же мы, имея интерполятор, сглаживаем карту высот во время работы? Берем координаты (X, Y) интересующей нас точки (обычно — персонажа или NPC), находмим ближайшие к нам на плоскости три точки карты высот, передаём все эти данные функции-интерполятору и получаем искомую высоту.

comments powered by HyperComments