Use a binary search to find the relevant point index in animations

[Nyrio]

A linear search is currently used to find the relevant point index in animations. This cost might be a bottleneck with long animations (and many of the existing modcharts have pretty long animations). You could use a binary search to make this cost logarithmic wrt the list size instead of linear.

Example (disclaimer: not compiled nor tested):

public Vector3 Interpolate(float time)
{
    if (_points == null || _points.Count == 0)
        return _vectorZero;
    if(_points.First().Point.w >= time)
        return _points.First().Point;
    if(_points.Last().Point.w <= time)
        return _points.Last().Point;

    int l = 0, r = _points.Count;
    while(l < r - 1) {
        int m = (l + r) / 2;
        if(_points[m].Point.w < time)
            l = m;
        else
            r = m;
    }

    float normalTime = (time - _points[l].Point.w) / (_points[r].Point.w - _points[l].Point.w);
    normalTime = Easings.Interpolate(normalTime, _points[r].Easing);
    if (_points[r].Smooth)
        return SmoothVectorLerp(_points, l, r, normalTime);
    else
        return Vector3.LerpUnclamped(_points[l].Point, _points[r].Point, normalTime);
}

[Nyrio]

Also, just from a code-cleanliness point of view, you can make the search a separate function that you call in the different interpolation functions since they have that part in common. Only what you do with the indices is different and this should happen after the loop like in my code sample above.

[Aeroluna]

Commit https://github.com/Aeroluna/NoodleExtensions/commit/33a2a8bb78ff9649bf64ec4509394d594ea9ad39 should hopefully implement this.