Integer linear integral interpolation curve in C # / Unity3D

Question

Is there a simple and efficient way to implement piecewise linear integer curve interpolation in C # (for Unity3D, if that matters)?
Details:

• A piecewise linear representation of the curve should be built over time. The first interpolation request comes before we have all the data points.
• The curve is strictly monotonous
• The first point is always (0, 0)
• The first coordinates of the data points are also strictly monotonic arrival times wrt, i.e. points are naturally ordered by their first coordinate.
• Data points are not in ranges that can cause cause overflow problems for 4-byte integers.
• The output does not have to be 100% accurate, so rounding errors are not a problem.

In C ++, I would do something like this:

#include <algorithm> #include <vector> #include <cassert> using namespace std; typedef pair<int, int> tDataPoint; typedef vector<tDataPoint> tPLC; void appendData(tPLC& curve, const tDataPoint& point) { assert(curve.empty() || curve.back().first < point.first); curve.push_back(point); } int interpolate(const tPLC& curve, int cursor) { assert(!curve.empty()); int result = 0; // below zero, the value is a constant 0 if (cursor > 0) { // find the first data point above the cursor const auto upper = upper_bound(begin(curve), end(curve), cursor); // above the last data point, the value is a constant 0 if (upper == end(curve)) { result = curve.back().second; } else { // get the point below or equal to the cursor const auto lower = upper - 1; // lerp between float linear = float((cursor - lower.first) * (upper.second - lower.second)) / (upper.first - lower.first); result = lower.second + int(linear); } } return result; } 

I can see how I could do something like this in C #, but nothing more concise or efficient. Any help would be appreciated.

EDIT: I don't need to be more precise, and I'm happy with piecewise linear interpolation, so the best quality of the interpolation is not my problem here.
What I'm looking for is an efficient and concise way to do this. By effective, I mean things like: relying on the fact that data points are naturally ordered to be able to use binary search to find the right segment

Answer 1

I would use this interpolation cube:

 x=a0+a1*t+a2*t*t+a3*t*t*t y=b0+b1*t+b2*t*t+b3*t*t*t 

where a0..a3 are calculated as follows:

 d1=0.5*(p2.x-p0.x); d2=0.5*(p3.x-p1.x); a0=p1.x; a1=d1; a2=(3.0*(p2.x-p1.x))-(2.0*d1)-d2; a3=d1+d2+(2.0*(-p2.x+p1.x)); 

b0 .. b3 are calculated in the same way, but use y coordinates, of course
p0..p3 - control points for the cubic interpolation curve
t = < 0.0 , 1.0 > - parameter of the curve from p1 to p2

This ensures that the position and the first output are continuous (c1). If you want to do this in integer math, then just scale ai,bi ant t . You can also add as many dimensions as you need, in the same way.

Now you need some kind of parameter to go through your interpolation points, for example u = <0 , N-1>

p(0..N-1) - list of control points
u = 0 means the starting point p(0)
u = N-1 means the endpoint p(N-1)
p0..p3 - control points used for interpolation

So, you need to calculate t and choose which points to use for interpolation

  double t=u-floor(u); // fractional part between control points int i=floor(u); // integer part points to starting control point used if (i<1) { P0=p( 0),P1=p( 0),P2=p( 1),P3=p( 2); } // handle start edge case else if (i==N-1) { P0=p(N-2),P1=p(N-1),P2=p(N-1),P3=p(N-1); } // handle end edge case else if (i>=N-2) { P0=p(N-3),P1=p(N-2),P2=p(N-1),P3=p(N-1); } // handle end edge case else { P0=p(i-1),P1=p(i ),P2=p(i+1),P3=p(i+2); } (x,y) = interpolation (P0,P1,P2,P3,t); 

If you want to do this on integer math, then just scale u,t accordingly. If N<3 , then use linear interpolation ... or duplicate the end points to N>=3

[edit1] linear interpolation method

 struct pnt { int x,y; }; pnt interpolate (pnt *p,int N,int x) { int i,j; pnt p; for (j=1,i=N-1;j<i;j<<=1); j>>=1; if (!j) j=1; // this just determine max mask for binary search ... can do it on p[] size change for (i=0;j;j>>=1) // binary search by x coordinate output is i as point index with p[i].x<=x { i|=j; if (i>=N) { i-=j; continue; } if (p[i].x==x) break; if (p[i].x> x) i-=j; } px=x; py=p[i].y+((p[i+1].yp[i].y)*(xp[i].x)/(p[i+1].xp[i].x)) return p; } 

add edge processing, for example x , does not match the points or the list of points is too small