Frage zu Bresenham Algorithmus

freakC++

Hallo zusammen,

ich habe gerade schnell den Bresenham Algorithmus implementiert:

void drawLine(int x_start, int y_start, int x_end, int y_end) {
		int dx = x_end - x_start;
		int dy = y_end - y_start;

		int x = x_start;
		int y = y_start;
		setPixel(x, y, 1, 0, 0);
		int err = dx / 2;

		while (x < x_end) {
			x++;
			err = err - dy;
			if (err < 0) {
				y++;
				err+=dx;
			}

			setPixel(x, y, 1, 0, 0);
		}		
	}

Liegt es daran, dass es früh am morgen ist, aber irgendwie sehe ich gerade nicht, wie der Algorithmus folgenden Fall beachtet:

Zeichne eine Linie von (0,0) nach (100,200). Der y-Wert des Zielpunktes ist also größer als der x-Wert. Weil die Schleife früher terminiert, wird bei mir eine Winkelhalbierende gezeichnet.

Wo ist mein Denk- oder Implementierungsfehler ?

LG, freakC++

tkausl

Zitat aus Wikipedia:

Der Algorithmus läuft dann so, dass man in der „schnellen“ Richtung (hier die positive x-Richtung) immer einen Schritt macht und je nach Steigung hin und wieder zusätzlich einen Schritt in der „langsameren“ Richtung (hier y).

In deinem Fall müsstest du also die "schnellere" Y-Richtung für die Schleife nehmen und alle 2 Schritte auch X um eines erhöhen.

Siehe hier für eine Implementierung in C:
http://de.wikipedia.org/wiki/Bresenham-Algorithmus#C-Implementierung

Wenn y positiv ist und größer als x, dann liegt y im zweiten Oktanten. Der Bresenham Algorithmus funktioniert jedoch nur für Linien im ersten Oktanten. Die Behandlung dieses Problems gibt Wiki übrigens nicht her (glaube ich zumindest). :p

L. G.,
IBV

SeppJ

freakC++ schrieb:

Wo ist mein Denk- oder Implementierungsfehler ?

Du hast die Anleitung nicht vollständig gelesen. Die typischen Pseuodcodes gelten nur für 0 < y < x oder |y| < x oder |y| < |x|, je nachdem, wie man es genau formuliert. Aber in jedem Fall musst du noch eine Fallunterscheidung machen und ggf. x und y des Algorithmus verdrehen.

hustbaer

@freakC++
~~Also falls du das nicht selbst schon rauslesen konntest: du musst zwei Schleifen machen - eine für "flache" und eine für "steile" Linien.~~

EDIT: OK, nicht wirklich. Es geht auch mit nur einer Schleife.

@freakC++
Also falls du das nicht selbst schon rauslesen konntest: Du musst deine Linien immer zum Ursprung verschieben, sie in den 1. Oktanten transformieren, den Algorithmus anwenden und das Ganze wieder zurücktransformieren und zurück verschieben.

L. G.,
IBV

hustbaer

IBV schrieb:

Du musst deine Linien immer zum Ursprung verschieben, sie in den 1. Oktanten transformieren, den Algorithmus anwenden und das Ganze wieder zurücktransformieren und zurück verschieben.

Nicht wirklich.
Aber du kannst ja gern mal Code herzeigen wie das aussehen soll wenn du meinst dass man es so macht.

@hustbaer: Es ist zumindest eine Möglichkeit die ich selbst so implementiert habe. SeppJ hat selbst angedeutet, dass in freakC++ Fall x und y vertauscht werden sollte, damit der Algorithmus anwendbar ist. Allerdings deckt das nur den Fall des 2. Oktanten ab. Die anderen sollten analog abgedeckt werden.
Code werde ich nicht herzeigen, da freakC++ ein Kommilitone von mir sein könnte, da er zur gleichen Zeit dasselbe Problem bearbeitet und unser Prof. sich ausdrücklich zu Abschreiben geäußert hat.
Was spricht denn mathematisch gegen meinen Vorschlag?

L. G.,
IBV

hustbaer

Hm.
Vielleicht hab ich auch nicht richtig verstanden was du meinst.

Ich meine auf jeden Fall: man muss keinen Code schreiben der zur Laufzeit irgendwas rumtransformiert.
Man kann Code schreiben wo der Code mehrere Schleifen enthält wo der Algorithmus entsprechend "transformiert" wurde (hast du vielleicht das gemeint?).

Oder man kann Code schreiben der ein paar Variablen mehr verwendet, dafür aber mit einer einzigen Schleife auskommt.

Sollte dann inetwa so aussehen:

vec2 delta = a - b;
vec2 step = sign(delta);
vec2 abs_delta = abs(delta);

vec2 primary_step;
vec2 secondary_step;
int big_delta;
int small_delta;

if (absdelta.x > absdelta.y)
{
  primary_step = vec2(step.x, 0);
  secondary_step = vec2(0, step.y);
  big_delta = absdelta.x;
  small_delta = absdelta.y;
}
else
{
  primary_step = vec2(0, step.y);
  secondary_step = vec2(step.x, 0);
  big_delta = absdelta.y;
  small_delta = absdelta.x;
}

set_pixel(a);

vec2 pt = a;
int error = big_delta / 2;
for (int i = 0; i < big_delta; i++)
{
    pt += primary_step;

    error += small_delta;
    if (error > big_delta)
    {
      error -= big_delta;
      pt += secondary_step;
    }

    set_pixel(pt);
}

Ich meinte:

1.  Verschiebe die Punkte relativ zum Ursprung (Punkt 1 ist bei (0, 0). Punkt 2 bei (p2.x - p1.x, p2.y - p1.y)).
2.  Transformiere die Punkte falls nötig in den ersten Oktanten.
3.  Bresenham-Algorithmus anwenden, d. h. (x, y) für den nächsten Punkt berechnen.
3.1 Bevor (x, y) gesetzt wird:
3.2 Relative Koordinaten in absolute Koordinaten zurückrechnen.
3.3 absolute((x, y)) zum ursprünglichen Oktanten zurücktransformieren.

Das hat uns der Prof. empfohlen und so hatte ich das umgesetzt. Aber deine Lösung ist denke ich deutlich eleganter, kürzer und effizienter.
Ich kann dir mal den Code per Mail schicken, wenn du willst.

L. G.,
IBV

Jester

IBV schrieb:

Das hat uns der Prof. empfohlen und so hatte ich das umgesetzt.

Bist du sicher, dass er das so zur Umsetzung empfohlen hat? Konzeptionell ist das super, weil es die Problemstellung auf eine zentrale Frage reduziert und erstmal Spezialfälle rausnimmt. Aber das ist sicher nicht so gedacht, dass man es dann genau so runtercodet.

Ja, er hat das so empfohlen. Ich habe auch schon abgegeben.

volkard

Jester schrieb:

Aber das ist sicher nicht so gedacht, dass man es dann genau so runtercodet.

Nicht genauso.
Vielleicht soll der Kreis vorbereitet werden, der innen ungern

plot(x,y)

hat, sondern lieber

plot(mx+x,my+y)

oder gar

plot(mx+x,my+y)
plot(mx+x,my-y)
plot(mx-x,my+y)
plot(mx-x,my-y)
plot(mx+y,my+x)
plot(mx+y,my-x)
plot(mx-y,my+x)
plot(mx-y,my-x)

EOP

Ich hatte mal nen richtig coolen code für Bresenham.
Self modifying asm code für "drüber und drunter".
Dummerweise hat meine Exfrau alles vernichtet. Sie wusste schon wo sie mich treffen kann...

hustbaer

@EOP
Das was ich hier als Pseudocode gezeigt habe lässt sich so ziemlich 1:1 auf Assembler übertragen.
(Zumindest wenn man einen "chunky" Display-Mode hat. Mit planaren Modi wird's umständlicher - da würde ich dann wirklich mehrere Schleifen empfehlen.)

Dabei packt man die drei 2D Vektoren pt , primary_step und secondary_step in je ein (Skalar-)Register. Und zwar pt als Adresse des Pixels und die beiden anderen als Adressänderung.

Der Code der dabei rauskommt sollte ziemlich optimal sein. Kein Grund für selbstmodifizierenden Code oder andere Grässlichkeiten

EOP

hustbaer schrieb:

Kein Grund für selbstmodifizierenden Code oder andere Grässlichkeiten

Selbstmodifizierender code ist eine der coolsten Sachen überhaupt.
Hatte Anfang der 90er ein Spiel, das seinen eigenen code ständig vor sich her geschoben und modifiziert hat. Quite cool.

EDIT:
Zeiten als ich noch Spaß dran hatte mich 12 Stunden ohne Essen oder Trinken mit TurboDebugger zu beschäftigen.

EDIT #2:
Und jetzt kommt volkard und setzt überall wo sie fehlen die richtigen Kommata in diesen und meinen vorherigen Satz ein. :p

volkard

EOP schrieb:

Ich hatte mal nen richtig coolen code für Bresenham.
Self modifying asm code für "drüber und drunter".
Dummerweise hat meine Exfrau alles vernichtet. Sie wusste schon wo sie mich treffen kann...

Ist nicht soo rasend schlimm. Was man sinnvoll selfmoodyfied hatte, ist ja was statisches, das jagt der Prozzi inzwischen durch wie nix.

Ich hätt gern als Andenken ein 64-er-Programm von mir ausgedruckt, was ich nur auf Tonbandcasette habe. Auch so ein Andenken.

EOP

volkard schrieb:

Ich hätt gern als Andenken ein 64-er-Programm von mir ausgedruckt, was ich nur auf Tonbandcasette habe. Auch so ein Andenken.

Nun gut, so alt bin ich auch wieder nicht, daß ich wie mein Bruder noch mit Lochkarten oder gar wie du mit Casetten gearbeitet hätte. Bin erst in den Fuffzigern. :p

EDIT:
Cassetten?

volkard

EOP schrieb:

EDIT:
Cassetten?

Floppy war mir zu teuer. Die hat ja so viel wie der Rechner selber gekostet.

EOP

Another thread hijacked...