Jak sprawdzić, czy jeden polygon pokrywa się w jakiejkolwiek części z innym polygonem (w przestrzeni 2D)?

Pytanie mam jak w temacie.

Najłatwiejsze wydaje się sprawdzenie, czy w polygonie A znajduje się którykolwiek z wierzchołków polygonu B (lub odwrotnie), np. używając regionów i funkcji PtInRegion. Niestety możliwe są sytuacje, w których dwa polygony będą się częściowo pokrywać, choć żaden z wierzchołków jednego nie wejdzie w obszar drugiego (wyobraźcie sobie małą literę t albo krzyż jako przykład - obie części się stykają, ale bez udziału wierzchołków).

Jedyne co mi przychodzi do głowy, to wyznaczanie dla wszystkich boków obu polygonów funkcji liniowych i sprawdzanie przecięć, a potem określanie, czy przecięcie leży na danym boku czy nie. Zadziałać zadziała, ale będzie to raczej dalekie od wydajności, zwłaszcza, że chciałbym testować w ten sposób bardzo wiele polygonów w krótkim czasie.

Jednym z tych polygonów jest bowiem pole widzenia gracza (o kształcie trójkąta), drugi polygon to ewentualny obiekt, który - o ile znajduje się w tym polu widzenia - musi zostać narysowany na ekranie. Gdy w polu widzenia znajduje się choćby jeden wierzchołek, to resztę jestem w stanie zrobić (dorysowuję sobie wszystkie sąsiednie wierzchołki, łączę je liniami, teksturuje itd). Problem mam z dużymi obiektami (np. ścianami), gdzie gracz nie jest wstanie wyłapać ani jednego wierzchołka, a przecież obiekt znajduje się w jego polu widzenia.

Może to pomoże?
http://mst.mimuw.edu.pl/lecture.php?lecture=gk1&part=Ch9
-- w kazdym razie, takie algorytmy są od dawna w użyciu...

Możesz narysować obiekty w świecie i tylko graczowi rzutować na jego polygon fragment świata, na który patrzy bez żadnego sprawdzania.

Nadziany Orzeł napisał(a):

Możesz narysować obiekty w świecie i tylko graczowi rzutować na jego polygon fragment świata, na który patrzy bez żadnego sprawdzania.

Rzecz w tym, że ja właśnie za pomocą wykrywania zachodzenia na siebie polygonów, wykrywam na co gracz patrzy.

Doczytałem, że ponoć najprostszą metodą takiego sprawdzania w przestrzeni 2D jest Drzewo Czwórkowe (Quadtree). Tyle tylko, że nie za bardzo rozumiem, jak takie drzewo miałby mi pomóc. Algorytm ten polega na podziale całej przestrzeni na 4 części, a potem określeniu czy w danej części znajduje się poszukiwany obiekt czy nie. Jeżeli nie, to cała taka ćwiartka może zostać pominięta i nie bierze udziału w dalszej analizie. Jeśli tak, że taką ćwiartkę znowu trzeba podzielić na 4 części, a potem znowu i znowu, aż do uzyskania satysfakcjonującej dokładności.

Nadal nie wiem jednak jak miałbym szybko sprawdzać, czy w danej ćwiartce znajdują się interesujące mnie obiekty. Dajmy na to mam mapę wielkości 200x200 pixeli. Dzielę ją na 4 ćwiartki, po 50x50 każda. Teraz muszę jakoś określić, czy któraś z tych ćwiartek nadaje się od odrzucenia (tj. nie zawiera żadnego polygonu wskazującego na obiekt lub jego fragment), czy też należy dokonać dalszego podziału.

Jak to zrobić? Mam w pętli badać pixel po pixelu? No ale jeżeli tak, to jaki jest sens tworzenia takiego drzewa? Przecież od razu mogę przelecieć całą mapę pixel po pixelu (bo do tego się to sprowadzi), zamiast bawić się w drzewo.

Chodzi o dziel i zwyciężaj jeśli w ćwiartce nie znajdują się na polygony to o niej zapominasz i masz 1/4 roboty z głowy, a jeśli się znajdują to tniesz na mniejsze tak długo aż dojdziesz do jakiegoś rozsądnego rozmiaru/ilości polygonów, i rozwiązujesz dla tego małego kawałka np. za pomocą przecięcia linii. Jak w sortowaniu dziel i zwycieżaj a końcówka przez wstawianie. Jeśli ktoś nie zrobi "po chamsku" tych poligonów piksel na pikselu to pi razy oko powinno byc n log n.

Wiem na czym polega ten algorytm, tylko nie widzę jego zastosowania do mojego problemu ;/.

Generalnie wychodzi na to, że jednak muszę robić to poprzez testy poligonów, tj. rozbijając każdy poligon na poszczególne boki i sprawdzając ewentualne przecięcia z polem widzenia gracza. Jestem w stanie to zrobić (w sumie właśnie tak robię w obecnej wersji mojego silnika), ale muszę to jakoś zoptymalizować, ograniczając ilość testowanych poligonów. Przecież nie ma sensu w sprawdzaniu każdego poligonu na danej mapie, skoro można się ograniczyć tylko do tych, które gracz ma w ogóle szansę w danej pozycji i przy danym ustawieniu kamery zobaczyć. Rzecz w tym, że nie wiem jak to osiągnąć.

Przychodzi mi do głowy coś takiego, żeby stworzyć sobie bazę danych dla każdej mapy z osobna, która będzie zawierała informacje na temat "dostrzegalności" wszystkich poligonów, ze wszystkich możliwych zakątków mapy (czyli dla każdego piksela), dla wszystkich możliwych orientacji kamery (360 stopni). Kij z tym ile potrwa wygenerowanie takiej bazy dla danej mapy (w końcu będzie robiona wcześniej - tj. na etapie tworzenia mapy przeze mnie - i dołączona w plikach gry, więc sam gracz tego nie odczuje), ale musi być jakiś bardziej elegancki i mniej pamięciożerny sposób (bo to jednak będzie wymagało przechowania dużej ilości informacji).

Plus za to byłby taki, że silnik nie musiałby już właściwie niczego obliczać w czasie rzeczywistym, bo wszelkie informacje na temat widoczności obiektów miałby zapisane w bazie. Na zasadzie: Gracz jest w punkcie (pikselu) X:276, Y:754 i jest obrócony o kąt 67%, więc należy narysować to, to i tamto.

Ewentualnie mógłbym darować sobie zapisywanie orientacji gracza i robić to w czasie rzeczywistym. Czyli: Gracz jest w punkcie X, Y, więc teoretycznie może z niego zobaczyć następujące polygony [LISTA]. Teraz przeszukuję listę (a nie całą mapę) pod kątem widoczności (biorąc pod uwagę orientację gracza) i rysuję wyniki.

Ciągle jednak myślę o jakiejś lepszej metodzie. Jakieś sugestie?

Generalnie wychodzi na to, że jednak muszę robić to poprzez testy poligonów, tj. rozbijając każdy poligon na poszczególne boki i sprawdzając ewentualne przecięcia z polem widzenia gracza (...) Przecież nie ma sensu w sprawdzaniu każdego poligonu na danej mapie, skoro można się ograniczyć tylko do tych, które gracz ma w ogóle szansę w danej pozycji i przy danym ustawieniu kamery zobaczyć. Rzecz w tym, że nie wiem jak to osiągnąć.

Moze coś takiego bouding box? W sensie najmniejszy prostopadłościan/prostokąt zawierający w sobie cały kształt, mając go mógłbyś bardzo łatwo ocenić które elementy na pewno się nie zawierają się w polu widzenia, które się zawierają a które wymagają dodatkowego sprawdzenia. Do tego zapisanie kształtów w strukturze danych pozwalającej znaleźć figury mogące znajdować się w prostopadłościanie też powinno być stosunkowo proste (mniej pamięcio chłonne niż pamiętanie każdej mozliwej opcji :P).

topik92 napisał(a):

Generalnie wychodzi na to, że jednak muszę robić to poprzez testy poligonów, tj. rozbijając każdy poligon na poszczególne boki i sprawdzając ewentualne przecięcia z polem widzenia gracza (...) Przecież nie ma sensu w sprawdzaniu każdego poligonu na danej mapie, skoro można się ograniczyć tylko do tych, które gracz ma w ogóle szansę w danej pozycji i przy danym ustawieniu kamery zobaczyć. Rzecz w tym, że nie wiem jak to osiągnąć.

Moze coś takiego bouding box? W sensie najmniejszy prostopadłościan/prostokąt zawierający w sobie cały kształt, mając go mógłbyś bardzo łatwo ocenić które elementy na pewno się nie zawierają się w polu widzenia, które się zawierają a które wymagają dodatkowego sprawdzenia. Do tego zapisanie kształtów w strukturze danych pozwalającej znaleźć figury mogące znajdować się w prostopadłościanie też powinno być stosunkowo proste (mniej pamięcio chłonne niż pamiętanie każdej mozliwej opcji :P).

To mi akurat niewiele da, bo piszę sobie bardzo prosty silniczek pseudo-3D, który działa w oparciu o wykrywanie wierzchołków polygonów, a następnie rzutowanie ich na plan. Potem wierzchołki są przenoszone w przestrzeń 3D (głębia jest liczona po prostu przez odmierzanie odległości danego wierzchołka od gracza na płaszczyźnie, w 2D), łączone liniami i teksturowane (tekstury są uproszczone i używają zwykłych deseni, przez co nawet nie muszę się bawić w ich poprawne nakładanie na obiekty z uwzględnieniem głębi; ot wypełniam polygon bitmapą i przebarwiam na wybrany kolor ;s).

Wpadłem na taki pomysł pisząc swoją wersję silnika raycastingowego, ale się okazało, że nie ja pierwszy. To samo zrobiło ID Software ze swoim Doomem po wcześniejszym stworzeniu Wolfensteina 3D :). No ale wracając, w chwili obecnej operuje tylko na prostych bryłach, tj. prostopadłościanach, więc bouding box absolutnie nic nie da ;(. W finalnej wersji planuję implementację bardziej złożonych modeli (testy w tech demie wypadły pomyślnie, więc raczej dam radę ;d) i wtedy pewnie z nich skorzystam, ale na razie to bez sensu.

Szukam jakiegoś skutecznego sposobu na ogarnięcie co znajduje się obecnie na scenie, bez wysyłania zapytań do wszystkich polygonów w obrębie mapy. Niby te polygony są bardzo proste (na każdy przypada raptem 4 boki), ale jednak to trochę mocy pożera, żeby liczyć dla każdego z nich funkcje liniowe i sprawdzać przecięcia. Jak już wiem co znajduje się na scenie, to dalej sprawdzenie samej widoczności obiektów idzie z górki. Używam do tego algorytmu malarza, z zaimplementowanym drzewem BSP, żeby uniknąć malowania niewidocznych przestrzeni.

No ale właśnie po to są te k-drzewa (czwórkowe czy ósemkowe) żeby odrzucić większość obiektów które są za daleko i nie ma ich sensu sprawdzać dokładniejszymi metodami w danym momencie.
I to jest dokładnie to o czym piszesz z tym liczeniem tej "bazy", tyle że podczas wczytywania levelu generujesz sobie drzewo czwórkowe dla mapy, a później je tylko odpytujesz żeby dostać tylko te obiekty które są w pobliżu w tym przypadku pola widzenia.

Alternatywą dla k-drzew, jest spatial hashing, który jest znacznie prostszy w implementacji, aczkolwiek sprawdza się tylko w przypadku ładnie/równomiernie rozłożonych obiektów, czyli np dla mapy.

http://zufallsgenerator.github.io/2014/01/26/visually-comparing-algorithms/