Jakiś czas temu zapytałem, jak ustalić, kiedy twarz nakłada się na inną. Porada polegała na użyciu bufora Z.
Nie mogę jednak użyć bufora Z w moim bieżącym projekcie i dlatego chciałbym użyć algorytmu malarza. Nie mam jednak pojęcia, kiedy powierzchnia jest za lub przed inną. Próbowałem wielu metod, ale wszystkie one zawodzą w przypadkach skrajnych lub zawodzą nawet w ogólnych przypadkach.
Oto lista metod sortowania, które próbowałem do tej pory:
- Odległość do punktu środkowego każdej twarzy
- Średnia odległość do każdego wierzchołka każdej twarzy
- Średnia wartość z każdego wierzchołka
- Najwyższa wartość z wierzchołków każdej powierzchni i narysuj je jako pierwsze
- Najniższa wartość z wierzchołków każdej powierzchni i narysuj je jako ostatnie
Problem polega na tym, że twarz może być bliżej, ale jest jeszcze dalej. Wszystkie te metody wydają się zawodne.
Edycja: Na przykład na poniższym obrazie powierzchnia z niebieskim punktem jako punktem środkowym jest pomalowana na powierzchni z czerwonym punktem jako punktem środkowym, ponieważ niebieski punkt jest bliżej. Wynika to jednak z faktu, że powierzchnia czerwonego punktu jest większa, a środek jest dalej. Powierzchnia z czerwonym punktem powinna być pomalowana na niebieską, ponieważ jest bliżej , podczas gdy odległość w środku wskazuje inaczej.
Czego dokładnie używa algorytm malarza, aby określić kolejność rysowania obiektów?
Odpowiedzi:
Zazwyczaj odległość punktu środkowego wielokąta od kamery jest używana do sortowania z. Algorytm malarza z natury nie może być w 100% dokładny. Zawsze będą przypadki, w których sortowanie się nie powiedzie, bez względu na używany punkt odniesienia.
Jeśli chcesz poprawnego sortowania Z za pomocą algorytmu malarza, musisz pokroić nakładające się wielokąty na mniejsze części (np. Używając drzewa czworokątnego) i posortować te części indywidualnie. Jednak procesor może stać się dość ciężki ...
Znaleziono ten plik Powerpoint, który ładnie ilustruje problem ( wersja PDF ).
źródło
W takich przypadkach dla mnie zawsze działało przy użyciu bsp-drzew. Podziel scenę, aż będziesz mieć wypukły zestaw wielokątów w węźle bsp-tree, a następnie możesz łatwo sortować wielokąty w obrębie węzłów. Zauważ, że sortując wielokąty z węzła bsp-tree wydaje się to ten sam problem, jak opisano powyżej, ale istnieje warunek nie tak oczywisty - po zbudowaniu bsp-tree wszystkie problematyczne przypadki są już rozwiązane - w węźle powinieneś zakończyć z zestawem wielokątów, z którego musi przejść test wypukłości - jeśli wybierzesz płaszczyznę z jednego wielokąta z tego zestawu, wszystkie pozostałe wielokąty znajdują się albo przed płaszczyzną, albo za płaszczyzną. Korzystanie z tych informacji ułatwia sortowanie - funktor sortowania pobiera 2 wielokąty - sprawdź, w której półprzestrzeni jest pierwszy wielokąt względem drugiego wielokąta, a także sprawdź położenie kamery względem drugiego wielokąta.
Należy również zauważyć, że testy określające stronę ustawienia kamery względem wielokątów i przemierzanie drzewa bsp są nieco inne w przypadku rzutowania ortograficznego i perspektywicznego.
Jeśli nie możesz sobie pozwolić na podział wielokątów wejściowych, myślę, że nie masz szczęścia.
źródło