Budowanie danych sąsiadujących trójkątów

Biorąc pod uwagę listę indeksów trójkątów, jak dokładnie można przekonwertować ją na listę indeksów z przyleganiem modułu cieniującego geometrię?

Zauważ, że ściśle mówimy tutaj o indeksach - wierzchołki są obecne, ale skupimy się wyłącznie na indeksach, ponieważ możemy ich użyć do dopasowania zduplikowanych wierzchołków bez konieczności przechodzenia do porównań zmiennoprzecinkowych i epsilonów - ta praca ma już zrobione.

Wiem, że dla każdego trójkąta na liście indeksy {0, 1}, {1, 2} i {2, 0} (lub {n, n + 1}, {n + 1, n + 2}, { n + 2, n} jeśli wolisz) z jego krawędzi; lista indeksów jest dobrze uformowana i prawidłowo przestrzega kolejności nawijania.

Wiem, że dla każdej takiej krawędzi możemy przeszukać całą listę pod kątem innego trójkąta, który wykorzystuje dwa z tych indeksów, a trzeci indeks tego trójkąta służy do wypełnienia sąsiedniego trójkąta dla tej krawędzi.

Wiem, że na liście sąsiadów każdy oryginalny trójkąt jest reprezentowany przez 6 indeksów, oryginalne indeksy przechodzą w przedziały 0, 2, 4; nowe wskaźniki uzupełniające dopasowanie znajdują się w polach 1, 3, 5. Indeks do uzupełnienia dla krawędzi {0, 1} trafia do boksu 1, indeks do uzupełnienia dla krawędzi {1, 2} idzie do boksu 3, indeks do wykonania dla krawędzi {2, 1} przechodzi do pola 5.

Co próbowałem?

Próbowałem brutalnego wymuszania, i tak, to zadziała, ale mam bardziej eleganckie podejście.

Próbowałem konstruktora list krawędzi Erica Lengyela, ale (1) wydaje się, że nie przestrzega oryginalnej kolejności trójkątów, (2) wydaje się, że nie przestrzega kolejności uzwojenia, (3) jest tak jasne, jak błoto, gdzie iść następnie po zbudowaniu listy krawędzi i (4) podejrzewam, że przykładowy kod zawiera tak oczywiste błędy rażące, jak „triangleIndex” kontra „faceIndex” - czy autor nawet skompilował kod, nie wspominając o uruchomieniu go, aby zweryfikować to?

Więc - jakieś sugestie lub wskazówki odtąd?

Spróbowałbym użyć do tego tabeli skrótów (na przykład, std::unordered_mapjeśli jesteś w C ++). Zbuduj tabelę skrótów, która odwzorowuje od połowy krawędzi (wyrażonej kolejno jako para indeksów) do trzeciego indeksu trójkąta, do którego należy połowa krawędzi.

Można to zbudować, po prostu iterując listę trójkątów i dodając trzy pół-krawędzie każdego trójkąta do tabeli skrótów. Jeśli twoja początkowa lista indeksów zawierała parę sąsiadujących trójkątów (0, 1, 2, 2, 1, 3), skończyłbyś się tabelą skrótów zawierającą:

(0, 1) -> 2
(1, 2) -> 0
(2, 0) -> 1
(2, 1) -> 3
(1, 3) -> 2
(3, 2) -> 1

Zauważ, że obie krawędzie (1, 2) i (2, 1) pojawiają się w tabeli, reprezentując dwa boki krawędzi i wskazując na trzeci wierzchołek każdego z dwóch trójkątów.

Następnie, aby zbudować dane o sąsiedztwie, wystarczy powtórzyć iterację po liście trójkątów i zapytać o krawędzie każdego trójkąta z przeciwnym uzwojeniem. Przetwarzając trójkąt (0, 1, 2), pytałeś o krawędzie (1, 0), (2, 1) i (0, 2). Znajduje przeciwny wierzchołek każdej krawędzi, jeśli istnieje.

Spójrz na strukturę danych w połowie krawędzi .

Z grubsza chodzi o to, że przechowujesz listę pół krawędzi , np. Połowę określonej krawędzi dołączoną do konkretnej ściany. Ta struktura następnie przechowuje również informacje o odpowiedniej połowie krawędzi dla przylegającej powierzchni.

Struktura danych sprawia, że ​​zapytania o łączność, przyleganie itd. Są bardzo wydajne. Istnieją algorytmy pozwalające na wydajne generowanie danych, choć niekoniecznie efektywne „uruchamianie gry” (prawdopodobnie będziesz chciał zrobić to offline w potoku zasobów).

Zobacz także te posty na blogu . Wierzę, że struktura i algorytmy są także w czasie rzeczywistym, ale nie pamiętam na pewno i nie mam kopii w biurze.