[A] Primitive zeichnen

[Vertexwahn]

Als Word2003: http://loop.servehttp.com/~vertexwahn/RunLengthSlice.pdf
Als PDF: http://loop.servehttp.com/~vertexwahn/RunLengthSlice.doc

Rastern von Strecken mit „RUN LENGTH SLICE ALGORITHM FOR INCREMENTAL LINES“

Vorwort

Stellt man in einem Forum die Frage wie man eine Strecke Rastern kann, dann wird häufig der Bresenham Algorithmus empfohlen. Zum Bresenham Algorithmus gibt es zahlreiche Artikel und Beschreibungen in Büchern zu finden (z. B. http://loop.servehttp.com/~vertexwahn/oldwiki/public_html_an_turing/bresenham.html). Ich möchte hier auf einen anderen Algorithmus eingehen, der ebenfalls von Jack Bresenham stammt und einige Jahre später veröffentlicht wurde und zeigen welchen Vorteil dieses Verfahren gegenüber dem Bresenham Algorithmus bringt.

Das Problem

Ein Raster besteht aus Pixel, die man sich idealisiert gitterförmig angeordnet vorstellen kann. Jedes Pixel einer Rastergrafik besitzt eine eindeutige Position, die durch ganzzahlige kartesische Koordinaten beschrieben werden kann.

Will man eine Strecke auf einem Raster darstellen so muss man sich Gedanken darüber machen wie man diese am besten durch Pixel des Rasters annähern kann. Im weiteren Verlauf werden dabei nur Strecken betrachtet die Start- und Endpunkte mit ganzzahligen Koordinaten besitzen.

Eine Strecke wird beschreiben durch einen Start und einen Endpunkt. Eine Strecke besitzt dabei eine bestimmte Ausdehnung in x bzw. y-Richtung. Die Achse, entlang welcher die größte Ausdehnung der Strecke stattfindet, wird als Hauptachse bezeichnet, die andere als Nebenachse.

Annäherung an die ideale Gerade

Im folgendem sollen nur Strecken betrachtet werden mit einer Steigung . Der Startpunkt der Strecke soll immer Ursprung (0|0) liegen. Der Endpunkt besitzt die Koordinaten (a|b). Später werden wir das Verfahren so abändern, so dass es für alle Steigungen funktioniert.

Die ideale Gerade wird beschrieben durch die Geradengleichung . Um eine möglichst gute Annährung an die ideale Gerade zu erreichen wird immer das Pixel gewählt, das den geringsten Abstand zur idealen Gerade aufweißt. D. h. ergibt sich der y-Wert 4.6 nach dem Auflösen der obigen Gleichung für einen bestimmten x-Wert so hat man die Auswahl zwischen dem y-Wert 4 oder 5. In diesem Fall wählt man den y-Wert 5, da dieser einen geringeren Abstand zur idealen Gerade besitzt wie der y-Wert 4.

Die Beobachtung

Betrachtet man verschiedene Strecken, so stellt man ein Muster fest:

Strecken bestehen aus horizontalen oder vertikalen Strecken, die sich nur in ihrer Länge unterscheiden. Diese bezeichne ich im Folgenden als Segmente. Das auffallende an diesen Segmenten ist, dass jede Strecke aus maximal vier verschiedenen langen Segmenten besteht. Weiter lassen sich innere und äußere Segmente unterscheiden. Zu den äußeren Segmenten gehören das letzte und das erste Segment. Das besondere an den äußeren Segmenten ist, das diese entweder gleich lang sind, oder sich maximal um ein Pixel in ihrer Länge unterscheiden. Gleiches gilt für die inneren Segmente. Diese sind alle gleich lang oder unterscheiden sich durch maximal ein Pixel. Man kann also innere und äußere Segemente unterschieden. Diese werden wiederum in kurze oder lange Segmente eingeteilt:

Länge langes äußeres Segment = Länge kurzes äußeres Segment + l
Länge langes inneres Segment = Länge kurzes inneres Segment + l

Die Idee

Eine Möglichkeit eine Strecke zu rastern ist folgende. Man ermittelt zunächst die Länge der einzelnen Segmente. Nun schreitet man entlang der Nebenachse der Gerade Pixel für Pixel und zeichnet jeweils die entsprechenden Segmente.

Wie aber ermittelt man die Länge dieser Segmente?

Beim ersten und letzten Segment muss die Strecke um ein halbes Pixel steigen. Bei den inneren Segmenten muss die Strecke jeweils um ein ganzes Pixel steigen. Anhand der Steigung lässt sich berechnen, welchen Weg man zurücklegen muss, um ein bzw. ein halbes Pixel zu steigen.

Im folgendem möchte ich auf einen Algorithmus von Jack Bresenham eingehen, den er in dem Artikel „RUN LENGTH SLICE ALGORITHM FOR INCREMENTAL LINES“ beschrieben hat. Dieser Artikel ist nicht mit dem Bresenham Algorithmus zu verwechseln.

Etwas Mathematik

Bevor es aber los geht möchte ich etwas Mathematik einführen. Zunächst die Gaußklammer:

Diese wird auch als Abrundungsfunktion bezeichnet und rundet immer auf die nächst kleinere oder gleiche ganze Zahl.

Als entsprechendes Pendant gibt es auch die Aufrundungsfunktion:

Beispiele:

Außerdem gilt:

Jetzt fehlt uns zu unserm Glück nur noch die Modulo Operation (Teilen mit Rest):

In der Programmiersprache C++ erfüllt der Modulo Operator % für positive ganze Zahlen den gleichen Zweck.

Die Modulo Operation ist einfach Teilen mit Rest wobei der Rest das Ergebnis ist:

Der Übergangspunkt

In folgender Skizze sind die Übergangspunkte orange markiert.

Der Übergangspunkt ist der Punkt an dem im nächsten Schritt eine diagonale Bewegung des Plotters erforderlich ist (Man kann sich vorstellen, das ein Plotter die Linie abfahren muss, in Programmcode sieht eine Horizontale Bewegung des Plotters so aus: x++, eine Diagonale so: x++;y++).

Die Übergangspunkte können durchnummeriert werden. Der i-te Übergangspunkt hat die x-Koordinate .

Zwischen zwei aufeinander folgenden Übergangspunkten und sind genau horizontale Bewegungen des Plotters nötig.

Berechnung der Übergangspunkte

In folgender Skizze ist der Schnittpunkt der idealen Geraden mit den horizontalen
Geraden mit den Gleichungen in blauer Farbe gezeigt.

Die blauen Schnittpunkte besizten die Koodinaten P(a,b) mit

Der Übergangspunkt i besitzt die Koordinaten

Besonderheit bei der Berechnung der Übergangspunkte

Wir sind aus dem Alltag gewohnt ab 0.5 Aufzurunden. Das heißt ergäbe sich der y-Wert 3.5 so würden wir auf 4 aufrunden. Bei der Annäherung an die ideale Gerade wollen wir immer den y-Wert wählen der näher am realen y-Wert liegt. Bei 3.5 spielt es deshalb keine Rolle, ob man 3.0 oder 4.0 wählt. Bresenham rundet in seinen Artikel bei 0.5 ab, statt wie aus den Alltag gewohnt aufzurunden. Ich verfahre in diesem Artikel genau so, jedoch werde ich am Ende zeigen wie man den Algotihmus ganz einfach so umstellen kann, so dass er ab 0.5 aufrundet statt abrundet.

Im obigen Beispiel ist der Schnittpunkt der Idealen Gerade blau markiert – er hat den y-Wert 0.5. Würde man ab 0.5 aufrunden statt abrunden würde sich folgender Geradenverlauf ergeben:

Wildes Umformen

Klar ist:

Durch umformen ergibt sich:

Für die weiteren Berechnungen werden die folgenden Konstanten eingeführt:

Da

und

gilt, kann man auch schreiben:

Da und ganze positive Zahlen sind kann man auch schreiben:

Damit ergibt sich:

Vereinfacht man diesen Ausdruck erhält man

Führt man folgende Folgen eine

so lässt sich der Ausdruck weiter umformen:

Bis jetzt haben wir einfach nur stur umgeformt ohne uns große Gedanken darüber zu machen welchen Sinn diese Umformungen hatten. Der Sinn dieser Umformungen war es zu zeigen, dass ein Horizontaler Lauf immer Q oder Q-1 horizontale Schritte lang ist. Warum das so ist sehen wir hier:

kann maximal werden
kann maximal werden

Damit kann maximal
werden.

Anders formuliert:

lässt sich aus berechnen.

, dann
, dann

Warum ist das so? Wie unterscheiden sich und ?

Wie man sieht unterschieden sich und im wesentlichem nur durch und

Wie unterscheiden sich und ?

Zurück zur anfänglichen Frage: Wie unterscheiden sich und ?

Für das erste Segement sind genau horizontale Bewegungen des Plotters nötig.

Betrachten wir nun das letzte Segment.

Allgemein gilt:
.

Damit ergibt sich für das letzte Segment:

Da <1, gilt:

Die Implementierung

template <typename T>
void try1(CImg<T>& img, int x1, int y1, int x2, int y2)
{
	assert(x1 == 0);
	assert(y1 == 0);

	int dA = x2 - x1;
	int dB = y2 - y1;

	assert(dA > dB);
	assert(dA > 0);
	assert(dB > 0);

	int M = dA / (2*dB);
	int N = dA % (2*dB);
	int Q = dA / dB;
	int R = dA % dB;

	draw_pixel(img, x1, y1);

	int currentX = x1;
	int currentY = y1;

	// 1ter lauf
	for(int i = 0; i < M; i++)
	{
		currentX++;
		draw_pixel(img, currentX, currentY);
	}

	currentX++;
	currentY++;
	draw_pixel(img, currentX, currentY);

	// d0 berechnen
	int di = N + 2*R - 2*dB;

	assert(di < 0);

	while(currentY < y2)
	{
		if(di < 0)
		{
			for(int i = 0; i < Q-1; i++)
			{
				currentX++;
				draw_pixel(img, currentX, currentY);
			}
			currentX++;
			currentY++;
			draw_pixel(img, currentX, currentY);

			di += 2*R;
		}
		else
		{
			for(int i = 0; i < Q; i++)
			{
				currentX++;
				draw_pixel(img, currentX, currentY);
			}
			currentX++;
			currentY++;
			draw_pixel(img, currentX, currentY);

			di += 2*R - 2*dB;
		}
	}

	// Letztes Segment
	if(N==0)
	{
		for(int i = 0; i < M-1; i++)
		{
			currentX++;
			draw_pixel(img, currentX, currentY);
		}
	}
	else
	{
		for(int i = 0; i < M; i++)
		{
			currentX++;
			draw_pixel(img, currentX, currentY);
		}
	}
}

Störend an dieser Implemntierung ist, dass sie nur für den 1. Oktanden Funktioniert und bei 0.5 nicht auf, sondern abrundet.

Durch umstellen des Vergleiches auf „kleiner“ auf „kleiner gleich“ und Rücksichtnahme beim Zeichnen des ersten und letzten Segements, kann man die Funktion so umprogrammieren, dass sie ab 0.5 aufrundet:

template <typename T>
void try2(CImg<T>& img, int x1, int y1, int x2, int y2)
{
	assert(x1 == 0);
	assert(y1 == 0);

	int dA = x2 - x1;
	int dB = y2 - y1;

	assert(dA > dB);

	int M = dA / (2*dB);
	int N = dA % (2*dB);
	int Q = dA / dB;
	int R = dA % dB;

	draw_pixel(img, x1, y1);

	int currentX = x1;
	int currentY = y1;

	// 1ter lauf
	if(N==0)
	{
		for(int i = 0; i < M-1; i++)
		{
			currentX++;
			draw_pixel(img, currentX, currentY);
		}
	}
	else
	{
		for(int i = 0; i < M; i++)
		{
			currentX++;
			draw_pixel(img, currentX, currentY);
		}
	}

	currentX++;
	currentY++;
	draw_pixel(img, currentX, currentY);

	// d0 berechnen
	int di = N + 2*R - 2*dB;

	while(currentY < y2)
	{
		if(di <= 0)
		{
			for(int i = 0; i < Q-1; i++)
			{
				currentX++;
				draw_pixel(img, currentX, currentY);
			}
			currentX++;
			currentY++;
			draw_pixel(img, currentX, currentY);

			di += 2*R;
		}
		else
		{
			for(int i = 0; i < Q; i++)
			{
				currentX++;
				draw_pixel(img, currentX, currentY);
			}
			currentX++;
			currentY++;
			draw_pixel(img, currentX, currentY);

			di += 2*R - 2*dB;
		}
	}

	// Letztes Segment

	//if(N==0)
	//{
	//	for(int i = 0; i < M-1; i++)
	//	{
	//		currentX++;
	//		draw_pixel(img, currentX, currentY);
	//	}
	//}
	//else
	//{
		for(int i = 0; i < M; i++)
		{
			currentX++;
			draw_pixel(img, currentX, currentY);
		}
	//}
}

Störend ist natürlich immer noch die Tatsache, dass der Algorithmus nur für den 1. Oktanten funktioniert und für die Startkoordinaten nur (0|0) zulässt.

Nutzt man Symmetrieeigenschaften aus so lässt sich der Algorithmus erweitern auf beliebige Steigungen:

template <typename T>
void try4(CImg<T>& img, int x1, int y1, int x2, int y2)
{
	int x = x1;
	int y = y1;
	draw_pixel(img, x, y);

	// 1.
	int dx = x2-x1;
	int dy = y2-y1;

	int adx = abs(dx);
	int ady = abs(dy);

	int da;// = max(adx,ady);
	int db;// = min(adx,ady);
	if(adx > ady)
	{
		da = adx;
		db = ady;
	}
	else
	{
		da = ady;
		db = adx;
	}

	int pB = db > da-db ? da-db : db;//min(db,da-db);

	// 2.
	int m21 = dx >= 0 ? 1 : -1;
	int m22 = dy >= 0 ? 1 : -1;

	int m11, m12;

	if(adx >= ady)
	{
		m11 = m21;
		m12 = 0;
	}
	else
	{
		m11 = 0;
		m12 = m22;
	}

	// 3.
	int s11;
	int s12;
	int s21;
	int s22;

	if(da < 2*pB || 
	   (da == 2*pB && dy < 0))
	{
		s11 = m21;
		s12 = m22;
		s21 = m11;
		s22 = m12;
	}
	else
	{
		s11 = m11;
		s12 = m12;
		s21 = m21;
		s22 = m22;
	}

	// 4.
	int LastRun = da;

	if(pB != 0)
	{
		// 5.
		int /*Q = da / pB;*/                       Q = da / db;
		int /*R = da % pB;*/                       R = da % db;
		int /*M = Q / 2;*/						   M = da / (2*db);
		int /*N = Q & 0x1 ? R + pB : R;*/          N = da % (2*db);
		int H = (dy < 0) && (N==0) ? M-1 : M;

		LastRun = (dy > 0) && (N==0) ? M-1 : M;

		//int Count = pB;
		int Count = db;

		int d = (dy >= 0) ? N+2*R-2*pB : (N+2*R-2*pB - 1);

		// 6.
		for(int i = 0; i < H; i++)
		{
			x += s11;
			y += s12;

			draw_pixel(img, x, y);
		}

		x += s21;
		y += s22;

		draw_pixel(img, x, y);

		while(true)
		{
			// 7.
			Count--;

			// 8.
			if(Count <= 0)
				break;

			// 9.
			H = d < 0 ? Q-1 : Q;

			// 10.
			for(int i = 0; i < H; i++)
			{
				x += s11;
				y += s12;

				draw_pixel(img, x, y);
			}

			x += s21;
			y += s22;

			draw_pixel(img, x, y);

			// 11.
			if(d<0)
			{
				d = d + 2*R;
			}
			else
			{
				d = d + 2*R - 2*db;
			}
		}
	}

	// 13.
	for(int i = 0; i < LastRun; i++)
	{
		x += s11;
		y += s12;

		draw_pixel(img, x, y);
	}
}

Ich habe noch eine weitere Variante implementiert die ebenfalls alle Steigungen abdeckt:

void try3(CImg<T>& img, int x1, int y1, int x2, int y2)
{
	// (x1,y1) = Koordinaten des linken Punktes
	// (x2,y2) = Koordinaten des rechten Punktes
	if(x1 > x2)
	{
		swap(x1,x2);
		swap(y1,y2);
	}

	// Horizontalle Gerade
	if (y1==y2)
	{
		for(int x = x1; x <= x2; x++)
			draw_pixel(img, x, y1);

		return;
	}

	if(x1==x2)
	{
		int miny, maxy;
		if(y1>y2)
		{
			maxy = y1;
			miny = y2;
		}
		else
		{
			maxy = y2;
			miny = y1;
		}
		for(int y = miny; y <= maxy; y++)
			draw_pixel(img, x1, y);

		return;
	}

	try3_LightSlope(img, x1, y1, x2, y2);
}

template <typename T>
void try3_LightSlope(CImg<T>& img, int x1, int y1, int x2, int y2)
{
	int dA = x2 - x1;
	int dB = y2 - y1;

	assert(dA > 0);

	// Steigung negativ?
	if (dB < 0)
	{
		try3_LightNegativSlope(img,x1,y1,x2,y2-2*dB,dA,-dB);
		return;
	}

	// Steigung größer 1?
	if(dA < dB)
	{
		// x mit y Vertauschen
		try3_HeavyPositiveSlope(img,y1,x1,y2,x2,dB,dA);
		return;
	}

	int M = dA / (2*dB);
	int N = dA % (2*dB);
	int Q = M*2;//dA / dB;
	int R = dA % dB;

	draw_pixel(img, x1, y1);

	int currentX = x1;
	int currentY = y1;

	// 1ter lauf
	if(N==0)
	{
		for(int i = 0; i < M-1; i++)
		{
			currentX++;

			draw_pixel(img, currentX, currentY);
		}
	}
	else
	{
		for(int i = 0; i < M; i++)
		{
			currentX++;
			draw_pixel(img, currentX, currentY);
		}
	}

	currentX++;
	currentY++;
	draw_pixel(img, currentX, currentY);

	// d0 berechnen
	int di = N + 2*R - 2*dB;

	while(currentY < y2)
	{
		if(di <= 0)
		{
			for(int i = 0; i < Q-1; i++)
			{
				currentX++;
				draw_pixel(img, currentX, currentY);
			}
			currentX++;
			currentY++;
			draw_pixel(img, currentX, currentY);

			di += 2*R;
		}
		else
		{
			for(int i = 0; i < Q; i++)
			{
				currentX++;
				draw_pixel(img, currentX, currentY);
			}
			currentX++;
			currentY++;
			draw_pixel(img, currentX, currentY);

			di += 2*R - 2*dB;
		}
	}

	// Letztes Segment
	for(int i = 0; i < M; i++)
	{
		currentX++;
		draw_pixel(img, currentX, currentY);
	}
}

template <typename T>
void try3_HeavyPositiveSlope(CImg<T>& img, int x1, int y1, int x2, int y2, int dA, int dB)
{

	int M = dA / (2*dB);
	int N = dA % (2*dB);
	int Q = M*2;//dA / dB;
	int R = dA % dB;

	draw_pixel(img, y1, x1);

	int currentX = x1;
	int currentY = y1;

	// 1ter lauf
	if(N==0)
	{
		for(int i = 0; i < M-1; i++)
		{
			currentX++;

			draw_pixel(img, currentY, currentX);
		}
	}
	else
	{
		for(int i = 0; i < M; i++)
		{
			currentX++;
			draw_pixel(img, currentY, currentX);
		}
	}

	currentX++;
	currentY++;
	draw_pixel(img, currentY, currentX);

	// d0 berechnen
	int di = N + 2*R - 2*dB;

	while(currentY < y2)
	{
		if(di <= 0)
		{
			for(int i = 0; i < Q-1; i++)
			{
				currentX++;
				draw_pixel(img, currentY, currentX);
			}
			currentX++;
			currentY++;
			draw_pixel(img, currentY, currentX);

			di += 2*R;
		}
		else
		{
			for(int i = 0; i < Q; i++)
			{
				currentX++;
				draw_pixel(img, currentY, currentX);
			}
			currentX++;
			currentY++;
			draw_pixel(img, currentY, currentX);

			di += 2*R - 2*dB;
		}
	}

	// Letztes Segment
	for(int i = 0; i < M; i++)
	{
		currentX++;
		draw_pixel(img, currentY, currentX);
	}
}

template <typename T>
void try3_LightNegativSlope(CImg<T>& img, int x1, int y1, int x2, int y2, int dA, int dB)
{
	// Steigung größer 1?
	if(dA < dB)
	{
		// x mit y Vertauschen
		try3_HeavyNegativeSlope(img,y1,x1,y2,x2,dB,dA);
		return;
	}

	int M = dA / (2*dB);
	int N = dA % (2*dB);
	int Q = M*2;//dA / dB;
	int R = dA % dB;

	draw_pixel(img, x1, y1);

	int currentX = x1;
	int currentY = y1;

	// 1ter lauf
	if(N==0)
	{
		for(int i = 0; i < M-1; i++)
		{
			currentX++;

			draw_pixel(img, currentX, -(currentY-y1)+y1);
		}
	}
	else
	{
		for(int i = 0; i < M; i++)
		{
			currentX++;
			draw_pixel(img, currentX, -(currentY-y1)+y1);
		}
	}

	currentX++;
	currentY++;
	draw_pixel(img, currentX, -(currentY-y1)+y1);

	// d0 berechnen
	int di = N + 2*R - 2*dB;

	while(currentY < y2)
	{
		if(di <= 0)
		{
			for(int i = 0; i < Q-1; i++)
			{
				currentX++;
				draw_pixel(img, currentX, -(currentY-y1)+y1);
			}
			currentX++;
			currentY++;
			draw_pixel(img, currentX, -(currentY-y1)+y1);

			di += 2*R;
		}
		else
		{
			for(int i = 0; i < Q; i++)
			{
				currentX++;
				draw_pixel(img, currentX, -(currentY-y1)+y1);
			}
			currentX++;
			currentY++;
			draw_pixel(img, currentX, -(currentY-y1)+y1);

			di += 2*R - 2*dB;
		}
	}

	// Letztes Segment
	for(int i = 0; i < M; i++)
	{
		currentX++;
		draw_pixel(img, currentX, -(currentY-y1)+y1);
	}
}

template <typename T>
void try3_HeavyNegativeSlope(CImg<T>& img, int x1, int y1, int x2, int y2, int dA, int dB)
{

	int M = dA / (2*dB);
	int N = dA % (2*dB);
	int Q = M*2;//dA / dB;
	int R = dA % dB;

	draw_pixel(img, y1, x1);

	int currentX = x1;
	int currentY = y1;

	// 1ter lauf
	if(N==0)
	{
		for(int i = 0; i < M-1; i++)
		{
			currentX++;

			draw_pixel(img, currentY, -(currentX-x1)+x1);
		}
	}
	else
	{
		for(int i = 0; i < M; i++)
		{
			currentX++;
			draw_pixel(img, currentY, -(currentX-x1)+x1);
		}
	}

	currentX++;
	currentY++;
	draw_pixel(img, currentY, -(currentX-x1)+x1);

	// d0 berechnen
	int di = N + 2*R - 2*dB;

	while(currentY < y2)
	{
		if(di <= 0)
		{
			for(int i = 0; i < Q-1; i++)
			{
				currentX++;
				draw_pixel(img, currentY, -(currentX-x1)+x1);
			}
			currentX++;
			currentY++;
			draw_pixel(img, currentY, -(currentX-x1)+x1);

			di += 2*R;
		}
		else
		{
			for(int i = 0; i < Q; i++)
			{
				currentX++;
				draw_pixel(img, currentY, -(currentX-x1)+x1);
			}
			currentX++;
			currentY++;
			draw_pixel(img, currentY, -(currentX-x1)+x1);

			di += 2*R - 2*dB;
		}
	}

	// Letztes Segment
	for(int i = 0; i < M; i++)
	{
		currentX++;
		draw_pixel(img, currentY, -(currentX-x1)+x1);
	}
}

Vergleich mit dem Bresenham Algorihtmus

Nach der Implementierung dieser zwei verschiedenen Varianten, die mit beliebigen Steigungen zurecht kommen hab ich einen kleinen Performance test mit dem Bresenham Algorihtmus durchgeführt, wobei folgende implementierung des Bresenham Algotihmus verwendet wurde:

template <typename T>
void Bresenham(CImg<T>& img, int d1x, int d1y, int d2x, int d2y) 
{    
	//unsigned char r=0,g=255,b=0;

	bool Z = true;     // zur Bestimmung der Bewegunsrichtung 
	int *m;            // Bewegungsrichtung/Vektoren 

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

	int da = abs(dx), db = abs(dy); 

	if(da-db<0)
	{
		int tmp = da;
		da = db;
		db = tmp;
		Z = false;
	}

	bool X = (dx >= 0); 
	bool Y = (dy >= 0); 

	static 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 = 2 * db - da; 
	int x = d1x; 
	int y = d1y; 

	//draw_pixel(img, x,y,r,g,b); 
	draw_pixel(img, x,y); 

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

		//draw_pixel(img, x,y,r,g,b); 
		draw_pixel(img, x,y); 
	} 
}

Um die Performance zu vergleichen können wurde folgendes Testprogramm angefertigt:

int main() 
{	
	CImg<unsigned char> img(640,400,1,3);	
	img.fill(255, 255, 255);		

	DWORD time = GetCurrentTime();

	for(int i=0; i<1000000;i++)
	{
		int x2=rand()%400;
		int y2=rand()%400;
		int x1=rand()%400;
		int y1=rand()%400;

		//Bresenham(img, x1,y1,x2,y2);
		//try3(img, x1,y1,x2,y2);
		try4(img, x1,y1,x2,y2);
	}

	std::cout<<"Dauer: "<<GetCurrentTime() - time<<std::endl;

	//img.save_png("test.png");
	img.display("Line Drawing");			// Display the image in a display window.

	return 0;
}

Folgendes Ergebnis ergab die Messung:

Die Implementierung try4 war in etwa so schnell wie der Bresenham Algorithmus. Die Variante try3 war die schnellste. Sieht man sich jedoch die Variante try3 genauer an, so stellt man fest, dass diese mehrere 100 Zeilen Code umfasst. Es ist fraglich, ob man mit dem Bresenham Algorithmus mit speziellen Code für bestimmte Steigungstypen nicht auch ähnliche Ergebnisse erreichen kann wie mit der Variaten try3.

Der „RUN LENGTH SLICE ALGORITHM FOR INCREMENTAL LINES” kann erst seinen Vorteil ausspielen wenn es lange horizontale oder vertikale Läufe gibt. Für beliebige Strecken ist aber der Algorithmus in etwa gleich auf mit dem Bresenham Algorithmus. Weiß man also zuvor nicht mit welcher Art von Gerade man es zu tun hat, so empfiehlt sich der Bresenham Algorithmus.

[estartu]

Fang zur Not einfach an und wenn es zu viel wird bzw. sich Auskopplungen lohnen kannst du es ja splitten.
Generell bietet sich aber bei deinem Thema eine Serie an, da man als Leser dann nicht vom Stoff erschlagen wird.

Ich würde mit einem Artikel als Grobüberblick anfangen und dann nach und nach alles abhandeln.
Wenn der Beginn des Threadtitels immer gleich ist, findet man das auch schön wieder.

[Ben04]

Schreib einfach mal einen Teil und skizziere den Rest, also Überschrift und ein paar Stichwörter und poste es mal. Dann lässt sich besser darüber reden. Falls es sich als zu lang rausstellen würde lässt sich in dem Fall noch einfach splitten und nicht viel Arbeit war um sonst.

[estartu]

Es ist doch auch sonst nichts umsonst, umstellen kann man immer noch - nur das macht zusätzliche Arbeit.

[Ben04]

estartu schrieb:

Es ist doch auch sonst nichts umsonst, umstellen kann man immer noch - nur das macht zusätzliche Arbeit.

Einleitung, Überleitung, Schlussfolgerung, "roter Faden" es gibt schon einige Sachen die man bei einer Umstellung neu machen muss.

[Vertexwahn]

ich werde zunächst mal das Rastern von Linien abhandeln - dazu werde ich einen erweiteten Bresenham Algo verwenden

[Vertexwahn]

#include "CImg-1.2.2.1\CImg.h"
#include <iostream>
using namespace cimg_library;

///////////////////////////////////////////////////////////////////////////////////////////
// Setzt ein bestimmtes Pixel in einer Rastergrafik.
template <class T>
void draw_pixel(CImg<T>& img, int x, int y, T red = 255, T green = 0, T blue = 0)
{
	if(x < 0 ||
	   y < 0 ||
	   img.height < y ||
	   img.width < x)
	   return;

	unsigned char color[3]={red,green,blue};	// Define a purple color
	y = img.height-y-1;
	img.draw_line(x,y,x,y,color);

}
///////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////
// Vertauscht die Werte zweier Variablen.
template <typename T>
void swap(T& x, T& y)
{
	T tmp = x;
	x = y;
	y = tmp;
}
///////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////
// Vom linken zum rechten Punkt laufen.
template <class T>
void draw_line1(CImg<T>& img, int x1, int y1, int x2, int y2)
{
	// (x1,y1) = Koordinaten des linken Punktes
	// (x2,y2) = Koordinaten des rechten Punktes
	if(x1 > x2)
	{
		swap(x1,x2);
	    swap(y1,y2);
	}

	// Steigung berechnen
	float m = float(y2 - y1) / (x2 - x1);

	// y-Achsen Abschnitt berechnen
	float t = y1 - m * x1;

	for(int x = x1; x <= x2; x++)
	{
		float y = m*x+t;

		draw_pixel(img, x,y+0.5); // ab 0.5 wird aufgerundet
	}
}
///////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////
// Vom unten nach oben laufen.
template <class T>
void draw_line2(CImg<T>& img, int x1, int y1, int x2, int y2)
{
	// (x1,y1) = Koordinaten des unteren Punktes
	// (x2,y2) = Koordinaten des oberen Punktes
	if(y1 > y2)
	{
		swap(x1,x2);
	    swap(y1,y2);
	}

	// Steigung berechnen
	float m = float(y2 - y1) / (x2 - x1);

	// y-Achsen Abschnitt berechnen
	float t = y1 - m * x1;

	for(int y = y1; y <= y2; y++)
	{
		float x = (y-t)/m;

		draw_pixel(img, x+0.5,y); // ab 0.5 wird aufgerundet
	}
}

///////////////////////////////////////////////////////////////////////////////////////////
/// Findet heraus entlang welche Achse (x oder y) die Strecke am längsten ist und wählt 
/// dann den geeigenten Algorihtmus
template <class T>
void draw_line3(CImg<T>& img, int x1, int y1, int x2, int y2)
{
	int x_axis_length = abs(x1-x2);
	int y_axis_length = abs(y1-y2);

	if(x_axis_length > y_axis_length)
	{
		draw_line1(img, x1, y1, x2, y2);
	}
	else
	{
		draw_line2(img, x1, y1, x2, y2);
	}
}
///////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////
// Symmetrie Eigenschaften ausnutzen. Ein Punkt im Oktant 1 mit (x,y) kann auf Oktant 2 
// abgebildet werden indem man die x und y Werte einfach vertauscht.
template <class T>
void draw_line4(CImg<T>& img, int x1, int y1, int x2, int y2)
{
	int x_axis_length = abs(x1-x2);
	int y_axis_length = abs(y1-y2);

	// x- und y-Werte vertauschen wenn y-Achse Hauptachse ist
	if(x_axis_length <= y_axis_length)
	{
		swap(x1,y1);
		swap(x2,y2);
	}

	// (x1,y1) = Koordinaten des linken Punktes
	// (x2,y2) = Koordinaten des rechten Punktes
	if(x1 > x2)
	{
		swap(x1,x2);
		swap(y1,y2);
	}

	// Steigung berechnen
	float m = float(y2 - y1) / (x2 - x1);

	// y-Achsen Abschnitt berechnen
	float t = y1 - m * x1;

	for(int x = x1; x <= x2; x++)
	{
		float y = m*x+t;

		if(x_axis_length > y_axis_length)
			draw_pixel(img, x,y+0.5); // ab 0.5 wird aufgerundet
		else
			draw_pixel(img, y+0.5,x); // Hier werden die zuvor vertauschten Werte wieder zurückgetäuscht
	}
}
///////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////
// Experiment
template <class T>
void draw_horizontal_line(CImg<T>& img, int x1, int x2, int y)
{
	for(int x = x1; x <= x2; x++)
	{
		draw_pixel(img, x, y);
	}
}

template <class T>
void draw_line5(CImg<T>& img, int x1, int y1, int x2, int y2)
{
	// vorerst nur 1. Oktant mit steigung   m € ]0;1[
	// und x1 < x2
	// und y1 < y2

	int a = abs(x1-x2);
	int b = abs(y1-y2);
	int r = a % b;
	int e = a % (2*b);

	int outer_run_length_short = a / (2*b);
	int inner_run_length_short = a / b;

	if(e == 0)
	{
		draw_horizontal_line(img, x1, x1+outer_run_length_short+1,y1);
		x1+= outer_run_length_short + 1 +1;
	}
	else
	{
		draw_horizontal_line(img, x1, x1+outer_run_length_short,y1);
		x1+= outer_run_length_short + 1;
	}

	e += r;

	if(e > b)
		e -= b;

	for(int y = y1+1; y < y2; y++)   // von unten nach oben zeichnen
	{
		if(e + r >= b)
		{
			draw_horizontal_line(img, x1, x1+ inner_run_length_short + 1, y);
			x1+= inner_run_length_short + 1 +1;
		}
		else
		{
			draw_horizontal_line(img, x1, x1+ inner_run_length_short, y);
			x1+= inner_run_length_short + 1;
		}	

		e += r;

		if(e > b)
			e -= b;
	}

	draw_horizontal_line(img, x1, x1+outer_run_length_short,y2);
}

template <typename T>
class Vector2D
{
public:
	Vector2D(T x, T y)
	{
		m_X = x;
		m_Y = y;
	}

	T getX()
	{
		return m_X;
	}

	T getY()
	{
		return m_Y;
	}
private:
	T m_X;
	T m_Y;
};

template <typename T>
class StraightLine2D
{
public:
	StraightLine2D(int x1, int y1, int x2, int y2)
	{
		m_Slope = T(y2 - y1) / T(x2 - x1);

		// y=mx+t
		// t=y-mx
		m_Intercept = y1-m_Slope*x1;
	}

	StraightLine2D(T slope, T intercept)
	{
		m_Slope = slope;
		m_Intercept = intercept;
	}

	StraightLine2D(T intercept)
	{
		m_Intercept = intercept;
	}

	T getIntercept() const
	{
		return m_Intercept;
	}

	T getSlope() const
	{
		return m_Slope;
	}
private:
	T m_Slope;
	T m_Intercept;
};

template <typename T>
Vector2D<T> intersect(const StraightLine2D<T> &a, const StraightLine2D<T> &b)
{
	Vector2D<T> intersectionPoint((b.getIntercept()-a.getIntercept())/a.getSlope(), b.getIntercept());
	return intersectionPoint;
}

template <class T>
void experiment(CImg<T>& img, int x1, int y1, int x2, int y2)
{
	using namespace std;

	// vorerst nur 1. Oktant mit steigung   m € ]0;1[
	// und y1 < y2

	StraightLine2D<double> line(x1,y1,x2,y2);

	double last = y1;

	int sum_of_run_lengths = 0;

	for(int y = y1; y <= y2; y++)
	{
		StraightLine2D<double> horizontal = 0.5 + y;

		Vector2D<double> intersectionPoint = intersect(line, horizontal);

		int run_length = floor(intersectionPoint.getX())-floor(last); 
		sum_of_run_lengths += run_length;

		cout<<"run length "<<y-y1<<": "<<"("<<intersectionPoint.getX()<<","<<intersectionPoint.getY()<<") "
<<last<<" bis "<<intersectionPoint.getX()<<" length="<<run_length<<endl;

		last = intersectionPoint.getX();
	}

	cout<<"sum_of_run_lengths: "<<sum_of_run_lengths<<" (Check: "<<x2-x1<<")"<<endl;
}
///////////////////////////////////////////////////////////////////////////////////////////

int main() {

	CImg<unsigned char> img(640,400,1,3);	// Define a 640x400 color image with 8 bits per color component.
	img.fill(255, 255, 255);		

	draw_line1(img, 10, 10, 200, 57);
	draw_line5(img, 10, 10, 200, 57);

	experiment(img, 10, 10, 200, 57);
	//draw_line5(img, 200, 57, 10, 10);
	//draw_line5(img, 100, 100, 200, 200);
	//draw_line5(img, 100, 100, 200, 100);
	//draw_line5(img, 100, 100, 140, 200);
	//draw_line5(img, 100, 100, 40, 200);

	system("pause");

//	img.save_png("test.png");
//	img.display("Line Drawing");			// Display the image in a display window.
	return 0;
}

run length 0: (12.0213,10.5) 10 bis 12.0213 length=2
run length 1: (16.0638,11.5) 12.0213 bis 16.0638 length=4
run length 2: (20.1064,12.5) 16.0638 bis 20.1064 length=4
run length 3: (24.1489,13.5) 20.1064 bis 24.1489 length=4
run length 4: (28.1915,14.5) 24.1489 bis 28.1915 length=4
run length 5: (32.234,15.5) 28.1915 bis 32.234 length=4
run length 6: (36.2766,16.5) 32.234 bis 36.2766 length=4
run length 7: (40.3191,17.5) 36.2766 bis 40.3191 length=4
run length 8: (44.3617,18.5) 40.3191 bis 44.3617 length=4
run length 9: (48.4043,19.5) 44.3617 bis 48.4043 length=4
run length 10: (52.4468,20.5) 48.4043 bis 52.4468 length=4
run length 11: (56.4894,21.5) 52.4468 bis 56.4894 length=4
run length 12: (60.5319,22.5) 56.4894 bis 60.5319 length=4
run length 13: (64.5745,23.5) 60.5319 bis 64.5745 length=4
run length 14: (68.617,24.5) 64.5745 bis 68.617 length=4
run length 15: (72.6596,25.5) 68.617 bis 72.6596 length=4
run length 16: (76.7021,26.5) 72.6596 bis 76.7021 length=4
run length 17: (80.7447,27.5) 76.7021 bis 80.7447 length=4
run length 18: (84.7872,28.5) 80.7447 bis 84.7872 length=4
run length 19: (88.8298,29.5) 84.7872 bis 88.8298 length=4
run length 20: (92.8723,30.5) 88.8298 bis 92.8723 length=4
run length 21: (96.9149,31.5) 92.8723 bis 96.9149 length=4
run length 22: (100.957,32.5) 96.9149 bis 100.957 length=4
run length 23: (105,33.5) 100.957 bis 105 length=5
run length 24: (109.043,34.5) 105 bis 109.043 length=4
run length 25: (113.085,35.5) 109.043 bis 113.085 length=4
run length 26: (117.128,36.5) 113.085 bis 117.128 length=4
run length 27: (121.17,37.5) 117.128 bis 121.17 length=4
run length 28: (125.213,38.5) 121.17 bis 125.213 length=4
run length 29: (129.255,39.5) 125.213 bis 129.255 length=4
run length 30: (133.298,40.5) 129.255 bis 133.298 length=4
run length 31: (137.34,41.5) 133.298 bis 137.34 length=4
run length 32: (141.383,42.5) 137.34 bis 141.383 length=4
run length 33: (145.426,43.5) 141.383 bis 145.426 length=4
run length 34: (149.468,44.5) 145.426 bis 149.468 length=4
run length 35: (153.511,45.5) 149.468 bis 153.511 length=4
run length 36: (157.553,46.5) 153.511 bis 157.553 length=4
run length 37: (161.596,47.5) 157.553 bis 161.596 length=4
run length 38: (165.638,48.5) 161.596 bis 165.638 length=4
run length 39: (169.681,49.5) 165.638 bis 169.681 length=4
run length 40: (173.723,50.5) 169.681 bis 173.723 length=4
run length 41: (177.766,51.5) 173.723 bis 177.766 length=4
run length 42: (181.809,52.5) 177.766 bis 181.809 length=4
run length 43: (185.851,53.5) 181.809 bis 185.851 length=4
run length 44: (189.894,54.5) 185.851 bis 189.894 length=4
run length 45: (193.936,55.5) 189.894 bis 193.936 length=4
run length 46: (197.979,56.5) 193.936 bis 197.979 length=4
run length 47: (202.021,57.5) 197.979 bis 202.021 length=5
sum_of_run_lengths: 192 (Check: 190)

[Vertexwahn]

Hier kann man schon ein bischen was von dem Artikel lesen (schreibe ihn mit Word daher nur mal als PDF)
http://loop.servehttp.com/~vertexwahn/uploads/LineDrawing.pdf

[Vertexwahn]

*gelöscht*

[Vertexwahn]

Status: Warte darauf, dass das pic-Tag wieder funktioniert - Artikel wäre eigentlich woweit fertig...

[Ben04]

Poste ihn trotzdem mal. Auch wenn es gerade Problem mit der Forensoftware gibt kann man trotzdem den Text überlesen. An die Bilder kommt man ja auch, wenn auch nur etwas umständlich.

[Vertexwahn]

ok ich hab ihn gepostet (siehe 1ter Beitrag) - bisher verwende ich ca. 80 Bilder, da ich auch die Formeln als Bilder abgespeichert habe - dazu könnte ich natürlich auch Latex verwenden...

[Vertexwahn]

mit Bilder:

Als Word2003: http://loop.servehttp.com/~vertexwahn/RunLengthSlice.pdf
Als PDF: http://loop.servehttp.com/~vertexwahn/RunLengthSlice.doc

[Ben04]

Ich finde, dass deinen Weg diesen Algorithmus zu erklären sich viel leichter geometrisch erklären lässt als mit mathematischen Formeln. Hier ist mein Ansatz. Vielleicht kannst du ja irgendetwas gebrauchen.

Als erstes würde ich das Segment nicht in der Mitte eines Pixels starten lassen sondern an einer Kreuzung des Rasters. Hierdurch gibt es nur noch 2 verschiedene Teilsegmente, deren Länge sich auch leicht herausfinden lässt.

Man beschränkt sich auf das erste Oktant und auf Segmente welche vom Nullpunkt aus auf einen Punkt (x, y) gehen (also an sich zeichnet man einen Vektor). Man stellt sich das Segment zum Punkt (y, y) vor. Dieser Spezialfall ist einfach und besteht aus y 1-Pixel Teilsegmenten.

Diese zieht man entlang der X-Axe auseinander bis man die gewünschte Länge erreicht hat (ohne auf das Raster zu achten, also die Pixels werden zu Rechtecken mit rationaler Länge) und man erhält ein Segment das immer noch aus y Teilen besteht. Da wir nichts entlang der Y-Axe verändert haben sind diese Teile immer noch 1 Pixel hoch. Die Länge lässt sich einfach mittels Thales bestimmen da die Höhe bekannt ist und sie ist y/x.

Da diese verzogenen Pixel aber nicht mehr rastergerecht sind müssen wir sie etwas anpassen damit sie wieder in das Gitter passen. Da die Höhe passt müssen wir nur die Länge anpassen. Da gibt es zwei Möglichkeiten : Auf- oder Abrunden. Also dein Q oder Q+1.

Wie man ein Teilsegment raster dürfte klar sein. Bleibt also nur noch zu bestimmen wann man welches Teilsegment rastert. Hier kann ich dir nicht mehr ohne weiteres folgen in deinem Artikel allerdings ist es glaub ich ist es der gleiche Ansatz wie im normalen Bresenham Algo.

Man verhält sich die reale Länge des Segments entlang der X-Axe und die des Rasterstrichs. Dies läuft auf banales Aufsummen heraus da man die Längen aller Teilstücke kennt. Ist der Betrag der Differenz (also die Abweichung vom optimalen Strich) kleiner als 0,5 gibt es ein kleines Stück und falls sie größer ist gibt es ein großes (da der Rasterstrich hinterher hinkt).

Durch genauere Betrachtung stellt man fest, dass die reale Länge immer eine rationale Zahl ist mit Teiler y. Durch ein wenig ausmultiplizieren kann man also auch alles mit Ganzzahlen machen. (Man sollte hier aber über den möglichen Überlauf sprechen und wieso dieser hier keine Rolle spielt.)

Um die Endpunkte in der Mitte der Pixel zu haben schneidet man die Anfangs- und Endteilstücke einfach in zwei und rundest wie man es gerade braucht.

Du geht ausgiebig auf das Problem des Abrundens bei 0,5 ein. Wieso ist das so wichtig? Mich stört es nicht wenn da abgerundet wird. Ich habe deine Funktion welche alle Oktanten beherrscht jetzt nicht im Detail angeschaut allerdings wird da auch richtig gerundet wenn es sich nicht um das 1. Oktant handelt? Darauf müsstest du eigentlich eingehen um konsequent zu sein. Dadurch, dass man dein Segment nämlich auf den Kopf stellt wird das Runden verändert.

Du wirfst den Leuten an den Kopf, dass es 4 verschiedene Teilsegmente gibt ohne wirkliche Begründung. Nicht sonderlich schön allerdings kann man das durchaus in einem Artikel machen der sich mehr mit der Implementierung beschäftigt. Dann gehst du aber ausgiebig auf das Problem der Länge dieser Teilsegmente ein. Diese könntest du konsequenterweise in diesem Fall auch den Leuten einfach an den Kopf werfen.

Wer sich für eine Begründung interessiert, der ließt bis er dies an den Kopf geworfen kriegt. Wer sich nur für einen funktionierenden Algo interessiert der hört bei den Formeln auf zu lesen. Du wechselst in der Mitte des Artikels die Zielgruppe.

Die Implementierung könntest viel lesbarer machen indem du die horizontalen Striche in eine eigene Funktion auslagerst.

Ist CImg<T> ein realer MS Type oder etwas was du dir ausgedacht hast?

Die Einleitung finde ich gut gemacht.

Soll nur konstruktive Kritik sein. Ist nicht schlecht was bis jetzt hast.

[Jester]

Ben04 schrieb:

Als erstes würde ich das Segment nicht in der Mitte eines Pixels starten lassen sondern an einer Kreuzung des Rasters. Hierdurch gibt es nur noch 2 verschiedene Teilsegmente, deren Länge sich auch leicht herausfinden lässt.

Das sehe ich gerade nicht. Welchen der jeweils vier in Frage kommenden Gitterpunkte wählst Du? Und entspricht das nicht gerade der Verschiebung des Gitters um eine halbe Gitterzelle in beiden Richtungen, so wie's auch in den Zeichnungen angedeutet ist?

Du wirfst den Leuten an den Kopf, dass es 4 verschiedene Teilsegmente gibt ohne wirkliche Begründung. Nicht sonderlich schön allerdings kann man das durchaus in einem Artikel machen der sich mehr mit der Implementierung beschäftigt. Dann gehst du aber ausgiebig auf das Problem der Länge dieser Teilsegmente ein. Diese könntest du konsequenterweise in diesem Fall auch den Leuten einfach an den Kopf werfen.

Wer sich für eine Begründung interessiert, der ließt bis er dies an den Kopf geworfen kriegt. Wer sich nur für einen funktionierenden Algo interessiert der hört bei den Formeln auf zu lesen. Du wechselst in der Mitte des Artikels die Zielgruppe.

Das sehe ich ähnlich. Ich hab mir die Rechnung angesehen. Die wird sich aber wohl sonst kaum jemand antun. Schon der Anfang "Klar ist:" und dann eine Formel mit Variablen, die irgendwo 2 Seiten vorher mal definiert wurden und dann eine völlig unmotivierte Berechnung wo in der Mitte noch lauter neue Variablen eingeführt werden. Sowas ist extrem anstrengend zu lesen. (und ich hab einiges an übung mit sowas). Vielleicht hilft eine Zeichnung in der die wichtigsten Variablen eingezeichnet sind? Und bitte mehr Motivation... was willst Du rauskriegen? Warum? Was ist die Idee, die hinter dem Beweis/der Rechnung steckt? So sieht das alles so aus als würde es vom Himmel fallen.

Ich finde es schön, dass Du auch die Theorie mit darstellen möchtest. Damit das aber von vielen Lesern genutzt wird, solltest Du versuchen es dem Leser so angenehm wie möglich zu machen. Eventuell ist es auch interessant dem leser die Möglichkeit zu geben nur das Ergebnis zu lesen und die Rechnungen zu überspringen, indem Du irgendwo genau sagt was Aussage ist und was zur Rechnung gehört.

[Ben04]

Jester schrieb:

Ben04 schrieb:

Als erstes würde ich das Segment nicht in der Mitte eines Pixels starten lassen sondern an einer Kreuzung des Rasters. Hierdurch gibt es nur noch 2 verschiedene Teilsegmente, deren Länge sich auch leicht herausfinden lässt.

Das sehe ich gerade nicht. Welchen der jeweils vier in Frage kommenden Gitterpunkte wählst Du? Und entspricht das nicht gerade der Verschiebung des Gitters um eine halbe Gitterzelle in beiden Richtungen, so wie's auch in den Zeichnungen angedeutet ist?

Ich wollte nicht sagen, dass der fertige Algo in der Mitte starten soll, sondern dass sich der Algo einfacher entwickeln lässt wenn man davon ausgeht. Am Ende geht man halt dann das erste und das letzte Segment in der Mitte durchschneiden und schon kann man wieder die Mitten der Pixel als Start und Ende angeben. An sich macht Vertexwahn ja auch nichts anderes in dem er sagt, dass M = Q/2. Du definierst es halt so wie es dir gerade am besten passt.

[Vertexwahn]

Ben04 schrieb:

Ist CImg<T> ein realer MS Type oder etwas was du dir ausgedacht hast?:)

Nö das ist eine Klasse von dieser Bibliothek:
http://cimg.sourceforge.net/

Kleiens Beispiel:

int main() {
    CImg<unsigned char> img(640,400,1,3);    // Define a 640x400 color image with 8 bits per color component.

    img.save_png("test.png");
    img.display("Test");  // Display the image in a display window.
    return 0;
}

ich wollte dem Leser nur einen Weg aufzeigen, wie man mit ganz einfachen mitteln ein paar Pixel auf dem Bildschirm einfärben kann. Jedoch bin ich mir jetzt nicht sicher ob ich im Artikel auf die Bibliothek kurz eingehen soll oder ob ich einfach nur Pseudocodemäßig einfach DrawPixel schreiben soll, wenn ein Pixel gepolottet wird...

[Ben04]

An sich brauchst du ja nur einen Weg eine Punktmenge auszugeben. Da hast du sehr viele Möglichkeiten : Array, Funktor. DrawPixel ist ja an sich der Funktorweg. Ich würde schon C++ verwenden und eine hypothetische Funktion PutPixel(x, y) verwenden. Die kann jeder dann seinen Bedürfnissen anpassen.

[Vertexwahn]

was ich momentan so treibe:

http://loop.servehttp.com/~vertexwahn/uploads/Rastern von Strecken.pdf
http://loop.servehttp.com/~vertexwahn/uploads/Rastern von Strecken.doc

der Hauptteil fehlt noch

[Ben04]

Ich hab jetzt keine Zeit mir das im Detail durch zu lesen. Es sieht aber schon viel besser aus als die Vorgängerversion.