Symulator EU07 (i nie tylko) > Na warsztacie

 Super szybki algorytm na długości krzywych Beziera

(1/4) > >>

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.

Nawigacja

[0] Indeks wiadomości

[#] Następna strona