Curves and what is it
Hello!
So, the topic of the article is curves, their analysis, own examples and how they can be used in game development.
First, I’ll look at Bezier curves.
bezier curve
Surely each of you heard about them. They are used everywhere, even the fonts on your screen are displayed thanks to these curves. Without these curves, vector graphics designers would not have such beautiful and smooth lines, there would be many times more work. But how can we use them?
These curves can be built in many ways, but only a few are suitable for programming.
1. Let’s consider the option when we know the number of points in advance. In this case, you can use a formula like P0 * (1-t)^n + a * P1 * (1-t)^(n-1) * t + … + Pn * t^n. For three points the coefficients will be 1 2 1, for four points 1 3 3 1, for five points 1 4 6 4 1 and similarly for others. They can be found using the formula (a + b)^n or 101^n, only zeros should be enough so that the numbers do not “layer”.
2. But what to do when we do not know the number of points? To determine the coefficients in this case, a large amount of memory is required and a stack overflow n!/k!*(nk)! is possible.
3. For the second case, there is a second solution – a recursive method developed by Paul de Casteljo. In this algorithm, we divide each segment with respect to t:(1-t) until one point remains.
So, let’s write the code that will implement the methods listed above:
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];
}
}
In terms of speed, the first one is the fastest, but it works with a known number of points. It is inferior in speed to the third, but it works with an unlimited number of points, so I recommend using this particular method.
Now it’s time to give your own examples. I developed my methods for interpolation, so they depend on the x-coordinate and return the y-coordinate. The most striking example of interpolation is the Lagrange spline, but now I will tell you about my methods. And the Lagrange interpolation polynomial produces a not always correct curve at some points.
What does interpolation actually do? This is a curve that passes through all given points, so Bezier curves are not an interpolation, they are an approximation!
First curve
So how did I arrive at my interpolation method. First, just imagine a curve. What should be? Linear interpolation comes to mind, only with smooth edges. How to make such a curve? For linear interpolation there is a formula:
y01(x)=y0+(y1-y0)(x-x0)/(x1-x0)=(y0(x1-x)+y1*(x-x0))/(x1-x0).
For smoothing, not only this function should influence us, but also the functions of the previous segment and the next segment. Thus, we get the formula:
y(x)=((y01(x)(x2-x)^2+y23(x)(x-x1)^2)/((x2-x)^2+(x-x1)^2)+y12(x))/2,
which calculates a curve on a segment 1-2. We check on the desmos website and the result is not bad. If you look closely, it seems that some final touch remains. On reflection, I realized that the curve responsible for the linear interpolation of a given segment should mainly affect the middle, that is, increase from the beginning to the middle and decrease from the middle to the end. For this we need a parabola, i.e. (x-x1)(x2-x1). The final formula looks even better:
y(x)=(y01(x)(x2-x)^2+2y12(x)(x2-x)(x-x1)+y23(x)(x-x1)^2)/2(x2-x1)^2+y12(x)/2.
Now we need the code that will implement this:
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;
}
}
But this interpolation works only on the segment between two points, while taking into account only four points. My main pride is another curve. It takes longer to calculate than this one, but it’s worth it. Let me tell you about her.
Second curve
After thinking about what parameters affect the value of a point, I came to the conclusion that the farther the X coordinate is from the X value of the point, the less influence. Accordingly, the equation becomes:
y(x)=(y1/(x-x1)+y2/(x-2)+…)/(1/(x-x1)+1/(x-x2)+…).
When translated into normal form, we don’t want to divide by 0, we get the following formula:
y(x)=Sum(i=0, n, yi*Product(j=0, i-1, x-xj)*Product(j=i+1, n, xj – x))/Sum(i= 0, n, Product(j=0, i-1, x-xj)*Product(j=i+1, n, xj – x)).
If you check this formula on the desmos website, you can immediately see that not only all points affect the curve, but there are no erroneous tests as with the Lagrange polynomial. The curve looks very smooth and pleasing to the eye, so it can compete with the Lagrange polynomial, and because the formula always gives the correct curve, my curve is better than the Lagrange polynomial. And it has the same number of iterations, since the coefficients can be calculated in one cycle. In code it will look like this:
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;
}
}
In game development, there are incredibly many moments where interpolation comes in handy: from simple smooth movement to terrain generation. I myself used interpolation also when changing the resolution of the image, but it played the most important role in the generation of the terrain. Thanks to interpolation or approximation, absolutely any set of points can be used – the algorithms will make everything look smooth and beautiful.
All of the above code is designed to be used in Unity, for pure c# you need to define the Vector3 and Vector2 classes, you can also replace float with double for more precision.
