👨🏽‍⚖️ 🚴 🕚 Pindahkan objek secara merata di sepanjang kurva 👨🏽‍🏫 🚌 🏩

Dalam proses mengembangkan game dalam kategori genre yang sama sekali berbeda, mungkin perlu "meluncurkan" objek game apa pun di sepanjang kurva yang mulus dengan kecepatan konstan atau terkontrol, baik itu truk yang bergerak dari kota A ke kota B, rudal yang ditembakkan di sepanjang lintasan yang licik, atau pesawat musuh melakukan manuver yang sudah ditentukan.

Mungkin, semua orang yang terkait dengan topik tersebut mengetahui atau setidaknya mendengar tentang kurva Bézier, B-splines, Hermite splines, dan interpolasi lainnya serta splines smoothing dan akan benar-benar menyarankan penggunaan salah satu dari mereka dalam situasi yang dijelaskan, tetapi tidak semuanya sesederhana itu seperti yang kami inginkan.

Dalam kasus kami, spline adalah fungsi yang menampilkan sekumpulan parameter input (titik kontrol) dan nilai argumen

t

$t$ (biasanya mengambil nilai dari 0 hingga 1) ke suatu titik di bidang atau di luar angkasa. Kurva yang dihasilkan adalah himpunan nilai dari fungsi spline untuk

t \in [0, 1]

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

Sebagai contoh, perhatikan kurva Bezier kubik , yang diberikan oleh persamaan berikut:

$gambar$

Kurva Kubik Bezier

Gambar menunjukkan dua kurva Bezier kubik, yang ditentukan oleh empat titik (kurva melewati dua di antaranya, dua sisanya menentukan kelengkungan).

gambar

Animasi menampilkan parameter t ke titik kurva

Untuk membangun rute yang lebih kompleks dan variabel dari bagian kurva, mereka dapat dihubungkan dalam sebuah rantai, menyisakan satu titik-link yang sama:

Sedikit spline Kita telah

menemukan tugas dan parameterisasi rute, sekarang kita beralih ke pertanyaan utama. Agar bidang konvensional kita bergerak di sepanjang rute dengan kecepatan konstan, setiap saat kita perlu menghitung titik pada kurva yang bergantung pada jarak yang ditempuh sepanjang kurva ini.

s (l e n)

$s(len)$ , sementara hanya memiliki kemampuan untuk menghitung posisi titik pada kurva dari nilai parameter

t

$t$ (fungsi

y (t)

$y(t)$ ). Pada tahap inilah kesulitan dimulai.

Pikiran pertama saya adalah melakukan pemetaan linier

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]$ dan menghitung

y (t)

$y(t)$ dari nilai yang dihasilkan - mudah, murah secara komputasi, secara umum, apa yang Anda butuhkan.

gambar

Masalah dengan metode ini segera terlihat - pada kenyataannya, jarak yang ditempuh

s

$s$ tergantung pada

t

$t$ secara nonlinier, dan untuk diyakinkan akan hal ini, cukup mengatur sepanjang rute yang didistribusikan secara seragam berdasarkan nilai

t

$t$ poin: titik yang

"merata" didistribusikan di sepanjang jalur

Bidang akan melambat di beberapa bagian dan dipercepat di bagian lain, yang membuat metode parameterisasi kurva ini sama sekali tidak dapat diterapkan untuk menyelesaikan masalah yang dijelaskan (bidang dipilih secara eksklusif sebagai contoh ilustratif dan tujuan untuk menjelaskan pergerakannya dengan cara yang benar secara fisik tidak dikejar ):

Visualisasi parameterisasi kurva yang salah

Setelah berkonsultasi dengan mesin pencari, di stackoverflow dan youtube , saya menemukan cara kedua untuk menghitung

s (l e n) = g (t)

$s(len) = g(t)$ , yaitu, representasi kurva dalam bentuk fungsi linier-sepotong (menghitung sekumpulan titik yang berjarak sama satu sama lain di sepanjang kurva):

Mewakili kurva dalam bentuk spline linier sepotong-sepotong

Prosedur ini berulang: sebuah langkah kecil dilakukan

t

$t$ , kita bergerak sepanjang kurva dengannya, menjumlahkan jarak yang ditempuh sebagai panjang spline linier sepotong-sepotong sampai jarak yang ditentukan tercapai, setelah itu titik diingat dan proses dilanjutkan.

Kode sampel

Sumber

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();
  }

Dan, tampaknya, masalahnya terpecahkan, karena Anda dapat membagi rute menjadi banyak segmen dan menikmati betapa mulus dan mantapnya objek bergerak, karena menghitung titik pada fungsi linier sepotong-sepotong adalah hal yang sederhana dan cepat. Namun pendekatan ini juga memiliki kelemahan yang cukup jelas yang menghantui saya - prosedur yang agak mahal untuk mengubah langkah partisi atau geometri kurva dan kebutuhan untuk menemukan keseimbangan antara akurasi (konsumsi memori lebih banyak) dan penghematan memori (rute "rusak" menjadi lebih terlihat).

Hasilnya, saya terus mencari dan menemukan artikel yang sangat bagus "Bergerak Sepanjang Kurva dengan Kecepatan Tertentu" , yang menjadi dasar penalaran lebih lanjut.

Nilai kecepatan dapat dihitung sebagai

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

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

X (t)

$X(t)$ - fungsi spline. Untuk mengatasi masalah tersebut, Anda perlu mencari fungsinya

Y (t) = X (s)

$Y(t)=X(s)$ dimana

s

$s$ - panjang busur dari titik awal ke titik yang diinginkan, dan ekspresi ini menetapkan hubungan antara

t

$t$ dan

s

$s$ ...

Dengan menggunakan substitusi variabel diferensiasi, kita dapat menulis

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

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

Dengan mempertimbangkan bahwa kecepatan adalah kuantitas non-negatif, kami memperolehnya

| \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},$

karena

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

$|\frac{dX}{ds}| = 1$ dengan kondisi bahwa modulus vektor kecepatan tetap tidak berubah (secara umum,

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

$|\frac{dX}{ds}|$ tidak sama dengan satu, tetapi dengan konstanta, tetapi untuk kesederhanaan perhitungan, kita akan menganggap konstanta ini sama dengan satu).

Sekarang kita mendapatkan rasio antara

t

$t$ dan

s

$s$ secara eksplisit:

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

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

darimana total panjang kurva

L

$L$ jelas dihitung sebagai

g (1)

$g(1)$ ... Menggunakan rumus yang dihasilkan, dimungkinkan, memiliki nilai argumen

t

$t$ , hitung panjang busur ke titik di mana nilai ini berada

t

$t$ ditampilkan.

Kami tertarik dengan operasi kebalikannya, yaitu menghitung nilai argumen

t

$t$ sepanjang busur tertentu

s

$s$ :

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

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

Karena tidak ada cara analitik umum untuk mencari fungsi invers, Anda harus mencari solusi numerik. Kami menunjukkan

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

$F(t)=g(t)-s.$ Untuk diberikan

s

$s$ , diperlukan untuk menemukan nilai seperti itu

t

$t$ di mana

F (t) = 0

$F(t)=0$ ... Jadi, tugas berubah menjadi tugas menemukan akar persamaan, yang dapat diatasi dengan sempurna oleh metode Newton.

Metode tersebut membentuk urutan perkiraan bentuk

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

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

Dimana

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}|.$

Menghitung

F (t)

$F(t)$ perlu menghitung

g (t)

$g(t)$ , yang perhitungannya, pada gilirannya, membutuhkan integrasi numerik.

Pilihan

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

$t_0=\frac{s}{L}$ sebagai perkiraan awal sekarang terlihat masuk akal (ingat pendekatan pertama untuk memecahkan masalah).

Selanjutnya, kita mengulangi menggunakan metode Newton sampai kesalahan solusi diterima, atau jumlah iterasi yang dilakukan sangat besar.

Ada masalah potensial dengan menggunakan metode Newton standar. Fungsi

F (t)

$F(t)$ - tidak menurun, karena turunannya

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

$F'(t)=|dY/dt|$ tidak negatif. Jika turunan keduanya

F^{″} (t) > 0

$F''(t)>0$ , maka fungsinya disebut konveks dan metode Newton di atasnya dijamin konvergen ke akar. Namun, dalam kasus kami,

F^{″} (t)

$F''(t)$ dapat berubah menjadi negatif, karena metode Newton dapat bertemu di luar rentang definisi

t \in [0, 1]

$t\in[0,1]$ ... Penulis artikel mengusulkan untuk menggunakan modifikasi metode Newton, yang, jika hasil iterasi berikutnya dengan metode Newton tidak termasuk dalam interval saat ini yang membatasi akar, maka akan memilih tengah interval ( metode dikotomi ). Terlepas dari hasil kalkulasi pada iterasi saat ini, kisarannya menyempit, yang berarti metode konvergen ke akar.

Tetap memilih metode integrasi numerik - Saya menggunakan kuadrat dari metode Gauss , karena memberikan hasil yang cukup akurat dengan biaya rendah.

Kode fungsi untuk menghitung 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;
}

Kode Fungsi Integrasi Numerik

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;
}

Selanjutnya, Anda dapat menyesuaikan kesalahan metode Newton, memilih metode integrasi numerik yang lebih akurat, tetapi masalahnya, pada kenyataannya, telah terpecahkan - sebuah algoritma untuk menghitung argumen dibangun

t

$t$ spline untuk panjang busur tertentu. Untuk menggabungkan beberapa bagian kurva menjadi satu dan menulis prosedur penghitungan umum

s (t)

$s(t)$ Anda dapat menyimpan panjang semua segmen dan menghitung sebelumnya indeks segmen tempat Anda ingin melakukan prosedur iteratif menggunakan metode Newton yang dimodifikasi.

Titik-titik terdistribusi merata di sepanjang jalur

Sekarang bidang bergerak secara seragam

Dengan demikian, kami telah mempertimbangkan beberapa cara untuk membuat parameter spline relatif terhadap jarak yang ditempuh, dalam artikel yang saya gunakan sebagai sumber, penulis menyarankan penyelesaian persamaan diferensial secara numerik sebagai opsi, tetapi, menurut komentarnya sendiri, lebih memilih metode yang dimodifikasi Newton:

Saya lebih suka pendekatan metode Newton karena umumnya t dapat dihitung lebih cepat daripada dengan pemecah persamaan diferensial.

Sebagai kesimpulan, saya akan memberikan tabel waktu untuk menghitung posisi titik pada kurva yang ditunjukkan pada tangkapan layar dalam satu utas pada prosesor i5-9600K:

Jumlah perhitungan	Waktu rata-rata, ms
100	0.62
1000	6.24
10000	69.01
100.000	672.81

Saya percaya bahwa kecepatan komputasi seperti itu memungkinkan untuk menggunakannya dalam berbagai game dan simulasi. Saya akan dengan senang hati mengklarifikasi dan mengkritik pada intinya di komentar.

Pindahkan objek secara merata di sepanjang kurva

More articles: