Wie füllt GDI Polygone?

  • Allgemein

Es gibt 10 Antworten in diesem Thema. Der letzte Beitrag () ist von jvbsl.

    Wie füllt GDI Polygone?

    Hallo,

    wisst ihr wie GDI eigentlich bei exemplarisch FillCircle, oder FillPolygon verfährt ?
    Ich hab versucht den Aufruf zu dekompilieren, das ist jedoch auch nur ein externer call zu gdiplus.dll.
    Hat jemand da eine Vermutung?

    Lieben Dank!

    Verschoben. ~Thunderbolt
    Und Gott alleine weiß alles am allerbesten und besser.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Thunderbolt“ ()

    @φConst Das Zauberwort heißt FloodFill. pinvoke.net/default.aspx/gdi32.FloodFill
    Lässt sich auch nachbauen, aber der API-Call ist performanter.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Ich würde vermuten, dass bei Circle/Ellipse das ganze über den Bresenham Algorithmus gemacht wird. Den kann man ja Grundsätzlich verwenden um nur den Rahmen zu Zeichnen. Aber wenn wir einfach am obersten Punkt anfangen und dann den Bresenham Algorithmus nach Rechts und Links gleichzeitig laufen lassen, dann bekommen wir(wenn ich Richtig liege) die Gegenüberliegenden Pixel und statt nur die Pixel zu Zeichnen ziehen wir eine Linie zwischen diesen beiden(einfache for-schleife, da diese auf gleicher Y-Höhe sein sollten). Sollte denke ich performanter sein als FloodFill. Ist auch parallelisierbar ;)
    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---

    Ich versuche echt nachzuvollziehen wie es GDI+ schafft, ein riesiges Polygon ( Dreieck eigentlich) innerhalb weniger ms zu plotten.
    @jvbsl , kannst du da etwas vorschlagen?

    Worauf wird das denn gezeichnet? Eine interne Bitmap?
    Kann man irgendwie auf die geänderten Pixels zugreifen, sodass man quasi FillPolygon Algortihmus verwenden kann, um zu ermitteln welche Punkte im Polygon liegen?

    Lieben Dank!
    Und Gott alleine weiß alles am allerbesten und besser.

    Das plotten eines Dreiecks könnte man eigt. auch mit Bresenham machen :D
    Naja es wird im Endeffekt auf einen HDC gezeichnet, aber was hast du denn eigt. genau vor?
    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---

    Definiere

    φConst schrieb:

    zu plotten
    falls sich da bei mir ein anderer Begriff dahinter verbirgt als bei Dir.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Hallo φConst,

    Polygone werden zum Zeichnen in Dreiecke zerlegt. Ein ausgefülltes
    Dreieck zeichnet man, indem man mit einem Linienalgorithmus gegen-
    überliegende Punkte auf gleicher Höhe von zwei Seiten des Dreiecks
    berechnet und diese dann durch eine waagerechte Linie verbindet. Für
    eine waagerechte Linie braucht man nur eine einfache Schleife, die
    die Punkte setzt.

    Für einen Kreis (oder Ellipse) werden die Eckpunkte eines regelmäßigen
    Vielecks berechnet, das dann wie ein Polygon gezeichnet wird. Bei einem
    Kreis (oder Ellipse) könnte man auch gegenüberliegende Punkte auf dem
    Kreis berechnen und diese dann ebenfalls durch eine gerade Linie verbinden.
    Das wird aber, soweit ich weiß, nicht gemacht.

    Der Floodfill-Algorithmus ist für einfache geometrische Figuren zu aufwändig
    und zu langsam. Er ist mehr für unregelmäßige Formen (z.B. Handzeichnung) und
    für komplexe Figuren (z.B. Spirale) geeignet.
    Das Zeichnen von Dreiecken ist aus Geschwindigkeitsgründen in Grafikkarten
    auf Hardwareebene umgesetzt.

    Um zu ermitteln, ob ein Punkt in einem Polygon liegt, gibt es einen Algorithmus.
    Im Programm kannst du aber die Region-Funktionen des OS verwenden (CreatePolygonRgn
    und PtInRegion). Das ist wahrscheinlich schneller als der Algorithmus.
    Gruss,

    Neptun

    Hallo, lieben Dank für eure Antworten,
    plotten war wohl der falsche Ausdruck, zeichnen im Allgemeinen sollte es sein.

    Ich versuche im Grunde eine Textur auf ein Dreieck zu mappen, gibt zwar TextureBrush, aber es bietet eben keine Textur-Koordinaten für die einzelnen Ecken
    des Dreiecks an, weswegen das ganze so komisch und dynamisch ist: Wenn das Dreieck größer wird, wird die Textur entsprechend umfassender angezeigt, wenn sie kleiner wird
    nur ein kleiner Bereich der Textur.

    Zwar bietet TextureBrush Möglichkeiten zur Manipulation an, exemplarisch Scale, Transform Rotation, aber wollte ungefähr so etwas Ähnliches wie bei DirectX erzielt bekommen.
    Und da war dann eben meine Idee jeden einzelnen Pixel selbst über LockBits zu setzen: Gibt aber herbe Perfomance-Probleme.

    Hier mein FloodFill-Algorithmus:

    C#-Quellcode

    1. static PointF[] pixels = new PointF[1920 * 1080];
    2. public static Tuple<PointF[], int> FloodFillTriQua(PointF[] points)
    3. {
    4. var pts = points.OrderBy(p => p.Y).ToArray();
    5. PointF up = pts[0];
    6. PointF down = pts[pts.Length - 1];
    7. pts = points.OrderBy(p => p.X).ToArray();
    8. PointF left = pts[0];
    9. PointF right = pts[pts.Length - 1];
    11. RectangleF rect = new RectangleF(down.X, up.Y, right.X - left.X, down.Y - up.Y);
    13. int a = 0;
    15. for (int i = (int)rect.X; i < (int)rect.X + (int)rect.Width; i++)
    16. {
    17. for (int j = (int)rect.Y; j < (int)rect.Y + (int)rect.Height; j++)
    18. {
    19. PointF p = new PointF(i, j);
    20. if (PointInPolygon(points, p))
    21. pixels[a++] = p;
    22. }
    23. }
    25. return new Tuple<PointF[], int>(pixels, a);
    27. }


    pixels ist bereits einmalig deklariert, damit ich nicht immer wieder ein Array erstellen muss.
    Und PointInPolygon hab ich aus StackOverflow:

    C#-Quellcode

    1. public static bool PointInPolygon(PointF[] points, PointF pt)
    2. {
    3. int i, j = 0;
    4. bool c = false;
    5. for (i = 0, j = points.Length - 1; i < points.Length; j = i++)
    6. {
    7. float x = points[i].X;
    8. float y = points[i].Y;
    10. float jx = points[j].X;
    11. float jy = points[j].Y;
    13. if (((y > pt.Y) != (jy > pt.Y)) &&
    14. (pt.X < (jx - x) * (pt.Y - y) / (jy - y) + x))
    15. c = !c;
    16. }
    17. return c;
    18. }


    Ziemlich cool der Test.. aber eben nicht performant.
    Hatte schon die Idee glaub ich gehabt, einfach zwei Wertepaare zu berechnen ( also v1 und v2 bilden eine Gerade und v2 und v3 eine andere, und jede Gerade durch ihren m Wert dividieren, sodass man zu jedem X entsprechend zwei Y Werte kriegt. Keine Ahnung ob das funktioniert..) Ich guck mal diesen Bresenham's Linien Algorithmus an
    Und Gott alleine weiß alles am allerbesten und besser.

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „φConst“ ()

    φConst schrieb:

    Gibt aber herbe Perfomance-Probleme

    Denk bei Zeitmessungen immer daran das ganze im Release ohne Debugger dran zu testen. Wenn man selbst viele Methodenaufrufe oder Logik hat kann im Release der Optimierer mit dem Jit schon einiges bringen. Die C# implementierung von LZMA beispielsweise komprimiert ein 200MB Datei bei mir im Debug inerhalb von 6 Minuten und im Release 1 Minute und 20 Sekunden.

    Naja klar, ValueTuple wäre z.B. schonmal besser.
    Was dann noch besser Wäre, wäre ein einfacher ScanLine Algorithmus. Optimieren könnte man dann später evtl. mittels Bresenham, aber dafür musst du die Polygone auch selbst triangulieren(oder du hast es bereits in triangulierter Form, was ja bei DirectX/OpenGL/Vulkan der Fall ist).
    ScanLine ist quasi, dass du eine Horizontale Gerade durch das Polygon ziehst und nur die Intersection mit den Edges des Polygons berechnest, dann musst du zwischen diesen ja nur über eine for-schleife die Punkte ausfüllen(Sonderfälle darf man auch nicht vergessen, z.B. wenn es direkt durch ein Vertex geht).

    Bresenham bringt dabei nur den Vorteil, dass eine jeweilige Scanline Kollision auf Basis des vorhergehenden Ergebnis berechnet werden kann und das ganze mit reinen int-Berechnungen, was das ganze relativ performant machen dürfte(zumindest für CPU).

    Für die Texturkoordinaten müsstest dir dann Baryzentrische Koordinaten ansehen, wofür du auch das Polygon Trianguliert brauchst.
    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---