2D-Grafik DrawLine Algorithmus schreiben

[Semox]

Liebes Java-Forum

Ich habe die Aufgabe einen Rasterisierer zu schreiben und hänge an der Stelle, daß ich nicht Linien mit negativer Steigung darstellen kann. Wie kann man das korrigieren?

Erklärung: Es gibt zwei Punkte und Koordinaten. Die Linie zeichne ich pixelweise mittels einer Formel, die aus dem Buch: "Fundamentals of Computergraphics" stammt:

(y0 − y1 )*x + (x1 − x0 )*y + x0 * y1 − x1 * y0 = 0

f (x, y, x0 , x1 , y0 , y1 ) = (y0 − y1 )*x + (x1 − x0 )*y + x0 * y1 − x1 * y0 ≡ 0

Im Prinzip wird damit eine verallgemeinerte Darstellung einer üblichen Funktion erzeugt:

f (x) = ax + b

Prüfe ob der nächste Pixel ober-/unterhalb einer gedachten Linie auf einem Raster liegt ? erhöhe y-Wert : verringere y-Wert einer Pixels.

Hier ist das entsprechende Snippet:

                // ++++++++++++++++++++++
		// + +
		// + YOU START HERE ! +
		// + +
		// ++++++++++++++++++++++
		if (figure instanceof Line) {
			System.out.println("line");
			Color c = Color.magenta;
			final Line line = (Line) figure;

			int x0 = (line.getP1()).get(0, 0).intValue();
			int x1 = (line.getP2()).get(0, 0).intValue();
			int y0 = (line.getP1()).get(1, 0).intValue();
			int y1 = (line.getP2()).get(1, 0).intValue();

			int y = y0;

			for (int x = line.getP1().get(0, 0).intValue(); x <= line.getP2()
					.get(0, 0).intValue(); ++x) {
				frameBuffer[x][y] = c;
				double kipp = (y0 - y1) * (x + 1) + (x1 - x0) * (y + 0.5) + x0
						* y1 - x1 * y0;
				if (kipp > 0) {
					--y;
				} else if (kipp < 0) {
					++y;
				}

			}
		}

Ich würde mich freuen, wenn mir jemand einen Rat geben kann.

Lieben Gruß,
Semo

 

[schalentier]

Ich empfehle: Bresenham-Algorithmus ? Wikipedia

 

[Semox]

Danke schalentier,

Soweit wie ich das sehe, ist der Bresenham-Alg. das was ich mache. Ich habe eine Fehlervariable "kipp" die größer oder kleiner 0 ist. Je nachdem gehe ich in y hoch oder runter. Das deckt sich mit der Beschreibung im Wikipedia Artikel. Leider führt mich das nicht weiter. Hast Du vielleicht entdeckt, weshalb "POSITIV"-steigende Linien (linksUnten --> rechtsOBEN) nicht gezeichnet werden?

Gruß,
Semo

EDIT: wollte positive Funktionen pixelweise zeichnen... Sorry genau umgekehrt beschrieben......

 

[Semox]

Sooooo... Konnte das Problem lösen, indem ich folgenden Algorithmus implementierte:

	private void drawLine(final Line line, final Color[][] frameBuffer) {
		System.out.println("line");

		Color c = Color.magenta;

		int x0 = (line.getP1()).get(0, 0).intValue();
		int x1 = (line.getP2()).get(0, 0).intValue();
		int y0 = (line.getP1()).get(1, 0).intValue();
		int y1 = (line.getP2()).get(1, 0).intValue();

		int dx = Math.abs(x1 - x0);
		int dy = Math.abs(y1 - y0);

		int sx = x0 < x1 ? 1 : -1;
		int sy = y0 < y1 ? 1 : -1;

		int delta = dx - dy;
		int e2;

		// Bresenham's line algorithm
		while (true) { //
			frameBuffer[x0][y0] = c;
			e2 = 2 * delta;
			if (e2 > -dy) {
				delta -= dy;
				x0 += sx;
			} else if (e2 < dx) {
				delta = delta + dx;
				y0 += sy;
			}
			if (x0 == x1 && y0 == y1)
				break;
		}
	}

Schön.

Dank für die rege Teilnahme am Diskurs. :bae:

Grüße,
Semo