Twierdzenie o rozdzielaniu osi za pomocą wielu wielokątów?

9

Próbuję zaimplementować twierdzenie o osi oddzielającej w języku C #. Mam funkcję, która może obliczyć minimalny wektor translacji między dwoma wielokątami. Nie mogę jednak stworzyć funkcji, która oblicza minimalny wektor translacji między jednym wielokątem a wieloma innymi wielokątami. Szczerze mówiąc, pracuję nad tym od miesięcy i nie jestem bliżej rozwiązania i nie byłem w stanie znaleźć rozwiązania online. Zawsze jest kilka przypadków, które nie zwracają prawidłowego wyniku, co prowadzi do błędów o wysokim priorytecie w mojej grze.

Oto typowe przypadki krawędzi, które nie działają poprawnie:

skrzynie krawędziowe

Czy istnieje dobrze znane rozwiązanie tego problemu? Wszystko, co mogę znaleźć, to ludzie, którzy mówią „po prostu wykonaj SAT na każdym wielokącie”, ale rzadko daje to minimalny wektor translacji.

Każda pomoc byłaby bardzo mile widziana.

collision-detection separating-axis-theorem użytkownik40698
źródło
Jednym z pomysłów, którego tak naprawdę nigdy nie przeprowadziłem do testowania, jest to, że niektóre osie separacji - takie, które przesunęłyby cię na boki do sąsiedniego wielokąta - mogłyby być oznaczone, aby nigdy nie były uważane za minimum. Wtedy jakiś rodzaj powtarzanego testu dałby dobre wyniki (być może z pewnym rodzajem FIFO i / lub limitem iteracji, aby zapobiec utknięciu w pętli).
Andrew Russell,
Jeszcze trudniejszą do rozwiązania wersją jest to, że krawędź kształtu jest tylko częściowo zakryta innym. Na przykład na obrazie w prawym górnym rogu, jeśli środkowy kwadrat jest wysunięty w prawo, aby być większym prostokątem. Jest to podobne do wyniku używanego przeze mnie kodu, który pobiera dziesiątki tysięcy zajętych / niezajętych komórek i redukuje to do stu większych kształtów kolizyjnych
Richard Tingle

Odpowiedzi:

2

Idealnie, nie budujesz swojego środowiska z wielokątów. Budujesz go z krawędzi (które być może obliczasz z zestawu wielokątów). Na przykład w twoim pierwszym przykładzie jest jedna ukośna krawędź; w ostatnim przykładzie pudełko spoczywa na pojedynczej poziomej krawędzi.

Fakt, że edytor lub narzędzia używają mniejszych, indywidualnych kształtów do budowania poziomu, nie powinien mieć wpływu na środowisko wykonawcze.

Nieco prostsze podejście po prostu usunie „wewnętrzne” krawędzie kształtów podstawowych. W ostatnim przykładzie pomiędzy polami „podłogowymi” są dwie krawędzie; zignoruj ​​je podczas wykrywania kolizji.

Możesz znaleźć lepsze zdjęcia i pomysły na implementację, czytając rozdział 4.5 (krawędzie i łańcuchy krawędzi) w dokumentacji Box2D .

Sean Middleditch
źródło
2
Używanie krawędzi (szczególnie krawędzi, nieco lepiej w przypadku łańcuchów krawędzi) ma tę główną wadę, że obiekty fizyki stają się bardzo łatwe do zablokowania w geometrii poziomu.
Andrew Russell
1
@AndrewRussell: tych problemów można uniknąć dzięki zwykłym poprawkom tunelowania. Upewnij się, że poruszające się obiekty mają dość przyzwoitą objętość / obszar, utrzymuj maksymalną prędkość na klatkę wystarczająco niską, aby nie mogły się poruszyć o więcej niż ~ połowę swojego najkrótszego wymiaru (lub wykonaj krok kilka razy, jeśli potrzebujesz, aby poruszać się szybciej), unikaj naprawdę ostre szczeliny i tym podobne w twojej geometrii poziomu, kilkakrotnie iteruj rozdzielczość, aż zbiegniesz się w „bezpiecznej” ostatecznej lokalizacji itp.
Sean Middleditch