Frage zu Bresenham Algorithmus

[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.

[Gast]

@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.

[Gast]

@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);
}

[Gast]

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.

[Gast]

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...

[EOP]

volkard schrieb:

mm. Was man sinnvoll selfmoodyfied hatte, ist ja was statisches, das jagt der Prozzi inzwischen durch wie nix.

Ja, sind Erinnerungen an DOS-Zeiten.
Das war noch schön als man alles wüst manipulieren konnte.

[hustbaer]

volkard schrieb:

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

Dafür hatte man mit Floppy auch nen Parallelrechner

@EOP
IIRC gab's ein paar A500 Spiele die auf dem A3000 nicht liefen, weil der 68030er nen Instruction-Cache hatte der nicht mit dem Daten-Cache synchronisiert war.
Das war dann weniger cool

[EOP]

hustbaer schrieb:

@EOP
IIRC gab's ein paar A500 Spiele die auf dem A3000 nicht liefen, weil der 68030er nen Instruction-Cache hatte der nicht mit dem Daten-Cache synchronisiert war.
Das war dann weniger cool

Ich hab immer nur DOS-Zeugs gemacht.
Und auch nur Sachen wenn es genervt hat, wie "Alle fünf Leben sind verbraucht. Neues Spiel?"
Obwohl ich nie ein Spieler war und bin. War nur ein Spaß, den ich für mich und 2, 3 Freunde gemacht hab.