So finden Sie Konturlinien für Appels Algorithmus zum Entfernen versteckter Linien

Zum Spaß versuche ich, einen Wire-Frame-Viewer für die DCPU-16 zu erstellen . Ich verstehe, wie man alles macht, außer wie man die Linien versteckt, die im Drahtrahmen versteckt sind. Alle Fragen hier auf SO setzen voraus, dass Sie Zugriff auf OpenGL haben. Leider habe ich für die DCPU-16 (oder irgendeine Art von Hardwarebeschleunigung) keinen Zugriff auf so etwas.

Ich habe in Google Books eine ziemlich gute Beschreibung des Appel-Algorithmus gefunden . Es gibt jedoch ein Problem, das ich nur schwer herausfinden kann.

Appel definierte Konturlinie als eine Kante, die von einem nach vorne gerichteten und einem nach hinten gerichteten Polygon geteilt wird, oder als ungeteilte Kante eines nach vorne gerichteten Polygons, das nicht Teil eines geschlossenen Polyeders ist. Eine Kante, die von zwei nach vorne gerichteten Polygonen geteilt wird, bewirkt keine Änderung der Sichtbarkeit und ist daher keine Konturlinie. In Abb. 8.4 sind die Kanten AB, EF, PC, GK und CH Konturlinien, die Kanten ED, DC und GI nicht.

Ich verstehe die Regeln des Algorithmus und wie er funktioniert, sobald Sie Ihre Konturlinien haben, aber ich verstehe nicht, was ich tun muss, um festzustellen, ob eine Kante " von einem nach vorne und nach hinten gerichteten Polygon geteilt wird, oder ungeteilte Kante eines nach vorne gerichteten Polygons, das aus Codierungssicht nicht Teil eines geschlossenen Polyeders ist . Ich kann mir eine Form ansehen und weiß, welche Linien Konturlinien in meinem Kopf sind, aber ich habe keine Ahnung, wie ich dieses "Verständnis" in einen codierten Algorithmus übertragen kann.

Aktualisieren

Ich habe einige Fortschritte bei der Bestimmung der Konturlinien erzielt. Ich fand diese beiden Vorlesungsunterlagen aus einer Klasse der University of Buffalo über Computergrafik.

Betrachten Sie die Kanten. Diese fallen in drei Kategorien.

1. Eine Kante, die zwei unsichtbare Flächen verbindet, ist selbst unsichtbar. Dies wird aus der Liste gelöscht und ignoriert.
2. Eine Kante, die zwei potenziell sichtbare Flächen verbindet, wird als "Materialkante" bezeichnet und muss weiter bearbeitet werden.
3. Eine Kante, die eine potenziell sichtbare Fläche und eine unsichtbare Fläche verbindet, ist ein Sonderfall einer "Materialkante" und wird auch als "Konturkante" bezeichnet.

Mit den beiden oben genannten Informationen kann ich der Möglichkeit näher kommen, dies als Code zu schreiben, aber ich habe noch einen langen Weg vor mir.

Damit die Regel "-facing" gilt, müssen Sie sicherstellen, dass alle Gesichter richtig ausgerichtet sind. Verwenden Sie beispielsweise die Regel für die rechte Hand. Dies bedeutet, dass die Scheitelpunkte einer Fläche so nummeriert werden sollten, dass eine positive Drehung in der Ebene der Fläche einer normalen Ausrichtung außerhalb des Polyeders entspricht. (Verstanden?) Oder einfacher gesagt, jedes Gesicht muss mit seiner nach außen gerichteten Normalität kommen.

Baumelnde Gesichter, dh die nicht zu einem geschlossenen Polyeder gehören, können als unbestimmt ausgerichtet angesehen werden.

Das Hauptgericht ist nun die Berechnung der Teile einer Kante, die von einem Konturpolygon verdeckt werden. Dieses Problem kommt dem des Abschneidens eines Liniensegments durch ein polygonales Fenster in 2D sehr nahe. Betrachten Sie zunächst die Stützlinie des Liniensegments und suchen Sie Schnittpunkte mit dem Polygon. Mithilfe einer Paritätsregel können Sie die Teile innerhalb und außerhalb des Polygons leicht bestimmen.