AccueilAccueil  FAQFAQ  RechercherRechercher  S'enregistrerS'enregistrer  MembresMembres  Connexion  

Partagez | 
 

 Decouper un polygone a partir d'une image

Voir le sujet précédent Voir le sujet suivant Aller en bas 
AuteurMessage
onilink_
Modérateur
avatar

Messages : 8902
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Decouper un polygone a partir d'une image   Lun 23 Jan 2017 - 21:01

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.

_________________
                 
Revenir en haut Aller en bas
arthuro
Utilisateur confirmé: Rang ****
avatar

Messages : 1321
Localisation : Grenoble / Méribel
Projet Actuel : CBNA

MessageSujet: Re: Decouper un polygone a partir d'une image   Lun 23 Jan 2017 - 23:01

Je pense que j'ai la solution idéale pour toi.

C'est exactement le même problème que en 3D mais en 2D.

Au lieu d'avoir un contour fait de maillage de triangles, tu as un maillage de segment  (Ensuite avec les segment, tu régénère tes triangles un avec algorithme de triangularisation de polygone).
Pour simplifier ton maillage 2D (=polygone), je te conseille de choisir un 'bon' algorithme.


Je te propose 3 étapes:
1) Marching square ( le version 2D du marching cube ) à partir de l'image de ton sprite (épaissi de 1-2 pixels)
2) Simplification du contour/maillage 2D par (http://mgarland.org/research/quadrics.html  (C'est un algorithme 3D, mais il fonctionnera à merveille en 2D).
3) Triangularisation du polygone simplifié (http://www.f-legrand.fr/scidoc/docmml/graphie/geometrie/polygone/polygone.html)

Normalement chaque étapes devrait te prendre 1 jours de développement. (~4/5 par jours)

J'ai déjà implémenté plusieurs fois chacun des algorithmes. N'hésite pas à me poser des questions (forum/skype/email).

Une petit explication de l'algorithme 2)
Spoiler:
 

Alternatives :
https://fr.wikipedia.org/wiki/Algorithme_de_Douglas-Peucker



PS: Petit soucis avec cette idée, c'est que la polygone n'est pas garantis de contenir ton sprite. Mais normalement, si tu épaissit ta forme de 2-3 pixels et qu'il y a asser de segment, le sprite ne devrait pas dépassé. Au pire, tu peux faire tourner plusieurs fois l'algorithme en augmentant l'épaisseur et le nombre de segments de manière automatique.

_________________

D'autres jeux :
In The Cube
In the cube 2


Dernière édition par arthuro le Lun 23 Jan 2017 - 23:20, édité 1 fois
Revenir en haut Aller en bas
arthuro
Utilisateur confirmé: Rang ****
avatar

Messages : 1321
Localisation : Grenoble / Méribel
Projet Actuel : CBNA

MessageSujet: Re: Decouper un polygone a partir d'une image   Lun 23 Jan 2017 - 23:12

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.

_________________

D'autres jeux :
In The Cube
In the cube 2
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

Messages : 8902
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Re: Decouper un polygone a partir d'une image   Mar 24 Jan 2017 - 9:06

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.




_________________
                 
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

Messages : 8902
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Re: Decouper un polygone a partir d'une image   Mar 24 Jan 2017 - 12:35

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)

_________________
                 
Revenir en haut Aller en bas
arthuro
Utilisateur confirmé: Rang ****
avatar

Messages : 1321
Localisation : Grenoble / Méribel
Projet Actuel : CBNA

MessageSujet: Re: Decouper un polygone a partir d'une image   Mar 24 Jan 2017 - 21:30

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

_________________

D'autres jeux :
In The Cube
In the cube 2
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

Messages : 8902
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Re: Decouper un polygone a partir d'une image   Jeu 26 Jan 2017 - 12:57

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.

_________________
                 
Revenir en haut Aller en bas
arthuro
Utilisateur confirmé: Rang ****
avatar

Messages : 1321
Localisation : Grenoble / Méribel
Projet Actuel : CBNA

MessageSujet: Re: Decouper un polygone a partir d'une image   Jeu 26 Jan 2017 - 22:16

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

_________________

D'autres jeux :
In The Cube
In the cube 2
Revenir en haut Aller en bas
[TheDarkTiger]
Modérateur
avatar

Messages : 7371
Localisation : Essonne

MessageSujet: Re: Decouper un polygone a partir d'une image   Ven 27 Jan 2017 - 11:53

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 ?

_________________
Bonne chance pour vos projets actuels ! Prêt à aider ceux qui en ont besoin ^^
l'antique http://www.membres.lycos.fr/thedarkminousite/
Bienvenue au 2516eme utilisateur : Gyratine !
Revenir en haut Aller en bas
http://www.membres.lycos.fr/thedarkminousite/
Contenu sponsorisé




MessageSujet: Re: Decouper un polygone a partir d'une image   

Revenir en haut Aller en bas
 
Decouper un polygone a partir d'une image
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» [Résolu][VX Ace] "Autotile" à partir d'une image
» Comment insérer une image d'après Servimg.com ?
» Comment créer une image en mosaïque ?
» à partir de quel âge avez vous mis bébé dans son siège iseos
» master culture de l'ecrit et de l'image Lyon II

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum Le CBNA :: Développement :: Programmation-
Sauter vers: