Alle Pixel eines 3D-Dreiecks berechnen

Edit: Ich habe das Problem lösen können (dank MrSparkle). Ich schreib' euch einfach den ganzen Code :evil::

public static double Dist(Point p1, Point p2)
{
	int x = Math.Abs(p1.X - p2.X);
	int y = Math.Abs(p1.Y - p2.Y);
	return Math.Sqrt(x * x + y * y);
}

public static Tuple<Point, Color, Double>[] GetLinePoints(Tuple<Point, Color, Double> p1, Tuple<Point, Color, Double> p2)
{
	if (p1.Item1 == p2.Item1)
		return new Tuple<Point, Color, Double>[1] { p1 };
	List<Tuple<Point, Color, Double>> ret = new List<Tuple<Point, Color, Double>>();
	double dist = Dist(p1.Item1, p2.Item1);
	for (int i = 0; i <= dist; i++)
	{
		double d1 = i / dist;
		double d2 = 1 - d1;
		Point p = new Point((int)Math.Round(p1.Item1.X * d1 + p2.Item1.X * d2), (int)Math.Round(p1.Item1.Y * d1 + p2.Item1.Y * d2));
		Color c = Color.FromArgb((int)Math.Round(p1.Item2.A * d1 + p2.Item2.A * d2), (int)Math.Round(p1.Item2.R * d1 + p2.Item2.R * d2), (int)Math.Round(p1.Item2.G * d1 + p2.Item2.G * d2), (int)Math.Round(p1.Item2.B * d1 + p2.Item2.B * d2));
		Double d = p1.Item3 * d1 + p2.Item3 * d2;
		ret.Add(new Tuple<Point, Color, Double>(p, c, d));
	}
	return ret.ToArray();
}

private static Tuple<Point, Color, Double>[] LowestAndHighestPoint(Tuple<Point, Color, Double>[] points, int x)
{
	if (points == null || points.Length == 0)
		return null;
	Tuple<Point, Color, Double> lowest = null;
	Tuple<Point, Color, Double> highest = null;
	foreach (Tuple<Point, Color, Double> point in points)
		if (point.Item1.X == x)
		{
			if (lowest == null || point.Item1.Y < lowest.Item1.Y)
				lowest = point;
			if (highest == null || point.Item1.Y > highest.Item1.Y)
				highest = point;
		}
	return new Tuple<Point, Color, Double>[] { lowest, highest };
}

public static Tuple<Point, Color, Double>[] GetTrianglePoints(Tuple<Point, Color, Double> p1, Tuple<Point, Color, Double> p2, Tuple<Point, Color, Double> p3)
{
	List<Tuple<Point, Color, Double>> temp = new List<Tuple<Point, Color, Double>>();
	temp.AddRange(GetLinePoints(p1, p2));
	temp.AddRange(GetLinePoints(p2, p3));
	temp.AddRange(GetLinePoints(p3, p1));
	Tuple<Point, Color, Double>[] points = temp.ToArray();
	List<Tuple<Point, Color, Double>> ret = new List<Tuple<Point, Color, Double>>();
	int lx = Math.Min(Math.Min(p1.Item1.X, p2.Item1.X), p3.Item1.X);
	int hx = Math.Max(Math.Max(p1.Item1.X, p2.Item1.X), p3.Item1.X);
	for (int x = lx; x <= hx; x++)
	{
		Tuple<Point, Color, Double>[] lh = LowestAndHighestPoint(points, x);
		ret.AddRange(GetLinePoints(lh[0], lh[1]));
	}
	return ret.ToArray();
}

Hallo zusammen,
ich versuche in C# ein Control zu programmieren, das 3D-Dreiecke (später vill. noch mehr) zeichenen kann (nur zum Spaß, ich weiß, dass das langsam ist).
Das Zeichnen der Punkte funktioniert, ich muss nur Punkte der Dreiecke berechnen. Ich habe dies ausprobiert:

public static Tuple<Point, Color, Double>[] GetLinePoints(Tuple<Point, Color, Double> p1, Tuple<Point, Color, Double> p2)
{
	if (p1.Item1 == p2.Item1)
		return new Tuple<Point, Color, Double>[0];
	List<Tuple<Point, Color, Double>> ret = new List<Tuple<Point, Color, Double>>();
	double dist = Dist(p1.Item1, p2.Item1);
	for (int i = 0; i <= dist; i++)
	{
		double d1 = i / dist;
		double d2 = 1 - d1;
		Point p = new Point((int)Math.Round(p1.Item1.X * d1 + p2.Item1.X * d2), (int)Math.Round(p1.Item1.Y * d1 + p2.Item1.Y * d2));
		Color c = Color.FromArgb((int)Math.Round(p1.Item2.A * d1 + p2.Item2.A * d2), (int)Math.Round(p1.Item2.R * d1 + p2.Item2.R * d2), (int)Math.Round(p1.Item2.G * d1 + p2.Item2.G * d2), (int)Math.Round(p1.Item2.B * d1 + p2.Item2.B * d2));
		Double d = p1.Item3 * d1 + p2.Item3 * d2;
		ret.Add(new Tuple<Point, Color, Double>(p, c, d));
	}
	return ret.ToArray();
}

public static Tuple<Point, Color, Double>[] GetTrianglePoints(Tuple<Point, Color, Double> p1, Tuple<Point, Color, Double> p2, Tuple<Point, Color, Double> p3)
{
	Tuple<Point, Color, Double>[] p12 = GetLinePoints(p1, p2);
	Tuple<Point, Color, Double>[] p32 = GetLinePoints(p3, p2);
	List<Tuple<Point, Color, Double>> ret = new List<Tuple<Point, Color, Double>>();
	int len = Math.Max(p12.Length, p32.Length);
	for (int i = 0; i < len; i++)
	{
		double d = (double)i / len;
		int i1 = (int)Math.Round(p12.Length * d);
		int i2 = (int)Math.Round(p32.Length * d);
		ret.AddRange(GetLinePoints(p12[i1], p32[i2]));
	}
	return ret.ToArray();
}

(Die Tuples beinhalten immer 1. den Punkt 2. die Punktfarbe und 3. die Tiefe.)

Dabei werden jedoch viele Pixel doppelt gesetzt und einige gar nicht (Anhang: blau = einmal gesetzt, rot = zweimal oder öfter gesetzt).
Es sollen jedoch alle Pixel des Dreiecks nur einmal im Array vorkommen. Ich habe schon viel ausprobiert, komme aber nicht weiter. Ich hoffe, ihr könnt mir helfen.

Edit: Ich muss erstmal nur alle Punkte zwischen drei Points berechnen. Den Rest kann ich aus den Punkten berechnen.

Ich hoffe, ihr könnt mir helfen.

Bestimmt. Wenn wir wissen um was es geht.
Dein Code ist von der Benennung her leider gar nicht aussagekräftig. Wenn ich was nach dem 3. durchlesen immer noch nicht kapiert hab, frag ich nach 😃
Beschreibe mal
* was rauskommen soll
* was stattdessen rauskommt
* was dein Code tun soll

Sorry, das war mein erster post in diesem forum und ich glaub mein 2. oder 3. post überhaupt.
GetLinePoints gibt die punkte der linie zwischen p1 und p2 mit der berechneten farbe und tiefe zurück.
GetTrianglePoints soll alle punkte im dreieck (mit farbe und tiefe) zurückgeben.

Tuple<Point, Color, Double>[] p12 = GetLinePoints(p1, p2);
Tuple<Point, Color, Double>[] p32 = GetLinePoints(p3, p2);

berechnet die punkte zwischen p1 und p2 und die punkte zwischen p3 und p2 (in der reihenfolge, sonst kommt da was falsches raus)

int len = Math.Max(p12.Length, p32.Length);

setzt len auf die länge des größeren punktarrays

for (int i = 0; i < len; i++)
{
    double d = (double)i / len;
    int i1 = (int)Math.Round(p12.Length * d);
    int i2 = (int)Math.Round(p32.Length * d);
    ret.AddRange(GetLinePoints(p12[i1], p32[i2]));
}

nimmt von beiden arrays den punkt für i und berechnet die punkte dazwischen und fügt diese zu ret hinzu.

return ret.ToArray();

-selbsterklärend, glaube ich

Was ist dann die Tiefe? Die 3. Koordinate?
Ich würd an deiner Stelle zuerst Klassen erstellen in denen die Werte gescheite Namen haben statt Item1 aus dem Tuple.

Wenn du sagst manche Punkte doppelt und manche gar nicht, ist das ein Problem der Rundung. Manche Berechnungen werden auf die selben int Werte gerundet. Deswegen sind Punkte doppelt drin und dafür fehlen wieder andere. Wenn du nicht parallel zu den Achsen laufen kannst, wird das ein ziemlicher Aufwand. Wenn dann noch die 3. Dimension dazu kommt, wirds noch krasser.

Wenn du wirklich Dreiecke haben willst, nimm eine Zeichenfunktion dafür.

Edit: wenn du die einzelnen Pixel haben willst, müsstest du das andersrum betrachten.
Bisher gehst du vom Dreieckspunkt aus und berechnest das Pixel. Du müsstest die Sichtweise umdrehen.
Berechne die Koordinaten Pixel der drei Ecken und durchlauf dann die Pixel der Reihe nach, so wie sie zwischen den Verbindungslinien liegen. Dann kriegst du wirklich jeden Bildschirmpunkt genau einmal.

Auf Youtube gibt es sehr viele gute Videos zum zeichen von Dreiecken.

Und für andere formen auch zum umrechnen von den Formen in Dreiecke(Polygone)

Leiderfällt mir grad keins ausm Kopf ein und mein internet is hier sehr lasch.
Findest bestimmt selbst ein paar gute videos 😛

Die drei Punkte(3D) und drei Farben habe ich in einer Klasse namens Triangle.
Die Punkte werden zu 2D-Koordinaten umgerechnet. Ich muss nur noch die Pixel (+ Farbe und Tiefe) dazwischen berechnen.

(Die Tiefe brauche ich übrigens, damit immer nur der vorderste Pixel gezeichnet wird)

Die Tiefe brauche ich übrigens, damit immer nur der vorderste Pixel gezeichnet wird

Nochmal: bitte erklären was das bedeutet.
Was ist der vorderste?

Beschreib doch mal den Hintergrund deiner beiden Methoden, was sollen die tun und wie willst du das erreichen.

Naja und dann bleibt aber immer noch das Problem dass du auf diese Weise nicht alle Pixel der Abbildungsebene genau einmal berechnen kannst.

Hi openglfreak,

um ein 3D-Dreieck in ein 2D-Bitmap zu zeichnen brauchst du üblicherweise folgende Operationen:

• 3D-Dreieck in 2D transformieren: Das geschieht typischerweise mit Matrizen, also WorldMatrix, ViewMatrix und ProjectionMatrix. Mit deren Hilfe kannst du je nach Perspektive die 2D-Koordinaten der 3 3D-Punkte des Dreiecks berechnen.

• Zeichnen der Außenkontur: Die drei Verbindungslinien zwischen den Punkten des 2D-Dreiecks kannst du mit Hilfe einer Linienfunktion von WindowsForms zeichnen oder mit Hilfe des Bresenham-Algorithmus' berechnen.

• Die Füllung des Dreiecks kannst du am einfachsten auch mit den Zeichenfunktionen von WinForms zeichnen (dann kannst du auch auf den zweiten Schritt verzichten) oder du erstellst dir horizontale Linien zwischen den Außenkonturen, die du im zweiten Schritt berechnet hast. So macht es auch OpenGL oder DirectX. Hier mal eine kurze Beschreibung: 3D Graphics with OpenGL Basic Theory

Ich kann in deinem Quellcode leider nicht erkennen, wo bzw. ob du diese drei Schritte irgendwo ausführst. Daher würde ich dir empfehlen, dir erstmal anzuschauen, wie andere an dieses Problem herangehen. Es gibt viele Beschreibungen und auch Quellcode im Netz, das Stichwort heißt "(3d) triangle rasterization".

Christian

Ich hab' schon eine Klasse namens Triangle in der die Punkte in 3D und die Farben der Punkte gespeichert sind. Außerdem hab' ich eine Klasse, die mir 3D Punkte in Bildkoordinaten umrechnet(noch ohne frei setzbare Kameraposition - kommt noch).
Die Methode Dist(Point, Point) errechnet die Distanz zwischen zwei Punkten:

public static double Dist(Point p1, Point p2)
{
    int x = Math.Abs(p1.X - p2.X);
    int y = Math.Abs(p1.Y - p2.Y);
    return Math.Sqrt(x * x + y * y);
}

@openglfreak
Dist war mir noch das klarste an der ganzen Sache 😃
Aber du scheinst ja wirklich keine Lust zu haben deinen Code im allerersten Beitrag zu erklären?
Dann wird aber niemand was brauchbares dazu sagen können. Selbst die Fehlerbeschreibung muss man sich selber zusammenreimen.
Erklär halt wirklich mal was du vorhast und was dein gezeigter Code tun soll. Erklär was "Tiefe" sein soll und so, du bringst immer nur die Farbe aber die ist an deinem Problem sehr wahrscheinlich das bedeutungsloseste. Wichtig ist nicht was du irgendwo hast und was sonst noch alles passiert in deinem Code, sondern was du uns hier zeigst und was dein Problem ist.