Remplir un polygone: Performance de Winding Rule vs Even Odd Rule

Question

Pour un polygone complexe (c'est-à-dire: auto-intersection), le choix entre les règles de remplissage Winding ou Pair-Impair a une incidence sur le remplissage du polygone.

Mais pour les polygones ne se croisant pas, existe-t-il une différence de performance entre les règles de remplissage Winding et Pair Impair? Je comprends que ce serait spécifique à l’implémentation, mais lequel des algorithmes est le plus efficace pour les polygones non complexes.

Une question de suivi est la complexité (c.-à-d. O (quoi?)) de chacun de ces algorithmes. Je veux savoir s'il est utile d'éliminer certains points du polygone (principalement les doublons ou ceux qui se trouvent sur la même ligne) pour améliorer les performances.

PS: Si cela compte, j'utilise xlib

PPS: Je peux confirmer que le problème n'est pas lié au matériel car l'utilisation d'une autre carte graphique ne modifie pas les performances

Answer 1

Aujourd'hui, la plupart des 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.

Comme il s’agit d’une question de performance, ma probabilité d’être correcte est d’environ 10% (avec une performance, vous avez 90% de chance de vous tromper sans mesurer). Si vous voulez en être sûr, vous n'avez pas d'autre moyen que d'écrire un petit test de performance et de constater par vous-même.

x11perf pourrait vous aider.

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

Il existe une deuxième version 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 ignore la règle de remplissage (qui ne s'applique pas aux polygones convexes). Commentaires sur l'algorithme: http: // cvsweb .xfree86.org / cvsweb / xc / programmes / Xserver / mi / mipoly.h? rev = HEAD

L’algorithme fonctionne de la manière suivante: il calcule le contour, puis crée des objets d’échelle (qui ne sont que des coordonnées x, y et une largeur) entre les arêtes. Si vous utilisez la règle EvenOdd, plusieurs 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 (c'est-à-dire que le code est identique pour les deux). remplir les règles).

Essayer d'améliorer les performances en optimisant les contours du polygone ne vous rapportera pas grand-chose dans les cas courants, sauf si vous savez que vos polygones contiennent un très grand nombre de points inutiles (par exemple, vous pouvez vous débarrasser de la moitié du nombre de points). points dans le cas commun). Optimiser un polygone avec & Lt; 10 points coûteront probablement plus cher que prévu.

Mais encore une fois: tout ceci est basé sur le sentiment de l’intestin ou la connaissance d’un vieil article. Si vous voulez savoir si des bogues dans le pilote de votre carte gfx gâchent le résultat, vous devez vous salir les mains et écrire un test qui mesure la durée de chaque cas. Il n’existe aucun moyen de connaître le temps d’exécution d’un algorithme complexe en le regardant simplement en raison de facteurs externes: vitesse des routines d’allocation de mémoire, quantité de mémoire disponible (quand le swapping démarre), nombre de cœurs de processeur que vous pouvez utiliser, combien d’autres processus vous disputeront pour le processeur, le découpage du dernier polygone à l’écran, les détails et optimisations d’implémentation, les bogues, etc.