Jak mogę wykonać test wewnętrzny trójkąta w siatkach wielokątów?

10

wprowadź opis zdjęcia tutaj Mam 3 wierzchołki (V1, V2, V3)losowo wybrane na regularnej siatce trójkąta. Dla tych 3 wierzchołków obliczyłem odległość geodezyjną i ścieżkę (używając Dijkstry) między nimi i utworzyłem powierzchnię podobną do trójkąta, jak na powyższym rysunku.

Teraz mam wierzchołki, które leżą na każdej ścieżce i mogę obliczyć odległości geodezyjne od danego wierzchołka.

Chcę uzyskać wierzchołki lub trójkąty, które leżą w obszarze podobnym do trójkąta. W jaki sposób mogę to zrobić?

mesh triangulation mkocabas
źródło
2
Zakładając, że podejście barycentryczne robi to, co moim zdaniem robi, byłoby dość powolne przy dużych setach. Wyobraź sobie zestaw 9 milionów wierzchołków z tylko 9 wierzchołkami w pożądanym zestawie. Po co iterować cały zestaw, gdy v1, v2 i v3 zapewniają wszystkie potrzebne informacje. Odpowiedź na zalanie byłaby najszybszym elastycznym rozwiązaniem. Choć nieelastyczny, jeśli możesz założyć, że masz w geometrii linie takie jak teraz, to najszybszym podejściem będzie linia skanowania.
Andrew Wilson,
Masz całkowitą rację co do problemów z wydajnością. Chciałbym zastosować to podejście w dużych oczkach, więc szukam wydajnej metody. Właściwie nie jestem zaznajomiony z algorytmami wypełniania powodziowego ani skanowania wypełnienia, przyjrzę się im. Dzięki.
mkocabas,
3
Wypełnienie zalewowe z wykresem rozpocznie się w węźle, odwiedzi każdy sąsiedni węzeł, jeśli warunek brzegowy zostanie spełniony i nie będzie odwiedzony, oznaczy go jako odwiedzony i powtórzy (rekurencja). Zmiana: zaznacz każdy węzeł na ścieżce jako odwiedzony i zacznij od węzła w zestawie. Następnie po prostu użyj kontroli odwiedzin jako warunku granicznego.
Andrew Wilson,
Dziękuję za szczegółowe wyjaśnienie. Uważam, że algo wypełnianie zalewowe jest bardziej rozsądne, ale chcę wdrożyć zarówno linię wypełniania zalewowego, jak i linię skanowania, a następnie porównać wyniki.
mkocabas,

Odpowiedzi:

4

Istnieje alternatywna metoda polegająca na wypełnianiu powodzi. Najpierw ułóż dane krawędzi w pętli, w której krawędzie tworzą pętlę przeciwnie do ruchu wskazówek zegara. Następnie zacznij od dowolnego punktu na pętli i wybierz krawędzie łączące ten punkt. Użyj wychodzącej krawędzi granicznej i skrzyżuj ją z drugą krawędzią wychodzącą, jeśli wskazuje ona normalną stronę twarzy, to jest to krawędź do uwzględnienia, jeśli nie, odrzuć ją. Od tej krawędzi kontynuuj, aż dojdziesz do krawędzi granicznej, w którym to momencie kończysz wypełnienie. Kontynuuj na jeszcze odwiedzanym wierzchołku krawędzi granicy.

joojaa
źródło
Nie znam algorytmu wypełniania powodzi. Twoje wyjaśnienie wydaje mi się trochę skomplikowane. Czy mógłbyś podać godne odniesienia do obejrzenia? Dzięki.
mkocabas,
Znalazłem rozwiązanie, czytając trochę. Dzięki.
mkocabas,
3

Skomentowałem już użycie wypełnienia zalewowego i tego, jak byłoby lepiej, ponieważ jest bardziej elastyczny, ale innym możliwym rozwiązaniem jest scanline. (Mówię, że jest to możliwe, ponieważ robi wiele założeń na temat twojej geometrii, ale dla konkretnego pokazanego zestawu i wielu podobnych działałoby.)

Na przykład z 3 punktami: Znajdź wierzchołek przecięcia z segmentu v1, v2 i linii, na której leży v3. (Wierzchołek w lewym górnym rogu v2) Nazwiemy ten wierzchołek v4.

For every vertex pair a,b down v1,v4 and v1,v3 
    For every vertex from a to b
        Mark as in the set
For every vertex pair a,b down v3,v2 and v4,v3
    For every vertex from a to b
        Mark as in the set

wprowadź opis zdjęcia tutaj

Nazywa się to scanline, ponieważ (na powyższym obrazku) wchodzisz jednocześnie po czerwonych i zielonych liniach, a następnie czerwone i niebieskie linie jednocześnie skanujesz linie podczas jazdy.

To rozwiązanie byłoby bardzo szybkie, jeśli istnieje wzorzec indeksu, co często ma miejsce. W przeciwnym razie konieczne byłoby obliczenie w celu ustalenia, który sąsiadujący wierzchołek leży na linii.

Zabawne jest skanowanie liniowe, barycentryczne testowanie (w obwiedni trójkąta) i wypełnianie przez zalanie to wszystkie sposoby rysowania trójkątów w renderowaniu 3d.

Andrew Wilson
źródło
2

Myślę, że możesz obliczyć niektóre współrzędne barycentryczne związane z powierzchnią dla każdego punktu na powierzchni, a następnie użyć ich do sprawdzenia wewnątrz lub na zewnątrz trójkąta.

Nie mam pod ręką dokładnego algorytmu, ale znalazłem następujący artykuł, który wydaje się obsługiwać dokładnie tego rodzaju współrzędne.

Współrzędne barycentryczne na powierzchniach

Dragonseel
źródło
Dzięki za odpowiedź i dokument referencyjny. Spróbuję wdrożyć proponowaną metodę.
mkocabas