Frage zum Rastern von Polygonen
-
Hallo,
ich beschäftige mich im Moment mit dem Rastern von Polygonen und bin auf Algorithmen gestoßen wie dem Scan-Line-Verfahren.
Ich habe ein Polygon mit beliebig vielen Ecken gegeben. Es kann konvex und konkav sein.
Nun laufe ich mit dem Bresenham-Algorithmus über jede Kante entlang und möchte mir ähnlich wie bei dem Scan-Line-Verfahren auf jeder Höhe Y den Schnittpunkt X mit einer waagerecht ausgelegten Geraden (also Asymptote mit Steigung 0) merken.
Am Ende sortiere ich für jede Zeile die X-Werte und möchte das Polygon nach dem Paritätsprinzip füllen. (Also Start: Nicht im Polygon, X1: Im Polygon, X2: Nicht im Polygon.Mein Problem: Kanten die nahezu waagerecht sind schneiden die Asymptote mathematisch zwar nur in einem Punkt, in Pixeln dank der Approximation aber viel öfter. Wie kann ich das umgehen?
Vielen dank.
Grüße
André
-
indem du nicht bresenham benutz, sondern einfach pro zeile pro kante einen x wert errechnest (denn genau das willst du ja eigentlich auch nur haben).
zur not kannst du im bresenham auch nur jeden x punkt ausgeben wenn du in eine neue zeile gehst (das ist normalerweise sowieso eine extra if abfrage im inner loop von bresenham).
-
Jo das hab ich mir auch schon überlegt. Das Problem mit der Approximation ist damit aber nicht gelöst. Stell dir vor, ich starte in einem beliebigen Ursprung und habe dort meinen ersten Eckpunkt. Der nächste Eckpunkt ist vier Pixel nach rechts verschoben und einen nach oben. Wenn ich nun nur einen Schnittpunkt berechne, dann wird das je nach Runden das obere dritte Pixel oder das untere dritte Pixel von der X-Achse aus betrachtet.
So weit so gut.Wenn ich nun aber an den Eckpunkten senkrechte Geraden runterziehe, macht es einen Unterschied, ob es das obere oder das untere Pixel ist. Ich brauche ja immer eine gerade Anzahl an Schnittpunkten. Mit dem oberen geht es, wenn ich das untere wähle, dann habe ich auf einer Achse drei Schnittpunkte
-
anjohn schrieb:
Wenn ich nun aber an den Eckpunkten senkrechte Geraden runterziehe, macht es einen Unterschied, ob es das obere oder das untere Pixel ist.
huh? senkrecht? du meinst waagerecht, oder? du sortierst die x punkte und zeichnest zwischen denen die linien, je nach paritaet.
Ich brauche ja immer eine gerade Anzahl an Schnittpunkten. Mit dem oberen geht es, wenn ich das untere wähle, dann habe ich auf einer Achse drei Schnittpunkte
wenn du pro gerade, pro y-zeile einen punkt setzt und das objekt ist geschlossen, wirst du mit einer geraden anzahl an punkten enden (bis auf implementations bugs an endpunkten :D)
-
Ja stimmt.
Ich muss mich korrigieren, es gäbe dann wohl zwei Schnittpunkte.
Habe ich die Eckpunkte (0|0) und (4|1), dann erhalte ich die Schnittpunkte (1|0) und (3|1).
Damit komme ich auf keine gültige Parität.Ich meine SENKRECHTE Geraden die ich am Rand herunterziehe. Das sind dann die Begrenzungen links und rechts. Oben drauf ist ein schiefes Dach, also meine am Anfang erwähnte "Problemgerade".
Das Problem ist auch, dass ich alle Eckpunkte hereinziehen muss, denn diese werden entweder doppelt oder einfach gezählt.
Schau einfach hier bei Abb.4.5: http://www-lehre.inf.uos.de/~cg/2006/skript/node31.htmlAlso Scan-Line ist ja theoretisch schön und gut auf dem Papier, aber irgendwann will ich es auch mal auf den Bildschirm bringen mit realen Pixeln
-
zur not kannst du im bresenham auch nur jeden x punkt ausgeben wenn du in eine neue zeile gehst (das ist normalerweise sowieso eine extra if abfrage im inner loop von bresenham).
Und das kam mir auch schon in den Sinn.
Ich glaube des Rätsels Lösung gefunden zu haben: Immer wenn ich in eine neue Zeile gehe, merke ich mir den neuen X-Wert, aber NICHT, wenn ich in die Zeile komme, in der mein Polygon-Eckpunkt liegt. Der muss immer rein.In meiner einstufig genäherten Geraden nehme ich also nur die Eckpunkte des Polygons in meine Liste auf. In einer zweistufig genäherten Geraden pack ich drei Punkte in meine Liste: Die Eckpunkte des Polygons und den X-Wert auf der "ersten Treppenstufe".
Kannst du das verrifizieren?