Poin ditempatkan secara merata di sepanjang kurva bezier

10

Saya telah melihat sekeliling untuk sementara waktu dan saya tidak dapat menemukan solusi untuk masalah ini. Katakanlah saya memiliki kurva bezier kubik (didefinisikan oleh 4 poin) dan saya ingin mendapatkan satu set poin yang berjarak merata di sepanjang kurva. Pikirkan untuk menempatkan teks di sepanjang kurva sebagai contoh.

Sekarang masalahnya adalah bahwa jika saya input t(nilai interpolasi dari 0-1) dengan kenaikan konstan titik-titiknya tidak merata spasi. Jarak di sepanjang kurva lebih kecil ketika kurva berbelok dan lebih panjang saat kurva lurus.

Jadi bagaimana cara menempatkan titik secara merata di sepanjang kurva bezier?

Foaly
sumber
4
Apakah Anda mencari solusi "murni matematika" (atau sangat efisien)? Jika tidak, pendekatan langsung adalah: Konversi kurva menjadi polyline, dengan berjalan di sepanjang kurva, meningkatkan t, katakanlah, 100 langkah, dan mengukur jarak antara titik yang dihasilkan. Kemudian, interpolasi sepanjang polyline ini seperti yang diinginkan.
Marco13
Saya pikir Anda sedang mencari kata kunci "parametrization panjang busur", yang dijawab misalnya dalam pertanyaan ini .
wondra
Apa yang dikatakan @ Marco13!
david van
Menurut jawaban / komentar, pendekatan yang saya sebutkan tidak hanya langsung, tetapi juga agak umum. Apakah ini untuk bahasa tertentu? Mungkin seseorang akan memposting beberapa baris kode kemudian ...
Marco13

Jawaban:

3

Ini lebih merupakan pertanyaan matematika. Jadi kurva bezier memiliki rumus berikut , baik dalam komponen xdan y.

B_x(t) = (1-t)^3 * P0_x + (1-t)^2 * t * P1_x + (1-t) * t^2 * P2_x + t^3 * P3_x
B_y(t) = (1-t)^3 * P0_y + (1-t)^2 * t * P1_y + (1-t) * t^2 * P2_x + t^3 * P3_y

Panjang perjalanan tsepanjang kurva gammadiberikan oleh:

length_gamma(t) = integration( sqrt( derivative(  gamma_x(s)  ) ^2 + derivative(  gamma_y(s)  ) ^2 ) )

Tidak ada solusi yang dapat ditulis manusia untuk integral, jadi Anda harus memperkirakan.

Ganti gamma(t)dengan ekspresi B(t)untuk mendapatkan panjang yang length_Bditempuh tsepanjang segmen bezier. Katakanlah itu bergerak dari 0ke L.

Sekarang pilih nnilai antara 0dan Lyang sesuai dengan poin yang berjarak sama. Misalnya, panjang formulir k*L/nuntuk kdari 0hingga n.

Sekarang Anda perlu membalik fungsi length_B, sehingga Anda dapat menghitung tkembali dari panjangnya l. Ini matematika yang cukup banyak dan saya malas sekali, coba lakukan sendiri. Jika tidak bisa, Anda bisa pergi ke pertukaran stack matematika . Untuk jawaban yang lebih lengkap, Anda bisa tetap pergi ke sana.

Setelah Anda memiliki length_Bfungsi terbalik (atau perkiraan yang masuk akal), proses Anda cukup sederhana.

  • Buat panjang l[k]jarak jalur yang diberikan jauh dari titik asal (P0_x,P1_x).
  • Hitung t[k]penggunaannya sesuai length_B_inverse.
  • Positing poin menggunakan (B_x(t[k]),B_y(t[k])).
Lærne
sumber
1
Terima kasih! Ternyata matematika yang Anda butuhkan untuk mengintegrasikan polinomial bernstein adalah mimpi buruk. Saya dapat menggunakan solusi
Foaly
0

Hanya untuk memperluas apa yang dikatakan Marco, teknik umum untuk melakukan ini adalah berjalan menyusuri kurva dengan kenaikan yang jauh lebih kecil daripada langkah-langkah panjang tetap yang ingin Anda ambil dan menyimpan titik output yang dihasilkan (dan mungkin jarak?) Dalam sebuah tabel.

Kemudian, Anda pergi melalui tabel dan membuang semua entri kecuali titik-titik yang paling dekat dengan kelipatan bilangan bulat dari jarak yang ingin Anda berjalan.

Maka Anda dibiarkan dengan tabel Anda dapat mengindeks langsung saat runtime dengan sangat cepat. Jika Anda ingin pergi ke tempat yang 5 kali ukuran jarak Anda, Anda melihat di tabel Anda di indeks [5].

Perhatikan bahwa Anda bisa melakukan dua langkah dalam satu dan tidak benar-benar menyimpan item tambahan dalam tabel untuk memulai, tetapi lebih mudah untuk memvisualisasikan dan memahami dalam dua langkah.

Saya pernah melihat teknik untuk benar-benar menghitung ini dengan cepat tanpa menghitung ulang tabel (tidak menggunakan iterasi / root juga!), Tapi sayangnya saya tidak dapat mengingat detailnya sama sekali):

Jika saya ingat atau menemukannya, saya akan memposting info!

Alan Wolfe
sumber
1
ini mungkin juga menarik bagi Anda: math.stackexchange.com/questions/15896/…
Alan Wolfe
0

Langkah 1 - Hasilkan poin N + 1 dengan menginterpolasikan kurva dengan kelipatan 1 / N. N harus cukup besar untuk hasil visual yang baik tetapi cukup kecil untuk mudah dihitung. Nilai 50 harus OK untuk sebagian besar situasi tetapi harus disesuaikan untuk kasus khusus Anda. Saya akan menyebutnya "titik interpolasi".

Atau Anda dapat membuat daftar pendek segmen dan secara rekursif memecah setiap segmen yang lebih panjang dari panjang segmen maksimum yang diinginkan (awalnya Anda harus menghasilkan setidaknya empat segmen untuk memperhitungkan kurva S di mana awal sangat dekat dengan akhir).

Langkah 2 - "Jalani garis" menggunakan titik-titik yang diinterpolasi dan jarak yang Anda inginkan di antara setiap titik.

Saya akan meninggalkannya di sini kode Persatuan saya:

public static Vector2[] InterpolateBezier(Vector2 start, Vector2 startControlPoint,
    Vector2 end, Vector2 endControlPoint, int segments)
{
    Vector2[] interpolated = new Vector2[segments + 1];
    interpolated[0] = start;
    interpolated[segments] = end;

    float step = 1f / segments;
    for (int i = 1; i < segments; i++)
    {
        interpolated[i] = GetBezierPosition(start, startControlPoint, end,
            endControlPoint, i * step);
    }

    return interpolated;
}

public static Vector2 GetBezierPosition(Vector2 start, Vector2 startControlPoint,
    Vector2 end, Vector2 endControlPoint, float t)
{
    float omt = 1f - t;
    float omt2 = omt * omt;
    float t2 = t * t;

    return
        start * (omt2 * omt) +
        startControlPoint * (3f * omt2 * t) +
        endControlPoint * (3f * omt * t2) +
        end * (t2 * t);
}

public static List<Vector2> WalkLine(Vector2[] points, float spacing, float offset = 0)
{
    List<Vector2> result = new List<Vector2>();

    spacing = spacing > 0.00001f ? spacing : 0.00001f;

    float distanceNeeded = offset;
    while (distanceNeeded < 0)
    {
        distanceNeeded += spacing;
    }

    Vector2 current = points[0];
    Vector2 next = points[1];
    int i = 1;
    int last = points.Length - 1;
    while (true)
    {
        Vector2 diff = next - current;
        float dist = diff.magnitude;

        if (dist >= distanceNeeded)
        {
            current += diff * (distanceNeeded / dist);
            result.Add(current);
            distanceNeeded = spacing;
        }
        else if (i != last)
        {
            distanceNeeded -= dist;
            current = next;
            next = points[++i];
        }
        else
        {
            break;
        }
    }

    return result;
}
Jorge Galvão
sumber
-1

Berikut ini beberapa algoritma yang memberikan hasil yang cukup baik:

  Point Index(float pos) const
  {
    int count = p.NumPoints();
    Vector val(0.0,0.0,0.0);
    for(int i=0;i<count;i++)
      { 
        val += bin(pos,i,count-1)*Vector(p.Points(i));
      }
    return Point(val);
  }
  float bin(float pos, int i, int n) const
  { 
    return float(ni(n,i)) * pow(double(pos), double(i))*pow(double(1.0-pos), double(n-i));
  }
  int ni(int n, int i) const
  {
    if (i==0) { return 1; }
    if (n==i) { return 1; }
    return ni(n-1,i-1)+ni(n-1,i);
  }
tp1
sumber