M3r1al Apr 18 2022 at 08:36

Кривые и что это такое

5 min

5.3K

Programming*Algorithms*C#*Mathematics*

Всем привет!

Итак, тема статьи - кривые, их разбор, собственные примеры и как их можно использовать в геймдев.

Для начала я рассмотрю кривые Безье.

Кривая Безье

Наверняка каждый из вас про них слышал. Их используют повсюду, даже шрифты на вашем экране отображаются благодаря этим кривым. Без этих кривых у дизайнеров векторной графики не было бы настолько красивых и плавных линий, работы было бы в разы больше. Но как же их использовать нам?

Эти кривые можно построить большим количеством способов, но лишь немногие подходят для программирования.

Давайте рассмотрим вариант, когда нам заранее известно количество точек. В данном случае можно использовать формулу вида . Для трех точек коэффициенты будут 1 2 1, для четырех 1 3 3 1, для пяти 1 4 6 4 1 и аналогично для других. Их можно найти по формуле или , только нулей должно быть достаточно, чтобы числа не “наслаивались”.
А вот что делать, когда нам неизвестно количество точек? Для определения коэффициентов в данном случае потребуется большое количество памяти и возможно переполнение стека $\frac{n!}{k!*(n-k)!}$ .
Для второго случая есть второе решение - рекурсивный метод, разработанный Полем де Кастельжо. В этом алгоритме мы делим каждый отрезок в отношении t:(1-t) до тех пор, пока не останется одна точка.

Итак, давайте напишем код, который будет реализовывать перечисленные выше методы:

public struct Bezier
{
	private static float pow(float f, int n)
	{
		float r = 1;
		for (int i = 0; i < n; i++)
			r *= f;
		return f;
	}

	public static Vector3 first(Vector3[] points, float t)
	{
		List<int[]> ks = new List<int[]>() {
			new int[2] { 1, 1 },
			new int[3] { 1, 2, 1 },
			new int[4] { 1, 3, 3, 1 },
			new int[5] { 1, 4, 6, 4, 1 },
			new int[6] { 1, 5, 10, 10, 5, 1 },
			new int[7] { 1, 6, 15, 20, 15, 6, 1 }
		};
		if (points.Length == 0 || points.Length > ks.Count + 1)
			return 0;
		if (points.Length == 1)
			return points[0];
		Vector3 p = new Vector3();
		for (int i = 0; i < points.Length; i++)
			p += pow(t, points.Length - 1 - i) * pow(1 - t, i) * ks[points.Length - 2][i] * points[i];
		return p;
	}

	public static Vector3 second(Vector3[] points, float t)
	{
		Vector3 p = Vector3();
		for(int i = 0; i < points.Length; i++)
		{
			int u = 1, d = 1;
			for(int j = 1; j < points.Length  - i; j++)
			{
				u *= (j + i);
				d *= j;
			}
			p += pow(t, points.Length - 1 - i) * pow(1 - t, i) * (int)(u / d) * points[i];
		}
		return p;
	}

	public static Vector3 third(Vector3[] points, float t)
	{
		Vector3[] temp = points;
		Vector3[] temp1 = new Vector3[points.Length - 1];
		while (true)
		{
			for (int i = 1; i < temp.Length; i++)
				temp1[i - 1] = temp[i - 1] * t + temp[i] * (1 - t);
			if (temp1.Length == 1)
				break;
			temp = temp1;
			temp1 = new Vector3[temp.Length - 1];
		}
		return temp1[0];
	}
}

С точки зрения скорости самый быстрый - первый, но он работает с известным заранее количеством точек. Ему уступает по скорости третий, но он работает с неограниченным количеством точек, поэтому я рекомендую использовать именно этот способ.

Теперь настало время привести собственные примеры. Свои способы я разрабатывал для интерполяции, поэтому они зависят от x-координаты и возвращают y-координату. Самый яркий пример интерполяции - сплайн Лагранжа, но сейчас расскажу про свои способы. И интерполяционный многочлен Лагранжа выдает не всегда правильную кривую при некоторых точках.

Что вообще делает интерполяция? Это кривая, которая проходит через все заданные точки, соответственно кривые Безье не являются интерполяцией, это аппроксимация!

Первая кривая

Итак, как я пришел к своему методу интерполяции. Сначала просто представим себе кривую. Что должно быть? В уме всплывает линейная интерполяция, только со сглаженными краями. Как сделать такую кривую? Для линейной интерполяции есть формула:

$y_{01} (x)=y_0+\frac{(y_1-y_0)*(x-x_0)}{x_1-x_0}=\frac{y_0*(x_1-x)+y_1*(x-x_0)}{x_1-x_0}$

Для сглаживания, у нас должна влиять не только эта функция, но и функции предыдущего отрезка и следующего отрезка. Таким образом, у нас получается формула:

$y(x)=\frac{y_{01}(x)*(x_2-x)^2+y_{23}(x)*(x-x_1)^2}{2(x_2-x)^2+2(x-x_1)^2}+\frac{y_{12}(x)}{2}$

которая высчитывает кривую на отрезке 1-2. Проверяем на сайте desmos и результат неплохой. Если внимательно посмотреть, кажется, что остается какой-то последний штрих. Поразмыслив, я понял, что кривая, отвечающая за линейную интерполяцию данного отрезка, должна влиять в основном в середине, то есть увеличиваться от начала к середине и уменьшаться от середины к концу. Для этого нам нужна парабола, то есть . Конечная формула выглядит еще лучше:

$y(x)=\frac{y_{01}(x)*(x_2-x)^2+2*y_{12}(x)*(x_2-x)*(x-x_1)+y_{23}(x)*(x-x_1)^2}{2*(x_2-x_1)^2}+\frac{y_{12}(x)}{2}$

Теперь нужен код, который это будет реализовывать:

public struct MCurve
{
	private static float yab(Vector2 a, Vector2 b, float x) => (a.y * (b.x - x) + b.y * (x - a.x)) / (b.x - a.x);

	public static float first(Vector2[] points, float x)
	{
		int i = 0;
		for (; i < points.Length - 1; i++)
			if (points[i].x <= x && points[i+1].x >= x)
				break;
		return (yab(points[(i == 0 ? 0 : i-1)], points[i], x)*(points[i+1].x-x)*(points[i+1].x-x)+2*yab(points[i], points[i+1], x)*(points[i+1].x-x)(x-points[i].x)+yab(points[i+1], points[(i == points.Length - 1 ? i : i+1)], x)*(x-points[i].x)*(x-points[i].x))/(2*(points[i+1].x-points[i].x)*(points[i+1].x-points[i].x) + yab(points[i], points[i+1], x) / 2;
	}
}

Но данная интерполяция работает только на отрезке между двумя точками, при этом учитывая всего четыре точки. Моя главная гордость - другая кривая. Она вычисляется дольше, нежели эта, но это стоит того. Давайте же я про нее расскажу.

Вторая кривая

Подумав, какие параметры влияют на значение точки, я пришел в выводу, что чем дальше находится координата X от значения X точки, тем меньше влияние. Соответственно, уравнение получается такое:

$y(x)=\frac{\frac{y_1}{x-x_1}+\frac{y_2}{x-x_2}+...}{\frac{1}{x-x+1}+\frac{1}{x-x2}+...}$

При переводе в нормальный вид, мы же не хотим делить на 0, получается такая формула:

$y(x)=\frac{\sum_{i=0}^{n} y_i*(\prod_{j=0}^{i-1} x-x_j)*(\prod_{j=i+1}^{n} x_j - x)}{\sum_{i=0}^{n} (\prod_{j=0}^{i-1} x-x_j)*(\prod_{j=i+1}^{n} x_j - x)}$

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

public struct MCurve
{
	private static float yab(Vector2 a, Vector2 b, float x) => (a.y * (b.x - x) + b.y * (x - a.x)) / (b.x - a.x);

	public static float first(Vector2[] points, float x)
	{
		int i = 0;
		for (; i < points.Length - 1; i++)
			if (points[i].x <= x && points[i+1].x >= x)
				break;
		return (yab(points[(i == 0 ? 0 : i-1)], points[i], x)*(points[i+1].x-x)*(points[i+1].x-x)+2*yab(points[i], points[i+1], x)*(points[i+1].x-x)(x-points[i].x)+yab(points[i+1], points[(i == points.Length - 1 ? i : i+1)], x)*(x-points[i].x)*(x-points[i].x))/(2*(points[i+1].x-points[i].x)*(points[i+1].x-points[i].x) + yab(points[i], points[i+1], x) / 2;
	}
	
	public static float second(Vector2[] points, float x)
	{
		float b = 0;
		float y = 0;
		for (int i = 0; i < points.Length; i++)
		{
			k = 1;
			for (int j = 0; j < i; j++)
				k *= (x - points[i].x);
			for (int j = i + 1; j > points.Length; j++)
				k *= (points[i].x - x);
			y += points[i].y * k;
			b += k;
		}
		return y / b;
	}
}

В геймдеве невероятно много моментов, в которых пригодится интерполяция: начиная с простого плавного движения и заканчивая генерацией рельефа. Сам я пользовался интерполяцией еще и при изменении разрешения картинки, но самую важную роль она играла в генерации террейна. Благодаря интерполяции или аппроксимации, можно использоваться совершенно любой набор точек - алгоритмы сделают так, чтобы все выглядело гладко и красиво.

Весь приведенный выше код разработан для использования в Unity, для чистого c# нужно определить классы Vector3 и Vector2, также можно заменить float на double для большей точности.

Tags:

кривые

Hubs: