I wrote this simple code:
public static class Bezier
{
private static Vector2 GetInterpolatedPoint(Vector2 a, Vector2 b, float t)
{
return new Vector2(a.X * (1f - t) b.X * t, a.Y * (1f - t) b.Y * t);
}
public static Vector2 GetPoint(IList<Vector2> points, float t)
{
int initialCount = points.Count;
Vector2[] buf;
while (points.Count > 2)
{
buf = new Vector2[points.Count-1];
for (int i = 0; i < points.Count - 1; i )
{
buf[i] = GetInterpolatedPoint(points[i], points[i 1], t);
}
points = buf;
}
return GetInterpolatedPoint(points[0], points[1], t);
}
}
Input:
- List of 100 random 2D points
- 0.0001f step (10 000 iterations)
Result:
- Calculated in ~1200ms.
It's too slow for my project. How can I improve this result? I need any tips for this code improvement or another way to calculate it more effective.
CodePudding user response：
With the most recent versions of C# it's possible to significantly speed this up.
You can do so in a few ways:
- Use
Span<T>andstackallocto avoid heap allocations. - Reuse that span so that only one memory allocation is needed. This requires maintaining the count of values as a separate variable.
- Specify the
Vector2parameters forgetInterpolatedPoint()asin.
Putting those together (and renaming the methods to have an Opt suffix):
public static class Bezier
{
static Vector2 getInterpolatedPointOpt(in Vector2 a, in Vector2 b, float t)
{
return new Vector2(a.X * (1f - t) b.X * t, a.Y * (1f - t) b.Y * t);
}
public static Vector2 GetPointOpt(IList<Vector2> points, float t)
{
int count = points.Count;
Span<Vector2> array = stackalloc Vector2[count]; // Not suitable for large arrays.
for (int i = 0; i < count - 1; i )
{
array[i] = getInterpolatedPointOpt(points[i], points[i 1], t);
}
while (--count > 2)
{
for (int i = 0; i < count - 1; i )
{
array[i] = getInterpolatedPointOpt(array[i], array[i 1], t);
}
}
return getInterpolatedPointOpt(array[0], array[1], t);
}
}
The separate loop for the first iteration uses the original data and the loop for the remaining iterations uses the span. This avoids copying the original data before interpolating it.
I wrote the following test code, but you should use Benchmark.Net for proper timings (this test code assumes that the original unoptimised methods are still in the class):
Random rng = new Random(123445);
Vector2[] buff = new Vector2[10000];
var sw = new Stopwatch();
for (int i = 0; i < 10; i)
{
for (int j = 0; j < buff.Length; j)
{
buff[j].X = rng.NextSingle();
buff[j].Y = rng.NextSingle();
}
sw.Restart();
Vector2 result1 = Bezier.GetPointOpt(buff, 0.0001f);
Console.WriteLine("GetPointOpt() took " sw.Elapsed.TotalMilliseconds);
sw.Restart();
Vector2 result2 = Bezier.GetPoint(buff, 0.0001f);
Console.WriteLine("GetPoint() took " sw.Elapsed.TotalMilliseconds);
Console.WriteLine(result1);
Console.WriteLine(result2);
Console.WriteLine();
}
The output (run in release mode):
GetPointOpt() took 107.5646
GetPoint() took 631.597
<0.49709368, 0.55904883>
<0.49709368, 0.55904883>
GetPointOpt() took 95.9445
GetPoint() took 502.4843
<0.5745254, 0.48695806>
<0.5745254, 0.48695806>
GetPointOpt() took 99.6847
GetPoint() took 507.7098
<0.59854025, 0.4798301>
<0.59854025, 0.4798301>
GetPointOpt() took 94.5894
GetPoint() took 480.0481
<0.4043915, 0.3434864>
<0.4043915, 0.3434864>
GetPointOpt() took 96.8213
GetPoint() took 481.8792
<0.4802326, 0.5464641>
<0.4802326, 0.5464641>
GetPointOpt() took 92.3702
GetPoint() took 478.834
<0.64281195, 0.72084826>
<0.64281195, 0.72084826>
GetPointOpt() took 109.5258
GetPoint() took 507.9398
<0.5327367, 0.6595588>
<0.5327367, 0.6595588>
GetPointOpt() took 92.3229
GetPoint() took 474.3246
<0.5084992, 0.57937586>
<0.5084992, 0.57937586>
GetPointOpt() took 107.6864
GetPoint() took 479.8337
<0.25628412, 0.6602504>
<0.25628412, 0.6602504>
GetPointOpt() took 98.2489
GetPoint() took 500.7994
<0.71759677, 0.50711>
<0.71759677, 0.50711>
This optimised code runs approximately five times faster.
Addendum 1: Benchmark.NET test code:
public class UnderTest
{
public UnderTest()
{
for (int j = 0; j < _buff.Length; j)
{
_buff[j].X = _rng.NextSingle();
_buff[j].Y = _rng.NextSingle();
}
}
[Benchmark(Baseline = true)]
public void Unoptimised()
{
Bezier.GetPoint(_buff, 0.0001f);
}
[Benchmark]
public void Optimised()
{
Bezier.GetPointOpt(_buff, 0.0001f);
}
readonly Random _rng = new Random(123445);
readonly Vector2[] _buff = new Vector2[10000];
}
Results:
| Method | Mean | Error | StdDev | Median | Ratio | RatioSD |
|------------ |---------:|---------:|---------:|---------:|------:|--------:|
| Unoptimised | 459.6 ms | 11.03 ms | 32.35 ms | 451.0 ms | 1.00 | 0.00 |
| Optimised | 106.8 ms | 2.13 ms | 3.79 ms | 106.5 ms | 0.22 | 0.02 |
Addendum 2: Write the getInterpolatedPoint() method inline.
It looks like this:
public static Vector2 GetPointOpt(IList<Vector2> points, float t)
{
int count = points.Count;
Span<Vector2> array = stackalloc Vector2[count]; // Not suitable for large arrays.
for (int i = 0; i < count - 1; i )
{
array[i].X = points[i].X * (1f - t) points[i 1].X * t;
array[i].Y = points[i].Y * (1f - t) points[i 1].Y * t;
}
while (--count > 2)
{
for (int i = 0; i < count - 1; i )
{
array[i].X = array[i].X * (1f - t) array[i 1].X * t;
array[i].Y = array[i].Y * (1f - t) array[i 1].Y * t;
}
}
return new Vector2(
array[0].X * (1f - t) array[1].X * t,
array[0].Y * (1f - t) array[1].Y * t);
}
However, the improvement from writing this inline is very marginal, which probably speaks to the effectiveness of the JIT compiler, which is likely already inlining the getInterpolatedPoint() method.
Results:
| Method | Mean | Error | StdDev | Ratio |
|------------ |----------:|---------:|----------:|------:|
| Unoptimised | 437.18 ms | 8.635 ms | 13.186 ms | 1.00 |
| Optimised | 77.90 ms | 1.546 ms | 3.735 ms | 0.18 |
The ratio is 0.18 rather than 0.22 - a marginal improvement of around 20% faster than calling getInterpolatedPoint().
CodePudding user response：
I actually have no idea about the theory of calculating Bezier curves, so I'm just assuming your math is correct, the way you are doing it. But it seems like your whole calculation can be done inplace instead of always creating new arrays. Ie, create a copy of your list first, and then work on this copy, considering one element less in each iteration, until you are down to only 2 elements ...
public static class Bezier
{
private static Vector2 GetInterpolatedPoint(Vector2 a, Vector2 b, float t)
{
return new Vector2(a.X * (1f - t) b.X * t, a.Y * (1f - t) b.Y * t);
}
public static Vector2 GetPoint(IList<Vector2> points, float t)
{
//Make a SHALLOW copy of your list
var copy = points.ToList();
for (int upper = copy.Count; upper > 2; upper--)
{
for (int i = 0; i < upper - 1; i )
{
copy[i] = GetInterpolatedPoint(copy[i], copy[i 1], t);
}
}
return GetInterpolatedPoint(copy[0], copy[1], t);
}
}
And if you want to reduce the number of created Vector2 objects, you could even refactor you GetInterpolatedPoint to manipulate one of the given vectors instead of returing a new one. But this may considered bad style ... Of course for this, you would also need to create a DEEP COPY of your initial list of points.
public static class Bezier
{
private static void GetInterpolatedPoint(Vector2 a, Vector2 b, float t)
{
a.X = a.X * (1f - t) b.X * t;
a.Y = a.Y * (1f - t) b.Y * t
}
public static Vector2 GetPoint(IList<Vector2> points, float t)
{
//make a DEEP copy of your list (ie copy all Vectors)
var copy = points.Select(x => new Vector2(x.X, x.Y)).ToList();
for (int upper = copy.Count; upper > 2; upper--)
{
for (int i = 0; i < upper - 1; i )
{
GetInterpolatedPoint(copy[i], copy[i 1], t);
}
}
GetInterpolatedPoint(copy[0], copy[1], t);
return copy[0];
}
}