4. Bresenham die 2te

Bresenham die 2te

  • V

    Mich fasziniert immer noch der Bresenham Algorithmus (http://www.research.ibm.com/journal/sj/041/ibmsjIVRIC.pdf) – nachdem ich jetzt den Teil "proof the recursive relation" verstanden habe hänge ich jetzt auf Seite 29 rum

    Bisher habe ich es so verstanden:
    Für andere Oktanten müssen einfach Δa und Δb nach einem anderen Schema berechnet werden und die Bewegungsrichtungen anders interpretiert werden.

    Was soll aber die Gleichung
    F(X, Y, Z) = (XZ, YZ, XZ, YZ)?

    was sollen das für Striche über X, Y, Z sein - Negation? - irgendwie verstehe ich den Sinn davon nicht

    Wie kann ich mit F(X, Y, Z) auf die Bewegungsrichtung schließen? Ich muss ja trozdem in der Tabelle nachschauen, welche Kombination für welche Beweungsrichtung steht... mmh

    0
  • 0

    Vielleicht solltest Du dich mal ins Mathe Forum verschieben lassen, ich denke nicht dass hier so viel Leute Ahnung davon haben.
    Ich für meinen Teil zB hab mir den Bresenham Code einfach kopiert, angepasst und war unwissend aber glücklich 🙂

    0
  • V

    hab mir halt gedacht - bevor ich mich mit der großen 3d Programmierung beschäftige lerne ich erst mal wie man eine Linie zeichnet 😉

    Ich hab mir gedacht der bresenham wird nur immer für den ersten oktanten behandlet - der rest wird einfach "gespiegelt"

    Bresenham gibt aber da so tolle Formeln an - aber irgendwie kann ich die nicht richtig interpretieren...

    0
  • R
    Mod

    dich scheint bresenham ja echt in den warnsinn zu treiben

    also wie du sicherlich festgestellt hast, hat bresenham einige fallunterscheidungen. dabei fängt man an, indem man die delta ausrechnet

    DeltaX = x2-x1;
DeltaY = y2-y1;

    nun prüft man, in welchem quadranten man ist. dabei wendet man öfter einen "trick" an, um nicht mehrmals leicht abgeänderten code verwalten zu müssen

    IncX = 1;
if(DeltaX<0)
{
    DeltaX=-DeltaX;
    IncX=-IncX;
}
IncY = 1;
if(DeltaY<0)
{
    DeltaY=-DeltaY;
    IncY=-IncY;
}

    auf diese weise verlagert man das problem Qausi auf den ersten quadranten, weil die Delta positiv sind.

    jetzt gibt es also nur noch die Fallunterscheidung, ob X oder Y größer ist

    if(DeltaX>=DeltaY)
{
... //inner loop
}
else
{
... //inner loop
}

    (das nun erkläre ich für den ersten fall, zweite ist ja analog).

    nun geht's ans eingemachte, dabei ist die sache an sich ganz simpel. man rechnet einfach mit brüchen. im genauen addiert man DeltaY/DeltaX immer aufeinander, sobald der zähler größer oder gleich dem nenner ist (der wert an sich also >=1 ist), ist es zeit einen schritt in Y zu machen.

    schritt für schritt schaut das so aus.

    erstmal wir der nenner definiert, oft als "error" bezeichnet.

    Error = 0;

    die schleife welche nun die linie zeichnet:

    //hier könnte man eigentlich an die position x1,y1 den ersten pixel setzen, 
//das ist zeichenkonventions abhängig
for(int a=0;a<DeltaX;a++)
{
.
.
.
}
//hier könnte man eigentlich an die position x2,y2 den letzten pixel setzen, 
//das ist zeichenkonventions abhängig

    im inneren der schleife muss man nun also x erhöhen

    x1+=IncX;

    den "zähler" muss man nun auch erhöhen.

    Error+=DeltaY;

    falls nun zähler größer als nenner ist, wird die y-position korrigiert und die zahl um 1 (der zähler also um den nenner) erniedrigt

    if(Error>DeltaX)
{
    y1+=IncY;
    Error-=DeltaX;
}

    nun setzt man nur noch den pixel

    Pixel(x1,y1);

    das ganze läuft also darauf hinaus brüche zu addieren.

    beispiel 1.)
    300 pixel in x und 100 in y
    man addiert also immer 1/3, alle 3 durchläuft ist die zahl 1, man geht also alle 3 durchläuft um 1 in y.
    beispiel 2.)
    300 pixel in x und 700 in y
    man addiert also immer 3/7, nach den ersten 3 durchläufen ist die Zahl 9/7, man zieht 7 vom zähler ab und hat 2/7, nach 2 additionen hat man 8/7 und zieht 7 vom zähler ab, sodass man bei 1/7 ist, nach 2 additionen hat man 7/7 und zieht 7 vom zähler ab, sodass man wieder bei 0/7 ist.

    hmm.. ich hoffe ich konnte das ganze einigermassen vermitteln. ich hab das gerade so ausgeworfen und kann nicht garantieren das alles 100%ig richtig ist.

    rapso->greets();

    0

  • Man kann eine Frage offensichtlich auf 2 Weisen ignorieren. 😎

    Bye, TGGC (Ein Jahr Helden)

    0
  • R
    Mod

    mag sein dass ich seine frage einfach nur nicht so verstanden habe wie du es tatst. ich hab aber mal alles erzählt was bresenham ausmacht um ihn zu verstehen und selbst coden zu können. vielleicht hillft es ja vw trotzdem weiter.

    rapso->greets();

    0
  • V

    > also wie du sicherlich festgestellt hast, hat bresenham einige fallunterscheidungen. dabei fängt man an, indem man die delta ausrechnet
    Bresenham schreibt
    Für |dx|-|dy| >= 0 ist
    da = |dx|
    db = |dy|

    Für |dx|-|dy| < 0
    Ist
    da = |dy|
    db = |dx|

    zu wählen (siehe Tabelle 1 Determination of form of Equations 2 and 4)

    Mein Problem liegt hier:

    „To find the form of (4), Boolean variables X, Y, and Z, corresponding to dx, dy, and |dx|-|dy|, are introduced. As shown in Table 1, these variables assume the value 0 or 1, depending on whether or not the correspondent is negative. To determine the assignment of m1, the function

    F(Y, Y, Z) = (XZ, YZ, XZ, YZ),

    found by inspection of Table 1, is introduced. Correspondence between values assumed by F and the assignment of m1 is indicated by columns headed F and m1. Similarly,

    G(X, Y) = (XY, XY, XY, XY)

    is used in conjunction with the G- and m2-columns of Table 1 to make the appropriate assignment to m2.”

    Ich verstehe einfach den Sinn davon nicht

    0
  • V

    meine bisherigen Erkenntnisse lassen sich hier nachlesen:
    http://www.fh-landshut.de/~jamann/Bresenham.doc

    hab eigentlich vor ein Tutorial darüber zu schreiben - leider fehlen mir aber noch 7 Oktanten, die ich behandeln muss 😉

    0
  • V

    *push*

    0

  • @rapso: Nix gegen den Inhalt deiness Posts. Gehört IMHO in die FAQ.
    @Vertex: Das geht analog.

    Bye, TGGC (Ein Jahr Helden)

    0
  • S

    Vertexwahn schrieb:

    hab eigentlich vor ein Tutorial darüber zu schreiben - leider fehlen mir aber noch 7 Oktanten, die ich behandeln muss 😉

    Hast Du ihn denn im 2dimensionalen verstanden?!? 🤡

    0
  • V

    *g* lustig - hilft aber auch nicht gegen meine Doofheit... ich brauch mal wieder was von dem Zeug... wie heißt es... Autocogito

    0
  • V

    > auf diese weise verlagert man das problem Qausi auf den ersten quadranten, weil die Delta positiv sind.

    Dieser Trick funktioniert beim Orginal Bresenham Algo nicht - für einen Plotter ist eine Strecke vom Punkt (0,0) zum Punkt (10,10) etwas anderes wie eine Strecke vom Punkt (10,10) zum Punkt (0,0).

    0
  • R
    Mod

    Vertexwahn schrieb:

    > auf diese weise verlagert man das problem Qausi auf den ersten quadranten, weil die Delta positiv sind.

    Dieser Trick funktioniert beim Orginal Bresenham Algo nicht - für einen Plotter ist eine Strecke vom Punkt (0,0) zum Punkt (10,10) etwas anderes wie eine Strecke vom Punkt (10,10) zum Punkt (0,0).

    das änderst du ja auch nicht. die zeichenrichtung bleibt gleich. das kann ich dir garantieren.

    rapso->greets();

    0
  • V

    @Raspo

    du hast recht die Zeichenrichtung bleibt die gleiche, aber bei einem Plotter wird einmal der Bewegungstyp M2 und einmal der Bewegungstyp M6 benötigt (siehe Bresenham). In der Computergrafik bietet es sich an hier vom Original Bresenham Algorithmus abzuweichen.

    0
  • V

    so hab ich jetzt eine sehr naive Bresnham Implementierung:

    void Bresenham(int d1x, int d1y, int d2x, int d2y)
	{	
		bool X, Y, Z;		// zur Bestimmung der Bewegunsrichtung
		int da, db;			// delta_a und delta_b
		int m1[2], m2[2];	// Bewegungsrichtung/Vektoren

		// delta a, delta b und Bewegungsrichtung bestimmen 
		int dx = abs(d2x) - abs(d1x);
		int dy = abs(d2y) - abs(d1y);

		if(abs(dx)-abs(dy)>=0)
		{
			da = abs(dx);
			db = abs(dy);
			Z = true;
		}
		else
		{
			da = abs(dy);
			db = abs(dx);
			Z = false;
		}

		if(dx >= 0)
			X = true;
		else
			X = false;

		if(dy >= 0)
			Y = true;
		else
			Y = false;

		if(X == true && Y == true && Z == true)
		{
			// m1 = M1
			// m2 = M2
			m1[0] = 1;
			m1[1] = 0;
			m2[0] = 1;
			m2[1] = 1;
		}
		else
		{
			if(X == true && Y == true && Z == false)
			{
				// m1 = M3
				// m2 = M2
				m1[0] = 0;
				m1[1] = 1;
				m2[0] = 1;
				m2[1] = 1;
			}
			else
			{
				if(X == true && Y == false && Z == true)
				{
					// m1 = M1
					// m2 = M8
					m1[0] = 1;
					m1[1] = 0;
					m2[0] = 1;
					m2[1] = -1;
				}
				else
				{
					if(X == true && Y == false && Z == false)
					{
						// m1 = M7
						// m2 = M8
						m1[0] = 0;
						m1[1] = -1;
						m2[0] = 1;
						m2[1] = -1;
					}
					else
					{
						if(X == false && Y == true && Z == true)
						{
							// m1 = M5
							// m2 = M4
							m1[0] = -1;
							m1[1] = 0;
							m2[0] = -1;
							m2[1] = 1;
						}
						else
						{
							if(X == false && Y == true && Z == false)
							{
								// m1 = M3
								// m2 = M4
								m1[0] = 0;
								m1[1] = 1;
								m2[0] = -1;
								m2[1] = 1;
							}
							else
							{
								if(X == false && Y == false && Z == true)
								{
									// m1 = M5
									// m2 = M6
									m1[0] = -1;
									m1[1] = 0;
									m2[0] = -1;
									m2[1] = -1;
								}
								else
								{
									// m1 = M7
									// m2 = M6
									m1[0] = 0;
									m1[1] = -1;
									m2[0] = -1;
									m2[1] = -1;
								}
							}
						}
					}
				}
			}
		}

		int gradient = 2 * db - da;
		int x = d1x;
		int y = d1y;

		SetPixel(x, y, 0, 255, 0);

		for(int i = 0; i < da; i++)
		{
			if(gradient >= 0)
			{
				x = x + m2[0];
				y = y + m2[1];
				gradient = gradient + 2 * db - 2 * da;
			}
			else
			{
				x = x + m1[0];
				y = y + m1[1];
				gradient = gradient + 2 * db;
			}

			SetPixel(x, y, 0, 255, 0);
		}
	}
    0

  • Die vielen verschachtelten ifs gefallen mir. Hat viel mehr Stil als nur so'n billiges Array... 😎

    Bye, TGGC (Ein Jahr Helden)

    0
  • V

    > Die vielen verschachtelten ifs gefallen mir. Hat viel mehr Stil als nur so'n billiges Array... 😎

    versteh ich nicht - kann kein C++ 😉

    wie würde man das mit Arrays lösen?

    ist es nicht viel schlimmer das ich mit zwei Multipliziere anstatt zu shiften?
    ist es nicht viel schlimmer das ich haufenweiße Variablen in der Funktion 70 mal in der Sekunde auf den Stack haue und dann wieder runterwerfe? 😉

    nö - jetzt im ernst - wie geht das mit Arrays?

    ich wollte es erst mit switch lösen 😉

    0 

  • array[8][4]={ { 0,1,0,1 }, ...
m= array[X?1:0+Y?2:0+Z?4:0][n]

    Indizes könnten auch vertauscht dein.

    Bye, TGGC (Ein Jahr Helden)

    0
  • V

    naja ich hab es nicht umsonst "naive" Implementierung genannt 😉 - ich könnte mir die hälfte der Fallunterscheidungen sparen wenn ich einfach den Endpunkt immer rechts vom Anfangspunkt setze ... ich will da jetzt gar nicht großartig zu optimieren anfangen, weil das eh keinen sinn hat, wenn man wie ich keine Ahnung von der Hardware hat (wie ich)

    z. B. wäre es sicherlich sinnvoll einen inkrementier befehl zu benutzen - weil der schneller wie die Subtraktion ist (Intel hat doch da extra den Befehl inc) usw. aber da kenn ich mich zu wenig aus und außerdem hat mir nur das Dokument von Bresenham interessiert und nicht das ich wirklich mal ernsthaft eine line zeichnen kann - ich bin da ein knallharter Theoretiker 😉

    0
Anmelden zum Antworten