AccueilAccueil  FAQFAQ  RechercherRechercher  S'enregistrerS'enregistrer  MembresMembres  Connexion  

Partagez | 
 

 Algorithme de rectangles recouvrant un masque binaire

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

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

MessageSujet: Algorithme de rectangles recouvrant un masque binaire   Mar 26 Aoû 2014 - 12:00

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 Razz).

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

Messages : 2213
Localisation : Oui

MessageSujet: Re: Algorithme de rectangles recouvrant un masque binaire   Mar 26 Aoû 2014 - 12:12

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!

_________________
Je suis partie sur les ailes du vent et la tempête m'a ramenée.
Revenir en haut Aller en bas
Chlorodatafile
Utilisateur confirmé: Rang *****
avatar

Messages : 2928
Localisation : Belfort
Projet Actuel :
Paralights

MessageSujet: Re: Algorithme de rectangles recouvrant un masque binaire   Mar 26 Aoû 2014 - 12:19

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. Smile

Sinon, dans la logique, l'algo 3 doit suffire, mais, j'ai peur qu'il soit lourd perso. xD
Revenir en haut Aller en bas
http://chlorodatafile.tumblr.com/
onilink_
Modérateur
avatar

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

MessageSujet: Re: Algorithme de rectangles recouvrant un masque binaire   Mar 26 Aoû 2014 - 16:20

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. Smile

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?

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

Messages : 2213
Localisation : Oui

MessageSujet: Re: Algorithme de rectangles recouvrant un masque binaire   Mar 26 Aoû 2014 - 16:28

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.

_________________
Je suis partie sur les ailes du vent et la tempête m'a ramenée.
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

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

MessageSujet: Re: Algorithme de rectangles recouvrant un masque binaire   Mar 26 Aoû 2014 - 16:50

Ouaip je connais, mais autant ne rien proposer pour la conversion si c'est pour mettre un truc aussi pourri Razz
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 Razz (avec un éditeur de polygones cpas bien compliqué)

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

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

MessageSujet: Re: Algorithme de rectangles recouvrant un masque binaire   Jeu 28 Aoû 2014 - 19:03

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)

_________________

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


Dernière édition par arthuro le Sam 13 Sep 2014 - 20:56, édité 3 fois
Revenir en haut Aller en bas
Chlorodatafile
Utilisateur confirmé: Rang *****
avatar

Messages : 2928
Localisation : Belfort
Projet Actuel :
Paralights

MessageSujet: Re: Algorithme de rectangles recouvrant un masque binaire   Jeu 28 Aoû 2014 - 20:19

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 !
Revenir en haut Aller en bas
http://chlorodatafile.tumblr.com/
[TheDarkTiger]
Modérateur
avatar

Messages : 7377
Localisation : Essonne

MessageSujet: Re: Algorithme de rectangles recouvrant un masque binaire   Mer 10 Sep 2014 - 2:36

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...).

_________________
Bonne chance pour vos projets actuels ! Prêt à aider ceux qui en ont besoin ^^
l'antique http://www.membres.lycos.fr/thedarkminousite/
Bienvenue au 2522eme utilisateur : Rain Bird !
Revenir en haut Aller en bas
http://www.membres.lycos.fr/thedarkminousite/
onilink_
Modérateur
avatar

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

MessageSujet: Re: Algorithme de rectangles recouvrant un masque binaire   Mer 10 Sep 2014 - 7:22

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 Razz
De base j'utilise déjà ça pour tout ce qui est objets statique.


_________________
                 
Revenir en haut Aller en bas
Contenu sponsorisé




MessageSujet: Re: Algorithme de rectangles recouvrant un masque binaire   

Revenir en haut Aller en bas
 
Algorithme de rectangles recouvrant un masque binaire
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» Masque de saison à la fraise : effet coup de fouet pour peau terne
» Masque
» masque carnaval
» Disparition du "masque" titre
» placenta bas inséré et recouvrant..césarienne programmée..

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