Algorithmus zum zeichnen eines Polygons (2D)?
-
Dank vieler guter Tipps von Euch, bekomme ich meine n-Ecke mittlerweile gezeichnet.
Falls es jemanden interessiert:
Zuerst zeichne ich meine Umrisslinien mit Bresenham in ein zweidimensionales Array der Größe des Bildes.
Die Probleme beim Zeilenweise füllen die D1BAKEL schon geschildert hat, vermeide ich, indem ich eine boolsche Variable verwende, in der ich mir merke ob der Hintergrund gezeichnet werden soll. Am Anfang der Zeile setze ich sie auf false und wechsele dann den Zustand bei jedem Wechsel von ?leerem Hintergrund? und Linie. Ist die Variable am Zeilenende ?true?, War in der Zeile eine oberer oder unterer Ecke des n-Ecks und ich mache die Änderung in dieser Zeile wieder rückgängig.
Der Hintergrund wird nur gezeichnet wenn die Variable ?true? ist und der Aktuelle Punkt nicht zu einer Linie gehört. Damit gibt es auch keinen Fehler, wenn die Linie in einer Zeile mehr als einen Pixel breit ist.Das ist zwar nicht gerade die schnellste Lösung, aber sie geht.
@ D1BAKEL
AntiAliasing bauche ich zwar nicht unbedingt, würde mich aber schon mal interessieren wie man so was macht. Bin für jeden Hinweis oder guten Link dankbar.@ ThomasRiker
Habe nicht ganz verstanden was Du meinst. In irgendeiner Datenstruktur muß ich meine n-Ecke ja ablegen, ich verwende ein 2dim Array. Gibt?s da eine bessere Möglichkeit?Wieso muss ich ein Dreieck unterteilen?
MfG Neo
-
Original erstellt von TomasRiker:
Wieso tastest Du das Dreieck nicht Zeile für Zeile ab? Ist doch einfacher und schneller als wenn man sich noch irgendein Array dazu bastelt.Sag ich doch...
-
Original erstellt von <Neo>:
**@ TomasRiker
Habe nicht ganz verstanden was Du meinst. In irgendeiner Datenstruktur muß ich meine n-Ecke ja ablegen, ich verwende ein 2dim Array. Gibt?s da eine bessere Möglichkeit?Wieso muss ich ein Dreieck unterteilen?**
Ein 2D-Array für die Punkte? Meinst Du nicht ein 1D-Array bestehend aus Punktstrukturen (mit x und y jeweils)?
Also, ich meine es wie folgt (Achtung, ASCII-Zeichnung!)
Du hast ein Dreieck:/\ / \ / \ / \ / \ / \ / \ /______________\Bei dem Dreieck ist keine Unterteilung nötig. Warum wirst Du später noch sehen. Jetzt beginnst Du ganz oben an der Spitze und zeichnest praktisch eine Linie mit nur einem Pixel breite.
Dann kommt die nächste Zeile, da fängt die Linie weiter links an und hört weiter rechts auf. Und so weiter, bis Du unten angekommen bist. Die x-Startkoordinate der Linie wird jedes Mal ein bisschen kleiner, und die x-Endkoordinate wird jedes Mal, also bei jeder Zeile, ein bisschen größer./\ /**\ /****\ /******\ /********\ / \ / *: Pixel \ /______________\So, jetzt hast Du ein anderes Dreieck:
A /\ / \ / \ / \ / \ / \ / \ /__ \ C \__ \ \__ \ \__ \ \__ \ \__ \ \__\ B(Das zackige unten soll eine durchgehende Linie sein)
Jetzt geht das mit dem linken Rand nicht mehr so schön, denn ab Punkt C würde die x-Startkoordinate der Linie auf einmal steigen, und nicht mehr fallen. Darum ist es dann einfacher, das Dreieck sich wie zwei Dreiecke vorzustellen:
A1 /\ / \ / \ / \ / \ / \ / \ A2 /__............\ B1 C1 \__ \ B2 \__ \ \__ \ \__ \ \__ \ \__\ C2Jetzt hast Du zwei Dreiecke: A1, B1, C1 und A2, B2, C2. Die sind nun einfach zu füllen, wie oben beschrieben.
[ Dieser Beitrag wurde am 17.03.2003 um 10:32 Uhr von TomasRiker editiert. ]
-
weil es keinen grund gibt das zu tun, beides ist gleich schnell
ob nun die daten für die interpolation der kanten auf den stack gebracht werden oder man nun die ergäbnisse der interpolation im 1lvl-cache hat.. also wer sich darüber aufregen würde..
da unser kunde aber ne einfach weise für sein problem wollte, hab ich ihm die genannt.. und da er das für beliebige polys(nicht nur dreiecke) will, lässt sich mein vorschlag auch sehr viel einfach erweitern. (egal ob für convex oder concav)
sagt mir aber bitte mal nen grund, weshalb ihr meint, dass man eueren algo nutzen sollte? ich sehe keinen vorteil auf cpu.
rapso->greets();
-
Original erstellt von <rapso>:
sagt mir aber bitte mal nen grund, weshalb ihr meint, dass man eueren algo nutzen sollte? ich sehe keinen vorteil auf cpu.Weil man damit überhaupt keine Werte zwischenspeichern muss, auch nicht auf'm Stack. Ausserdem kann man dies ebenso für beliebige Polys verwenden. Zuerst das Poly clippen, dann die Linien der Höhe nach sortieren, von oben nach unten vorgehen, alle Punkte aus aktiven Linien berechnen. Jetzt von links nach rechts und den Stift immer an und ausschalten, wenn man an einem der Punkte vorbei kommt.
-
während des durchlaufes der h-line passen wohl nicht alle daten in die register, wo sind sie dann wenn nicht auf dem stack?
rapso->greets();
-
Original erstellt von rapso:
während des durchlaufes der h-line passen wohl nicht alle daten in die register, wo sind sie dann wenn nicht auf dem stack?Ich würde schon sagen, das diese zwei Werte in die Register passen könnten. Was soll'n das überhaupt für'ne Begründung für unnütze Arrays werden, wenn's fertig ist?
-
also bei bresenham hat man pro kante 2positionen, ein delta und ein schwellenwert (jetzt so ma auf die schwelle), man bekommt alle register eigentlich schön gefüllt, da sind dann einige stackoperationen...
ob man nun die kanten daten auf den stack packt und dann jeweils eine h-line schreibt, oder ob man die kantenposition in ein arrays stopft und erst alle h-line positionen berechnet, das ist total egal.
aber ihr müßt ja in jedem kleinem fitzel beweisen das eure idiologie besser ist *fg*
übrigens läuft der softwarerenderer von Unreal auf eine ähnliche weise wie der von mir vorgegebene algorithmus, weil
- man danach besser optimieren kann
- es egal ist wieviel ecken ein poly hat, weil jede ecke nur für sich betrachtet wird
- man nicht sortieren muss
- es keinerlei nachteile gegenüber den alten algorithmen gibt
- es total billig ist beliebig geformte polys zu zeichnen, concave, convexe, sich schneidende kanten beinhaltende...rapso->greets();
-
das eine schwelle soll schnelle heißen
und
"ob man nun die kanten daten auf den stack packt und dann jeweils eine h-line schreibt, oder ob man die kantenposition in ein arrays stopft und DANN erst alle h-line positionen berechnet, das ist total egal."
-
Der Framebuffer wird möglicherweise dein tolles Array swappen. Bei Unreal gibts nur Dreiecke, also warum für andere Polygone optimieren?
-
weil man so an kanten automatisch zwei nebeneinander liegende kanten aufheben kann wenn sie in einer ebene liegen
so sicher bin ich mir nicht, dass bei unreal (wohgemerkt1) dreiecke waren, denn die levels bestanden immer aus rechtekigen flächen (vielleicht intern 2dreiecke, das weiß ich nicht)
die mußten ja sowieso die edges für z.B. vodoo karten generieren.b-buffer soweit ich weiß...
rapso->greets();
-
Original erstellt von rapso:
weil man so an kanten automatisch zwei nebeneinander liegende kanten aufheben kann wenn sie in einer ebene liegenNö, bei Unreals Softwarerenderer geht das nicht. Gibt wohl doch keine Vorteile.
-
Wie wärs wenn ihr beide einfach ein kleines Programm schreibt und die Perfomance misst. Das ist jetzt nur blanke Theorie.
-
Original erstellt von Lars:
Wie wärs wenn ihr beide einfach ein kleines Programm schreibt und die Perfomance misst. Das ist jetzt nur blanke Theorie.Ok, schreib ein Framework dazu!
-
tja, keine vorteile und der unreal renderer macht das, man müssen die blöd sein... jedenfalls falls deine erfahrung mit b-buffern wirklich so superior sind, dass nichtmal die coder von der engine mit dir mithalten können.
rapso->greets();
-
Original erstellt von rapso:
**tja, keine vorteile und der unreal renderer macht das, man müssen die blöd sein... jedenfalls falls deine erfahrung mit b-buffern wirklich so superior sind, dass nichtmal die coder von der engine mit dir mithalten können.rapso->greets();**
Was kann ich dafür, wenn die keinen Plan haben. BTW kenn ich mich auch mit A und C-Buffern aus.
-
Um z. B. zu entscheiden, ob ein Punkt innerhalb eines Polygons liegt, betrachtet man die Summe der Winkel zwischen dem zu untersuchenden Punkt und allen Eckpunkten des Polygons.
Ist die Winkelsumme Null, so liegt der Punkt außerhalb des Polygons.
Bei überschneidungsfreien Polygonen beträgt die Winkelsumme für einen inneren Punkt 360°; bei sich überschneidenden Polygonen (wie etwa das Pentagramm) haben Punkte auf der Überschneidungsfläche ein Vielfaches davon.
-
Beim Dreieck ist der Ansatz mit den Winkeln aber nicht empfehlenswert, da es viel schnellere Algorithmen gibt. Unter www.geometryalgorithms.com findest Du was dazu.
Aber Dein Vorschlag ist doch nicht wirklich, Pixel für Pixel auf dem Bildschirm durchzugehen und zu prüfen, ob er sich innerhalb eines der zu zeichnenden Polygone befindet, oder? Das wäre doch absolut langsam... pro Pixel und pro Polygon wären dann etliche atan2's nötig.
Nein, man geht einfach jedes Polygon durch (dabei sollte es schon in Form von Dreiecken vorliegen) und zeichnet es Zeile für Zeile.
-
Ich habe ja auch keineswegs behauptet, daß der Algorithmus schnell sei.
Jedoch glaube ich, daß die bisherigen Lösungsvorschläge nur für die besonders gutartigen, konvexen Polygone problemlos funktionieren.
Aber was machst Du z. B. bei der mit "?" markierten Innenfläche des Pentagramms? Ausfüllen oder nicht? Und wie ist die Dreieckszerlegung?.........../|.......... ..........|*|.......... ..........|**\......... .--------/---+-------.. ..\*****|????|*****/... ....\***|?????\**/..... ......\/??????|/....... ......|*\????/|........ ...../****\/***\....... ....|****/..\**|....... ....|**/......\|....... ....|/.................
-
Original erstellt von Krösus:
Und wie ist die Dreieckszerlegung?Algo dafür:
solange in der Polylist nicht alles Dreiecke
nimm zwei Eckpunkte eine Polys
teile das Poly an der Verbindungslinie, wenn die keine Begrenzungslinie des Polys schneidetSo, jetzt kannste los-/zerlegen!
