在C＃分段线性整数曲线插补/ Unity3D [英] Piecewise linear integer curve interpolation in C#/Unity3D
问题描述
有没有C＃实现分段线性整数到整数曲线插补一个简单，有效的方法（适用于Unity3D，如果它的事项）结果
详情如下：
Is there a simple, efficient way to implement a piecewise linear integer-to-integer curve interpolation in C# (for Unity3D, if it matters) ?
Details are as follows:
- 分段线性曲线，表示有一段时间待建。第一插值请求到来之前，我们拥有所有的数据点
- 的曲线是严格单调
- 第一点总是（0,0）
- 数据点的第一个坐标，也是严格单调WRT到达时间，即点自然是他们的第一个坐标排序。
- 的数据点都没有在范围内，将导致为4字节的整数原因溢出问题
- 输出不一定100％准确，所以舍入误差是不是一个问题。
- The piecewise linear curve representation has to be built over time. The first interpolation request comes before we have all data points
- The curve is strictly monotonous
- The first point is always (0, 0)
- The data points' first coordinates are also strictly monotonous w.r.t arrival time, i.e. the points are naturally ordered by their first coordinate.
- The data points are not in ranges that would cause cause overflow problems for 4-byte integers
- The output does not have to be 100% accurate, so rounding errors are not an issue.
在C ++中，我会做这样的事情：
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;
}
我可以看到我怎么能做到这一点在C＃这样的工作类的东西，但没有简练或有效。 。任何帮助将不胜感激。
I can see how I could do something that work sort of like this in C#, but nothing as concise or efficient. Any help will be appreciated.
编辑：
我并不需要更准确，我与分段线性插值非常高兴，所以更好的插值质量不是我这里的问题。结果
我所寻找的是这样的一种高效，简洁的方法。通过高效的，我的意思是这样的话：依靠事实，数据点自然下令能够使用二进制搜索找到合适的段
I do not need to be more accurate, and am perfectly happy with piecewise linear interpolation, so better interpolation quality is not my problem here.
What I am looking for is an efficient, concise way of doing this. By efficient, I mean things like: relying on the fact that the data points are naturally ordered to be able to use binary search to find the proper segment
推荐答案
我会用这个插值立方：
x=a0+a1*t+a2*t*t+a3*t*t*t
y=b0+b1*t+b2*t*t+b3*t*t*t
其中a0..a3计算是这样的：
where a0..a3 are computed like this:
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计算的方式相同，但使用Y坐标当然
- p0..p3是三次插值曲线
- T = LT控制点; 0.0，1.0>是曲线参数P1到P2的
- 这确保了位置和一阶导数是连续的（C1）
- 当你要做到这一点的整数运算然后就扩展AI，双蚁牛逼相应
- 您也可以为你以同样的方式需要 $添加尽可能多维度b $ b
- b0 .. b3 are computed in same way but use y coordinates of course
- p0..p3 are control points for cubic interpolation curve
- t = < 0.0 , 1.0 > is curve parameter from p1 to p2
- this ensures that position and first derivation is continuous (c1)
- when you want to do this on integer math then just scale ai,bi ant t accordingly
- you can also add as many dimensions as you need in the same manner
- p（0..N-1）控制点列表
- U = 0表示启动点p（0）
- U = N-1表示终点p（N-1）
- P0..P3用于控制点插
-
所以你需要计算T和指向用于插
- p(0..N-1) are your control points list
- u = 0 means start point p(0)
- u = N-1 means end point p(N-1)
- P0..P3 are control points used for interpolation
so you need to compute t and which points to use for interpolation
现在你需要一些参数，通过你的插值点，例如 U =℃下，N-1>
Now you need some parameter to go through your interpolation points for example u = <0 , N-1>
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);
当你想要做这个整数运算然后就扩展U，T因此
线性插值方法
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;
}
p.x=x;
p.y=p[i].y+((p[i+1].y-p[i].y)*(x-p[i].x)/(p[i+1].x-p[i].x))
return p;
}
- 添加边缘情况处理...
- 如x是出于必然或点列表太小了点
这篇关于在C＃分段线性整数曲线插补/ Unity3D的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
