C#/Unity3D 中的分段线性整数曲线插值

本文关键字：线性 整数 曲线 插值 分段 Unity3D | 更新日期: 2023-09-27 17:56:10

有没有一种简单有效的方法可以在 C# 中实现分段线性整数到整数曲线插值（对于 Unity3D，如果它很重要）？
详情如下：

  • 分段线性曲线表示必须随时间推移而构建。第一个插值请求是在我们拥有所有数据点之前发出的
  • 曲线严格单调
  • 第一个点始终是 （0， 0）
  • 数据点的第一个坐标也是严格单调的w.r.t到达时间，即点自然地按其第一个坐标排序。
  • 数据点不在会导致 4 字节整数溢出问题的范围内
  • 输出不必 100% 准确，因此舍入误差不是问题。

在C++，我会做这样的事情：

#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# 中做一些类似工作的事情，但没有那么简洁或高效。任何帮助将不胜感激。

编辑：我不需要更精确，并且对分段线性插值非常满意，因此更好的插值质量不是我的问题。
我正在寻找一种高效、简洁的方法来做到这一点。通过高效，我的意思是：依靠数据点自然排序的事实，以便能够使用二叉搜索来找到适当的段

C#/Unity3D 中的分段线性整数曲线插值

我会使用这个插值立方体：

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

其中a0..a3的计算方式如下：

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 = < 0.0 , 1.0 >是从p1到p2的曲线参数

这可确保位置和第一次导数是连续的 （c1）。如果你想在整数数学上做到这一点，那么只需相应地缩放ai,bi蚁t。您还可以以相同的方式根据需要添加任意数量的维度

现在您需要一些参数来遍历插值点，例如u = <0 , N-1>


p(0..N-1)控制点列表
u = 0表示起点p(0)
u = N-1 表示终点p(N-1)
P0..P3是用于插值的控制点

因此，您需要计算t并选择用于插值的点

    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即可。如果N<3则使用线性插值...或复制端点，直到N>=3

[编辑1] 线性插值法

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超出点数范围或点列表太小

相关文章：