4. Bresenham die 2te

Bresenham die 2te

  • 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
  • V
     

    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 *m;			// 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;

	int array[8][4] =
	{
		{ 0,-1,-1,-1 },		
		{ 0,-1,1,-1 },		
		{ 0,1,-1,1 },		
		{ 0,1,1,1 },		
		{ -1,0,-1,-1 },		
		{ 1,0,1,-1 },		
		{ -1,0,-1,1 },		
		{ 1,0,1,1 },		
	};

	m = array[(X?1:0) + (Y?2:0) + (Z?4:0)];

	int gradient = (db<<1) - da;
	int x = d1x;
	int y = d1y;

	SetPixel(x, y);

	for(int i = 0; i < da; i++)
	{
		if(gradient >= 0)
		{
			x = x + m[2];
			y = y + m[3];
			gradient = gradient + (db<<1) - (da<<1);
		}
		else
		{
			x = x + m[0];
			y = y + m[1];
			gradient = gradient + (db<<1);
		}
		SetPixel(x, y);
	}
}

    ich hoffe der code ist bis auf die SetPixel Funktion Standardkonfrom

    0
Anmelden zum Antworten