Algo BMP->Multi Drawstat
Posté le 15/08/2018 23:40
Le sujet est apparu dans la shout, et je me suis dit qu'il y avait peut être possibilité de faire un algo potable. L'algorithme vise à obtenir la solution optimale (pas juste une solution potable).
On va prendre comme l'exemple le sprite de drak, avec uniquement la plus grosse partie :
(du coup il lui manque un oeil et une partie de sa carapace, mais shh.)
Il fait 32x32 px, et on vise un ordre de magnitude de quelques minutes.
On ne prend que le multi drawstat, car dans le super drawstat on doit aussi prendre en compte l'ordre de dessin.
L'algo fera :
0) Division du sprite en plusieurs parties qui ne se touchent pas, et calcul séparé de chacune de ces parties
1) Recensement de chaque point noir du sprite (à la louche, on va dire qu'il y en a 256, soit 1/4 des pixels)
2) Traçage de chaque ligne existante entre chaque point (soit 256*255 = ~65000 ce qui est faisable)
3) Parmi les lignes tracées, ne retenir que celles qui ne traversent que des pixels noirs
On devrait obtenir environ 1000 lignes (au pif total).
4) Parmi les lignes tracées, enlever celles qui sont totalement incluses dans une et une seule ligne, et qui ne voisinent pas d'autres lignes :
On enlève donc la ligne verte (car totalement incluse dans la ligne rouge) :
Par contre, on n'enlève pas la ligne verte ici, parce qu'elle pourrait faire partie de la solution optimale (elle est voisine à une autre ligne) :
5) Parmi les lignes qui restent, enlever celles qui sont superposées (comme on trace les lignes dans les 2 sens, ce qui est obligé car avec l'algo de brezenham ça ne donne pas les mêmes résultats, on peut avoir des lignes verticales ou horizontales superposées)
6) La partie la plus consommatrice : calculer (avec un algo magique) le nombre de lignes minimum pour couvrir tout le sprite.
On a ensuite uniquement besoin de trouver un groupement de lignes qui est égal au nombre de lignes minimum et qui couvre tout le sprite (ça doit se faire assez simplement).
Pour optimiser cette partie, on ne peut pas enlever les lignes qui se superposent. Par exemple, dans ce sprite, la solution optimale contient deux lignes qui se superposent :
La seule optimisation qui me vient à l'esprit est de ne prendre que les groupements qui couvrent tout le sprite. Par contre pour faire ça sans itérer sur chaque groupement (qui, pour 500 lignes, est de l'ordre de 2^500 = 10^150 = quand même beaucoup) aucune idée.
Du coup faudrait implémenter cet algo afin de voir les lignes qui restent à l'étape 6, voir si c'est faisable
Citer : Posté le 17/08/2018 18:40 | #
D'accord, merci pour l'exemple !
Il y a pas un prblème de continuité entre les traits dans ton exemple ?
Parce que le dernier point d'un segment doit être exactement le même que le premier du second. Là tu as trouvé les traits qui ne chevauchent pas.
Citer : Posté le 17/08/2018 18:47 | #
À priori en Multi DS c'est pas un problème.
Citer : Posté le 17/08/2018 18:55 | #
Nope, le multi drawstat est composé de vecteurs et non pas de points (ce qui le rend plus optimisé car les lignes n'ont pas à se chevaucher, et plus facile à calculer car on ne doit pas prendre en compte le levé de crayon).
Je précise d'ailleurs que les 70 lignes sont pour la plus grande partie du sprite, que j'ai updaté dans le topic.
Ecrivez vos programmes basic sur PC avec BIDE
Citer : Posté le 17/08/2018 19:11 | #
Ah je pensais que tu voulais faire du Super DrawStat pardon (à part ça je connais bien c'est moi qui ait inventé la méthode
Très bien, par contre j'ai quelques objections
Le MDS est plus gourmand en mémoire car tu dois renseigner deux points par segments plus la variable T, alors que c'est 1 point par segment en SDS.
Il peut être bien plus rentable de faire du cheuvauchement que de l'éviter à tout prix :
Ajouté le 17/08/2018 à 19:19 :
arrff je sais je suis chiant je suis trop tatillion
Citer : Posté le 17/08/2018 22:07 | #
En voyant ton image je me suis dit que le plus simple serait peut être d'avoir l'image en fond clair, puis redessiner par dessus l'image avec des traits. Laisser l'utilisateur trouver la meilleure façon...
Drak a fait ça. Vois dans son topic, l'outil existe, il est prêt, il est utilisable.
Nope, le multi drawstat est composé de vecteurs et non pas de points (ce qui le rend plus optimisé car les lignes n'ont pas à se chevaucher, et plus facile à calculer car on ne doit pas prendre en compte le levé de crayon).
Dans ce cas-là, ce que tu as fait est stupide, tu devrais garder les traits maximaux. Dans ton point 4, le cas où tu dis « là par contre on ne retire pas », tu devrais retirer. En MDS le fait d'être voisin d'une autre ligne n'apporte en effet aucune optimisation.
Le MDS est plus gourmand en mémoire car tu dois renseigner deux points par segments plus la variable T, alors que c'est 1 point par segment en SDS.
Je vois d'autres avantages au Super DrawStat :
- On peut le stocker en-dehors du code
- On peut concaténer des listes pour accélérer certains tracés
- (On peut le modifier en éditant les listes)
Citer : Posté le 17/08/2018 22:42 | #
Nope, je vais prendre comme exemple ce sprite :
Si on prend le trait maximal, ça fait 3 traits :
Si on fait en diagonale, ça fait 2 traits :
Du coup la ligne verte du point 4 pourrait parfaitement faire partie de la solution optimale.
Ecrivez vos programmes basic sur PC avec BIDE
Citer : Posté le 17/08/2018 22:43 | #
Sauf que là, le trait maximal, c'est la diagonale de droite dans la troisième image. En effet, (5,1) est plus long que (5,0).
Citer : Posté le 17/08/2018 22:45 | #
En effet. Du coup, ce sprite :
Le trait maximal fait 4 mais les diagonales font 3.
Ecrivez vos programmes basic sur PC avec BIDE
Citer : Posté le 17/08/2018 22:46 | #
Pas exactement 3, mais oui, là c'est correct.
Citer : Posté le 18/08/2018 00:34 | #
Je sais que cette intervention n'est pas très utile, mais j'adore ce sujet de conversation ! Je trouve vos échanges riches et passionnants !
Citer : Posté le 18/08/2018 10:33 | #
En effet. Du coup, ce sprite :
Le trait maximal fait 4 mais les diagonales font 3.
Je ne vois pas vraiment pourquoi. Je pense que, dans ta phase 4, tu devrais retirer tous les traits qui sont entièrement inclus dans d'autres.
Ici, les deux traits que tu utilises pour former ta solution optimale ne sont inclus dans aucun autre. Donc moi, je les aurais conservés, et j'aurais donc trouvé ta solution optimale.
Si tu veux, je peux prouver que ma remarque est juste de façon formelle. Comme ça, ce que je raconte sera plus clair
Citer : Posté le 18/08/2018 10:54 | #
Je vais faire beaucoup de sprites d'exemple moi
Dans celui ci, la ligne rouge est totalement incluse dans la bleue, mais elle fait partie de la solution optimale. (après oui, on pourrait mettre le trait bleu au lieu du rouge et ça donnerait la même chose, mais on superpose un pixel
D'ailleurs c'est vrai que si on suppose que la longueur des lignes n'importe pas (à tester) on ne devrait pas pénaliser la superposition, et donc on pourrait arriver à une solution optimale bien plus rapidement.
Ecrivez vos programmes basic sur PC avec BIDE
Citer : Posté le 18/08/2018 10:58 | #
Je crois que vous partez trop loin. On vous demande pas LA solution optimale, on vous demande une solution optimale. Dans les deux cas ça ma parait raisonnable de tracer le dessin en 3 traits, quelque soit leur longueur.
Et puis si vous voulez faire un concours de solution, why not x)
Citer : Posté le 18/08/2018 11:30 | #
Quelques benchmarks :
- Tracer 50 fois un trait de longueur 1 : 2947 ms
- Tracer 50 fois un trait qui fait la diagonale de l'écran : 3183 ms
- Tracer 50 fois 2 traits de longueur 1 : 3150 ms
Une différence d'un pixel fait une petite différence : 3030ms contre 3050 ms pour 50 traçages de lignes de 47 et 48 pixels respectivement.
Du coup il est mieux de ne pas superposer les lignes, mais l'algorithme devra le faire pour pouvoir supprimer les lignes totalement incluses dans d'autres lignes (afin de diminuer le nombre de lignes).
On va dire que rajouter 100 pixels équivaut à rajouter une autre ligne.
Ecrivez vos programmes basic sur PC avec BIDE
Citer : Posté le 18/08/2018 11:45 | #
Je vais faire beaucoup de sprites d'exemple moi
Dans celui ci, la ligne rouge est totalement incluse dans la bleue, mais elle fait partie de la solution optimale. (après oui, on pourrait mettre le trait bleu au lieu du rouge et ça donnerait la même chose, mais on superpose un pixel
Eh bien oui. On peut mettre le bleu et on superpose un pixel. Moi je dis que tu devrais mettre le bleu. Ça ne te coûte pas plus cher en temps de tracé.
Par contre, tu peux gagner beaucoup de lignes dans ton set. Je trouve que c'est hyper important !
Mais bien sûr, c'est ce que je prétends depuis le début ! xD C'est vrai que je ne l'ai pas mentionné sur ce topic, mais j'ai plusieurs fois suggéré que les deux difficultés étaient :
1. Gérer le levé de crayon (Super DrawStat seulement)
2. Exploiter l'autorisation de réécrire les pixels noirs
Je crois que vous partez trop loin. On vous demande pas LA solution optimale, on vous demande une solution optimale. Dans les deux cas ça ma parait raisonnable de tracer le dessin en 3 traits, quelque soit leur longueur.
Et puis si vous voulez faire un concours de solution, why not x)
Traiter les petits exemples à la main est la meilleure façon de comprendre ce qu'il se passe !
On va dire que rajouter 100 pixels équivaut à rajouter une autre ligne.
Merci pour le benchmark ! Je suis prêt à considérer que le coût du temps de tracé est négligeable par rapport au gain en temps de recherche, donc on ne sait toujours pas d'ailleurs s'il sera raisonnable.
Citer : Posté le 18/08/2018 16:03 | #
Y'a un problème dans l'algo
Dans ce cas, je vire pas la ligne verte, qui est elle-même inclue dans la ligne rouge et dans la ligne rouge moins 1 pixel
Ça demande un peu plus de réflexion pour ne garder que les lignes pertinentes.
Citer : Posté le 18/08/2018 16:47 | #
J'étais justement en train d'argumenter que la phrase devrait être :
Le débat de tout à l'heure, où tu as dit qu'on se cassait la tête pour rien, était pour en décider... é_é
Citer : Posté le 18/08/2018 16:52 | #
En effet, je dirais "qui ne voisine pas d'autres lignes allant dans une direction différente".
Ecrivez vos programmes basic sur PC avec BIDE
Citer : Posté le 18/08/2018 16:56 | #
En effet, je dirais "qui ne voisine pas d'autres lignes allant dans une direction différente".
Théorème : toute ligne incluse dans une autre ligne est inutile.
Preuve : soit L une ligne totalement incluse dans une autre ligne L'. Soit S une solution optimale.
Si L ∉ S, alors L est inutile.
Si L ∈ S, soit S' = S \ { L } ∪ { L' }, c'est-à-dire la solution S où L a été remplacée par L'.
- S' est toujours une solution : comme L ⊆ L', S' couvre tous les pixels noirs. De plus, comme L' ne couvre que des pixels noirs, S' couvre uniquement des pixels noirs.
- S' est optimale car |S'| = |S|.
Ainsi il existe une solution optimale S' qui n'utilise pas L, donc L est inutile.
-
Convaincu ?
Citer : Posté le 18/08/2018 18:08 | #
Que signifie |S| ?
Citer : Posté le 18/08/2018 18:11 | #
Le cardinal de l'ensemble, soit le nombre de lignes dans la solution.