Podział wielokątów na trójkąty

Kolega rr- rzucił dzisiaj na kanale #warsztat ciekawy problem rysowania dowolnych wielokątów za pomocą samych trójkątów. Jak wiadomo, karty graficzne posługują się właśnie trójkątami, zatem w celu wyświetlenia wielokąta należy go odpowiednio podzielić. Matematycy dowodzą, że jest to zawsze możliwe, i podają prosty sposób dla wielokątów wypukłych: należy po prostu narysować wszystkie przekątne wychodzące z jednego wierzchołka. Nie jest trudno przełożyć ten przepis na kod.

Co jednak z dowolnymi wielokątami? Tu sprawa wydaje się bardziej skomplikowana, chociaż – jak się ukazuje – rysowanie przekątnych można na ten przypadek uogólnić. Wpadłem jednak na inny pomysł, polegający na odpowiednim “chodzeniu” po wierzchołkach naszego wielokąta i “odcinaniu” od niego kolejnych trójkątów brzegowych. Wygląda to mniej więcej tak:

1. Startujemy od dowolnego wierzchołka wielokąta.
2. Mając i-ty wierzchołek sprawdzamy, czy da się go połączyć z (i+2)-im (modulo liczba wierzchołków) tak, aby powstały przy tym odcinek mieścił się w wielokącie:
   • jeśli tak, to z wierzchołków: i-tego, (i+1)-ego i (i+2)-ego tworzymy nowy trójkąt, wierzchołek (i+1)-szy usuwamy z wielokąta i przechodzimy do (i+2)-ego
   • jeśli nie da się tak połączyć wierzchołków, przechodzimy do wierzchołka (i+1)-ego i próbujemy dalej
3. Po wykonaniu pełnego cyklu kontynuujemy przechodzenie po wielokącie, usuwanie wierzchołków i tworzenie trójkątów – aż do momentu, gdy sam nasz wielokąt stanie się trójkątem. Będzie to oczywiście ostatni składający się na niego trójkąt.

Na tym rysunku można prześledzić, jak wyglądają kolejne cykle spaceru po krawędziach wielokąta – oznaczyłem je różnymi kolorami:

Z tym sposobem wiąże się oczywiście problem stwierdzenia, czy dany odcinek należy do wielokąta – co w ogólności nie musi być takie proste ani efektywne (może mieć złożoność liniową). Dodatkowo wielokąt może być “wredny” i niezbyt dobrze poddawać się operacji obcinania trójkątów. Na szczęście można udowodnić, że w każdym cyklu da się przynajmniej jeden taki trójkąt wyodrębnić. Te dwa fakty powodują, że cała operacja może mieć złożoność sięgającą nawet O(n³), chociaż pewnie da się ją zaimplementować lepiej.
Jest naturalnie bardzo możliwe, że algorytm ten jest znany od dawna, a ja po prostu nie przeczesałem Internetu dość dokładnie w poszukiwaniu już istniejącego opisu. Jednak biorąc pod uwagę to, co przed chwilą powiedziałem o jego możliwej “efektywności”, nie jest to znów takie pewne ;-) Istnieje aczkolwiek szansa, że może się on przydać komuś, kto implementuje bibliotekę graficzną 2D w oparciu o API w rodzaju DirectX czy OpenGL.

Trójkątyzacja

Wyświetlanie pojedynczych trójkątów – nawet najpiękniej pokolorowanych – to oczywiście dopiero początek. Niezależnie od tego, czy uczymy się obsługi jakiejś biblioteki 3D czy też piszemy własną, chcemy zająć się przede wszystkim wyświetlaniem brył. Rodzajów możliwych brył jest oczywiście sporo, ale te często używane i “regularne” ich rodzaje charakteryzują się przede wszystkim tym, że dają się opisać równaniami matematycznymi i zależnościami geometrycznymi. Wiemy na przykład, że sfera jest taką figurą, która składa się ze wszystkich punktów znajdujących się dokładnie w określonej odległości od danego – środka.
Problem w tym, że takich punktów jest “dość” dużo, bo nieprzeliczalnie wiele. Zarówno tą, jak i każdą inną bryłę w tradycyjnym renderingu zwykło się więc przybliżać automatycznie generowanymi trójkątami (jest to różnica np. w stosunku do raytracingu, czyli śledzenia promieni). Nazywa się to triangulacją i wymaga kilku operacji, takich jak:

1. Wyznaczenie odpowiedniej liczby punktów należących do powierzchni. Ich ilość powinna być regulowana – tak, aby w razie potrzeby otrzymywać siatki o różnych gęstościach punktów, a więc wpływać na jakość obrazu wynikowego (i, oczywiście, szybkość rysowania).
2. Połączenie wygenerowanych wierzchołków w trójkąty. W przypadku stosowania backface cullingu, czyli eliminowania powierzchni zwróconych przeciwnie do obserwatora, należy zadbać o właściwą kolejność wierzchołków w tych trójkątach.
3. Obliczenie wektorów normalnych dla wierzchołków. Wiadomo, że w gotowych siatkach możliwe jest przybliżone wyznaczenie tych wektorów w oparciu o sam rozkład trójkątów i kilka iloczynów wektorowych, lecz sposób ten jest niedokładny. Nie powinniśmy też z niego korzystać, gdy mamy dodatkową informację o powierzchni, którą nasze trójkąty przybliżają. W sferze na przykład dokładnie wiadomo, że normalne muszą być równoległe do wektorów biegnących od środka do punktu na powierzchni sfery.

I to w zasadzie wszystko. Warto oczywiście natychmiast sprawdzić rezultat przy pomocy renderowania w trybie wireframe, czyli rysowania tylko konturów figur. Jeśli wszystko dobrze pójdzie, to można się już pochwalić czymś więcej niż tylko jednym trójkątem, co też niniejszym czynię :)