Bresenham Algorithmus

Benutzeravatar
UdoWeber
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 156
Registriert: 8. Nov 2009 15:13

Bresenham Algorithmus

Beitrag von UdoWeber »

Soweit ist mir die Rechnung klar, allerdings habe ich da mal noch eine Frage:

Bsp.: Grade von P1(2,1) nach P2(6,6)

--> dx=4 dy=5

Berechne Entscheidungsvariable --> E= 5/4 - 1/2 = 3/4

E > 0 --> x = x+1 und y = y+1 E = E + 5/4 - 1 = 3/4 + 5/4 - 1 = 1

Jetzt meine Frage:

Beim ersten Schritt setz ich für x = x + 1 den ersten Punkt ein, sprich x = 2 + 1 = 3 und y = 1 + 1 = 2 ?
Und im nächsten durchlauf ist mein x dann 3 bzw. 2, richtig?

Danke für eure Hilfe, habe da in den Folien kein Beispiel mit Zahlen gefunden :(

Bzw. im Internet habe ich folgendes gefunden und hier wird
mit P(1,1) angefangen, obwohl die Linie in P1(0,0) startet , weshalb die Frage bei mir erst aufgetaucht ist.

Osterlaus
BSc Spammer
BSc Spammer
Beiträge: 1263
Registriert: 23. Aug 2007 12:46
Wohnort: DA

Re: Bresenham Algorithmus

Beitrag von Osterlaus »

Schritt für Schritt, hoffentlich ohne Fehler ;) Ich gehe hier übrigens nach dem Algorithmus aus den Folien!
  • Initial: \(\Delta x = 6 - 2 = 4, \Delta y = 6 - 1 = 5, x = 2, y = 1, fehler = \frac{\Delta x}{2} = 4\)
  • Setze Pixel bei (x,y), also bei (2,1)
  • \(x = x + 1 = 2 + 1 = 3, fehler = fehler - \Delta y = 4 - 5 = -1 \Rightarrow y = y + 1 = 1 + 1 = 2, fehler = fehler + \Delta x = -1 + 4 = 3\)
  • Setze Pixel bei (x,y), also bei (3,2)
  • \(x = x + 1 = 3 + 1 = 4, fehler = fehler - \Delta y = 3 - 5 = -2 \Rightarrow y = y + 1 = 2 + 1 = 3, fehler = fehler + \Delta x = -2 + 4 = 2\)
  • Setze Pixel bei (x,y), also bei (4,3)
  • \(x = x + 1 = 4 + 1 = 5, fehler = fehler - \Delta y = 2 - 5 = -3 \Rightarrow y = y + 1 = 3 + 1 = 4, fehler = fehler + \Delta x = -3 + 4 = 1\)
  • Setze Pixel bei (x,y), also bei (5,4)
  • \(x = x + 1 = 5 + 1 = 6, fehler = fehler - \Delta y = 1 - 5 = -4 \Rightarrow y = y + 1 = 4 + 1 = 5, fehler = fehler + \Delta x = -4 + 4 = 0\)
  • Setze Pixel bei (x,y), also bei (6,5)
Schaut nach einer logischen Linie aus, nur der Endpunkt (6,6) wird nicht getroffen.

Benutzeravatar
UdoWeber
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 156
Registriert: 8. Nov 2009 15:13

Re: Bresenham Algorithmus

Beitrag von UdoWeber »

Erst mal danke für die Antwort :)
Mmmm interessant... ich bin jetzt nach dem Algorithmus aus der Folie CG_Pipeline_extra.pdf gegangen.
Kommt im Prinzip das selbe raus, wenn ich den Anfangspunkt als ersten x und y Wert nehm wovon ich jetzt mal ausgehe, da du es auch gemacht hast:

P(2,1) und P2(6,6)
dx = 4
dy = 5

E = dy/dx - 1/2 = 5/4 - 1/2 = 3/4
E > 0 --> x = x+1 = 2 + 1 = 3 y = y + 1 = 1 + 1 = 2 --> P(3,2);

E = E + dy/dx - 1 = 3/4 + 5/4 - 1 = 1
E > 0 --> x = x+1 = 3 + 1 = 4 y = y + 1 = 2 + 1 = 3 --> P(4,3);

E = E + dy/dx - 1 = 1 + 5/4 - 1 = 5/4
E > 0 --> x = x+1 = 4+ 1 = 5 y = y + 1 = 3 + 1 = 4 --> P(5,4);

E = E + dy/dx - 1 = 5/4 + 5/4 - 1 = 6/4
E > 0 --> x = x+1 = 5 + 1 = 6 y = y + 1 = 4 + 1 = 5 --> P(6,5);

E = E + dy/dx - 1 = 6/4 + 5/4 - 1 = 7/4
E > 0 --> x = x+1 = 6 + 1 = 7 y = y + 1 = 5 + 1 = 6 --> P(7,6);

Da stellen sich mir jetzt die nächsten Fragen:
Wann terminiert das? Also wann hör ich mit den Rechenschritten auf? Gehört P(7/6) jetzt noch dazu?
Und wieso wird der Endpunkt P(6,6) nicht getroffen!? Obwohl er ja offensichtlich zur Linie gehört!? Was falsch gemacht? Oder einfach durch den Algorithmus bedingt?

Osterlaus
BSc Spammer
BSc Spammer
Beiträge: 1263
Registriert: 23. Aug 2007 12:46
Wohnort: DA

Re: Bresenham Algorithmus

Beitrag von Osterlaus »

Du hast aber schon eine Iteration zuviel drin: Die Schleife endet, wenn der x-Wert des Zielpunkts erreicht ist. Und dass der Zielpunkt nicht genau erreicht wird, ist eben eine Eigenart des Bresenham.

Benutzeravatar
UdoWeber
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 156
Registriert: 8. Nov 2009 15:13

Re: Bresenham Algorithmus

Beitrag von UdoWeber »

Ah ok, wunderbar vielen Dank für Deine Hilfe :) !

Iniii
Neuling
Neuling
Beiträge: 9
Registriert: 17. Jun 2009 22:14

Re: Bresenham Algorithmus

Beitrag von Iniii »

Start- und Endpixel sind ja schon gegeben durch den Start-und Endpunkt. Man nimmt beim Bresenham schon an, dass die Start- und Endpunkte auf dem Raster liegt. Deshalb terminiert der Algorithmus sozusagen einen Schritt vor dem Endpunkt.

Osterlaus
BSc Spammer
BSc Spammer
Beiträge: 1263
Registriert: 23. Aug 2007 12:46
Wohnort: DA

Re: Bresenham Algorithmus

Beitrag von Osterlaus »

Streng genommen deckt der in den Folien angegebene Algorithmus das aber nicht ab: das Startpixel setzt er explizit, das Endpixel nicht.

Iniii
Neuling
Neuling
Beiträge: 9
Registriert: 17. Jun 2009 22:14

Re: Bresenham Algorithmus

Beitrag von Iniii »

Streng genommen hast du da wohl Recht :D
Eine Folie vor dem Algorithmus steht aber (Folie 48): Herleitung: Anfangs- und Endpunkt auf dem Raster [...]
Schätze mal, dass das in dem Algorithmus in den Folien vergessen oder einfach weggelassen wurde, da sowieso vorrausgesetzt... Auf jeden Fall muss das Pixel da ja noch hin, die Linie hört ja nicht einfach ein Pixel früher auf^^

Osterlaus
BSc Spammer
BSc Spammer
Beiträge: 1263
Registriert: 23. Aug 2007 12:46
Wohnort: DA

Re: Bresenham Algorithmus

Beitrag von Osterlaus »

Iniii hat geschrieben:Streng genommen hast du da wohl Recht :D
Eine Folie vor dem Algorithmus steht aber (Folie 48): Herleitung: Anfangs- und Endpunkt auf dem Raster [...]
Schätze mal, dass das in dem Algorithmus in den Folien vergessen oder einfach weggelassen wurde, da sowieso vorrausgesetzt... Auf jeden Fall muss das Pixel da ja noch hin, die Linie hört ja nicht einfach ein Pixel früher auf^^
Warum sollte sie nicht früher aufhören? Zwischendrin ist sie ja auch ungenau ;)

Iniii
Neuling
Neuling
Beiträge: 9
Registriert: 17. Jun 2009 22:14

Re: Bresenham Algorithmus

Beitrag von Iniii »

Ja ungenau, aber es fehlen ja nirgends Pixel^^

Benutzeravatar
UdoWeber
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 156
Registriert: 8. Nov 2009 15:13

Re: Bresenham Algorithmus

Beitrag von UdoWeber »

Ok, da stellt sich mir wieder die Frage, wenn Start und Endpunkt schon gesetzt ist, setz ich dann trotzdem den ersten Punkt in den Algorithmus ein und terminiert er dann eins vor x!?

Iniii
Neuling
Neuling
Beiträge: 9
Registriert: 17. Jun 2009 22:14

Re: Bresenham Algorithmus

Beitrag von Iniii »

Also, du setzt den ersten Punkt ein, damit du überhaupt den zweiten berechnen kannst. Du kannst ja nicht den Startpunkt weglassen und mit dem zweiten Punkt anfangen, da du den ja noch gar nicht kennst.
Und er terminiert einen Schritt vor dem Endpixel. Von diesem wird aber schon ausgegangen, dass es im Raster ist und muss deswegen ja nicht erst nochmal berechnet werden.

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Re: Bresenham Algorithmus

Beitrag von mister_tt »

Das Problem bei dem o.g. Beispiel ist, dass die Steigung > 1 ist. Laut Folie 48 sollte die Steigung zwischen 0 und 1 liegen für den Algo. Deshalb terminiert der Algo in diesem Fall auch nicht.

Jetzt fragt mich nicht, wie man in solchen Fällen vorgeht 8)

Benutzeravatar
UdoWeber
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 156
Registriert: 8. Nov 2009 15:13

Re: Bresenham Algorithmus

Beitrag von UdoWeber »

Ja ok, war ein blödes Beispiel mit Steigung 1, danke für eure Hilfe. ;)

BjörnW
Erstie
Erstie
Beiträge: 13
Registriert: 14. Apr 2010 17:18

Re: Bresenham Algorithmus

Beitrag von BjörnW »

bei einer steigung >1 könnte man die gerade an der winkelhalbierenden spiegeln, den algorithmus ausführen und wieder zurückspiegeln

Antworten

Zurück zu „Archiv“