Jak znaleźć linie konturu dla algorytmu usuwania ukrytych linii Appela

Dla zabawy próbuję stworzyć przeglądarkę z ramką dla DCPU-16 . Rozumiem, jak to zrobić wszystko oprócz ukrywania linii ukrytych w ramce drucianej. Wszystkie pytania tutaj na SO zakładają, że masz dostęp do OpenGL, niestety nie mam dostępu do niczego takiego w przypadku DCPU-16 (ani żadnego rodzaju przyspieszenia sprzętowego).

Znalazłem dość dobry opis algorytmu Appela w Google Books . Jest jednak jeden problem, z którym mam problem.

Zatwierdź zdefiniowaną linię konturu jako krawędź dzieloną przez wielobok skierowany do przodu i do tyłu lub niepodzieloną krawędź wielokąta skierowanego do przodu, który nie jest częścią zamkniętego wielościanu. Krawędź dzielona przez dwa skierowane do przodu wielokąty nie powoduje zmiany widoczności i dlatego nie jest linią konturową. Na ryc. 8.4 krawędzie AB, EF, PC, GK i CH są liniami konturowymi, podczas gdy krawędzie ED, DC i GI nie są.

Rozumiem zasady algorytmu i sposób jego działania, gdy masz już linie konturu, ale nie rozumiem, co muszę zrobić, aby ustalić, czy krawędź jest „ wspólna dla wieloboku skierowanego do przodu i do tyłu, lub nieudostępniona krawędź wielokąta zwróconego do przodu, który nie jest częścią zamkniętego wielościanu "z punktu widzenia kodowania. Mogę patrzeć na kształt i wiem, które linie są liniami konturowymi w mojej głowie, ale nie mam pojęcia, jak przenieść to „zrozumienie” do zakodowanego algorytmu.

Aktualizacja

Poczyniłem pewne postępy w określaniu linii konturowych. Znalazłem te dwie notatki z wykładu z klasy Uniwersytetu w Buffalo na temat grafiki komputerowej.

Rozważ krawędzie. Można je podzielić na trzy kategorie.

1. Krawędź łącząca dwie niewidoczne ściany jest sama w sobie niewidoczna. Zostanie to usunięte z listy i zignorowane.
2. Krawędź łącząca dwie potencjalnie widoczne ściany nazywa się „krawędzią materiału” i będzie wymagać dalszego przetwarzania.
3. Krawędź łącząca potencjalnie widoczną powierzchnię z niewidoczną powierzchnią jest szczególnym przypadkiem „krawędzi materiału” i jest również nazywana „krawędzią konturu”.

Korzystając z powyższych dwóch informacji, jestem w stanie zbliżyć się do możliwości napisania tego jako kodu, ale wciąż mam przed sobą długą drogę.

Aby zachować regułę „-facing”, musisz upewnić się, że wszystkie twarze są odpowiednio zorientowane. Użyj na przykład reguły prawej ręki, co oznacza, że ​​wierzchołki twarzy powinny być ponumerowane w taki sposób, aby dodatni obrót w płaszczyźnie twarzy odpowiadał normalnemu wskazaniu na zewnątrz wielościanu. (Rozumiesz?) Lub prościej, każda twarz musi być normalnie skierowana na zewnątrz.

Zwisające twarze, tj. Nienależące do zamkniętego wielościanu, można uznać za mające nieokreśloną orientację.

Teraz głównym obliczeniem jest obliczanie części krawędzi, które są ukryte przez wielokąt konturowy. Problem ten jest bardzo podobny do przycinania segmentu linii przez okno wielokąta w 2D. Najpierw rozważ linię podparcia segmentu linii i znajdź przecięcia z wielokątem. Używając reguły parzystości, możesz łatwo określić części wewnątrz i na zewnątrz wielokąta.