Jak określić długość ścieżki?

Mam grę, która wymaga, aby każdy gracz poruszał się jedną określoną ścieżką. Rysuję ścieżkę za pomocą krzywych Béziera. Jak mogę określić całkowitą rzeczywistą (nieliniową) długość ścieżki i odległość, jaką pokonał każdy gracz? (Odległość między punktem początkowym a określonym punktem na ścieżce).

AKTUALIZACJA:

Ścieżka jest reprezentowana w płaszczyźnie kartezjańskiej (2D).

Jak powiedzieli poprzednie odpowiedzi, obliczenie długości krzywej Beziera jest trudne ( niemożliwe ?). Powiedziałbym, że 100% gier wykorzystuje przybliżoną długość, która jest prawie zawsze wystarczająco dokładna.

Kilka miesięcy temu wdrożyłem go, stosując proponowane podejście polegające na podzieleniu krzywej na „małe” segmenty i dodaniu ich długości. Jest przykładem realizacji C ++ tutaj .

Pomiar długości krzywej Beziera jest trudny. Jeśli nie przeszkadza ci niewielka niedokładność, prostym rozwiązaniem byłoby przybliżenie krzywych Beziera liniami prostymi i obliczenie sumy długości linii. Im więcej segmentów utworzysz, tym lepsze zbliżenie.

Parametryzacja długości splajnu wyższego rzędu (tj. Większego niż 1 rząd) musi być aproksymowana; nie można go przedstawić bezpośrednio, stąd fakt, że nie jest łatwo znaleźć bezpośrednie rozwiązanie tego problemu.

Niektóre istniejące implementacje (kod kopiuj-wklej):

Stosując przybliżenia Czebyszewa , według autorów, dokładność rośnie wraz ze wzrostem wielkości krzywej. Spójrz na pseudokod pp. 7-8, reszta to opis innych algorytmów, na których oparli swoje podejście, które możesz zignorować. Wiele odnośników online określa tę metodę jako dobrą.

Zobacz także te zwięzłe podejścia.

Zaczęło się to jako komentarz do komentarza do odpowiedzi @ bummzack, ale stało się zbyt długie.

jak mogę określić, ile segmentów powinienem mieć

Istnieją dwa podejścia. Pierwszy to tylko standardowy algorytm renderowania krzywej Béziera: punkty kontrolne tworzą obwiednię krzywej, więc jeśli wszystkie punkty kontrolne znajdują się w epsilon odcinka linii od punktu początkowego do punktu końcowego, przybliżamy go jako linię; w przeciwnym razie dzielisz za pomocą algorytmu de Casteljau. Epsilon jest wybierany zgodnie z błędem, jaki chcesz uzyskać w wyniku końcowym. (Do renderowania jest to zwykle 0,5 piksela).

Drugim podejściem jest udoskonalenie tego przy użyciu arytmetyki przedziałowej. Weź długość linii od początku do końca jako dolną granicę, a sumę długości linii przechodzących przez punkty kontrolne jako górną granicę. Ponownie podziel według wymagań ostatecznych błędów.

Zwykle dzieli się na t = 0,5, ale algorytm de Casteljau pozwala na podział w dowolnym punkcie, więc jeśli masz sześcienny Bézier z punktami kontrolnymi od C_0 do C_3, a C_2 jest znacznie bliżej segmentu linii między punktami końcowymi niż C_1, możesz zauważyć, że podział jeden z 1/3 lub 2/3 daje mocniejsze granice. Nie analizowałem algebry, aby uzasadnić, która opcja byłaby lepsza, ale możesz eksperymentować i składać raporty, jeśli chcesz. Jeśli nic więcej, chciałem zaznaczyć, że istnieje taka opcja.

Obliczenia długości sparametryzowanej krzywej można dokonać, biorąc całkę z sqrt ((dx / dt) ² + (dy / dt) ²), gdzie dx / dt jest pochodną składowej x krzywej i dy / dt jest pochodną składowej y krzywej. W przypadku splajnu Béziera te dwa są takie same, ponieważ równanie można rozszerzyć na dowolny wymiar.

Wzór na sześcienną splajn Béziera jest następujący: B (t) = (1 - t³) * P0 + 3 (1 - t) ²t * P1 + 3 (1 - t) t² * P2 + t³ P3 gdzie P0 do P3 to punkty kontrolne.

Według Wolfram | Alpha pochodna tego wzoru to: d (B (t)) / dt = 3 (t (t (P3 - P0) + P2 (2 - 3t) + P1 (3t² - 4t + 1))

Teraz możesz umieścić to z powrotem w równaniu długości krzywej i obliczyć całkę od t = 0 do t = 1. Niestety, Wolfram | Alpha przekroczył limit czasu, gdy próbuję to zrobić. Możesz jednak dokonać integracji numerycznej.