A game framework written with osu! in mind.
keii.dev
1// Copyright (c) ppy Pty Ltd <contact@ppy.sh>. Licensed under the MIT Licence.
2// See the LICENCE file in the repository root for full licence text.
3
4using System;
5using System.Linq;
6using System.Reflection;
7using System.Runtime.Serialization;
8using osu.Framework.Extensions.Color4Extensions;
9using osu.Framework.Graphics;
10using osu.Framework.Graphics.Colour;
11using osu.Framework.Graphics.Effects;
12using osu.Framework.Graphics.Primitives;
13using osu.Framework.Graphics.Transforms;
14using osuTK;
15using osuTK.Graphics;
16
17namespace osu.Framework.Utils
18{
19 public static class Interpolation
20 {
21 public static double Lerp(double start, double final, double amount) => start + (final - start) * amount;
22
23 /// <summary>
24 /// Interpolates between 2 values (start and final) using a given base and exponent.
25 /// </summary>
26 /// <param name="start">The start value.</param>
27 /// <param name="final">The end value.</param>
28 /// <param name="base">The base of the exponential. The valid range is [0, 1], where smaller values mean that the final value is achieved more quickly, and values closer to 1 results in slow convergence to the final value.</param>
29 /// <param name="exponent">The exponent of the exponential. An exponent of 0 results in the start values, whereas larger exponents make the result converge to the final value.</param>
30 public static double Damp(double start, double final, double @base, double exponent)
31 {
32 if (@base < 0 || @base > 1)
33 throw new ArgumentOutOfRangeException(nameof(@base), $"{nameof(@base)} has to lie in [0,1], but is {@base}.");
34 if (exponent < 0)
35 throw new ArgumentOutOfRangeException(nameof(exponent), $"{nameof(exponent)} has to be bigger than 0, but is {exponent}.");
36
37 return Lerp(start, final, 1 - Math.Pow(@base, exponent));
38 }
39
40 /// <summary>
41 /// Interpolates between a set of points using a lagrange polynomial.
42 /// </summary>
43 /// <param name="points">An array of coordinates. No two x should be the same.</param>
44 /// <param name="time">The x coordinate to calculate the y coordinate for.</param>
45 public static double Lagrange(ReadOnlySpan<Vector2> points, double time)
46 {
47 if (points == null || points.Length == 0)
48 throw new ArgumentException($"{nameof(points)} must contain at least one point");
49
50 double sum = 0;
51 for (int i = 0; i < points.Length; i++)
52 sum += points[i].Y * LagrangeBasis(points, i, time);
53 return sum;
54 }
55
56 /// <summary>
57 /// Calculates the Lagrange basis polynomial for a given set of x coordinates. Used as a helper function to compute Lagrange polynomials.
58 /// </summary>
59 /// <param name="points">An array of coordinates. No two x should be the same.</param>
60 /// <param name="base">The index inside the coordinate array which polynomial to compute.</param>
61 /// <param name="time">The x coordinate to calculate the basis polynomial for.</param>
62 public static double LagrangeBasis(ReadOnlySpan<Vector2> points, int @base, double time)
63 {
64 double product = 1;
65
66 for (int i = 0; i < points.Length; i++)
67 {
68 if (i != @base)
69 product *= (time - points[i].X) / (points[@base].X - points[i].X);
70 }
71
72 return product;
73 }
74
75 /// <summary>
76 /// Calculates the Barycentric weights for a Lagrange polynomial for a given set of coordinates. Can be used as a helper function to compute a Lagrange polynomial repeatedly.
77 /// </summary>
78 /// <param name="points">An array of coordinates. No two x should be the same.</param>
79 public static double[] BarycentricWeights(ReadOnlySpan<Vector2> points)
80 {
81 int n = points.Length;
82 double[] w = new double[n];
83
84 for (int i = 0; i < n; i++)
85 {
86 w[i] = 1;
87
88 for (int j = 0; j < n; j++)
89 {
90 if (i != j)
91 w[i] *= points[i].X - points[j].X;
92 }
93
94 w[i] = 1.0 / w[i];
95 }
96
97 return w;
98 }
99
100 /// <summary>
101 /// Calculates the Lagrange basis polynomial for a given set of x coordinates based on previously computed barycentric weights.
102 /// </summary>
103 /// <param name="points">An array of coordinates. No two x should be the same.</param>
104 /// <param name="weights">An array of precomputed barycentric weights.</param>
105 /// <param name="time">The x coordinate to calculate the basis polynomial for.</param>
106 public static double BarycentricLagrange(ReadOnlySpan<Vector2> points, double[] weights, double time)
107 {
108 if (points == null || points.Length == 0)
109 throw new ArgumentException($"{nameof(points)} must contain at least one point");
110 if (points.Length != weights.Length)
111 throw new ArgumentException($"{nameof(points)} must contain exactly as many items as {nameof(weights)}");
112
113 double numerator = 0;
114 double denominator = 0;
115
116 for (int i = 0; i < points.Length; i++)
117 {
118 // while this is not great with branch prediction, it prevents NaN at control point X coordinates
119 if (time == points[i].X)
120 return points[i].Y;
121
122 double li = weights[i] / (time - points[i].X);
123 numerator += li * points[i].Y;
124 denominator += li;
125 }
126
127 return numerator / denominator;
128 }
129
130 public static ColourInfo ValueAt(double time, ColourInfo startColour, ColourInfo endColour, double startTime, double endTime, Easing easing = Easing.None)
131 => ValueAt(time, startColour, endColour, startTime, endTime, new DefaultEasingFunction(easing));
132
133 public static EdgeEffectParameters ValueAt(double time, EdgeEffectParameters startParams, EdgeEffectParameters endParams, double startTime, double endTime, Easing easing = Easing.None)
134 => ValueAt(time, startParams, endParams, startTime, endTime, new DefaultEasingFunction(easing));
135
136 public static SRGBColour ValueAt(double time, SRGBColour startColour, SRGBColour endColour, double startTime, double endTime, Easing easing = Easing.None)
137 => ValueAt(time, startColour, endColour, startTime, endTime, new DefaultEasingFunction(easing));
138
139 public static Color4 ValueAt(double time, Color4 startColour, Color4 endColour, double startTime, double endTime, Easing easing = Easing.None)
140 => ValueAt(time, startColour, endColour, startTime, endTime, new DefaultEasingFunction(easing));
141
142 public static Colour4 ValueAt(double time, Colour4 startColour, Colour4 endColour, double startTime, double endTime, Easing easing = Easing.None)
143 => ValueAt(time, startColour, endColour, startTime, endTime, new DefaultEasingFunction(easing));
144
145 public static byte ValueAt(double time, byte val1, byte val2, double startTime, double endTime, Easing easing = Easing.None)
146 => ValueAt(time, val1, val2, startTime, endTime, new DefaultEasingFunction(easing));
147
148 public static sbyte ValueAt(double time, sbyte val1, sbyte val2, double startTime, double endTime, Easing easing = Easing.None)
149 => ValueAt(time, val1, val2, startTime, endTime, new DefaultEasingFunction(easing));
150
151 public static short ValueAt(double time, short val1, short val2, double startTime, double endTime, Easing easing = Easing.None)
152 => ValueAt(time, val1, val2, startTime, endTime, new DefaultEasingFunction(easing));
153
154 public static ushort ValueAt(double time, ushort val1, ushort val2, double startTime, double endTime, Easing easing = Easing.None)
155 => ValueAt(time, val1, val2, startTime, endTime, new DefaultEasingFunction(easing));
156
157 public static int ValueAt(double time, int val1, int val2, double startTime, double endTime, Easing easing = Easing.None)
158 => ValueAt(time, val1, val2, startTime, endTime, new DefaultEasingFunction(easing));
159
160 public static uint ValueAt(double time, uint val1, uint val2, double startTime, double endTime, Easing easing = Easing.None)
161 => ValueAt(time, val1, val2, startTime, endTime, new DefaultEasingFunction(easing));
162
163 public static long ValueAt(double time, long val1, long val2, double startTime, double endTime, Easing easing = Easing.None)
164 => ValueAt(time, val1, val2, startTime, endTime, new DefaultEasingFunction(easing));
165
166 public static ulong ValueAt(double time, ulong val1, ulong val2, double startTime, double endTime, Easing easing = Easing.None)
167 => ValueAt(time, val1, val2, startTime, endTime, new DefaultEasingFunction(easing));
168
169 public static float ValueAt(double time, float val1, float val2, double startTime, double endTime, Easing easing = Easing.None)
170 => ValueAt(time, val1, val2, startTime, endTime, new DefaultEasingFunction(easing));
171
172 public static decimal ValueAt(double time, decimal val1, decimal val2, double startTime, double endTime, Easing easing = Easing.None)
173 => ValueAt(time, val1, val2, startTime, endTime, new DefaultEasingFunction(easing));
174
175 public static double ValueAt(double time, double val1, double val2, double startTime, double endTime, Easing easing = Easing.None)
176 => ValueAt(time, val1, val2, startTime, endTime, new DefaultEasingFunction(easing));
177
178 public static Vector2 ValueAt(double time, Vector2 val1, Vector2 val2, double startTime, double endTime, Easing easing = Easing.None)
179 => ValueAt(time, val1, val2, startTime, endTime, new DefaultEasingFunction(easing));
180
181 public static RectangleF ValueAt(double time, RectangleF val1, RectangleF val2, double startTime, double endTime, Easing easing = Easing.None)
182 => ValueAt(time, val1, val2, startTime, endTime, new DefaultEasingFunction(easing));
183
184 public static TValue ValueAt<TValue>(double time, TValue startValue, TValue endValue, double startTime, double endTime, Easing easing = Easing.None)
185 => ValueAt(time, startValue, endValue, startTime, endTime, new DefaultEasingFunction(easing));
186
187 public static TValue ValueAt<TValue, TEasing>(double time, TValue startValue, TValue endValue, double startTime, double endTime, in TEasing easing)
188 where TEasing : IEasingFunction
189 => GenericInterpolation<TValue, TEasing>.FUNCTION(time, startValue, endValue, startTime, endTime, easing);
190
191 public static double ApplyEasing(Easing easing, double time)
192 => ApplyEasing(new DefaultEasingFunction(easing), time);
193
194 public static double ApplyEasing<TEasing>(in TEasing easing, double time)
195 where TEasing : IEasingFunction
196 => easing.ApplyEasing(time);
197
198 private static class GenericInterpolation<TEasing>
199 where TEasing : IEasingFunction
200 {
201 public static ColourInfo ValueAt(double time, ColourInfo startColour, ColourInfo endColour, double startTime, double endTime, in TEasing easing)
202 {
203 if (startColour.HasSingleColour && endColour.HasSingleColour)
204 return ValueAt(time, (Color4)startColour, (Color4)endColour, startTime, endTime, easing);
205
206 return new ColourInfo
207 {
208 TopLeft = ValueAt(time, (Color4)startColour.TopLeft, (Color4)endColour.TopLeft, startTime, endTime, easing),
209 BottomLeft = ValueAt(time, (Color4)startColour.BottomLeft, (Color4)endColour.BottomLeft, startTime, endTime, easing),
210 TopRight = ValueAt(time, (Color4)startColour.TopRight, (Color4)endColour.TopRight, startTime, endTime, easing),
211 BottomRight = ValueAt(time, (Color4)startColour.BottomRight, (Color4)endColour.BottomRight, startTime, endTime, easing),
212 };
213 }
214
215 public static EdgeEffectParameters ValueAt(double time, EdgeEffectParameters startParams, EdgeEffectParameters endParams, double startTime, double endTime, in TEasing easing)
216 => new EdgeEffectParameters
217 {
218 Type = startParams.Type,
219 Hollow = startParams.Hollow,
220 Colour = ValueAt(time, startParams.Colour, endParams.Colour, startTime, endTime, easing),
221 Offset = ValueAt(time, startParams.Offset, endParams.Offset, startTime, endTime, easing),
222 Radius = ValueAt(time, startParams.Radius, endParams.Radius, startTime, endTime, easing),
223 Roundness = ValueAt(time, startParams.Roundness, endParams.Roundness, startTime, endTime, easing),
224 };
225
226 public static SRGBColour ValueAt(double time, SRGBColour startColour, SRGBColour endColour, double startTime, double endTime, in TEasing easing)
227 => ValueAt(time, (Color4)startColour, (Color4)endColour, startTime, endTime, easing);
228
229 /// <summary>
230 /// Interpolates between two sRGB <see cref="Color4"/>s in a linear (gamma-correct) RGB space.
231 /// </summary>
232 /// <remarks>
233 /// For more information regarding linear interpolation, see https://blog.johnnovak.net/2016/09/21/what-every-coder-should-know-about-gamma/#gradients.
234 /// </remarks>
235 public static Color4 ValueAt(double time, Color4 startColour, Color4 endColour, double startTime, double endTime, in TEasing easing)
236 {
237 if (startColour == endColour)
238 return startColour;
239
240 double current = time - startTime;
241 double duration = endTime - startTime;
242
243 if (duration == 0 || current == 0)
244 return startColour;
245
246 var startLinear = startColour.ToLinear();
247 var endLinear = endColour.ToLinear();
248
249 float t = Math.Max(0, Math.Min(1, (float)easing.ApplyEasing(current / duration)));
250
251 return new Color4(
252 startLinear.R + t * (endLinear.R - startLinear.R),
253 startLinear.G + t * (endLinear.G - startLinear.G),
254 startLinear.B + t * (endLinear.B - startLinear.B),
255 startLinear.A + t * (endLinear.A - startLinear.A)).ToSRGB();
256 }
257
258 public static Colour4 ValueAt(double time, Colour4 startColour, Colour4 endColour, double startTime, double endTime, in TEasing easing)
259 {
260 if (startColour == endColour)
261 return startColour;
262
263 double current = time - startTime;
264 double duration = endTime - startTime;
265
266 if (duration == 0 || current == 0)
267 return startColour;
268
269 var startLinear = startColour.ToLinear();
270 var endLinear = endColour.ToLinear();
271
272 float t = Math.Max(0, Math.Min(1, (float)easing.ApplyEasing(current / duration)));
273
274 return new Colour4(
275 startLinear.R + t * (endLinear.R - startLinear.R),
276 startLinear.G + t * (endLinear.G - startLinear.G),
277 startLinear.B + t * (endLinear.B - startLinear.B),
278 startLinear.A + t * (endLinear.A - startLinear.A)).ToSRGB();
279 }
280
281 public static byte ValueAt(double time, byte val1, byte val2, double startTime, double endTime, in TEasing easing)
282 => (byte)Math.Round(ValueAt(time, (double)val1, val2, startTime, endTime, easing));
283
284 public static sbyte ValueAt(double time, sbyte val1, sbyte val2, double startTime, double endTime, in TEasing easing)
285 => (sbyte)Math.Round(ValueAt(time, (double)val1, val2, startTime, endTime, easing));
286
287 public static short ValueAt(double time, short val1, short val2, double startTime, double endTime, in TEasing easing)
288 => (short)Math.Round(ValueAt(time, (double)val1, val2, startTime, endTime, easing));
289
290 public static ushort ValueAt(double time, ushort val1, ushort val2, double startTime, double endTime, in TEasing easing)
291 => (ushort)Math.Round(ValueAt(time, (double)val1, val2, startTime, endTime, easing));
292
293 public static int ValueAt(double time, int val1, int val2, double startTime, double endTime, in TEasing easing)
294 => (int)Math.Round(ValueAt(time, (double)val1, val2, startTime, endTime, easing));
295
296 public static uint ValueAt(double time, uint val1, uint val2, double startTime, double endTime, in TEasing easing)
297 => (uint)Math.Round(ValueAt(time, (double)val1, val2, startTime, endTime, easing));
298
299 public static long ValueAt(double time, long val1, long val2, double startTime, double endTime, in TEasing easing)
300 => (long)Math.Round(ValueAt(time, (double)val1, val2, startTime, endTime, easing));
301
302 public static ulong ValueAt(double time, ulong val1, ulong val2, double startTime, double endTime, in TEasing easing)
303 => (ulong)Math.Round(ValueAt(time, (double)val1, val2, startTime, endTime, easing));
304
305 public static float ValueAt(double time, float val1, float val2, double startTime, double endTime, in TEasing easing)
306 => (float)ValueAt(time, (double)val1, val2, startTime, endTime, easing);
307
308 public static decimal ValueAt(double time, decimal val1, decimal val2, double startTime, double endTime, in TEasing easing)
309 => (decimal)ValueAt(time, (double)val1, (double)val2, startTime, endTime, easing);
310
311 public static double ValueAt(double time, double val1, double val2, double startTime, double endTime, in TEasing easing)
312 {
313 if (val1 == val2)
314 return val1;
315
316 double current = time - startTime;
317 double duration = endTime - startTime;
318
319 if (current == 0)
320 return val1;
321 if (duration == 0)
322 return val2;
323
324 double t = easing.ApplyEasing(current / duration);
325 return val1 + t * (val2 - val1);
326 }
327
328 public static Vector2 ValueAt(double time, Vector2 val1, Vector2 val2, double startTime, double endTime, in TEasing easing)
329 {
330 float current = (float)(time - startTime);
331 float duration = (float)(endTime - startTime);
332
333 if (duration == 0 || current == 0)
334 return val1;
335
336 float t = (float)easing.ApplyEasing(current / duration);
337 return val1 + t * (val2 - val1);
338 }
339
340 public static RectangleF ValueAt(double time, RectangleF val1, RectangleF val2, double startTime, double endTime, in TEasing easing)
341 {
342 float current = (float)(time - startTime);
343 float duration = (float)(endTime - startTime);
344
345 if (duration == 0 || current == 0)
346 return val1;
347
348 float t = (float)easing.ApplyEasing(current / duration);
349
350 return new RectangleF(
351 val1.X + t * (val2.X - val1.X),
352 val1.Y + t * (val2.Y - val1.Y),
353 val1.Width + t * (val2.Width - val1.Width),
354 val1.Height + t * (val2.X - val1.Height));
355 }
356 }
357
358 private static class GenericInterpolation<TValue, TEasing>
359 where TEasing : IEasingFunction
360 {
361 public static readonly InterpolationFunc<TValue, TEasing> FUNCTION;
362
363 static GenericInterpolation()
364 {
365 const string interpolation_method = nameof(GenericInterpolation<TEasing>.ValueAt);
366
367 var parameters = typeof(InterpolationFunc<TValue, TEasing>)
368 .GetMethod(nameof(InterpolationFunc<TValue, TEasing>.Invoke))
369 ?.GetParameters().Select(p => p.ParameterType).ToArray();
370
371 MethodInfo valueAtMethod = typeof(GenericInterpolation<TEasing>).GetMethod(interpolation_method, parameters);
372
373 if (valueAtMethod != null)
374 FUNCTION = (InterpolationFunc<TValue, TEasing>)valueAtMethod.CreateDelegate(typeof(InterpolationFunc<TValue, TEasing>));
375 else
376 {
377 var typeRef = FormatterServices.GetSafeUninitializedObject(typeof(TValue)) as IInterpolable<TValue>;
378
379 if (typeRef == null)
380 throw new NotSupportedException($"Type {typeof(TValue)} has no interpolation function. Implement the interface {typeof(IInterpolable<TValue>)} interface on the object.");
381
382 FUNCTION = typeRef.ValueAt;
383 }
384 }
385 }
386 }
387
388 public delegate TValue InterpolationFunc<TValue, TEasing>(double time, TValue startValue, TValue endValue, double startTime, double endTime, in TEasing easingType) where TEasing : IEasingFunction;
389}