Bresenham's Algorithmus für Linien - begreife eine Sache nicht

Du brauchst keinen Code zu tippen, nur den Sinn dieser 2, also der 'Verschiebung', die man hat in eigenen Worten fassen. Oder wenigstens sagen ob ich richtig oder falsch lag mit der Vermutung, daß es wegen der 0,5 so gemacht wurde.

randa

@TGGC: lass es.

Ich find diese Implementation des Bresenham irgendwie komisch, ich hab den Algorithmus etwas anders implementiert. Ich kann ehrlich gesagt auch nicht nachvollziehen, wieso das mir 2 Multipliziert wird.
Allerdings frage ich mich, woher die y2, y1, x2, x1 Werte kommen, die hast du hier nicht deklariert. Hat es was mit denen aufsich? Gibts da vielleicht noch kontext?

Hi randa, das ist mehr ein Pseudo-Code. x1 und y1 sind die Startpunkte und x2 mit y2 die Endpunkte. Hier habe ich die Vorlesung angesehen (Kapitel 3, die erste - 2D-Grundlagen: Punkt, Geradengleichung, Bresenham-Linie, Antialiasing). Sowie ich das verstanden habe wurde die ganze Sache mit dem Fehler nur deswegen verschoben, damit man in der if-Abfrage die Prüfung auf 0 machen kann, was deutlich schneller ist als gegen 0,5. Bin mir aber jetzt wie gesagt nicht ziemlich sicher, daher habe ich auch gepostet. Verwirrend finde ich auch die Sache mit der zweiten Geraden...

TGGC

randa schrieb:

@TGGC: lass es.

Du hast recht, den Leuten noch Lesen beizubringen ist mir echt zu viel.

Bye, TGGC \-/

randa

ich verstehe nicht, warum man irgendwo eine prüfung auf 0.5 machen muss.
Deine Frage ist, warum mit 2. Ich weiß es nicht. Poste mal den richtigen code der gesamten funktion, denn mir jedenfalls ist es nicht ersichtlich. Aber ich kenne auch diese Implementierung nicht, da können dir andere vielleicht helfen. Aber ich geb dir mal den code der Linienfunktion, so wie ich es gemacht hab:

void line (int x1, int y1, int x2, int y2, int Color, uchar* out)
{
	//Die Formel für die Berechnung der Position im screen Array
	int offset=y1*SCREEN_W+x1;

	int deltax=0;
	int deltay=0;
	int nenner=0;
	int zaehler=0;
	int xplus=0;
	int yplus=0;

	deltax=x2-x1;
	deltay=y2-y1;
	xplus=1;

	//SCREEN_W=SCREEN_WIDTH=Bildschirm-x-breite ;)
	yplus=SCREEN_W;

	if (deltax<0) { deltax=-deltax; xplus=-xplus; }
	if (deltay<0) { deltay=-deltay; yplus=-yplus; }

	//Da Deltax nun deltay sein kann, müssen in dem Fall auch die Inkrementierungsschritte vertauscht werden

	if (deltay>deltax) { int tmp=deltax; deltax=deltay; deltay=tmp; int temp=xplus; xplus=yplus; yplus=temp; }

	nenner=deltax;
	zaehler=deltay;

	for (int i=0; i<deltax+1; i++)
	{
		out[offset]=Color;

		offset+=xplus;
		zaehler+=deltay;

		if (zaehler>=nenner) { zaehler-=nenner; offset+=yplus; }
	}
}

Für mich persönlich verständlicher, weil ich die Variablen als zähler-nenner Bezeichne und für mich nachvollziehbarer ist.
Jedenfalls musste ich nirgends mit 2 malnehmen.

Eine Prüfung auf 0,5 weil falls der Fehler über 0,5 liegt (weicht von der Ideallinie ab) es ein Pixel nach oben (y-Achse) statt nach rechts gesetzt wird (frühere Versuche, auch auf der Seite zu finden).
Deine Funktion braucht mehr Rechenzeit, da die if-Abfrage nicht auf 0 sondern auf den nenner prüft und um das zu vermeiden wurde es auf 'meinem' Beispiel halt verschoben (?). Das Beispiel ist außerdem vereinfacht, es funktioniert nur im 1. Oktanten.
@TGGC du gehst mir auf den Sack, wenn du 'lesen' kannst, kannst du einfach sagen, ob ich richtig oder falsch mit meiner Vermutung liege (Ja oder Nein ist deutlich kürzer und dazu noch hilfreicher als der Mist, den du hier abziehst ).

durito

Strogij, ignoriere den Typen. Sinnlose und dumme comments zu posten ist sein liebstes (und einziges?) Hobby, also lass ihn labern und lass Dich davon nicht ablenken

randa

na also, dann hast du es ja kapiert. Und ich auch.

Strogij schrieb:

Deine Funktion braucht mehr Rechenzeit, da die if-Abfrage nicht auf 0 sondern auf den nenner prüft

Na, wenn du meinst Wenn das der ganze Sinn dieses "mal 2"-Hokuspokus ist.

Außerdem, wenn du schon auf dieser low-level Ebene Argumentierst:
Du machst in jedem Schleifendurchlauf folgendes:

1)Rufst Eine Funktion auf
2)Übergibst Argumente, diese müssen auf den Stack gelegt werden
3)Es werden sonst noch irgendwelche sachen gemacht (faktisch wird in den Screen-Array geschrieben)
4)return aus der Funktion
Das ist langsamer.

Obwohl deins langsamer ist, ist es vollkommen gleich. Ich glaube, höchstens mit dem QueryPerformanceCounter könnte man hier einen signifikanten unterschied feststellen (wenn überhaupt)
So viel dazu

Du meinst setPixel()? Aber wie willst du dann eine Linie zeichnen?
@durito danke, werde ich mir merken.

randa

Strogij schrieb:

Du meinst setPixel()? Aber wie willst du dann eine Linie zeichnen?
@durito danke, werde ich mir merken.

Ja ich sag ja nix, das ist unter umständen die einzige möglichkeit. Bei mir nicht, ich habe den ScreenPointer Direkt und schreibe auch rein. Ohne funktion.

Was ich noch sagen wollte: Ich höre oft, dass manche sagen, dies und das sei schneller, und begründen dies, indem sie sich unwesentliche dinge in der syntax o.ä. berufen. Ich glaube, es gibt keinen irgend messbaren unterschied zwischen deiner und meiner if-Abfrage, denn es handelt sich hier nur um ein paar bits unterschied. Sowas ist irrelevant. Manche sollten sich lieber drauf konzentrieren, performante algorithmen zu entwerfen, anstatt sich um so irrelevante sachen zu kümmern.

Ist jetzt nicht spezifisch auf dich bezogen, wollte das nur mal gesagt haben, weil du auf die if Anweisung gedeutet hast.

Ne, ist klar das habe ich auch aus der Vorlesung, dass es keinen gewaltigen Unterschied macht ist bei heutigen Prozessoren verständlich (Bresenham's Algo ist ja auch von 1965).

randa

Strogij schrieb:

dass es keinen gewaltigen Unterschied macht ist bei heutigen Prozessoren verständlich (Bresenham's Algo ist ja auch von 1965).

Es macht auch bei uralten Prozessoren keinen unterschied. Du hasts noch nicht ganz gecheckt: es geht nur um ein paar bits!

TGGC

durito schrieb:

Strogij, ignoriere den Typen. Sinnlose und dumme comments zu posten ist sein liebstes (und einziges?) Hobby, also lass ihn labern und lass Dich davon nicht ablenken

Mit persönlichen Beleidigungen kommst du auch nicht weiter.

Bye, TGGC \-/

Ich meine jetzt nur die if-Abfrage.

randa

Strogij schrieb:

Ich meine jetzt nur die if-Abfrage.

die hab ich auch gemeint. Wenn man vom Bresenham-Algorithmus spricht, kann man ja kaum von ein paar bits sprechen.

Ja, das stimmt.

randa

na also