Polygonerstellung, CCW-Sortierung von Punkten
-
Hallo!
Habe hier ein Problem, bei dem mir einfach keine gescheite Lösung einfallen will. Es geht um folgendes:
Ich rendere eine Box bestehend aus 6 Polygonen. Diese Box schneide ich mit der Near Plane, um die Schnittpunkte zu erhalten. Diese Punkte benötige ich, um das durch Clipping entstandene Loch wieder zu schließen, indem ich mir aus den berechneten Schnittpunkten ein neues Polygon bastele.
Die Schnittpunkte habe ich. Mein Problem liegt nun darin sie entgegengesetzt dem Uhrzeigersinn zu sortieren, damit ein zu mir zeigendes Polygon dabei heraus kommt und kein Murks.
Mein bisheriger Ansatz war es, den Mittelpunkt der Schnittpunkte zu berechnen und dann Vektoren von diesem zu den jeweiligen Schnittpunkten zu bilden. Im Anschluss nehme ich mir einen Vektor als "Ursprung" und berechne mir den Winkel zu den anderen Vektoren.
Das Problem hierbei ist aber, dass ich sowohl mit dem Kosinus(Skalarprodukt), als auch mit dem Sinus(Kreuzprodukt) doppelte Werte bekomme, da diese ja periodisch sind und ich somit nur bis 180 Grad Werte bekomme...Hat jemand eine Idee, wie ich diese Punkte in die richtige Reihenfolge bekomme?
-
Wenn die Punkte a, b und c heißen:
(a - b) x (c - b)
ausrechnen (x soll das Kreuzprodukt sein) und gucken ob der resultierende vektor zu dir zeigt oder von dir weg (z-Koordinate positiv oder negativ). In einem Fall dann die Reihenfolge tauschen. Ich weiß jetzt die Regel nicht, in welchem. Also ausprobieren oder nachschlagen.