Xiaolin Wu Linien-Algorithmus - So richtig?

[blopblopblop]

Hallo,

habe mir mal aus dem Pseudocode aus der englischen Wikipedia folgendes gebaut:

float fpart(float x)
{
	return x - (float)(int)x;
}

float rfpart(float x)
{
	return 1.0f - fpart(x);
}

void drawLine(float x1, float y1, float x2, float y2)
{
	float dx = x2 - x1;
	float dy = y2 - y1;

	if(fabs(dx) > fabs(dy))
	{
		if(x2 < x1)
		{
			float tmp;

			tmp = x1;
			x1 = x2;
			x2 = tmp;

			tmp = y1;
			y1 = y2;
			y2 = tmp;
		}

		float gradient = dy / dx;

		float xend, yend;
		float xgap;
		int xpxl1, ypxl1;
		int xpxl2, ypxl2;
		float intery;

		xend = (float)(int)(x1 + 0.5f);
		yend = y1 + gradient * (xend - x1);
		xgap = rfpart(x1 + 0.5f);
		xpxl1 = (int)xend;
		ypxl1 = (int)yend;
		setPixel(xpxl1, ypxl1, rfpart(yend) * xgap);
		setPixel(xpxl1 + 1, ypxl1, fpart(yend) * xgap);
		intery = yend + gradient;

		xend = (float)(int)(x2 + 0.5f);
		yend = y2 + gradient * (xend - x2);
		xgap = fpart(x2 + 0.5f);
		xpxl2 = (int)xend;
		ypxl2 = (int)yend;
		setPixel(xpxl2, ypxl2, rfpart(yend) * xgap);
		setPixel(xpxl2, ypxl2 + 1, fpart(yend) * xgap);

		for(int x = (int)xpxl1 + 1; x < (int)xpxl2; x++)
		{
			setPixel(x, (int)intery, rfpart(intery));
			setPixel(x, (int)intery + 1, fpart(intery));
			intery += gradient;
		}
	}
	else
	{
		if(y2 < y1)
		{
			float tmp;

			tmp = y1;
			y1 = y2;
			y2 = tmp;

			tmp = x1;
			x1 = x2;
			x2 = tmp;
		}

		float gradient = dx / dy;

		float xend, yend;
		float ygap;
		int xpxl1, ypxl1;
		int xpxl2, ypxl2;
		float interx;

		yend = (float)(int)(y1 + 0.5f);
		xend = x1 + gradient * (yend - y1);
		ygap = rfpart(y1 + 0.5f);
		ypxl1 = (int)yend;
		xpxl1 = (int)xend;
		setPixel(xpxl1, ypxl1, rfpart(xend) * ygap);
		setPixel(xpxl1, ypxl1 + 1, fpart(xend) * ygap);
		interx = xend + gradient;

		yend = (float)(int)(y2 + 0.5f);
		xend = x2 + gradient * (yend - y2);
		ygap = fpart(y2 + 0.5f);
		ypxl2 = (int)yend;
		xpxl2 = (int)xend;
		setPixel(xpxl2, ypxl2, rfpart(xend) * ygap);
		setPixel(xpxl2 + 1, ypxl2, fpart(xend) * ygap);

		for(int y = ypxl1 + 1; y < ypxl2; y++)
		{
			setPixel((int)interx, y, rfpart(interx));
			setPixel((int)interx + 1, y, fpart(interx));
			interx += gradient;
		}
	}
}

Es scheint auch alles zu funktionieren. Nur frage ich mich jetzt, wie man den Code noch optimieren kann und ob evtl. doch noch Fehlerchen drin sind?

Ist das der schnellste Algo für Linien mit glatten Kanten?

Thx!

[David_pb]

Nur frage ich mich jetzt, wie man den Code noch optimieren kann und ob evtl. doch noch Fehlerchen drin sind?

Du könntest z.B. Fixedpoint-, statt Fließkomma-Arithmetik verwenden. Die Frage ist aber ob du den Code überhaupt optimieren musst, hast du das Gefühl, dass das Zeichnen zu langsam ist?
Ob Fehler beim Zeichnen entstehen kannst du ja schnell prüfen, in dem du in alle möglichen Richtungen Linien, ausgehend von einem Punkt, zeichnest.

[blopblopblop]

Ja, ist mir etwas zu langsam. Wäre schön, wenn das schneller gehen würde. Also eindeutige Fehler erkenne ich beim Zeichnen nicht.

Leider finde ich über Google auch keine viel besseren Implementierungen. Wenn jemand eine optimierte Implementierung in Inline-Assembler findet/schnell machen kann, wäre ich demjenigen sehr verbunden. Bin da leider nicht so fit drin.

[volkard]

Assembler bringt hier erstmal nichts, außer daß Du Dir die Optimierungsmöglichkeiten nimmst.
Ich würde an Festpunktarithmetik denken, vielleicht 8 oder 12 Bits nach dem Komma? Sind die ersten 8 Nachkommabits am Ende einfach die Helligkeit?