Decouper un polygone a partir d'une image

Hello,
je cherche actuellement un algorithme d'optimisation de rendu pour découper un sprite dans un polygone qui soit a la fois le plus fidèle possible, mais qui a le moins de triangles.



Je n'ai trouvé que des logiciels payants, aucune source ni algo sur le net.
Ex de logiciels:
https://www.spriteuv.com/#features-section
https://www.codeandweb.com/texturepacker/tutorials/using-spritesheets-with-unity

J'ai trouvé des messages qui parlaient d'utiliser le "Convex Hull" de l'image, sauf que je comprend pas comment on peut partir de ça sur une image comme ci dessus (le dragon), et ils précisaient pas si cela servait pour les polygones concaves...
Bref si vous avez des pistes, je suis preneur!
(dans l'idéal si ça gère les "trous" ce serait le top, mais au pire je ferais sans)

Et au pire je vous tiendrais au courant si je trouve quelque chose.

En faite, j'ai dis plutôt des bétises:

Il existe des algorithme dit "concave hull".

C'est comme si ton sprite était un ensemble de points et qu'on faisait rouler un disque en contact avec ces points.
On supprimer les points qui ne touches jamais le cercle.

Gros cercle => peu de segment.
Petit cercle => beaucoup de segment.

Regarde plutôt ceci:
http://www.portailsig.org/content/sur-la-creation-des-enveloppes-concaves-concave-hull-et-les-divers-moyens-d-y-parvenir-forme
https://github.com/Wildhoney/ConcaveHull


On remarque sur les images que tu nous as données, les sommets des polygones ne sont pas sur la bordure du sprite. Sans doute, qu'il faut ensuite rassembler les sommets du concave hull avec ce que tu décris dans ma première réponse.

Ahah jsuis justement tombé sur ce lien hier soir (mais le forum était down du coup j'ai rien pu poster).
Je pense que le concave hull a plusieurs problèmes en fait, après y avoir réfléchis:
-il faut utiliser tous les points extérieurs sous peine d'avoir une peau qui "mange" sur le sprite
-si on veut pallier a ce problème, il faut utiliser une version simplifiée du sprite, mais dans ce cas je pense justement que le hull deviens presque trivial a faire manuellement

Voici l'idée que j'ai eu et que j'ai testé sur ce sprite:


Première étape, on utilise une grille pour obtenir une version polygonale simplifiée du sprite:


Le polygone étant bêtement le contour de cette nouvelle surface (que l'on peut obtenir avec un algo assez basique constitué d'une boucle et de conditions).
Bon, par contre, ça ne gère pas les trous, mais je pense qu'en découpant l'algorithme en plusieurs étapes cela pourrait marcher.

On a donc les points suivants:


Maintenant le but est de réduire au mieux le nombre de points en supprimant les points 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 au pire il doit y avoir moyen de trouver une heuristique (semble dépendre pas mal 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.


On a désormais 18 points, on peut utiliser une triangulation pour voir le résultat final:

(16 tris)

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
-de même il serait intéressant de bouger des points vers l’extérieur pour voir si cela ne permet pas de simplifier la forme


Je pense que je vais prochainement implémenter l'algo pour voir ce que ça donne sur des formes diverses et variées avec des paramètres de grilles et de suppression differents.

Quelques nouveaux essais avec une grille avec des cellules de 32x32 et de 64x64.


(7 tris)

(5 tris)

Plus la grille est grosse et plus un algo de post processing deviens nécessaire pour limiter les pertes.
On pourrait imaginer ce genre de résultat final:

(on gagne de la place et un tri)


(on gagne de la place et un tri)

ça à l'air de fonctionner à la perfection. Merci pour les images.
Tu va en faire quoi?

Le but est de faire un texture atlas avec optimisations polygonales.
En effet j'ai déjà un packer qui utilise des rectangles et pour les petits sprites tout roule.
Par contre pour les gros sprites cela pose deux problèmes:
-dessiner des surfaces transparentes est inutilement coûteux pour le pixel shader, donc tout sprite concave avec des gros trous comme le dragon ci dessus va avoir des pertes de perfs au rendu (alors qu'avec quelques tris ont peut gagner beaucoup de perfs)
-on perd beaucoup de place lors du bin packing

L'idée est donc d’implémenter l'algo ci dessus, puis de faire un bin packing pour les polygones qui englobent les sprites, et utiliser tout ça pour un système de rendu optimisé.
Je verrais peut être aussi pour faire un système de tesselation qui peut être intéressant dans certains cas (déformations de sprites par ex), a voir.

ça explique pourquoi tu étais intéressé par spriteuv.com !

Pour y avoir réfléchi à ce problème, il y a des choses qu'un logiciel aura beaucoup de mal (voir même ne pourra jamais) trouver.

Principalement, c'est le contexte de l'image.

Enfin, les buts sont probablement différents, donc pour ton application, c'est peut être pas utile.

Moi, c'était pour de l'animation, donc la découpe à la main était 'obligatoire' dans le sens où, comme je bouge les vertexes, si elles sont mal placées, ça fout l'image en l'air.

Si toi, c'est de l'affichage sans déformation (et où tu veux juste optimiser les pixels transparents), alors, une recherche automatique est plus intéressante.

Un exemple concret sur ton dragon, c'est la séparation tête / cou.
à la main, on met les polygones où on veux pour pouvoir bouger la tête et le cou.

Toi, ça sera probablement statique, donc, la position des vertexes est pas cruciale, tant que tu minimise les points transparents.


Dans ce but, je te conseille de grossir ton image de deux trois pixels sur chaque côté, puis de faire une dilatation de ton masque.
Ensuite, relance ton algo, tu mangera moins les bords et ton image étant plus 'mole' et 'ronde', tu pourra mieux optimiser.

Tu peux aussi faire un algo qui "lèche" ton masque en suivant son contour, et qui retiens le nombre de pixels transparents. Si le suivant ajoute plus de pixels qu'un nouveau segment, alors, on clos l'ancien et on en ajoute un nouveau ?
En gérant les marges de pixels en trop, on doit pouvoir faire quelque chose de correct ?

Ou alors, partir sur un blob convexe qui vient coller au masque, puis qui calcule le nombre de pixels économisés et subdivise là où il y a le plus de perte pour tenter d'améliorer le score ?