Remplissage d'un polygone: Exécution d'une règle d'enroulement par rapport à une règle impaire

Question

Pour un polygone complexe (ie: auto-intersection), le choix entre les règles de remplissage Enroulement ou Pair-impair fait une différence dans la manière dont le polygone est rempli. Mais pour les polygones qui ne se croisent pas, il existe une différence de performance entre les règles de remplissage Winding ou Even Odd. Je comprends que ce serait spécifique à l'implentation, mais lequel des algorithmes est le plus efficace pour les polygones non complexes.

Une question de suivi quelle est la complexité (c'est-à-dire O (quoi?)) De chacun de ces algorithmes. Je veux savoir si cela vaut la peine de se débarrasser de certains points du polygone (principalement des doublons ou de ceux qui sont sur la même ligne) pour améliorer les performances.

PS: S'il importe du tout, je me sers xlib

PPS: Je peux confirmer le problème est pas lié au matériel que l'utilisation d'une carte graphique différente ne change pas les performances

Answer 1

Aujourd'hui, la plupart implémentations de X utilisent le matériel 2D de votre carte graphique de sorte que la différence entre les deux est probablement négligeable. Puisqu'il s'agit d'une question de performance, les chances que ma réponse soit correcte sont d'environ 10% (avec une performance, vous avez 90% de chances de vous tromper sans mesurer). Si vous voulez être sûr, il n'y a pas d'autre moyen que d'écrire un petit test de performance et de voir par vous-même.

x11perf pourrait aider.

Vous pouvez trouver l'algorithme pour le matériel de remplissage de polygone indépendant ici: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolygen.c?rev=HEAD

Il y a une deuxième version qui est beaucoup plus rapide si vous êtes sûr que votre polygone est convexe: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolycon.c?rev=HEAD

La deuxième version ne tient pas compte de la règle de remplissage (qui ne s'applique pas aux polygones convexes). Commentaires sur l'algorithme: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipoly.h?rev=HEAD

L'algorithme fonctionne de la façon suivante: Il calcule le contour, puis crée des objets span (qui sont juste une coordonnée x, y et une largeur) entre les bords. Si vous utilisez la règle EvenOdd, d'autres objets span seront créés s'il y a des intersections. S'il n'y en a pas (par exemple, lorsque le polygone est convexe), vous ne remarquerez pas de différence d'exécution car la règle de remplissage équivaut à une variable booléenne dans la boucle principale de miFillPolygon (ie la plupart du code est identique remplir les règles). Essayer d'améliorer les performances en optimisant les contours du polygone ne vous coûtera pas beaucoup dans le cas le plus commun sauf si vous savez que vos polygones contiennent un très grand nombre de points inutiles (disons, vous pouvez vous débarrasser de la moitié du nombre des points dans le cas commun). L'optimisation d'un polygone avec < 10 points coûtera probablement plus qu'il n'atteint.

Mais encore une fois: Tout cela est basé sur le sentiment de l'intestin ou la connaissance d'un vieil article. Si vous voulez savoir si des bugs dans votre pilote de carte gfx affectent le résultat, vous devez vous salir les mains et écrire un test qui mesure la durée de chaque cas. Il n'y a aucun moyen de déterminer l'exécution d'un algorithme complexe en le regardant simplement à cause de facteurs externes: vitesse des routines d'allocation de mémoire, quantité de mémoire libre (quand le swap démarre), nombre de cœurs de processeur que vous pouvez utiliser, combien d'autres processus vont vous battre pour le CPU, le découpage du polygone final sur l'écran, les détails d'implémentation et les optimisations, les bugs, etc.