Jak uzyskać dokładne wyniki za pomocą algorytmu Painter?

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.

wprowadź opis zdjęcia tutaj

Czego dokładnie używa algorytm malarza, aby określić kolejność rysowania obiektów?

3d algorithm objects face

— pimvdb
źródło

Algorytm malarza jest tylko rysunek od tyłu do przodu.

— Jonathan Connell

@ 3nixios: Tak, oczywiście, ale w jaki sposób mogę określić kolejność „od tyłu do przodu”?

— pimvdb

Wszystkie twoje obiekty, trójkąty lub wierzchołki będą w pewnej odległości od kamery, kiedy zaczniesz rysować. Implementacja podstawowego algorytmu (czy udało ci się?) Polegałaby na określeniu odległości od kamery dla każdego trójkąta i narysowaniu ich w kolejności od najbliższej do najbliższej. Gdy to zrobisz, musisz zacząć szukać skrzyżowań i pokroić trójkąty, co jest zupełnie inną grą w piłkę . Dlaczego nie możesz już użyć bufora Z? : P

— Jonathan Connell

@ 3nixios: Masz całkowitą rację, ale mam problem z obliczeniem odległości. Jak powiedziałem, wypróbowałem kilka metod odległości, ale wszystkie nie są idealne. Ta kolejność wynika z sortowania odległości między punktami środkowymi: i.imgur.com/AcfCm.png .

— pimvdb

Czy wszystkie twoje wielokąty są na takiej regularnej siatce? Jeśli tak, mogą istnieć rzeczy specyficzne dla siatki, które możesz zrobić, aby to poprawić.

— CiscoIPPhone

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 ).

— grzmot
źródło

Dzięki za ten program Powerpoint pomógł mi rozwiązać problem.

— pimvdb

Link jest zepsuty. Czy ktoś może znaleźć kopię?

— Keavon

@Keavon Edited. Znalazłem działający link do pliku.

— bummzack

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.

— biskup
źródło