Algorithmus zum zeichnen eines Polygons (2D)?
-
Naja, IMHO bräuchte man eine Ungleichung, in die man einen Punkt einsetzt. Wenn die Ungleichung dann stimmt, dann ist der Punkt im Polygon, wenn nicht, dann eben nicht. Aber nichtmal mir als Mathematiker ist eine solche Ungleichung bekannt. Ist allerdings auch nicht mein Gebiet.
-
Super, bin echt beruhigt.
Habs zuerst auch über Ungleichungen versucht, bin da aber kläglich daran gescheitert und hab schon an mir gezweifelt. Vor allem da ich ja Polygone mit unterschiedlich vielen Ecken zeichnen will ist der Ansatz mit den Ungleichungen gar nicht so einfach.Oder bekommts jemand von Euch hin?
MfG Neo
-
ich denke, so etwas passt besser in das Grafikprogrammier Forum
-
Die Lösungsanzsätze, die bisher angeboten wurden, sind in Ordnung, aber von der Geschwindigkeit suboptimal. Wird denn eine möglichst schnelle Lösung gesucht?
-
mathematiker.. so so
aber mal ne ganz einfach methode hier
also in der zeichenfunktion:
int BufferL[BILDHOECHE];
int BufferR[BILDHOECHE];initialisier die buffer mit -1 pro entry.
dann hast du ja beim dreieck die 3-eckpunkte, die sortierst du von oben nach unten
nun berechnest du die kante vom obersten zum untersten punkt.
dazu:
steigung = (x3-x1)/(y3-y1); // alles floats
dann
for( int ypos=y1;ypos<=y3;ypos++) { BufferL[ypos]= x1+((float)ypos-y1)*steigung; }das machst du dann auch mit der linkie vom obersten punkt zum mittleren und vom mittleren zum untersten.
natürlich dann in BufferR
danach
for(int y=0;y<hoeche;y++) { if(BufferL[y]!=-1 && BufferR[y]!=-1) { int inc=1; if(BufferL[y]>BufferR[y]) inc = -1; for(int x=BufferL[y];x!=BufferR[y];x+=inc) SetPixel(x,y); } }rapso->greets();
ps. sorree falls es da bugs gibt, hab das ma eben hier runtergerattert.. ansonsten google
-
Wofür die Buffer? Die Outline sollte man per Bresenham bestimmen. Aber evtl. sollte man einfach mal die Hardware ranlassen, man müsste ewben erstmal die Rahmenbedingungen kennen.
-
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. ]
