Habe gestern mal einen Tesselation-Algo ausprobiert, dessen Name ich leider nicht kenne.
Ich schätze zwar, dass der generell deutlich mehr Line-Intersection-Tests benötigt als z.B. Pig Ear, also dürfte nicht besonders optimal sein. Und schmale lange Dreiecke sind ja auch nicht besonders hübsch, alles mehr so Brute-Force, also dürfte nicht wirklich von Interesse sein. Aber: er funktioniert ;)
Dafür ist die Formulierung ziemlich simpel: Nimm einen beliebigen Punkt im Loop als Startpunkt an, gehe im Umlaufsinn durch welche Punkte von dort aus "sichtbar" sind, und füge diese zum aktuellen Fan hinzu. Für Punkte die nicht sichtbar sind, mache einen neuen Loop auf welcher separat gelöst wird.
Ist entfernt mit Schweinsöhrchen verwandt, aber schneidet keine einzelnen Dreiecke ab, sondern ganze Polyloops (welche am Ende dann alle jeweils durch einen einzelnen Fan repräsentiert werden können, dabei aber nicht konvex sein müssen), und arbeitet von innen nach außen statt von außen nach innen.
Die Idee ist an einen Bot angelehnt, welcher seine Umgebung von einem Punkt aus scannt, offene Portale im Scanpanorama markiert, später dann zu diesen hinrollt und von dort aus die noch unbekannten Bereiche dahinter scannt, bis keine Portale mehr übrig sind.
Im Bild startet der Algo bei 0; 1 ist sichtbar, 2 und 3 nicht, 4 ist wieder sichtbar, also wird ein separater Loop 1,2,3,4 in die ToDo-Liste gelegt. Ebenso 4,5,6, sowie 7-19 usw. Zum aktuellen Fan gehören dagegen die von 0 aus "sichtbaren" Punkte 0,1,4,6,7,19,...
Die blauen Kreise markieren jeweils den letzten sichtbaren Punkt und damit Startpunkt für abgetrennte Polyloops, die blaue Linie die Schnittkante zum nächsten wieder sichtbaren Punkt; abgetrennte Dreiecke (wie z.B. 4,5,6) sind trivial und haben hier im Debug-Render keinen neuen Startpunkt, sondern werden ungeprüft in die Renderliste gelegt.
