Algorithmus zum zeichnen eines Polygons (2D)?
-
schau es dir einfach an, dann weißt du wofür..
außerdem ist bresenham sau langsam für ein 3zeilen hoches 1600 pixel breites triangle...
rapso->greets();
-
Original erstellt von rapso:
schau es dir einfach an, dann weißt du wofür..Habe ich, und deswegen hab ich se auh für unnütz empfunden.
Original erstellt von rapso:
**außerdem ist bresenham sau langsam für ein 3zeilen hoches 1600 pixel breites triangle...
**Dann sollte man ihn alt dafür etwas modifizieren! Zumindest kann man linken und rechten Rand berechnen ohne Multiplikationen und Divisionen in der inneren Schleife. Ok, genug dummes Gelaber von mir hierzu, weiss gar nicht, obs zu einer Lösung führt.
-
Vielleicht solltest du mal sagen, ob das nur für konvexe, oder auch für konkave n-Ecke sein soll. Wenns nämlich nur für konvexe sein soll, kann man jedes n-Eck problemlos in Dreiecke zerlegen, bei konkaven muss man da n bisschen aufpassen. Für Dreiecke gibts nämlich auch n Algorhitmus, google hilft da weiter...
-
Auf die Geschwindigkeit kommt es bei meiner Anwendung eher weniger an. Bei mir geht es nicht um Graphikausgaben in Echtzeit, sondern um automatische Bildauswertung, Segmentierung, Objekterkennung u.ä.. Je nach Bildauflösung können diese Verfahren schon bis zu mehreren Minuten pro Bild dauern.
Zur Ergebnisdarstellung brauche ich dann die n-Ecke. Wichtiger als die Geschwindigkeit ist, dass die Umrisslinien möglichst exakt und ?glatt? gezeichnet werden.Unter konvexen und konkaven n-Ecken kann ich mir höchstens im 3D etwas vorstellen?? Mir genügt ja schon 2D.
Ich Google dann mal nach Bresenham und der Zerlegung von Vielecke in Dreiecke und dann müsste ich es wohl hinkriegen.
MfG Neo
-
Unter konvexen und konkaven n-Ecken kann ich mir höchstens im 3D etwas vorstellen?? Mir genügt ja schon 2D.
Naaa... "konvex" bedeutet ja nur, daß man alle Eckpunkte mit allen Eckpunkten verbinden kann, ohne das Polygon (n-Eck) zu verlassen. Das geht auch in 2D.
MfG, Sarge
-
Oh, da lag ich ja ziemlich falsch. Demnach können meine n-Ecke auch konkave sein.
Ist dann eine Dreieckszerlegung überhaupt noch möglich, oder müssen die n-Ecke dazu konvex sein?
MfG Neo
-
Original erstellt von <Neo>:
Ist dann eine Dreieckszerlegung überhaupt noch möglich, oder müssen die n-Ecke dazu konvex sein?Ja, die Zerlegung ist dann auch möglich, wenn auch algorithmisch komplexer, da man die Diagonalen zum Zerlegen nicht mehr beliebig wählen kann.
-
Folgendes Methode zum Polygone Zeichnen hab ich mal irgendwo gelesen:
Zuerst mal braucht man für jede Zeile des Bildes ein Array, am besten man nimmt ein 2-dimensionales Array das genauso viele Einträge wie das Bild selbst hat.
Dann geht man von Punkt zu Punkt die Kanten entlang (ich würde es mit Bresenham machen) und schreibt diese Linien in das Extra array. Man hat dann im Prinzip ein Bild im Speicher das nur die Umrisse enthält.
Jetzt geht man zeilenweise durch das Bild. Man fängt links an und sucht den ersten Pixel der zu einer Kante gehört, dann füllt man alle Pixel die rechts davon kommen mit der gewünschten Farbe. Das macht man solange bis wieder ein Pixel im 'Linienbild' kommt. Man muss bis zum Ende der Zeile suchen, weil wenn nochmal eine Linie kommt muss man wieder anfangen zu zeichnen.Ich hoffe das ist jetzt verständlich. Das Polygon darf dafür natürlich nicht allzu 'durcheinander' sein, sonst gibts Fehler
-
was ich in meiner post vorgeschlagen hatte, erlaubt dir die kanten in arrays zu stopfen und dann zu zeichnen.. ich hab nur 2kanten-arrays, sicherlich kann man beliebig viele davon erstellen.
so zeichnest du jedes n-eck, auch die, die den screen schneiden ohne klippen zu müssen während der kantenerstellung.rapso->greets();
-
Also die Methode von 0x00000001 hat das Problem, dass auch in einer Zeile nur ein Pixel ist, z.B. in der obersten und untersten Zeile. Mittndrin kanns auch passieren, dass nach dem Linienzeichnen auch 3 Punkte sein. Das würde dann dazu führen, dass das Füllen nicht mehr funktioniert. Ach, und Neo, wie hättest du denn gern deine glatten Linien, mit AntiAliasing? Das sollte nämlich recht kompliziert werden, wenns aber wirklich so sein soll, dann poste mal.
-
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. Du musst dazu zwar das Dreieck in zwei Teildreiecke aufteilen (zumindest meistens), aber dann ist es ziemlich einfach. Auch mit Interpolation von Farben, Texturkoordinaten etc..
-
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."
