Symulator EU07 (i nie tylko) > Na warsztacie
Super szybki algorytm na długości krzywych Beziera
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:
--- Cytat: muri w 25 Marca 2015, 22:16:24 ---Ja pkt drugi rozumiem tak jak w załączniku. Ale pierwszego to wcale ;(
--- Koniec cytatu ---
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: ---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); }
--- Koniec kodu ---
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: ---PointF a, b, c, d;
a = t.Point1; b = t.Point1 + t.CVec1; c = t.Point2 + t.CVec2; d = t.Point2;
--- Koniec kodu ---
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.
Nawigacja
[#] Następna strona
Idź do wersji pełnej