🤝 🤱🏿 🚴🏻 曲線に沿ってオブジェクトを均等に移動します 👨‍👦‍👦 🙎🏾 🍹

まったく異なるジャンルのカテゴリでゲームを開発する過程で、A市からB市に移動するトラック、狡猾な軌道に沿って発射されるミサイル、敵の飛行機など、一定または制御された速度で滑らかな曲線に沿ってゲームオブジェクトを「起動」する必要がある場合があります。敷設された操作を実行します。

おそらく、このトピックに関連するすべての人が、ベジエ曲線、Bスプライン、エルミートスプライン、その他の補間および平滑化スプラインについて知っているか、少なくとも聞いたことがあるでしょう。説明されている状況でそれらの1つを使用することを絶対に正しく提案しますが、すべてがそれほど単純なわけではありません。私たちが望むように。

この場合、スプラインは、入力パラメーター（制御点）のセットと引数の値を表示する関数です。

t

$t$ （通常は0から1までの値を取ります）平面上または空間内のポイントに。結果の曲線は、のスプライン関数の値のセットです

t \in [0, 1]

$t\in[0,1]$ ..。

例として、次の式で与えられる3次ベジエ曲線を考えてみます。

$画像$

キュービックベジエ曲線

この図は、4つのポイントで定義される2つのキュービックベジエ曲線を示しています（曲線はそのうちの2つを通過し、残りの2つは曲率を定義します）。

パラメータtをカーブポイントに表示するアニメーション

カーブセクションからより複雑で可変のルートを構築するために、それらをチェーンで接続して、1つの共通のポイントリンクを残すことができます。

ピースワイズスプライン

ルートのタスクとパラメータ化を理解したので、次にメインの質問に移ります。条件付き平面がルートに沿って一定の速度で移動するためには、この曲線に沿って移動した距離に応じて、いつでも曲線上の点を計算できる必要があります。

s (l e n)

$s(len)$ 、パラメータの値から曲線上の点の位置を計算する機能しかありませんが

t

$t$ （関数

y (t)

$y(t)$ ）。困難が始まるのはこの段階です。

私の最初の考えは線形マッピングを行うことでした

l e n \in [0, L e n g t h] \Rightarrow t \in [0, 1]

$len\in[0, Length] \Rightarrow t\in[0,1]$ 計算します

y (t)

$y(t)$ 結果の値から-簡単で、計算上安価で、一般的に、必要なもの。

この方法の問題はすぐに明らかになります-実際、カバーされた距離

s

$s$ に依存します

t

$t$ 非線形に、そしてこれを確信するためには、値によって均一に分布されたルートに沿って配置するだけで十分です

t

$t$ ポイント：

パスに沿って「均等に」分布するポイント

航空機は、一部のセクションで減速し、他のセクションで加速するため、曲線のパラメーター化のこの方法は、説明された問題の解決には完全に適用できません（平面は説明のための例としてのみ選択され、物理的に正しい方法でその動きを説明するという目標は追求されませんでした）：

曲線の誤ったパラメータ化の視覚化

検索エンジンを調べた後、stackoverflowとyoutubeで、計算する2番目の方法を見つけました

s (l e n) = g (t)

$s(len) = g(t)$ つまり、ピースワイズ線形関数の形式でのカーブの表現（カーブに沿って互いに等距離にある点のセットを計算する）：

ピースワイズ線形スプラインとしてのカーブの表現

この手順は反復的です：小さなステップが実行されます

t

$t$ 、曲線に沿って移動し、指定された距離がカバーされるまでピースワイズ線形スプラインの長さとして移動した距離を合計します。その後、ポイントが記憶され、プロセスが再開されます。

サンプルコード

public Vector2[] CalculateEvenlySpacedPoints(float spacing, float resolution = 1)
  {
    List<Vector2> evenlySpacedPoints = new List<Vector2>();
    evenlySpacedPoints.Add(points[0]);
    Vector2 previousPoint = points[0];
    float dstSinceLastEvenPoint = 0;

    for (int segmentIndex = 0; segmentIndex < NumSegments; segmentIndex++)
    {
      Vector2[] p = GetPointsInSegment(segmentIndex);
      float controlNetLength = Vector2.Distance(p[0], p[1]) + Vector2.Distance(p[1], p[2]) + Vector2.Distance(p[2], p[3]);
      float estimatedCurveLength = Vector2.Distance(p[0], p[3]) + controlNetLength / 2f;
      int divisions = Mathf.CeilToInt(estimatedCurveLength * resolution * 10);
      float t = 0;
      while (t <= 1)
      {
        t += 1f/divisions;
        Vector2 pointOnCurve = Bezier.EvaluateCubic(p[0], p[1], p[2], p[3], t);
        dstSinceLastEvenPoint += Vector2.Distance(previousPoint, pointOnCurve);

        while (dstSinceLastEvenPoint >= spacing)
        {
          float overshootDst = dstSinceLastEvenPoint - spacing;
          Vector2 newEvenlySpacedPoint = pointOnCurve + (previousPoint - pointOnCurve).normalized * overshootDst;
          evenlySpacedPoints.Add(newEvenlySpacedPoint);
          dstSinceLastEvenPoint = overshootDst;
          previousPoint = newEvenlySpacedPoint;
        }

        previousPoint = pointOnCurve;
      }
    }

    return evenlySpacedPoints.ToArray();
  }

そして、ピースワイズ線形関数でポイントを計算するのは簡単で速い問題なので、ルートを多くのセグメントに分割して、オブジェクトがどれほどスムーズかつ着実に移動するかを楽しむことができるため、問題は解決したようです。しかし、このアプローチには、私を悩ませた非常に明らかな欠点もあります。パーティションのステップまたは曲線のジオメトリを変更するためのかなりコストのかかる手順と、精度（より多くのメモリ消費）とメモリ節約（「壊れた」ルートがより顕著になる）のバランスを見つける必要があります。

その結果、私は探し続けて、優れた記事「指定された速度で曲線に沿って移動する」に出くわしました。これに基づいて、さらなる推論が行われました。

速度値は次のように計算できます

σ (t) = | V (t) | = | \frac{d X}{d t} |

$\sigma(t) = |V(t)|=|\frac{dX}{dt}|$ どこ

X (t)

$X(t)$ -スプライン機能。問題を解決するには、関数を見つける必要があります

Y (t) = X (s)

$Y(t)=X(s)$ どこ

s

$s$ -始点から目的の弧までの弧の長さ。この式により、

t

$t$ そして

s

$s$ ..。

微分変数置換を使用して、

\frac{d Y}{d t} = \frac{d X}{d s} \frac{d s}{d t} .

$\frac{dY}{dt}=\frac{dX}{ds}\frac{ds}{dt}.$

速度が負でない量であることを考慮に入れると、次のようになります。

| \frac{d Y}{d t} | = | \frac{d X}{d s} | | \frac{d s}{d t} | = \frac{d s}{d t},

$|\frac{dY}{dt}|=|\frac{dX}{ds}||\frac{ds}{dt}|=\frac{ds}{dt},$

なぜなら

| \frac{d X}{d s} | = 1

$|\frac{dX}{ds}| = 1$ 速度ベクトルの係数が変化しないという条件によって（一般的に言えば、

| \frac{d X}{d s} |

$|\frac{dX}{ds}|$ は1ではなく定数ですが、計算を簡単にするために、この定数を1に等しくします）。

今、私たちは間の比率を取得します

t

$t$ そして

s

$s$ 明示的に：

s = g (t) = \int_{0}^{t} | \frac{d Y (τ)}{d t} | d τ,

$s=g(t)=\int_{0}^{t}|\frac{dY(\tau)}{dt}|d\tau,$

曲線の全長

L

$L$ 明らかに次のように計算されます

g (1)

$g(1)$ ..。結果の式を使用して、引数の値を持つことが可能です

t

$t$ 、この値がである点までの円弧の長さを計算します

t

$t$ 表示されています。

逆の操作、つまり引数の値を計算することに関心があります

t

$t$ 与えられた弧の長さに沿って

s

$s$ ：

t = g^{- 1} (s) .

$t=g^{-1}(s).$

逆関数を見つける一般的な分析方法がないため、数値解を探す必要があります。私たちは

F (t) = g (t) - s .

$F(t)=g(t)-s.$ 与えられた

s

$s$ 、そのような値を見つける必要があります

t

$t$ これで

F (t) = 0

$F(t)=0$ ..。したがって、このタスクは、ニュートンの方法で完全に対処できる方程式の根を見つけるタスクに変わりました。

このメソッドは、次の形式の一連の近似を形成します。

t_{i + 1} = t_{i} - \frac{F (t_{i})}{F^{'} (t_{i})},

$t_{i+1}=t_i-\frac{F(t_i)}{F'(t_i)},$

どこ

F^{'} (t) = \frac{d F}{d t} = \frac{d g}{d t} = | \frac{d Y}{d t} | .

$F'(t)=\frac{dF}{dt}=\frac{dg}{dt}=|\frac{dY}{dt}|.$

計算するには

F (t)

$F(t)$ 計算する必要があります

g (t)

$g(t)$ 、その計算には、数値積分が必要です。

選択

t_{0} = \frac{s}{L}

$t_0=\frac{s}{L}$ 最初の概算が妥当に見えるようになりました（問題を解決するための最初のアプローチを思い出してください）。

次に、ソリューションエラーが許容できるようになるまで、または実行される反復回数が非常に多くなるまで、ニュートンの方法を使用して反復します。

ニュートンの標準的な方法を使用することには潜在的な問題があります。関数

F (t)

$F(t)$ -その派生物以来、減少しない

F^{'} (t) = | d Y / d t |

$F'(t)=|dY/dt|$ 非負です。二次導関数の場合

F^{″} (t) > 0

$F''(t)>0$ の場合、関数は凸型と呼ばれ、その関数に対するニュートンの方法はルートに収束することが保証されます。しかし、私たちの場合、

F^{″} (t)

$F''(t)$ ニュートンの方法が定義範囲外に収束する可能性があるため、負になる可能性があります

t \in [0, 1]

$t\in[0,1]$ ..。記事の著者は、ニュートンの方法の修正を使用することを提案しています。これは、ニュートンの方法による次の反復結果がルートの境界となる現在の間隔に該当しない場合、代わりに間隔の中央を選択します（二分法）。現在の反復での計算結果に関係なく、範囲が狭くなります。これは、メソッドがルートに収束することを意味します。

数値積分の方法を選択することは残っています-ガウス法の直交位相を使用しました。それは低コストでかなり正確な結果を提供するからです。

t（s）を計算するための機能コード

public float ArcLength(float t) => Integrate(x => TangentMagnitude(x), 0, t);

private float Parameter(float length)
{
  float t = 0 + length / ArcLength(1);
  float lowerBound = 0f; 
  float upperBound = 1f;

  for (int i = 0; i < 100; ++i)
  {
    float f = ArcLength(t) - length;

    if (Mathf.Abs(f) < 0.01f)
      break;

    float derivative = TangentMagnitude(t);
    float candidateT = t - f / derivative;

    if (f > 0)
    {
      upperBound = t;
      if (candidateT <= 0)
        t = (upperBound + lowerBound) / 2;
      else
        t = candidateT;
    }
    else
    {
      lowerBound = t;
      if (candidateT >= 1)
        t = (upperBound + lowerBound) / 2;
      else
        t = candidateT;
    }
  }
  return t;
}

数値統合機能コード

private static readonly (float, float)[] CubicQuadrature =
{(-0.7745966F, 0.5555556F), (0, 0.8888889F), (0.7745966F, 0.5555556F)};

public static float Integrate(Func<float, float> f, in float lowerBound, in float uppedBound)
{
  var sum = 0f;
  foreach (var (arg, weight) in CubicQuadrature)
  {
    var t = Mathf.Lerp(lowerBound, uppedBound, Mathf.InverseLerp(-1, 1, arg));
    sum += weight * f(t);
  }

  return sum * (upperBound - lowerBound) / 2;
}

次に、ニュートンの方法の誤差を調整し、数値積分のより正確な方法を選択できますが、実際には問題は解決されています-引数を計算するためのアルゴリズムが構築されました

t

$t$ 与えられた弧の長さのスプライン。曲線の複数のセクションを1つに結合し、一般化された計算手順を作成するには

s (t)

$s(t)$ すべてのセグメントの長さを保存し、変更されたニュートンメソッドを使用して反復手順を実行するセグメントのインデックスを事前に計算できます。

パスに沿って均等に分布するポイント

平面が均一に移動する

ようになりました。したがって、移動距離に関してスプラインをパラメータ化するいくつかの方法を検討しました。ソースとして使用した記事では、オプションとして、著者は微分方程式を数値的に解くことを提案していますが、彼自身の意見によれば、修正された方法を好みます。ニュートン：

一般に、tは微分方程式ソルバーよりも高速に計算できるため、ニュートン法のアプローチを好みます。

結論として、i5-9600Kプロセッサの1つのスレッドのスクリーンショットに示されている曲線上の点の位置を計算するための時間の表を示します。

計算数	平均時間、ミリ秒
100	0.62
1000	6.24
10000	69.01
100,000	672.81

このような計算速度により、さまざまなゲームやシミュレーションで使用できると思います。コメントで本質的に明確にし、批判することを嬉しく思います。

曲線に沿ってオブジェクトを均等に移動します

More articles: