Füllen eines Polygon: Leistung der Windungsregel vs Gerade Ungerade-Regel

Question

Bei einem komplexen Polygon (dh selbstschneid). Die Wahl zwischen der Wicklung oder den Selbst-Odd Füllung Regeln macht einen Unterschied in der Art und Weise das Polygon gefüllt ist

Aber für nicht schneidende Polygone gibt es einen Unterschied in der Leistung zwischen der Wicklung oder der Gerade Ungerade Füllung Regeln. Ich verstehe, wäre es implentation spezifisch, sondern die die Algorithmen ist leistungsfähigere für nicht komplexen Polygone.

Eine Follow-up-Frage, was die Komplexität (dh O (was?)) Von jedem dieser Algorithmen. Ich will wissen, ob es sich lohnt im Polygon von einigen Punkten loszuwerden (hauptsächlich Duplikate oder diejenigen, die auf der gleichen Linie sind) zu verbessern.

PS: Wenn es darauf ankommt überhaupt, ich bin mit xlib

PPS: Ich habe das Problem bestätigen kann, ist keine Hardware im Zusammenhang als eine andere Grafikkarte nicht die Leistung ändern

Answer 1

Heute sind die meisten Implementierungen von X verwenden, um die 2D-Hardware der Grafikkarte, so dass die Differenz zwischen den beiden wahrscheinlich vernachlässigbar ist.

Da dies eine Leistung Frage ist, steht die Chancen meine Antwort richtig sein, sind etwa 10%, obwohl (mit Leistung, Sie eine 90% ige Chance hast, falsch zu sein, ohne Messung). Wenn Sie sicher sein wollen, gibt es keine Möglichkeit, sondern einen kleinen Performance-Test zu schreiben, und überzeugen Sie sich selbst.

x11perf helfen könnte.

Sie können den Algorithmus für die Hardware-unabhängige Polygon finden füllen hier: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolygen.c?rev=HEAD

Es gibt eine zweite Version, die viel schneller ist, wenn Sie sicher, dass Ihr Polygon konvex ist: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolycon.c?rev=HEAD

Die zweite Version ignoriert die Füllregel (die nicht auf konvexe Polygone gelten). Kommentare zum Algorithmus: http: // cvsweb .xfree86.org / cvsweb / xc / Programme / Xserver / mi / mipoly.h? rev = HEAD

Der Algorithmus arbeitet auf diese Weise: Es berechnet die Umrisse, dann Spanne Objekte erstellt (die nur ein x sind, y-Koordinate und eine Breite) zwischen den Rändern. Wenn Sie die EvenOdd Regel verwenden, wird mehr Spannweite Objekte erstellt werden, wenn es Überschneidungen gibt. Wenn es keine gibt (zum Beispiel, wenn das Polygon konvex ist), dann werden Sie nicht einen Laufzeitunterschied bemerken, da die Füllung Regel in der Hauptschleife des miFillPolygon auf eine boolean Variable beträgt (dh der größte Teil des Codes ist für beide gleich füllen Regeln).

Der Versuch, die Leistung zu verbessern, indem die Kontur des Polygons Optimierung werden Sie nicht viel im gemeinsamen Fall kaufen, außer, wenn Sie wissen, dass Ihre Polygone eine sehr hohe Anzahl von unnötigen Punkte enthalten (zum Beispiel, können Sie die Hälfte der Anzahl der loszuwerden weist im allgemeinen Fall). Die Optimierung eines Polygons mit <10 Punkten wird wahrscheinlich mehr kosten, als es erreicht.

Aber noch einmal: Diese basieren alle auf Bauchgefühl oder das Wissen eines alten Artikels. Wenn Sie wissen möchten, ob Fehler in Ihrem Grafikkartentreiber Chaos mit dem Ergebnis, müssen Sie Ihre Hände schmutzig machen und einen Test schreiben, der misst, wie lange jeder Fall nimmt. Es gibt keine Möglichkeit, die Laufzeit eines komplexen Algorithmus zu sagen, indem man einfach es bei der Suche aufgrund externer Faktoren: Geschwindigkeit der Speicherzuweisungsroutinen, Größe des freien Speichers (wenn nicht Swapping Start), die Anzahl der CPU-Kerne die Sie verwenden können, wie viele andere Prozesse werden Sie für die CPU kämpfen, des letzten Polygon auf dem Bildschirm ausschnitt, Details der Implementierung und Optimierungen, Bugs etc.