Hallo,
im Folgenden sei gezeigt, wie Dreiecke sehr schnell gefüllt werden können.
Genutzt wird hierzu der sogenannte Scanline-Algorithmus.
Dieser Algorithmus iteriert durch ein Array, in der sowohl die minimalen und maximalen X-Positionen der Seiten einer Figur gespeichert sind.
Pro Zeile werden dann die minimale und maximale X-Komponente ausgelesen und in einer for-Schleife mit dem Interval [min, max] die jeweiligen Pixel zwischen diesen
beiden gesetzt.
Die Größe des Array ist die Höhe des Bildschirms multipliziert mit zwei, das jeweils die min, max Werte der jeweiligen Zeile abbildet.
Auf den Algorithmus stieß ich _ in diesem Video: .
Für Berechnung der jeweiligen Min-Max Werte ist lediglich lineare Algebra notwendig.
Ein Dreieck wird aus drei Punkten gebildet.
Diese drei Punkten werden jeweils mit Gerade verbunden und zu einem Dreieck ergänzt.
Jedes Dreieck hat in der Regel einen oberen, mittleren und unteren Punkt.
Den oberen Punkt nenne ich O, den mittleren M und analog dazu den unteren U.
Es werden drei Strecken gebildet, die jeweils die Seiten
OM
MU
UO
repräsentieren.
Eine Gerade hat folgende Darstellung:
y = m * x + b
Die Steigung lässt sich ganz schnell über den Steigungsdreieck berechnen:
m = (b.y - a.y) / (b.x - b.y)
Der Achsenabschnitt lässt sich folgendergestalt berechnen:
b = y - m * x
Weil wir die X Werte für jede Zeile (Y-Position) bestimmen möchten, müssen wir die lineare Gleichung nach x auflösen:
x = (y - b) / m
Weil aber eben genau diese Funktion mehrmals aufgerufen wird (in drei for Schleifen) und Division eine aufwändige Operation ist, berechnen wir im Konstruktor einfach
m_frac = 1 / m
und können dann bei jedem Iterationsschritt dann statt zu dividieren multiplizieren (was soweit ich weiß wesentlich schneller ist) :
x = (y - b) * m_frac
Es gibt jedoch einige Sonderfälle zu beachten, exemplarisch wenn es sich um ein rechtwinkliges Dreieck handelt.
In so einem Fall würde die Steigung entweder 0 oder unendlich betragen weil entweder im Nenner oder Zähler eine 0 vor käme.
Der Algorithmus sieht dann ungefähr so aus:
1.) Punkte nach upper, mid, lower sortieren
2.) Strecken bilden von upper zu mid, mid zu lower, lower zu upper
3.) Index berechnen: Das heißt, analysieren ob Strecke OM MU im Min -oder Max-Bereich liegt
4.) Die Zeilen der jeweiligen Geraden durch-iterieren und die Min-Max Werte setzen
5.) _Draw() aufrufen, und als Parameter Y-Werte der Lower und Upper-Punkte übergeben
6.) For-Schleife von Lower.Y bis Upper.Y, Min-Max auslesen, For-Schleife von Min bis Max, Pixel setzen...
Zu Punkt 3:
Hierfür ist es notwendig den Schnittpunkt zwischen OM und MU zu berechnen.
Der Schnittpunkt lässt sich über die Formel:
x = |(OM_b - MU_b) / (OM_m - MU_m)|
berechnen.
Die Betragsstriche aus dem Grund, weil so die Größe der jeweiligen Werte keine Rolle spielen. Es muss also nicht im vorhinein geprüft werden welche Zahl größer ist.
Der dort zustande kommende X-Wert muss dann in eine der Gerade eingesetzt werden:
y = m * x + b
Mit dem Y-Wert wird dann eine neue - konstante Funktion - formuliert, und der X-Wert des Schnittpunktes mit UO ermittelt.
Wenn nun dieser X-Wert größer ist als der X-Wert des Schnittpunktes zwischen OM MU, so ist die Gerade UO im maximalen Bereich, und vice versas.
Hier eine Illustration:
Der Code:
Die FillTriangle-Methode:
Die _DrawScanLine-Methode:
Ergebnis:
Liebe Grüße.
_
im Folgenden sei gezeigt, wie Dreiecke sehr schnell gefüllt werden können.
Genutzt wird hierzu der sogenannte Scanline-Algorithmus.
Dieser Algorithmus iteriert durch ein Array, in der sowohl die minimalen und maximalen X-Positionen der Seiten einer Figur gespeichert sind.
Pro Zeile werden dann die minimale und maximale X-Komponente ausgelesen und in einer for-Schleife mit dem Interval [min, max] die jeweiligen Pixel zwischen diesen
beiden gesetzt.
Die Größe des Array ist die Höhe des Bildschirms multipliziert mit zwei, das jeweils die min, max Werte der jeweiligen Zeile abbildet.
Auf den Algorithmus stieß ich _ in diesem Video: .
Für Berechnung der jeweiligen Min-Max Werte ist lediglich lineare Algebra notwendig.
Ein Dreieck wird aus drei Punkten gebildet.
Diese drei Punkten werden jeweils mit Gerade verbunden und zu einem Dreieck ergänzt.
Jedes Dreieck hat in der Regel einen oberen, mittleren und unteren Punkt.
Den oberen Punkt nenne ich O, den mittleren M und analog dazu den unteren U.
Es werden drei Strecken gebildet, die jeweils die Seiten
OM
MU
UO
repräsentieren.
Eine Gerade hat folgende Darstellung:
y = m * x + b
Die Steigung lässt sich ganz schnell über den Steigungsdreieck berechnen:
m = (b.y - a.y) / (b.x - b.y)
Der Achsenabschnitt lässt sich folgendergestalt berechnen:
b = y - m * x
Weil wir die X Werte für jede Zeile (Y-Position) bestimmen möchten, müssen wir die lineare Gleichung nach x auflösen:
x = (y - b) / m
Weil aber eben genau diese Funktion mehrmals aufgerufen wird (in drei for Schleifen) und Division eine aufwändige Operation ist, berechnen wir im Konstruktor einfach
m_frac = 1 / m
und können dann bei jedem Iterationsschritt dann statt zu dividieren multiplizieren (was soweit ich weiß wesentlich schneller ist) :
x = (y - b) * m_frac
Es gibt jedoch einige Sonderfälle zu beachten, exemplarisch wenn es sich um ein rechtwinkliges Dreieck handelt.
In so einem Fall würde die Steigung entweder 0 oder unendlich betragen weil entweder im Nenner oder Zähler eine 0 vor käme.
Der Algorithmus sieht dann ungefähr so aus:
1.) Punkte nach upper, mid, lower sortieren
2.) Strecken bilden von upper zu mid, mid zu lower, lower zu upper
3.) Index berechnen: Das heißt, analysieren ob Strecke OM MU im Min -oder Max-Bereich liegt
4.) Die Zeilen der jeweiligen Geraden durch-iterieren und die Min-Max Werte setzen
5.) _Draw() aufrufen, und als Parameter Y-Werte der Lower und Upper-Punkte übergeben
6.) For-Schleife von Lower.Y bis Upper.Y, Min-Max auslesen, For-Schleife von Min bis Max, Pixel setzen...
Zu Punkt 3:
Hierfür ist es notwendig den Schnittpunkt zwischen OM und MU zu berechnen.
Der Schnittpunkt lässt sich über die Formel:
x = |(OM_b - MU_b) / (OM_m - MU_m)|
berechnen.
Die Betragsstriche aus dem Grund, weil so die Größe der jeweiligen Werte keine Rolle spielen. Es muss also nicht im vorhinein geprüft werden welche Zahl größer ist.
Der dort zustande kommende X-Wert muss dann in eine der Gerade eingesetzt werden:
y = m * x + b
Mit dem Y-Wert wird dann eine neue - konstante Funktion - formuliert, und der X-Wert des Schnittpunktes mit UO ermittelt.
Wenn nun dieser X-Wert größer ist als der X-Wert des Schnittpunktes zwischen OM MU, so ist die Gerade UO im maximalen Bereich, und vice versas.
Hier eine Illustration:
Der Code:
C#-Quellcode
- public static int GetIndex(Line upMid, Line midDown, Line downUp)
- {
- float iX = 0;
- float iY = 0;
- float diffM = upMid.Slope - midDown.Slope;
- if (float.IsNaN(diffM) || float.IsInfinity(diffM))
- {
- iX = upMid.End.X;
- iY = upMid.End.Y;
- }
- else
- {
- iX = Math.Abs((upMid.AxisSection - midDown.AxisSection) / (upMid.Slope - midDown.Slope));
- iY = upMid.GetY(iX);
- }
- float inX = downUp.GetX(iY).Value;
- return iX > inX ? 1 : 0;
- }
Die FillTriangle-Methode:
C#-Quellcode
-
- private PointF _Up = new Point();
- private PointF _Mid = new Point();
- private PointF _Down = new Point();
- public void FillTriangle(PointF a, PointF b, PointF c)
- {
- if (a.Y <= b.Y && a.Y <= c.Y)
- _Up = a;
- else if (b.Y < a.Y && b.Y <= c.Y)
- _Up = b;
- else if (c.Y <= a.Y && c.Y <= b.Y)
- _Up = c;
- if (a.Y >= b.Y && a.Y >= c.Y)
- _Down = a;
- else if (b.Y >= a.Y && b.Y >= c.Y)
- _Down = b;
- else if (c.Y >= a.Y && c.Y >= b.Y)
- _Down = c;
- if (a != _Up && a.Y >= _Up.Y && a != _Down && a.Y <= _Down.Y)
- _Mid = a;
- else if (b != _Up && b.Y >= _Up.Y && b != _Down && b.Y <= _Down.Y)
- _Mid = b;
- else if (c != _Up && c.Y >= _Up.Y && c != _Down && c.Y <= _Down.Y)
- _Mid = c;
- if (_Up.Y >= Height)
- return;
- if (_Down.Y < 0)
- return;
- if (_Up.X >= Width && _Mid.X >= Width && _Down.X >= Width)
- return;
- if (_Up.X < 0 && _Mid.X < 0 && _Down.X < 0)
- return;
- Line upMidLine = new Line(_Up, _Mid);
- Line midDownLine = new Line(_Mid, _Down);
- Line downUpLine = new Line(_Down, _Up);
- int indexUpMid = Utilities.GetIndex(upMidLine, midDownLine, downUpLine);
- int indexMidDown = indexUpMid;
- int indexDownUp = 1 - indexMidDown;
- // up to mid
- for (float y = _Up.Y; y < _Mid.Y; y++)
- {
- _SetScanLineBuffer((int)y, (int)upMidLine.GetX(y), indexUpMid);
- }
- // mid to down
- for (float y = _Mid.Y; y < _Down.Y; y++)
- {
- _SetScanLineBuffer((int)y, (int)midDownLine.GetX(y), indexMidDown);
- }
- // mid to down
- for (float y = _Up.Y; y < _Down.Y; y++)
- {
- _SetScanLineBuffer((int)y, (int)downUpLine.GetX(y), indexDownUp);
- }
- _DrawScanLine((int)_Up.Y, (int)_Down.Y);
- }
Die _DrawScanLine-Methode:
C#-Quellcode
- private void _DrawScanLine(int yMin, int yMax)
- {
- Parallel.For((yMin >= 0 ? yMin : 0), (yMax <= Height ? yMax : Height), delegate (int y)
- {
- int xMin = _ScanLine[0 + y * 2];
- int xMax = _ScanLine[1 + y * 2];
- for (int x = xMin; x < xMax; x++)
- {
- if (x + 1 < 0 || x + 1 >= Width)
- continue;
- _BackBuffer.SetPixel(x, y, r, g, b);
- }
- });
- }
Ergebnis:
Liebe Grüße.
_
Und Gott alleine weiß alles am allerbesten und besser.
