Super szybki algorytm na długości krzywych Beziera

[HTD]

Może się komuś przyda, tysiące razy szybszy od używanego w MaSzynie:

Źródła:
https://github.com/HTD/FastBezier

Demo:
http://nisza.org/dl/FastBezier.7z

(Demo wymaga .NET 3.5, więc pójdzie na XP pod x86) ;)

Pozdrówka i Wesołych Świąt wszystkim, ho, ho, ho! ;)

Opis działania:

Na szybko, wykorzystujemy fakt, że dla krzywych Beziera 2-go stopnia długość da się policzyć z całki, czyli bez żadnych iteracji, praktycznie natychmiast. Potrzebne wzory znalazłem w internetach :) Dalej wykorzystujemy fakt, że krzywe Beziera 3-go stopnia dla torów dają się praktycznie idealnie przybliżyć krzywymi 2-go stopnia. Bo na krzywe wyższego stopnia niż 2 nie ma normalnych wzorów obliczeniowych. OK, a gdyby ten jeden szczególny tor miał "dziwną geometrię"? Na to jest bardzo sprytny sposób. Wystarczy podzielić naszą krzywą na segmenty, które dają się przybliżyć z wystarczającą precyzją, następnie obliczyć długości tych segmentów i zsumować. Cały trick to wyznaczenie ile segmentów potrzeba dla uzyskania zadanej precyzji. W przypadku toru na którym to testowałem - w ogóle nie potrzeba segmentów. Przynajmniej, jeśli zadowala nas precyzja 1ppm, absolutnie nieosiągalna metodą interpolacji odcinkami. Na mojej maszynie kod testowy wyciąga około 2 milionów takich obliczeń w ciągu sekundy. Popularny algorytm z interpolacją odcinkami daje radę tylko około 3 tysięcy. Przesadziłem z tym "tysiące razy szybszy"? Bynajmniej. W MaSzynie precyzja interpolacji jest ustawiona na mniej więcej 5cm. W interpolacji krzywą 2-go stopnia precyzja przekracza 1ppm, czyli długość liczona jest z dokładnością do mikronów ;)

[Wiggle]

Osobiście krzywych Beziera używam przy grafice wektorowej, kiedy to nie koniecznie łatwiej, ale za to w idealny sposób, np. obrysować jakiś obrazek czy coś :) Myślę, że wykorzystanie tego w naszym symulatorze byłoby ciekawym rozwiązaniem, bo w przypadku tworzenia torowiska byłoby znacznie łatwiej niż jest teraz ;)
Pozdrawiam :)

[youBy]

Byłoby? Torowisko w MaSzynie jest na krzywych bezziera od kilkunastu lat.

[HTD]

Jeśli liczenie długości lub inne interpolacje w MaSzynie mogłyby zyskać na wydajności, mogę przepisać to w C++. Jeśli nie, zawsze przyda się do obliczania pozycji składu znając tory pomiędzy punktem A i B (to było głównym celem). BTW, autor wzoru całkowego to kopalnia wiedzy o geometrii. Na jego stronie jest cała masa wypasionych algorytmów. Polecam linki w źródłach, można się dowiedzieć sporo o krzywych Beziera, a nawet o innych sklejanych.

[Sumer]

Narzędzie, które chciałbym stworzyć służyłoby także do prowadzenia misji, a więc zawierałoby także wszelkie narzędzia, które teraz realizuje się za pomocą eventów tylko w prostszy sposób. Nie da się zrobić w zasadzie VD bez posiadania rozkładu jazdy, a jak już i tak to trzeba zrobić to samą mechanikę można zdecydowanie rozbudować. Do tego byłoby to przygotowanie do zrobienia multiplayera z prawdziwego zdarzenia, który obsługiwałby nie tylko samą kwestię prowadzenia pociągu przez poszczególne osoby ale także może być połączony z symulacją sterowania ruchem.

[firleju]

Jak chcesz się dołączyć przyjmę chętne osoby współpracy w tym temacie.

[ShaXbee]

@HTD: potrzebuje nastepujacych algorytmow:

• znajdz punkt na krzywej w pozycji t o zakresie 0.0 - 1.0
• znajdz punkt na krzywej w odleglosci x w linii prostej od punktu w pozycji t

[HTD]

Poszukam jak znajdę chwilę czasu, chociaż pierwszy wzór masz w tym źródle co podlinkowałem, drugi jest w edytorze, chociaż nie mam pewności czy wrzuciłem ten drugi na Git-a.
Rozumiem, że w drugim przypadku chodzi o minimalną odległość punktu od krzywej?

[muri]

Ja pkt drugi rozumiem tak jak w załączniku. Ale pierwszego to wcale ;(

[Ra]

Przepraszam, że się wtrącam, ale obliczanie ruchu na krzywych Béziera jest zasadniczo zbędne dla symulacji. Linie kolejowe buduje się z odcinków prostych, łuków kołowych oraz krzywych przejściowych. Krzywe przejściowe można sprowadzić do równania y=x³, dla którego można utworzyć odpowiednie funkcje szczególne z funkcji elementarnych, unikając algorytmów iteracyjnych. Symulacja bardziej zaawansowanych krzywych przejściowych (klotoida, krzywa Blossa, krzywa Kleina) będzie raczej marginalna, bo raczej ma wpływ na żywotność taboru niż wrażenia z jazdy. Ewentualnie dla tych krzywych też można utworzyć pochodne funkcje szczególne. W profilu pionowym używa się odcinków prostych oraz łuków o dużych promieniach (5km, 10km, 20km). Drogi buduje się na podobnych zasadach. Jazda po krzywych Béziera byłaby potrzebna do obecnych scenerii, na których te krzywe występują. Jednak po doprowadzeniu torów do stanu zgodnego z inżynierią kolejową, krzywych Béziera być nie powinno i lepiej się skupić na jakimś bardziej istotnym zagadnieniu.

[ShaXbee]

@Ra: i rozumiem ze olejemy istniejace scenerie, albo zmusimy ponownie grupe ludzi do ich przeorania? Przerabialismy to zbyt wiele razy w roznych wariantach i zniechecilo to skutecznie ludzi zajmujacych sie wydawaniem MaSzyny.

[ShaXbee]

Ja pkt drugi rozumiem tak jak w załączniku. Ale pierwszego to wcale ;(

Pierwszy HTD juz ogarnal, drugi rozumiesz dobrze ;-)

[HTD]

https://github.com/HTD/ScnEdit/blob/master/Bezier.cs - długości i punkty na krzywej Beziera 1-go i 2-go stopnia (z edytora).
https://github.com/HTD/ScnEdit/blob/master/V3D.cs - klasa wektorów używana przez Bezier.cs (z edytora).

Trochę nie nadążam tu: to dałoby się w istniejących sceneriach zastąpić krzywe Beziera innymi typami krzywych? Tzn automagicznie? Bo jeśli nie (wymagana ręczna edycja) - to wsparcie dla nieszczęsnych Bezierów jest konieczne. Nikt raczej nie będzie setek kilometrów przerabiał ręcznie raczej. A jeśli teoretycznie się da z automatu, to może warto spróbować? Puścić jakiś automat na wszystkich sceneriach, dodać do exe nowy typ krzywych i już. Tak tylko pytam.

Co do tematu:
http://caffeineowl.com/graphics/2d/vectorial/cubic2quad01.html
Wzór na P(t). Polecam włączyć Javę na tej stronie - rysunki i animacje pozwoliły mi zrozumieć temat na tyle, żeby zaimplementować wzory obliczeniowe w C#.

Co do odległości punktu na krzywej od punktu P to zwykła długość wektora, czyli problem trywialny.

Nie wiem do czego potrzebujesz tych wzorów. Żeby policzyć dokładnie długość trasy np dla wygenerowania rozkładu - dobrze nadaje się moja funkcja z edytora. Działa na zasadzie interpolacji krzywych Beziera 2-go stopnia do pierwszego stopnia. Dla większości torów błąd tej interpolacji jest całkowicie pomijalny. Z krzywej pierwszego stopnia długość liczy się z prostej całki, w kodzie jest gotowy wzór. Algorytm nie jest iteracyjny więc praktycznie nie ma nic szybszego.

W przypadku bardziej wymyślnych Bezierów 2-go stopnia można je zawsze interpolować za pomocą kilku (tzn. nie setek) krzywych pierwszego stopnia i nadal mamy bardzo szybki kod. Algorytm podziału też jest w kodzie edytora. Bardziej dla zabawy tam umieszczony, bo przy torach scenerii nie trzeba nic dzielić, wszystko liczone jest w jednym kroku.

Inne zastosowanie które jest mi potrzebne w edytorze to znajdowanie np sygnalizacji czy innych punktów w pewnej odległości od toru - ale to jak wspomniałem - sprowadza się do znalezienia długości wektora. Względnie zbioru punktów leżących w odległości R od krzywej. Na potrzeby zaznaczania w edytorze wystarczy podzielić krzywe na proste odcinki, nie musi być ich wcale dużo dla uzyskania całkowicie wystarczającej dokładności zaznaczania.

Jeszcze prostsza metoda zaznaczania - dzielimy krzywą na punkty w odległości r, i szukamy punktów w odległości R (>r) od tych punktów. Przy r wystarczająco mniejszym od R mamy wystarczającą dokładność. Dla przyśpieszenia możemy robić to powiedzmy w dwóch albo 3 krokach, od większego R i maksymalnie uproszczonego kształtu obszaru wyszukiwania, do mniejszych R i bardziej dokładnych kształtów. Niedługo wybieram się na urlop to będę miał w końcu czas zaimplementować w edytorze wyszukiwanie po odległości od toru.

[ShaXbee]

@HTD: potrzebne mi to do ruchu wozkow po torze - wozki trzymaja stala odleglosc od siebie w linii prostej.

[HTD]

W takim razie

Kod: [Zaznacz]

public V3D P(double t) { return A + 3 * t * (B - A) + 3 * t * t * (C - 2 * B + A) + t * t * t * (D - 3 * C + 3 * B - A); }
Wózek jedzie po krzywej, t zmienia się od 0 do 1, masz kolejne P o współrzędnych leżących na krzywej. Oczywiście możesz sobie wyskalować P dowolnie, np w metrach, jak policzysz długość krzywej z wzoru z linka, który wkleiłem (dodałem) w poprzedniej odpowiedzi.
Oczywiście punkty B i C są tutaj bezwzględne, nie jak w SCN, w odniesieniu do A i D.

W kodzie rysującym mapkę mam:

Kod: [Zaznacz]

PointF a, b, c, d;
a = t.Point1; b = t.Point1 + t.CVec1; c = t.Point2 + t.CVec2; d = t.Point2;

Zamiast typu double można używać float, testowałem różnice wydajności pomiędzy tymi dwoma i są niezauważalne, nawet przy dużych sceneriach.
  Dodano: 28 Marca 2015, 09:32:15 Tak na marginesie - do celów innych niż edycja scenerii wygodniej byłoby przeliczyć wszystkie Beziery 2-go stopnia do krzywych 1-go stopnia (albo i nawet eliptycznych czy innych o których wspominał Ra) i wtedy obliczenia nam się bardzo uproszczą. Samo przeliczenie jest proste i szybkie, można je wykonać na etapie samego ładowania danych.

W sumie tak sobie pomyślałem że faktycznie, do naszych celów powinniśmy unikać algorytmów i wzorów iteracyjnych bo raz, są koszmarnie wolne, dwa, komplikują niepotrzebnie kod, trzy - w projektach torów czy dróg są doskonale zbędne.

Bezierów używa się raczej w grafice, gdzie potrzebujemy odwzorowania bardzo dowolnych kształtów i krzywizn, przy torach nie ma tej dowolności, chyba, że chcemy odwzorować bardzo pogięty odkształcony tor, ale wydaje mi się, że to się raczej inaczej robi (nie znam na tyle budowy symka).

W sumie nie zgłębiałem konwersji do łuków elips, być może to byłoby optymalne rozwiązanie?
  Dodano: 28 Marca 2015, 09:46:02 @Ra:
Dlaczego w symku są używane krzywe Beziera 2-go stopnia? Czy przypadkiem nie dlatego, że silnik graficzny ma dla nich wbudowane wsparcie? Bo jeśli tak, to może można by zrobić taki myk: w sceneriach zmienić typ krzywych na eliptyczne (łuki okręgów) i przejściowe, natomiast do rysowania robić konwersję do Bezierów? To mogłoby nieco odchudzić i uprościć pliki z torami, uprościć i przyśpieszyć obliczenia typu znajdowanie długości czy punktów.
Ogólnie cała zabawa wymagałaby tylko trochę dodatkowego RAM-u - trzymasz w pamięci 2 mapy torów - graficzną (do rysowania) i topograficzną (dla obliczeń). Jeśli istnieje proste przekształcenie każdego odcinka toru w odpowiadający odcinek innego typu to gra mogłaby być warta świeczki.
W swoim edytorze mam to trochę podobnie rozwiązane. Jest źródłowa wersja mapy i wersja do rysowania. Aktualnie obie używają tych samych typów krzywych, co wynika właśnie ze wsparcia silnika graficznego. Ale grafika swoją drogą, a obliczenia swoją. Fajnie by było, gdyby mapa była bardziej modelem teoretycznym, a nie tak jak teraz - bardziej plikiem graficznym.

[ShaXbee]

Pierwszy wzor znam na pamiec ;-) Moze rzeczywiscie daloby sie automatycznie skonwertowac wiekszosc, ale wsparcie musi zostac dla flexow.

[firleju]

Jak dużo obliczeń nam zajmie konwersja tam i z powrotem? Jest sens to robić? Łatwiej przerobić krzywą 1-st na beziera czy z powrotem?
No i drugie pytanie czy można zrobić tak, żeby dany typ krzywej był okreslany parametrem enum i był brany odpowiedni typ obliczeń do przemieszczania.

[HTD]

Równie łatwo w obie strony. Chyba, że masz na myśli ilość taktów CPU, to nie sprawdzałem, ale miałoby to znaczenie tylko w przypadku przeliczania w czasie rzeczywistym. Ale i tu jeśli chcesz zastąpić algorytm iteracyjny całkowym to dostaniesz kod o rząd wielkości szybszy, więc nie ma się co zastanawiać, jeśli aproksymujesz długość powiedzmy z 10 czy 100 odcinków, to po prostu można z miejsca zastąpić konwersją do 1 stopnia i policzeniem całki z podanego wzoru. Jeśli oczywiście potrzebujesz długości w czasie rzeczywistym. Użycie CPU spadnie, na słabszych maszynach powinien nawet podskoczyć FPS ;)

Krzywa 2-go stopnia ma sens tylko jeśli ktoś w scenerii umieścił bardzo nietypowo krzywy tor, wygięty w kierunku jednego z końców, nierównomiernie. To można sprawdzić kiedyś skanując wszystkie pliki torów i licząc odchylenie pomiędzy długością 2 stopnia a 1 stopnia. Z drugiej strony - biorąc pod uwagę promienie łuków i długości odcinków torów - wizualna różnica powinna być niezauważalna. Różnica w długości też groszowa. Różnica w szybkości obliczania długości za to znacząca.

Dodatkowo, zapisanie w pliku 1 toru wymaga jednego parametru mniej. Pliki mogą się skrócić. Można je skrócić jeszcze bardziej poprzez zaokrąglenie wartości do cyfr rzeczywiście znaczących, część miejsc dziesiętnych w parametrach to zwykły "szum bitowy".