appartenance d'un point à un triangle

[deathangel]

Salut tout le monde

voilà, je suis actuellement confronté à un problème d'algo (en partie résolu).
Il s'agit de l'appartenance d'un point à un triangle.

Un triangle est un triplet de points, chaque point ayant une coordonnée x et y.
On doit savoir si un point (x,y) se trouve dans ce triangle.

J'ai testé l'algo du nombre d'intersections avec une demie droite -> fonctionne difficilement car beaucoup de cas à traiter (le point à vérifier se trouve dans l'alignement d'une arête) mais ca passe. Son problème est qu'il est horriblement lent vu la quantité de données que j'ai à traiter (retrouver dans quel triangle parmi plus de 3 000 000 se trouve mon point)

J'ai ensuite testé la méthode de calcul des angles. La somme des angles entre les segments (centre-triangle[i]) et (centre-triangle[i+1]) = 360 °.
Fonctionne à peu près, mais toujours aussi lent car nécessité de trier les vertex du triangle dans le sens trigo + calcul de sinus/cosinus

Donc j'aurais aimé savoir si vous aviez des autres idées pour faire un tel calcul mais beaucoup plus rapidement.

merci d'avance

[Lightness1024!]

http://forum.games-creators.org/showthread.php?t=2124&highlight=triangle

vive rechercher :)

aucun algo de detection point/triangle ne sera assez rapide pour 3 millions de triangles par frame. Le code qui s'execute le plus vite est le code qui ne s'execute pas !
donc tu dois partitionner ton espace pour ne tester que les bonnes zones.

[deathangel]

c'est pas 3 millions de triange par frame, c'est pour un traitement prérendu de triangulation de delaunay et approximation d'un terrain. Mais je passe plus de temps sur des tests que sur de la prog :s

[Atréides]

Hmm.. tu ne peux pas lancer ton prog le soir ?

[deathangel]

ben c'est encore en cours de développement donc je dois faire des tests régulier, sinon c'est ce que je fais, je lance la nuit...

[Lightness1024!]

d'accord, je suppose que ton algorithme est quadratique alors.
i.e.: par exemple tu testes pour chaque point l'intersection avec chaque triangle ?

ce qui en effet sur 3 millions de triangles ca doit prendre une demi heure non ?
tu pourrais diviser le temps par un tout petit peu plus que 1 en optimisant mais ca sera pas transcendant. La meilleure des optimisation c'est la diminution de la complexité moyenne.
je conseille de trouver des heuristiques.

moi personellement j'ai rajouté avant chaqun de mes tests de collisions, l'exclusion bounding box qui est super efficace quand les points sont super loins des triangles et n'ont donc aucune chance de collisionner.

edit: et le test par systeme d'intersection de segments comme tu l'as est lent en effet, la somme des angles encore pire et peu précis, une méthode meilleure est celle que j'ai préconisée dans le topic que j'ai cité dans mon premier post sur ce thread, je te conseille de l'étudier ;)

[deathangel]

pour optimiser, j'ai déjà diviser mon terrain en quadtree, et je suis en train d'essayer de voir pour la position relative par rapport aux segments composants le triangle (d'après ce que j'ai compris du lien que tu avais filé, merci)

L'autre truc qui est lent c'est le format de stockage des données je pense. Tous les triangles sont stockés dans un vector et la vitesse de celui-ci n'est pas transcendante comparé à un tableau. Seul problème, c'est que je peux pas le modifier, sinon les 95% du gros programme qui me fait le calcul ne marchera plus :(

[grob1212]

Pas moyen de profiter de la puissance de calcul du GPU ? Lorsque le problème est grandement parallèlisable, on peut utiliser les multiples unités de calcul du GPU pour gagner du temps. C'est ce que j'ai fait dans ma thèse pour améliorer l'efficacité de mon algorithme de vision par ordinateur d'un facteur 100 par rapport à une implémentation purement CPU.

Ce n'est toutefois qu'une piste, il faut vérifier si ton algo peut tirer partie de la puissance du GPU, et prendre en compte la difficulté relative de l'implémentation. Pour plus d'informations sur le GPGPU : http://www.gpgpu.org

[wedge]

Salut :)

Perso j'ai trouvé cet algorithme qui marche pas trop mal :) peut être à adapter selon tes besoins :)


typedef struct POINT_tag // POINT_t …… ?
{
int x; // x ??
int y; // y ??
} POINT_t;


typedef struct LINE_tag // LINE_t …… ?????
{
POINT_t a; // ??
POINT_t b; // ??
} LINE_t;

typedef struct TRIANGLE_tag // TRIANGLE_t …… ???
{
POINT_t a;
POINT_t b;
POINT_t c;
} TRIANGLE_t;

int side( POINT_t *p, LINE_t *e )
{

POINT_t p1 = *p;
POINT_t p2 = e->a; // ???? e ???
POINT_t p3 = e->b; // ???? e ???

// ???? (p2,p1), (p2,p3) ???????
const int n = p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);
if ( n > 0 ) return 1; // ?
else if ( n < 0 ) return -1; // ?
else return 0; // ??
}//side

bool PointInTriangle( POINT_t *p, TRIANGLE_t *t )
{
LINE_t ab, bc, ca;
ab.a = t->a; ab.b = t->b;
bc.a = t->b; bc.b = t->c;
ca.a = t->c; ca.b = t->a;
const int pab = side( p, &ab ); // ???? ab ????? p ???
const int pbc = side( p, &bc ); // ???? bc ????? p ???
const int pca = side( p, &ca ); // ???? ca ????? p ???

// ???????????
if ( (0 < pab) && (0 < pbc) && (0 < pca) )
return true; // ? p ????????(????)
if ( (0 > pab) && (0 > pbc) && (0 > pca) )
return true; // ? p ????????(?????)

// ???????????
if ( (0 <= pab) && (0 <= pbc) && (0 <= pca) )
return false; // ? p ????????(????)
if ( (0 >= pab) && (0 >= pbc) && (0 >= pca) )
return false; // ? p ????????(?????)

// ?????????? 0
return false;
}//PointInTriangle


Désolé pour les commentaires mais ca vient d'un site japonais donc meme moi je peux pas tradur, mais j'ai fais les tests et ca marche très bien chez moi, dans mon petit algorithme.