Voir la version complète : Collisions qui en veux ? :D
TheTiger
05/11/2005, 16h51
Je viens de découvrir une technique algorithmique pour savoir si un point est dans un triangle ou non...en bidouillant un peu :p
J'ai lu dans un article que si l'on a un triangle ABC et un point P et que l'on veux savoir si P est dans ABC alors on doit calculer le cosinus de chaque angle (PA,PB) (PB,PC) (PC,PA) puis on doit récupérer l'angle en ° et la somme doit faire 360° alors le point est dans le triangle ABC mais cette méthode est assez lourde pour le procésseur car le calcule d'un ARCcos est assez "long" (pa tant que ça mais à force oui)
L'algo ressemble à cela :
//on a 4 points A, B, C,P
//on calcule:
PA=A-P;
Norme(PA);
PB=B-P;
Norme(PB);
PC=C-P;
Norme(PC);
//et on calcule
CosAB=PA*PB
CosBC=PB*PC
CosCA=PC*PA
//enfin on fait la somme des angles
SommeAngle=arccos(CosAB)+arccos(CosBC)+arccos(CosCA)
et si SommeAngle~=360° alors le point P est dans le triangle.
Moi je vous propose la méthode suivante :
//on a 4 points A, B, C,P
//on calcule:
PA=A-P;
Normalize(PA);
PB=B-P;
Normalize(PB);
PC=C-P;
Normalize(PC);
//on fait la somme des vecteurs:
Vecteur SVect=PA+PB+PC;
//on calcule la taille du vecteur SVect
TailleSVect=Norme(SVect);
si TailleSVect>1 alors le point n'est pas dans le triangle
sinon il est dans le triangle !!!
Je ne sais pas si cette méthode existait avant je suppose que oui en tout cas sachet que j'ai trouvé cela en bidouillant un peu :D
Et si des gens sont intéréssés par les collisions notament les elipsoïde ben je partagerais volontier mon expérience :)
deathangel
05/11/2005, 18h01
c'est sympa, mais cette méthode ne fonctionne que sur les polygones convexes.
Pour les polygones quelconques (concave, convexe, à trou), il existe la méthode des intersections, le problème, c'est que cette méthode est également assez lourde :s
La méthode (http://www.iag.asso.fr/articles/intersection.htm)
TheTiger
05/11/2005, 19h38
c'est vrai que cela peut s'étendre à toute la gamme des formes convexes j'y avait même pas pensé...en tout cas merci t'a remarque est vraiment bien malgré qu'ici mon objectif était simplement de savoir si un point était dans un triangle ou non ça m'a ouvert l'espris :D
En tout cas je sens que si j'ai du temps je vais faire une doc sur les collisions... bien entendu il en existe déjà pas mal et je vais m'appuyer sur une en particulier tout en ajoutant certaine techniques tel que celle que j'ai évoquée ci-dessu dans le but de rendre plus complet et assez simple les détections de colisions car je doit l'avouer, cela à était mon principale problème quand j'ai commencé à faire des jeux...
Je proposerais des techinques plus rapide mais moi réaliste au niveau de la gestions de terrain car je sais que pour la plus part des programmeur de jeux ils y en a qui veulent faire des jeux de rôles dans les quel il y a pas mal de terrain, en effet gérer tout les polygones en collisions c'est pas gagné ;)
Enfin je voudrais savoir si il serais possible de créer aprés les cartes graphiques, les cartes physiques :) ça serait comme une carte graphique ou une carte son c'est à dire que cette carte serait spécialisée dans le calcule de colisions mais aussi de réaction physique et cela pourait être pratique et permeterait de rendre des jeux super réaliste non ? Enfin c'est une petite idée sans prétention...
J'espère trouver assez de temps pour tout ça ^^
deathangel
05/11/2005, 20h09
suffit de demander :
ici (http://www.hardware.fr/html/news/?date=09-03-2005#7351) et là (http://www.hardware.fr/html/news/?date=28-10-2005#7862)
TheTiger
05/11/2005, 21h25
Au c'est génial je savais pas que y en a qui on eu l'idée mais là c'est vraiment good merci mec ^^
effectivement c'est aegia qui fait ca, ca a un peu fait de bruit mais pas trop y a 3 4 mois. evidement Havok est derriere (depuis que j'ai vu le unreal engine, je crois que je me trompe pas de moteur, je respecte ces gens !!)
(death angel je te vole pas ton post, je develop un peu parce que ca me branche ce truc)
edit : j'ai merde en lisant, aegia et havok sont pas du tout main dans la main ! c'est vraiment dommage, mais bon ca le fait pour la concurrence positive...
sinon pour ta methode, au premier abord j'aime bien sa "facilité de mise en oeuvre" (je dis pas que ca a ete facile de la trouver), et puis c'est clairement pour les triangles ! pas pour les polygones. de toute facon, pour un polygone convexe (edit : concave), je place la reponse la plus elegante juste apres le pb des trucs NP complets (trouver une solution a un probleme non polynomial dans un temps polynomial c'est bien ca ?) en terme de difficulte. Maintenant, je peux me tromper et c'est surement le cas, chacun son graal.
Cependant... en relisant la mienne que j'ai sué a ecrire ca donne:
dans un for
- je calcule un des 3 segments
- je calcule la distance entre le point cherche et une des extremites du segment selon le segment (2 dot en soustraction)
- la c'est un peu lourd parce que je decoupe le segment d'apres cette longueur (donc je fais une racine pour normaliser et multiplier par cette longueur, y a des fastinvsqrt, mais le pb c'est que je n'ai jamais su la reelle complexite de ce truc... bref)
- j'ajoute le troncon de segment au point duquel la distance est calculee.
les 3 dernieres operations se resument a "projeter le point sur le segment"
ensuite j'enleve le point a cette projection et j'obtient le nouveau segment perpendiculaire au segment.
je calcule la distance entre le point (celui qu'on cherche depuis le debut, qui n'a rien fait) et le point auquel on l'avait deja compare tout a l'heure, et je le multiplie par la distance entre le troisieme sommet qui n'est pas dans le segment et toujours le meme point du triangle avec qui on travaille depuis le debut.
edit : distance selon la hauteur calcule : 2 x 2 dots.
C'est galere un entretenir un gros post ! desol'...
donc en fait, je regarde si le sommet qui n'est pas dans le segment est du meme cote du segment que le point : si c'est le cas, le resultat est positif, sinon il est negatif.
edit : encore ! je viens d'avoir un coup de sang, j'ai eu peur d'avoir voulu m'epargner une normalisation necessaire mais pour la hauteur, pas besoin de normaliser puisque c'est le signe qui m'interesse et qu'il y a le meme segment en jeu des 2 cotés... ouf... enfin c'est clair que je te remercie, et j'insiste, continue, parce qu'a ce train la je vais trouver la faille de ma gestion de collision : j'ai quelques poly qui rentrent dans mes spheres...
je fais donc ca 3 fois, et et des que c'est negatif, clairement, le point est en dehors du triangle, sinon je dois encore tester les segments restants.
je poste un peu pour faire mon cinema parce que je prefere ma methode (question de plaisir de la decouverte) et surtout parce que celle que tu as trouvee quelque part (pas celle que tu as inventé, celle que tu as "trouve") est effectivement imprecise (a cause des angles).
Et aussi parce que la tienne et la mienne ont a peut pres la meme complexite : 3 sqrt et (ta derniere norme tu as du voir qu'il n'y a pas besoin de sqrt-iser pour la comparer a 1).
La tienne se base sur des segments qui s'inscrivent dans les angles, la mienne sur les hauteurs.
La tienne est plus elegante, la mienne est plus facile a comprendre (me trompe je ? sondage ?).
je conclurais donc:
Felicitations ! tu es le plus fin algoritmiste de nous deux :] (cqfd)
je rend la thread, a bientot j'espére !
edit : je me suis fait grilled, tt encore la :)
continue surtout, nous en faut plein des bonne astuces !
TheTiger
05/11/2005, 22h26
"cqfd" ça me rappel quand j'ai taté la prépa mais ça doit pas être qu'en prépa ça bon bref !!!
wé j'ai pensé à qqchose dans le style de t'a démarche mais chez moi y a pas de produit scalaire ;) enfin je tient à préciser que je l'ai découverte tout seul mais aprés si elle existe déjà ce qui n'est pas impossible ben je n'en savais rien...
je précise bien que celle que j'ai trouvé comme un grand :p c'est celle sans les angles là ^^ la plus simple l'autre c'est pas de moi mais je ne tient pas à imposer mon copy right bien au contraire je souhaite aider un max de personnes :)
Et je propose à chacun de poser sont idée même si c'est plus ou moin éfficasse.
En fin je suis pas sur de bien bien comprendre vraiment t'a démarche mais ça me rappel une de mes idées que je n'ai pas développé car je pensais que ça serait trop lourd mais vu comme ça peut-être pas il faut voir en détaille
alors si tu pourais être plus claire sans vouloir te contrarier et je vais quand même me forcer à comprendre car c'est probablement la fatigue ^^.
Merci pour ton idée car personnelement je suis trés ouvert à ce genre de suggestions et trés souvent on apprend des choses.
youpi y a du repondant :)
alors ma methode c'est : si le point est DANS le triangle;
c'est qu'il n'est pas (par elimination) derriere UN des segment.
il est face (face, dans le sens, vers le sens logique de la hauteur)
a chaque segment.
C'est pour ca que ca ne marche QUE sur les poly convexes, meme si je ne compte faire ca que pour les triangles.
Oula sinon j'avais bien compris que t'avais trouve tout seul !
on a tous besoin d'un algo de depart pour trouver la voie a suivre, donc tu as cherche, ce que tu as trouve ne t'as pas contente et tu as persevere : excellent.
Par ailleurs je precise que je n'ai pas trouve la mienne dans la minute : je l'avais au chaud dans mon visual et elle attendait son heure.
apres pour des methodes "unitaires" comme ca, c'est vrai que je pense qu'y a pas de mal au contraire a communiquer, ce genre de defi ca developpe l'esprit de groupe en plus !
Pour finir j'ai fait la fac, et qu'y a t'il de mal dans les dot ? c'est juste des gentilles petites multiplications ! (enfin, les gouts et les produits hein ;)
je ne sais pas si "nos" tienne et mienne existaient, mais probablement des mathematiciens plus talentueux l'ont tate avant l'age du bib... nous ne sommes que des informaticiens...
Et je veux bien mettre le code de la mienne mais peut etre dans le post suivant, ca merite de separer (pour pas que j'edite 30 fois)
je prefere juste expliquer au lieu de paster, ce n'est pas pour obfuscater ce que je dis.
for (i = 0; i < 3; i++)
{
line = tri[i] - tri[(i+1)%3]
mu = dot(pt, line) - dot(tri[i], line)
InvSqrt(ilen, dot(line, line))
proj = line * mu * ilen
proj = proj + tri[i]
h = proj - pt
signe = (dot(pt, h) - dot(tri[i], h)) *
(dot(tri[(i+2)%3], h) - dot(tri[i], h))
if (signe < 0)
{
return false;
}
}
TheTiger
05/11/2005, 23h25
C'est bien la méthode qui me trotait dans la tête, pour te dire que elle est bien :p mais que j'ai pas vaiment pensée à ça en fait...comment dire...j'ai entre vu une possibilité du genre sans y porter attention et là ben t'a bien eu raison car ça marche nikel ton afaire :D
Vala.
Si t'est intéréssé par une petite doc sur les collisions avec des ellipsoïdes et des triangles voir même la réaction du support... Elle est bien faite et je voudrais pas la garder pour ma pome et d'ailleur je la met en pièce jointe :)
Cette doc n'est pas de moi !!!
La miène sera à venir si j'ai le temps !!!
D'ailleur je pense en faire un début ce soir :)
PS : j'ai abandonné la prépa je suis en 1er anné d'IUT info car cté pas mon truque la prépa ^^
ok je choppe, en esperant la tienne, avec des vrais morceaux de code du gcn dedans.
c'etait toi le gars qui avait des pbs de prepa avec la thread longue comme le bras ? j'ai pas ete sympa en voyant ca ! bon... maintenant j'espere que tout va mieux pour toi, le temps de coder et tout ...
(je suis hors sujet, je sais, mea maxima culpa, mais bon... je le ferais pu msieur le juge)
soir :)
edit: ah ben oui, le telemachos, ben je trouve que c'est bien de le trouver ici, il a encore beaucoup a m'apprendre perso, j'espére avoir le temps.
deathangel
06/11/2005, 00h32
elle fait quoi la fonction dot ?? j'ai pas compris :(
TheTiger
06/11/2005, 00h41
dot c'est le produit scalaire
t'a 2 vecteurs de coordonnés (x,y,z) et (x',y',z')
dot((x,y,z),(x',y',z'))=x*x'+y*y'+z*z'
:)
C'est assez difficile à comprendre le produit scalaire moi même j'ai encore un peut de mal aprés une Terminal S :D
Lightness1024!
06/11/2005, 01h13
taratata, pense que c'est une projection et hop tout est clair :)
et aussi pense a la formule ||a||.||b||.cos(a,b) ca aide.
toutes ces histoires de points dans un triangle on en avait déja parlé sur le v3:
http://forumv3.games-creators.org/viewtopic_5825.htm
deathangel
06/11/2005, 01h17
le produit scalaire y a pas de problème, mais c'était la dénomination dot qui m'était inconnue...merci du renseignement
oui et la petite astuce qui fait le gout de la sauce c'est que
dot(pt, AB) - dot(A, AB)
donne "indirectement" la distance la plus courte du pt a AB, (si au dessus on utilise AB normalisée)
http://img467.imageshack.us/img467/9067/dotdot7vs.png
elle est positive si on est devant, negative si on est derriere (enfin a droite ou a gauche en fonction du sens de AB)
bref, avec ce point on a la projection sur la droite, la perpendiculaire, a vous de trouver d'autres joyeusetes.
notement, si je deplace la droite perpendiculaire obtenue jusqu'a ce qu'elle passe par A, je peux rejouer a projeter pt dessus, et avant d'exploser dans mes calculs, j'arreterais la.
je n'ai pas invente cette petite astuce particuliere,
je l'ai lue et assimilée
elle est tres utile et apparement classique.
en y reflechissant ensemble, dot et prod vectoriel sont plus faciles a assimiler. C'est une relation angulaire entre 2 pointeurs dans l'espace (ou le plan, selon la dimension)
mais c'est vrai que si je les separe, je n'ai plus l'impression de comprendre aussi bien.
l'astuce est donc tres liee aux produits vectoriels meme si elle n'en utilise pas, puisque elle permet de trouver une perpendiculaire particuliere. Apparement, dans le monde mathematique, tout se contredemontre et se recoupe... et ca c'etait le siecle dernier ! maintenant c'est l'ere des maths quantiques, et un jour les chercheurs... nous en mettrons peut etre plein la vue.
have a nice digression, soir.
TheTiger
06/11/2005, 01h35
Wé je ne doute pas de tes capacités en math deathangel c'est juste que moi perso le trouve pas ça super évident c'est tout :)
Oké je sait bien Lightness mais j'ai trouvé un bien meilleur moyen...mais merci quand même car ça viens compléter ce post pour éviter de radoter :p
ok ok tout le monde connaissait deja mon astuce :)
et ben tanpis, ca m'a fait plaisir !
Lightness1024!
06/11/2005, 02h08
lol :)
en tout cas le coup de la somme des directions normalisées > 1 je trouve ca pas con du tout !
c'est meme carrément amusant. mais j'ai une critique de sécurité, si le point est SUR une des arrêtes il y a risque de division par zero lors de la normalisation.
et la technique "Laeti²x/forumsV3" avec les produits scalaires est bien plus rapide parce qu'il n'y a pas de division floating ni de racine carrées (encore pire).
je fais un topic complet pour la detection ellipsoide parce que j'ai des problemes avec depuis plusieurs mois.
genial lightness !
j'ai mis mon code de cote edit:de detection ellipsoide, il est en "production" (lol) mais je sais qu'il n'est pas completement okay.
j'en causerais volontiers.
(sinon j'ai 3 invsqrt quand meme, meme en fast)
TheTiger
06/11/2005, 19h35
Ben je savais pas que les divisions flotante prenait autant de temps...
Et il n'y a pas de risque de vivision par 0 on teste simplement si la taille du vecteur n'est pas à 0...
Bon dans mon algo y a quoi ?
+3 soustractions vectoriel
+3 assignations.
il y a 3 normalisations qui font chacune
+6 multiplications
+3 additions
+1 racine carrée
+1 assignation
+1 teste de cette racine carré par rapport à un 0 ce qui est assez rapide
+1 division flotante
+1 assignation.
puis on a
+3 additions vectoriels
+1 assignations.
encore une normalisation
+1 test par rapport à 1.
en développé ça donne :
+3 soustractions vectoriel
+3 assignations.
//il y a 3 normalisations
+6 multiplications
+3 additions
+1 racine carrée
+1 assignation
+1 teste de cette racine carré par rapport à un 0 ce qui est assez rapide
+1 division flotante
+1 assignation.
+6 multiplications
+3 additions
+1 racine carrée
+1 assignation
+1 teste de cette racine carré par rapport à un 0 ce qui est assez rapide
+1 division flotante
+1 assignation.
+6 multiplications
+3 additions
+1 racine carrée
+1 assignation
+1 teste de cette racine carré par rapport à un 0 ce qui est assez rapide
+1 division flotante
+1 assignation.
//puis
+3 additions vectoriels
+1 assignations.
//il y a 1 normalisation
+6 multiplications
+3 additions
+1 racine carrée
+1 assignation
+1 teste de cette racine carré par rapport à un 0 ce qui est assez rapide
+1 division flotante
+1 assignation.
//et enfin
+1 test par rapport à 1.
tout ceci 1 et unique fois
Je compare avec l'autre algo :p
Alors on admetra que la boucle n'est pas indispensable et que l'on peut tout programmer en un coup
on a donc 3 fois :
+1 soustraction vectoriel
+1 assignation.
2 produits scalaires qui ont
+3 multiplication
+3 additions
+1 assignation.
puis on a
+1 soustration
+1 assignation
+1 produit scalaire
+1 racine carré
+1 assignation
+2 multiplications(flotante)
+1 assignation
+1 somme vectoriel
+1 assignation
+1 soustraction
+1 assignation
+2 produits scalaires
+1 soustraction
+1 multiplication
+2 produits scalaires
+1 soustraction
+1 une assignation
+1 test par rapport à 0
en développé ça donne :
+1 soustraction vectoriel
+1 assignation.
+3 multiplication
+3 additions
+1 assignation.
+3 multiplication
+3 additions
+1 assignation.
+1 soustration
+1 assignation
+3 multiplication
+3 additions
+1 assignation.
+1 racine carré
+1 assignation
+2 multiplications(flotante)
+1 assignation
+1 somme vectoriel
+1 assignation
+1 soustraction
+1 assignation
+3 multiplication
+3 additions
+1 assignation.
+3 multiplication
+3 additions
+1 assignation.
+1 soustraction
+1 multiplication
+3 multiplication
+3 additions
+1 assignation.
+3 multiplication
+3 additions
+1 assignation.
+1 soustraction
+1 une assignation
+1 test par rapport à 0
tout ceci 3 fois
Bon ben tout ça 3 fois je ne saurais pas vraiment comparrer car aprés si les divisions flotante sont si longue que ça...
Faut voir aprés moi je dirais que si les divisions flotante son vraiment longue alors autant dire que les 2 algo se valent probablement :p quoi que mon algo ai pas mal de racine carré c'est vrai !!!
Le plus simple serait de les programmer tout les 2 et de les éxécuter un nombre suffisant de fois en calculant le nombres de millisecondes que l'algo à mis à ce répéter x fois.
Je cherche simplement au plus rapide :)
Donc je propose que Laeti²x m'envoi sont code optimisé avec toute les fonctions histoire que ce soit pas moi qui le programmes car si j'optimise mal aprés...
Et je mettrait mon code on aura donc 2 bou de code qui effectu la même chose avec un point qui sera à l'intérieur du triangle car c'est le pire des cas aprés je testerais un point qui sera à l'extérieur de la 1er arrète et la sont code sera probablement plus rappide mais on doit se baser sur le pire des cas non ? Enfin on tiendras compte du fait que le code ne ce fait pas forcément 3 fois ^^
clap, clap, clap :)
tres belle action de thetiger, methodologie pour un benchmark.
je t'envoie le code, le temps de le passer en stand alone.
fodra prendre des cas de figures differents, mais identiques sur les 2,
et logguer les resultat pour faire un graphe avec des batons.
cela dit, j'ai l'impression de retourner a la fac, a jouer avec les autres a "c'est moi qui ai l'implementation la plus efficace", des bons souvenirs :)
a bientot
Lightness1024!
06/11/2005, 21h03
non il n'y a pas de racine dans l'autre algo, voici le code de la version sans structures précalculées:
//-------------------------------------------------------------------------------------------------------
// Fonction: vérifie si un point se situe dans le prisme infini dont la section droite est le triangle
// créé par les points tv1, tv2 et tv3.
//-------------------------------------------------------------------------------------------------------
bool IsInPrism(const SHORT3DVECTOR& point, const SHORT3DVECTOR& tv1, const SHORT3DVECTOR& tv2, const SHORT3DVECTOR& tv3)
{
// on vérifie que tous les points du triangle sont différents:
if (equiv(&tv1, &tv2) || equiv(&tv1, &tv3) || equiv(&tv2, &tv3))
return false;
DOUBLE3DVECTOR v1, v2, n, n2;
int vertx;
SHORT3DVECTOR arr[3];
memcpy(&arr[0], &tv1, sizeof(SHORT3DVECTOR));
memcpy(&arr[1], &tv2, sizeof(SHORT3DVECTOR));
memcpy(&arr[2], &tv3, sizeof(SHORT3DVECTOR));
// vecteurs directeurs:
v1.x = tv2.x - tv1.x;
v1.y = tv2.y - tv1.y;
v1.z = tv2.z - tv1.z;
v2.x = tv3.x - tv1.x;
v2.y = tv3.y - tv1.y;
v2.z = tv3.z - tv1.z;
CrossProduct (&n, &v1, &v2);
int vtx2;
double proj;
for (vertx = 0; vertx < 3; vertx++)
{
vtx2 = vertx + 1;
if (vtx2 >= 3)
vtx2 = 0;
// vecteur point-sommet:
v1.x = arr[vertx].x - point.x;
v1.y = arr[vertx].y - point.y;
v1.z = arr[vertx].z - point.z;
// vecteur arrête:
v2.x = arr[vtx2].x - arr[vertx].x;
v2.y = arr[vtx2].y - arr[vertx].y;
v2.z = arr[vtx2].z - arr[vertx].z;
// un vecteur normal à l'arrête (oui c con, mais disons que ya pas d'autre description):
CrossProduct (&n2, &v2, &n);
// projection du vecteur point-sommet sur la normale:
DotProduct (&proj, &v1, &n2);
if (proj < 0.0)
{ // le point est à l'exterieur du triangle
return false;
}
}
return true;
}
des assignations, des prod vectoriels et des prods scalaires.
mais pas de racine ni de normalisation ni de division donc quelque soit le nombre d'assignations en plus c'est plus rapide que ton algo qui nécessite obligatoirement 3 normalisations donc division + racine :D
mais par contre il est amusant :)
pour le fun, le code de la version avec "normales" précalculées est encore plus rapide:
///-------------------------------------------------------------------------------------------------------
// Fonction: vérifie si un point se situe dans un triangle de la structure POLY_N_PLANE
// note : encore la même que celle d'au dessus mais spéciale optimisée collisions
//-------------------------------------------------------------------------------------------------------
bool IsInPNPPrism(const D3DXVECTOR3& point, const POLY_N_PLANE* pnp)
{
int vertx;
D3DXVECTOR3 v;
for (vertx = 0; vertx < 3; ++vertx)
{
v = pnp->vertex[vertx] - point;
if (D3DXVec3Dot(&v, &pnp->EdgeNormal[vertx]) < 0.0f)
{ // point en dehors du triangle
return false;
}
}
return true;
}
dans la foulee
j'etais sur irc j'ai parle a un copain thesard : dans les labos il adooorent positivement les analyses de complexite :
prevoir comment ca se passera quand on change les donnees
(quand on passe a un poly par exemple au lieu d'un triangle)
connaitre le facteur multiplication du temps de calcul.
il me conseille de faire une analyse empirique.
diverses tailles de problemes
pour chaque taille un temps moyen
et enfin une courbe (et gaffe a l'interpretation si l'echelle est logarithmique)
100 exec pour chaque taille.
demarre avec des pb de taille 10, multiplie par 2 a chaque fois.
genre 10 fois,
ca te fait 1000 executions.
voila, perso je lui fait confiance, il fait vraiment ca souvent :)
apres c'est des idees pour le faire, et y a pas de regles etablies...
royal lightness.
vraiment, c'est la version optimal de mon truc, en plus ca vient de tes archives je vois.
J'auto proclame le test du point en dehors de normal, officiel pour les collisions.
en plus le coup avec les normales precalculees ca explique un peu pourquoi dans n'importe quel moteur on se fait chier a trimbaler normales et binormales !
ca vaut le coup !
TheTiger
06/11/2005, 21h37
Wé c'est bien optimisé en effet mais ce qui me gène c'est juste que il y aura toujours ce bon vieux problème entre optimisation est espace mémoire avec les précalculés :p alors ça dépand aprés faut voir entre les 2 algos que Ligtness propose suivant si on veut de la place mémoire ou de la puissance porcesseur :)
Et j'avous que mon algo est lourd de par les instructions qu'il utilise mais il est plus légé que la méthode des angles avec l'arc cos :p
Et en plus il est marrant héhé
bref je vais quand même méditer sur tout ça et je compte bien développer mon propre algo de racine carré ^^
c'est assez simple à faire en fait une racine carré ^^
On prend une variable R qui sera le résultat et on a X la valeur au carrée
Racine(X):
R=1
Do
{
R=(X+R)/2;
}while(abs(X-R*R)>Epsilone);
return R;
avec Epsilone qui est l'approximation que l'on veux avoir et moi je pense que ici on peut faire une faible approximation :p quoi que...enfin c'est à voir tout ça ^^ mais je vais y réfléchir de plus prés à votre algo les gars, il est vraiment intéréssant !!!
Lightness1024!
06/11/2005, 22h03
wow, ca à l'air interressant cette méthode pour la racine faudra que je regarde ca de plus pres.
ca va plus vite que le 1/sqrt du SSE ? :p :D
TheTiger
07/11/2005, 00h23
Il faudra que tu m'expliques cette histoire de 1/sqrt avec l'histoire du SSE ^^ :D
Lightness1024!
07/11/2005, 02h31
voila un truc que j'ai chopé sur un forum:
From superpig via private message
SSE has both SQRT and RSQRT instructions, but you don't really get much benefit unless you're doing four of them at once. Say you want to get the lengths of four vectors, stored as a structure of arrays:
__declspec(align(16)) struct blockOfFourVectors
{
float xValues[4];
float yValues[4];
float zValues[4];
float lengths[4];
}
blockOfFourVectors data;
__asm
{
movaps xmm0, [data + 0x00] ; load x components
movaps xmm1, [data + 0x10] ; load y components
movaps xmm2, [data + 0x20] ; load z components
; square each component
mulaps xmm0, xmm0
mulaps xmm1, xmm1
mulaps xmm2, xmm2
; sum them into xmm0
addps xmm0, xmm1
addps xmm0, xmm2
; sqrt to get length
sqrtps xmm0, xmm0
; save out
movaps [data + 0x30], xmm0
}
That would calc all four lengths into data.lengths. For just a single vector it's not really worthwhile (and unless you store that vector in a SoA, would require a load of shuffling).
ca dit que SSE c'est bien pour faire du SIMD mais pour une seule racine la FPU fera tres bien l'affaire.
TheTiger
07/11/2005, 19h50
Wé en tout cas pour ma racine carré ça marche pas je me suis planter dans l'algo au retapage ^^ donc en fait c'est :
Racine(X):
R=1
Do
{
R=(R+X/R)/2;
}while(abs(X-R*R)>Epsilone)
return R;
j'ai pas tout lu , mais le sujet m'intéresse , je lirai tout ça plus tard dans la semaine , à tête reposée.
j'ai trouvé cette fonction pour déterminer si un point se trouve dans un triangle. Je n'ai pas encore détaillé et comparé avec ce que vous proposez .
Below is a function that determines if a point is inside a triangle or not. This
is used in the collision detection step. Thanks to Keidy from Mr-Gamemaker
who posted this particular version of the function in a little competition we
held about who could post the fastest one.
typedef unsigned int uint32;
#define in(a) ((uint32&) a)
bool checkPointInTriangle(const VECTOR& point,
const VECTOR& pa,const VECTOR& pb, const VECTOR& pc)
{
VECTOR e10=pb-pa;
VECTOR e20=pc-pa;
float a = e10.dot(e10);
float b = e10.dot(e20);
float c = e20.dot(e20);
float ac_bb=(a*c)-(b*b);
VECTOR vp(point.x-pa.x, point.y-pa.y, point.z-pa.z);
float d = vp.dot(e10);
float e = vp.dot(e20);
float x = (d*c)-(e*b);
float y = (e*a)-(d*b);
float z = x+y-ac_bb;
return (( in(z)& ~(in(x)|in(y)) ) & 0x80000000);
}
j'avais aussi fait cette fonction pour un triangle en 2D, faudrait que je l'adapte à la 3D , mais je pense que la fonction en C++ ci dessus est nettement plus efficace.
Procedure CollisionTriangle(*T.Triangle,*P.point)
;Test la collision du point avec le triangle
;pour en savoir plus http://tanopah.jo.free.fr/seconde/region.html
;Plan 1
xu1=*T\X2-*T\X1:yu1=*T\Y2-*T\Y1
c1=*T\Y1*xu1-*T\X1*yu1
P1=*T\X3*yu1-*T\Y3*xu1+c1
ax1=*P\x*yu1-*P\y*xu1+c1
;Plan 2
xu2=*T\X3-*T\X2:yu2=*T\Y3-*T\Y2
c2=*T\Y2*xu2-*T\X2*yu2
P2=*T\X1*yu2-*T\Y1*xu2+c2
ax2=*P\x*yu2-*P\y*xu2+c2
;Plan 3
xu3=*T\X1-*T\X3:yu3=*T\Y1-*T\Y3
c3=*T\Y3*xu3-*T\X3*yu3
P3=*T\X2*yu3-*T\Y2*xu3+c3
AX3=*P\x*yu3-*P\y*xu3+c3
If Signe(ax1)=Signe(P1) And Signe(ax2)=Signe(P2) And Signe(AX3)=Signe(P3)
Resultat=#True
EndIf
ProcedureReturn Resultat
EndProcedure
salut comtois
alors je vois, que.... tu calcules le vecteur AB ok...
bref...
(je vous epargne mes deboires a comprendre ce language qui m'est inconnu, ni le basic de mon enfance, ni du pascal, ni du C/C++, c'est du darkbasic c'est ca ?)
ce qui revient a une facon tres astucieuse en termes de cycles CPU pour
comparer par exemple BC ^ CA et PC ^ CA
ou AB ^ BC et PB ^ BC
ou CA ^ AB et PA ^ AB
soit verifier que P est du meme cote que A de BC,
que P est du meme cote que B de AC
que P est du meme cote que C de AB
donc ca marche super bien, il a fallu que je deroule pour voir la meme demarche que la mienne ... c'est bien ca j'ai pas reve ?
la premiere me parait + marrante, allons y:
hum deja... pa pour le sommet c'est pas des plus cools comme notation ca evoque un segment (je sais tu l'as trouve c'est pas de ta faute)
a et c sont les tailles des segments au carre et b est le cosinus de l'angle AB AC * taille AB * taille AC.
donc float ac_bb est egal = cos AB AC
ohhhhh merci tout plein ! ca evite la normalisation !
je connaissais pas cette technique pour avoir l'angle sans normaliser prealablement les vecteurs... :)
bon apres j'aime pas trop la methode parce que c'est approximatif mais
(AP * AB * cos AP AB * AC * AC) - (AP * AC * cos AP AC * AB * AC * cos AB AC)
soit (cos AP AB) - (cos AP AC * cos AB AC)
puis
(AP * AC * cos AP AC * AB * AB) - (AP * AB * cos AP AB * AB * AC * cos AB AC)
soit (cos AP AC) - (cos AP AB * cos AB AC)
puis
(cos AP AB) - (cos AP AC * cos AB AC) + (cos AP AC) - (cos AP AB * cos AB AC) - (cos AB AC)
soit : (1 - cos AB AC) * (cos AP AB + cos AP AC) - cos AB AC
je ne connais pas assez ma trigo, mais ca doit vouloir dire
angle AP AC + angle AB AP = angle AB AC
mais c'est tres marrant.
je m'etais jamais pose la question de savoir pourquoi 2 vecteurs normalise en dot donnaient la valeur de l'angle entre eux et 2 vecteur identiques en dot la longueur de ce vecteur au carre...
La premiere methode que tu proposes est donc valide "et originale", et monte a 3 le nombre de methodes a tester, TheTiger, t'as du boulot la ;)
TheTiger
08/11/2005, 23h56
Nan j'ai plus de bouleau en fait :p
Je vais simplement tester la dernière méthode en tous cas je vais revoir celle avec : tester si le point P est du même coté que A par rapport à BC et faire de même avec les 3 coté, celle la est vraiment cool donc je vais la mettre à font et je pense que elle sera la plus rapide ^^ aller bonne nuit à tous
(je vous epargne mes deboires a comprendre ce language qui m'est inconnu, ni le basic de mon enfance, ni du pascal, ni du C/C++, c'est du darkbasic c'est ca ?)
Désolé pour les déboires, j'aurais peut-être dû développer un peu plus :)
Alors non c'est pas du darkbasic, c'est du purebasic.
La structure manquante
Structure Triangle
X1.l
Y1.l
X2.l
Y2.l
X3.l
Y3.l
EndStructure
Bon je ne détaille pas plus , tu as déjà démêlé la ficelle :)
Sinon , effectivement , j'utilise la régionalisation , et j'ai mis l'adresse pour les infos complémentaires .
moi j'ai lu un articles dans livres traitant ce genre de prbmle et il ont pyeroposée une methode assez simple a mettre en oeuvre la methode la voila :
si on veut savoir si un point p est inclu dans un polygone forme un ensemble de points il suffit de tester les colision des arretes du polygone avec un demi droite infini dont l'origine est le point p. si le nombre d'intersection est paire alors le point p est en dehors du polygone sino bingo il est inclue.
bien sure y a quelques cas particuliers qu'il faut traiter separemment comme exemple lorsque la demi droite passe exactement sur une arete du polygone
mais je pense que c la methode la plus simple que j'ai pu trouvé
et moi je dis que ca ne marche pas parce que :
http://img506.imageshack.us/img506/692/tag8mk.png (http://imageshack.us)
dans cette figure le point rouge est en dehors du polygone, il est derriere les hypers plans en angle aigu, et devant les 3 autres.
"tester les colision des arretes du polygone avec un demi droite infini dont l'origine est le point p" donne 3 collisions, un nombre impair.
A vue de nez ca ne marche qu'avec les polygones convexes.
si si , elle fonctionne cette méthode,j'ai même lu un article à ce sujet rédigé par un agrégé de mathématiques et docteur en informatique et professeur à l'université et qui l'enseigne à ses étudiants, on peut quand même le croire non ? :)
le site du monsieur en question (http://llaic3.u-clermont1.fr/~mr/)
Et dans ton schéma , il y a 2 collisions , pas 3 (si la demi doite est dirigée vers la droite) .
Je vais aussi tester avec les API window , Dri sur un autre forum m'a donné l'idée , je vais faire des tests de vitesse.
CreatePolygonRgn()
PtInRegion()
il faut d'abord fait un projection pour ramener le triangle dans un repère 2D
ensuite CreatePolygonRgn() avec les points du triangle
et PtInRegion() pour tester si le point est dans le triangle .
ok ça fait un code qui n'est pas portable , mais je m'en fous , si c'est rapide et que ça me simplifie la vie :)
http://img508.imageshack.us/img508/1083/tag8mk0gx.png (http://imageshack.us)
anaaay comtois !
je vois que tu veux dire.
Ci dessus, ce que moi, je voulais dire : les hypers plans des aretes sont orientes sur mon dessin. J'ai considere le positionnement relatif du point avec eux.
Fin surtout, j'ai rien compris a l'enonce. Merci pour le lien.
L'autre méthode, pour les polygones convexes, c'est de sommer les angles consecutifs entre le point et les sommets du polygone. Si la somme vaut 360° le point est dedans, si elle vaut 0° il est dehors.
une autre méthode pour le calcul d'un point dans un triangle ?
#define POINT_IN_TRI(V0,U0,U1,U2) \
{ \
float a,b,c,d0,d1,d2; \
/* is T1 completly inside T2? */ \
/* check if V0 is inside tri(U0,U1,U2) */ \
a=U1[i1]-U0[i1]; \
b=-(U1[i0]-U0[i0]); \
c=-a*U0[i0]-b*U0[i1]; \
d0=a*V0[i0]+b*V0[i1]+c; \
\
a=U2[i1]-U1[i1]; \
b=-(U2[i0]-U1[i0]); \
c=-a*U1[i0]-b*U1[i1]; \
d1=a*V0[i0]+b*V0[i1]+c; \
\
a=U0[i1]-U2[i1]; \
b=-(U0[i0]-U2[i0]); \
c=-a*U2[i0]-b*U2[i1]; \
d2=a*V0[i0]+b*V0[i1]+c; \
if(d0*d1>0.0) \
{ \
if(d0*d2>0.0) return 1; \
} \
}
Source de l'info (http://www.cs.lth.se/home/Tomas_Akenine_Moller/code/opttritri.txt)
Faut que je regarde celui là aussi (http://www.cs.lth.se/home/Tomas_Akenine_Moller/raytri/)
Salut,
Désolé de remonter ce sujet.
Je me demande quel est l’algorithme le plus optimisé pour traiter les collisions sur mon objet qui a des propriétés assez particulières.
Il s’agit d’un objet 3D construit par l’extrusion d’un polygone quelconque. L’objet ressemble à celui-ci http://arpam.free.fr/denner_fichiers/prisme.gif mais contrairement à lui mon volume n’a pas une base convexe.
Je ne sais pas si tous vos algorithmes sont adaptables en 3D ? En tous cas la plupart sont réservés aux polygones convexes. Je suis néanmoins tenté d’adapter l’algo de Lightness1024! (page 2) de la façon suivante :
- Je divise mon objet en volume de base convexe
- Plutôt que de parcourir chaque vertex, je parcours chaque face dont je calcule le vecteur normal, puis j’utilise le produit scalaire de la même manière.
Je ne sais pas si tous vos algorithmes sont adaptables en 3D ? En tous cas la plupart sont réservés aux polygones convexes.
ou tu peux tout convertir en triangles. et tu n'as plus qu'à gérer les collisions avec des triangles.
Ensuite l'algo à mettre en oeuvre va dépendre de ton application , si c'est pour gérer l'intersection d'un rayon avec ton objet , ou une sphère avec ton objet les méthodes seront différentes.
vBulletin® v.3.6.5, Copyright ©2000-2009, Jelsoft Enterprises Ltd. Tous droits réservés - Version française vbulletin-fr.org