Un algorithme simple pour decouper un polygone à partir d’une image
Contexte
Afficher des sprites peut vite devenir inutilement couteux si un gros pourcentage de l’image contient seulement des pixels transparents.
Une optimisation efficace est de transformer un ‘quad’ texturé, en un polygone texturé qui contient moins de pixels transparents. On gagne aussi la possibilité de faire du bin packing polygonal pour obtenir des textures moins larges.
La difficulté étant de trouver un polygone avec le moins de triangles possibles (les triangles aillant aussi un cout de rendu) tout en minimisant la surface transparente affichée.
Algorithme
1. Simplification
On fait un downscale nearest neighbor pour simlifier le sprite. Plus le downscale est fort et plus le polygone sera approximatif, moins il y aura de triangles.
On obtient un polygone de base étant simplement le contour de cette nouvelle surface. On supprime les points inutiles, n’étant pas nécessaires pour la prochaine étape.
On a donc les points suivants:
2. Reduction des vertex
Maintenant le but est de réduire au mieux le nombre de points en supprimant les vertices inutiles. On peut définir une règle assez simple pour savoir si un point est utile ou non:
- si le point est enlevé et que le nouveau segment coupe l’image, il est utile
- si une fois le point enlevé, la surface ajoutée est supérieure a X cases (j’ai pris 3 dans mon exemple ci dessous), il est utile
- sinon il est inutile
On part du point ou il y a une petite croix et on applique l’algo de suppression pour chaque point qui va suivre.
Le point de départ ne semble pas important (d’après mes autres tests manuels). Mais sinon il devrait y avoir un moyen de trouver une heuristique correcte (cela semble dépendre de “l’angle” externe du coin ou il se situe, sa taille etc).
Les points bleus sont les points jugés inutiles après le parcours de l’algorithme.
3. Triangulation
On a désormais 18 points, on peut utiliser une triangulation pour voir le résultat final.
16 tris
4. Post processing
Étape facultative qui peut faire gagner pas mal de surface, surtout quand il a peu de triangles.
Pour chaque point exterieur, on fait glisser le point vers l’interieur du polygone d’un pas fixe (une petite valeur pour plus de précision).
On répète l’opération tant qu’il est possible de contracter des vertices.
Améliorations possibles
Avec une bonne heuristique, une fois qu’on a cette “peau”, on pourrait être tenté d’ajouter de nouveaux points pour voir s’ils permettent d’en supprimer d’autres.
Il serait intéressant de bouger des points vers l’extérieur pour voir si cela ne permet pas de simplifier la forme.
Exemples avec des grilles plus larges
Voici des exemples avec une grille plus grosse.
7 tris
On remarquera que le nombre de tris nécessaires diminue grandement, tout en perdant en surface inutile.
5 tris
Un post processing est d’autant plus important sur une grille large.
Calculs
L’image d’origine fait 301x224 = 67 424 pixels.
On utilise imagemagick pour compter les pixels blancs et noirs.
convert image.png -define histogram:unique-colors=true -format %c histogram:info:-
46 284 pixels black
21 140 pixels white
On a donc ~69% de l’image qui est transparente, mais va quand même faire calculer le pixel shader.
46284/(301⋅224)⋅100 = ~69
44 669 pixels black
33 136 pixels white
La version polygonale à 16 triangles a quand à elle ~12k pixels inutiles à afficher.
On à réussi à éliminer 74% des pixels transparents avec cette version.
100−(33136−21140)/46284⋅100 = ~74