Algorithme de rectangles recouvrant un masque binaire

Voila, pour mon moteur de collision j'ai besoin de convertir des masques binaires en shapes convexes, du coup j'ai un peu regardé pour avoir un algo pas trop lourd (sachant que l'algo naïf serait de convertir chaque pixel en un carré, ce serait très lourd).

Donc dans l'idée j'ai 3 idées d'algo, mais j'ai réussi (et essayé surtout) que d'implémenter la seconde:

Donc je me demandais si un algo du genre existait déjà histoire de pas réinventer la roue, et si vous pensez que le 3ième algo est optimal quelque soit les cas (pour ma part il me semblerait très logique que oui mais bon, y a peut être moyen de trouver un contre exemple ).

Je t'avoue que j'ai pas trop capté le troisième schéma ^^'
De même, mes numéros c'est quoi?

Sinon je pensais, en général dans le rectangle qui englobe complètement le sprite, bah ia plus de pixels pleins que de pixels vide, donc ce serait ptet mieux de tester les collisions avec les pixels vide et de retourner le contraire, nan ?
Par exemple, si ton cercle fait 50px de rayon :
aire_cercle=pie*50*50=7 854
aire_carre=100*100=10 000
Donc si tu check les pixels qui ne font pas partie du cercle t'as plus que 10 000-7 854=2 146 pixels à vérifier, ca fait dans les 3.5 fois moins!

Perso je passe par des figures polygonales, dont je défini les points correctement pour englober la forme, cette méthode aussi est intéressante mais n'est-elle justement pas plus lourde en calcul ?

Si tu fais par une bibliothèque de forme avec 4 types d'intersection, entre shape, avec un segment, avec un ray, et un point, et 3 types de formes, le rectangle basique, le polygone, de 3 à +infini points, et le cercle, défini respectivement, par un point et une taille, 3 points, et un point et un rayon, ça pourrait aller non ?

Si tu fais un truc assez précis, la marge d'erreur n'excède pas le pixel normalement.

Sinon, dans la logique, l'algo 3 doit suffire, mais, j'ai peur qu'il soit lourd perso. xD

Térence68 a écrit:

Je t'avoue que j'ai pas trop capté le troisième schéma ^^'
De même, mes numéros c'est quoi?

Le nombre de rectangles qu'il faut pour composer le masque selon la méthode utilisée.
Ça permet ensuite de faire des tests de collisions avec des polygones.
Pour le 3 ième algo je remplis juste la forme de rectangles "maximaux" qui se chevauchent.

Térence68 a écrit:

Sinon je pensais, en général dans le rectangle qui englobe complètement le sprite, bah ia plus de pixels pleins que de pixels vide, donc ce serait ptet mieux de tester les collisions avec les pixels vide et de retourner le contraire, nan ?
Par exemple, si ton cercle fait 50px de rayon :
aire_cercle=pie*50*50=7 854
aire_carre=100*100=10 000
Donc si tu check les pixels qui ne font pas partie du cercle t'as plus que 10 000-7 854=2 146 pixels à vérifier, ca fait dans les 3.5 fois moins!

Yep c'est pas con, mais dans beaucoup de cas c'est l'inverse en fait si on utilise la 3 ième méthode. Néanmoins ajouter une variable qui indique la méthode après avoir calculé la meilleur en testant les deux, ça pourrait être une bonne opti ouai. A tester donc.

Chlorodatafile a écrit:

Perso je passe par des figures polygonales, dont je défini les points correctement pour englober la forme, cette méthode aussi est intéressante mais n'est-elle justement pas plus lourde en calcul ?

12 intersections box/polygones, de nos jours c'est très léger. Mais ça demande quand même d'avoir une bonne opti de la surface pour pas se retrouver avec un millier de tests inutiles.

Chlorodatafile a écrit:

Si tu fais par une bibliothèque de forme avec 4 types d'intersection, entre shape, avec un segment, avec un ray, et un point, et 3 types de formes, le rectangle basique, le polygone, de 3 à +infini points, et le cercle, défini respectivement, par un point et une taille, 3 points, et un point et un rayon, ça pourrait aller non ?

Non, le pixel perfect c'est très pratique. J'ai déjà les formes de base mais dans certains cas cplus ****** qu'autre chose a utiliser alors qu'un simple masque ferait grandement l'affaire. Puis bon, un game engine n'est pas sensé se contenter de ce qui pourrait aller, il met tout ce dont les gens peuvent avoir besoin.

Chlorodatafile a écrit:

Si tu fais un truc assez précis, la marge d'erreur n'excède pas le pixel normalement.

Sinon, dans la logique, l'algo 3 doit suffire, mais, j'ai peur qu'il soit lourd perso. xD

Ben justement le pixel ça veux rien dire, si ton masque a un scale x16 ça deviens une très grosse marge d'erreur.
Pour la lourdeur des calculs ce sera a l'utilisateur de faire gaffe, mais les intersections par polygone ça reste assez leger quand même si tu fais pas n'importe quoi.


Sinon, en passant, personne connais un algo pas trop ****** a implémenter et surtout efficace pour subdiviser un polygone concave en plusieurs polygones convexes?

Ok, compris.
http://fr.openclassrooms.com/informatique/cours/theorie-des-collisions/formes-plus-complexes
"Un algorithme pour transformer le polygone non-convexe en triangles peut être le suivant :
1 - On parcourt les points du polygone non-convexe.
2 - Pour un point i, on considère son voisin précédent et son voisin suivant. Si le triangle formé par ces trois points est dans le polygone, alors on ajoute le triangle à la liste, et on considère le polygone non-convexe restant comme étant le même polygone auquel on retire le sommet i (on relie donc i-1 et i+1).
3 - etc.

C'est un algorithme glouton, et le polygone restant finit par être un triangle.

On peut tester l'appartenance du triangle en regardant si l'angle du point i est aigu ou obtus par rapport au sens de parcours."
Après j'ai jamais testé donc je sais pas ce que ca vaut.

Ouaip je connais, mais autant ne rien proposer pour la conversion si c'est pour mettre un truc aussi pourri
J'ai déjà vu des algos capable de faire des trucs bien classe, y en a un dont j'avais la source mais il était quand même bien compliqué.
Au pire les gens feront ça manuellement en attendant (avec un éditeur de polygones cpas bien compliqué)

Je peux te proposer un truc sympa.
C'est très dépendant de l'architecture que tu as déjà mis en place et de tes exigences en terme de performance. (Des fois, c'est mieux de faire quelque chose de naïf : plus rapide a concevoir, plus maintenable, moins performant )

Si tu est pret à modifier un poil ton détecteur de collision.
Tu pourrais faire cela:

Le masque de collision est un quadtree englobant ton objet:
premier niveau la AABB englobante,
récursivement, une boite peut être pleine, semi-pleine ou vide.
les boite semi-pleine sont découpé en 4 boîtes qui peuvent êtres pleines, semi-pleine, ou vide.
On découpe récursivement, je pense que tu comprend parfaitement le principe.

Du coup la collision se fait entre les box de niveau 1. Si le test est valide, on passe au niveau 2. Pour chaque couples de boites de niveau 2 collisionnante, on fait le test de niveau 3 et ainsi de suite.
A la fin, il peut rester des boites pleines en collisions ou plus rien. C'est ce qui te donne l'indication si les deux objets sont en collisions.


avantages:
* Tests simples (AABB <-> AABB)
* Toutes les formes sont possibles. (non-convexe, non-connexe, ...)
* Algo pas trop compliqué.
* Bonnes performances : 99% du temps on fait uniquement la collision niveau1 <-> niveau1.  Et lorsqu'il y a vraiment une collision, le nombre de test est assez réduit du fait de la division récursive. En fait, c'est adaptatif, on effectue des calculs que quand on en a besoin.
* assez réduit en taille.

En terme de performance avec ton rond, c'est en moyenne 12 fois plus performant (tu avait 12 AABB).

Après, c'est quand même du boulot, donc il faut être certain d'avoir besoin de performances.

A+ Oni.

_____

AABB = rectangle orienté (droit par rapport à l'écran)

Arthuro, tu viens de me donner une solution à une des grosses pbmatiq de mon moteur physique actuel. o_o

J'avais un fonctionnement similaire, mais, j'avais pas pensé au fait qu'on pouvait descendre en détails récursivement !

M'est avis qu'avec un 'U' à la place d'un disque, tu change pas mal les performances de tes algos onilink_.

La solution d'arthuro me semble plus générale, sauf si bien sûr, tu peux passer par des polygones (ce qui serait, je pense, plus générale, quoi qu'effectivement pas forcément plus performant... Faut voir...).

Avec un gribouillis aussi, mais après c'est a l'user de pas faire n'importe quoi avec.

Surtout qu’après y a la bounding box englobante, et je peut toujours ajouter un système de partitionnement s'il y a plus de N box pour représenter un masque.

Edit: Ah ben j'avais pas vu le poste d'Arthuro mais oui c'est ce qu'il proposais
De base j'utilise déjà ça pour tout ce qui est objets statique.