Discussion :

[LittleWhite]

Bonjour à tous,

Moi aussi j'ai un problème de picking (cela doit au moins arriver une fois dans la vie d'un programmeur, non?).
En fait, dans mon cas, ce n'est pas vraiment la récupération du rayon à partir de la souris mon problème, mais de la détection d'intersection du rayon avec les triangles de ma scène.

Voici le code de la récupération du rayon:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
gluUnProject(point.x(),viewport[3]-point.y(),0,
            (worldMatrix * m_camera.viewMatrix()).constData(),m_projectionMatrix.constData(),viewport,
            &px0,&py0,&pz0);
 
gluUnProject(point.x(),viewport[3]-point.y(),1,
			 (worldMatrix * m_camera.viewMatrix()).constData(),m_projectionMatrix.constData(),viewport,
			 &px1,&py1,&pz1);

Donc, si je suis juste, je récupère le point en profondeur 0 dans mon view frustrum (soit le point le plus proche de la camera) et le point en profondeur 1 (soit le point le plus loin de ma caméra, mais toujours dans frustrum défini par ma perspective).

Pour information, la perspective est définie comme suit, à chaque redimenssionement de la fenêtre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

m_projectionMatrix.perspective(60.0, width/static_cast<qreal>(height), 0.1, 600.0);

Le viewport est simplement récupéré par un glGetIntegerv() approprié.

Maintenant, passons au coeur du problème.
D'après ce que j'ai pu trouvé sur internet, la methode de détection d'intersection d'un rayon avec un triangle est en deux étapes:
- Détection du point de collision du rayon sur le plan définit par le triangle
- Vérification si le point d'intersection est dans le triangle ou non

Pour la première partie, nous calculons l'angle entre la normale du plan (soit la normale du triangle) et le rayon. Grace à cette angle, nous savons sur quelle proportion du rayon, le plan se trouve. Donc, nous pouvons retrouver le point avec une interpolation linéaire (je simplifie peut être un peu de trop).
Le code que j'ai:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
QVector3D normal = (normals[indices[i]] + normals[indices[i+1]] + normals[indices[i+2]]) / 3;
 
float divFactor = QVector3D::dotProduct(ray,normal);
if ( divFactor == 0.f )
{
	qDebug() << "We are parallel";
	// The ray is // to the triangle ; Go next triangle
	continue;
}
 
float fract = (-1.f/divFactor) * ( rayStart.x() * normal.x() + rayStart.y() * normal.y() + rayStart.z() * normal.z() + rayStart.distanceToPlane(v1,normal));
 
QVector3D collisionPoint = rayStart + fract * ray;

(On notera que pour le calcul de la variable fract, je peux utiliser un dotProduct, mais j'ai actuellement cette ligne là, pour des raisons de tests.)
La ligne qui peut être fausse est le rayStart.distanceToPlane(v1,normal), car certes, il faut connaitre la distance, mais je ne suis pas sur que je calcul celle-ci correctement.

Pour la deuxième partie du processus, sachant que notre point est sur le plan du triangle, nous allons calculer les trois angles:
- AIB
- BIC
- CIA

A, B et C sont les points du triangle, I le point d'intersection.
Si la somme de ces trois angles est égale à 360, nous sommes dans le triangle, sinon, nous sommes en dehors.

Le code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
QVector3D pv1 = v1 - collisionPoint;
pv1.normalize();
QVector3D pv2 = v2 - collisionPoint;
pv2.normalize();
QVector3D pv3 = v3 - collisionPoint;
pv3.normalize();
 
float a1 = QVector3D::dotProduct(pv1,pv2);
float a2 = QVector3D::dotProduct(pv2,pv3);
float a3 = QVector3D::dotProduct(pv3,pv1);
 
qDebug() << "Angles (deg): " << MathUtils::ranToDeg(acosf(a1)) << ";" << MathUtils::ranToDeg(acosf(a2)) << ";" << MathUtils::ranToDeg(acosf(a3));
qDebug() << "Sum: " << acosf(a1) + acosf(a2) + acosf(a3);
 
if ( acosf(a1) + acosf(a2) + acosf(a3) >= 6.28f )
{
	qDebug() << "found";
	//listCollidingShaped.push_back(itShapeModel);
	break;
}

Voilà.

Pour tester tout ce code, j'ai un triangle définit comme suit:

1.0 -1.0 -1.9
0.0 1.0 -1.9
-1.0 -1.0 -1.9

Et mon problème est tel que même si je déplace le triangle en Z, l'algorithme ne me trouve pas la bonne position pour le point d'intersection. Le problème est certainement lié avec la distance entre le début du rayon et le plan du triangle, mais je après de multiple tentative, je n'ai pas trouvé l'erreur. C'est pourquoi je vous demande votre aide.

Merci d'avance

[stardeath]

bonsoir,

est ce que tu peux mettre où tu as trouvé ton algo pour l'intersection rayon/triangle, je le trouve assez exotique.

regarde si avec http://softsurfer.com/Archive/algori...rithm_0105.htm ou http://www.cs.virginia.edu/~gfx/Cour...tersection.pdf si ça ne passe pas mieux.

[LittleWhite]

Hum,

Ma source est une recherche sur google.
Pouvez vous m'expliquer pourquoi vous pensez que l'algorithme est exotique, il me semblait pourtant correct ...
Merci pour vos liens, je regarde prochainement

[pyros]

Salut,

Si je ne me trompe, le frustum est entre -1 et 1, donc le point le plus proche de la camera (sur le near clip) est en -1 et non 0. Ton problème vient peut être de là...

[stardeath]

par exotique, j'entends que je n'ai jamais vu le calcul de l'intersection fait comme ça.

[LittleWhite]

Salut,

Si je ne me trompe, le frustum est entre -1 et 1, donc le point le plus proche de la camera (sur le near clip) est en -1 et non 0. Ton problème vient peut être de là...

Le problème ne vient pas de là. Mais comme je ne suis pas encore certain de la bonne valeur à utiliser, j'essaie les deux (même si cela ne change pas vraiment grand chose. En fait, si on veut un rayon, les deux sont bons, je crois, car le rayon (la droite) reste la même, avec la même direction).

J'ai essayé cet algo -> http://softsurfer.com/Archive/algori...rithm_0105.htm
Il donne de meilleur résultat (bonne intersection qui varie selon la profondeur du triangle) par contre, si je tourne autour de mon triangle, ça marche plus
Donc je cherche

Merci pour l'aide

[stardeath]

si tu tournes le triangle (selon la méthode), il ne faut pas oublier de renseigner l'algo de picking de cette rotation.

[LittleWhite]

si tu tournes le triangle (selon la méthode), il ne faut pas oublier de renseigner l'algo de picking de cette rotation.

Euh ...
Je n'avais pas du tout compris cela ... car les gluUnProject se basent sur la matrice modelview et la matrice de project, donc pour moi, le rayon était déjà tourné dans la bonne rotation.
Ce qui fait, que l'algorithme de détection d'intersection, sera toujours juste, car lui, il se base sur ce rayon...

[stardeath]

c'est pour ça que je précise selon la méthode que tu utilises pour la rotation (comme je ne peux pas deviner comment tu gères tes rotations),
personnellement je n'utilise jamais le unproject, que je trouve foireux, j'utilise une solution maison avec une classe caméra qui va bien.

[Anthanoj]

J'avais déjà entendu cette methode de la somme des angles, si ça fait 360 c'est bon.
Par ailleurs je ne l'ai vu que sur internet et pas dans la littérature, on lui préfère la technique des coordonnées barycentrique, qui est beaucoup plus élégante et qui peut servir pour d'autre chose.


Je crois que j'avais lu la technique la dedans, excellent bouquin au passage
[ame="http://www.amazon.fr/Real-Time-Collision-Detection-Christer-Ericson/dp/1558607323/ref=sr_1_1?ie=UTF8&qid=1311668988&sr=8-1"]Real-Time Collision Detection: Amazon.fr: Christer Ericson: Livres anglais et ?trangers@@AMEPARAM@@http://ecx.images-amazon.com/images/I/41GwM8ClmaL.@@AMEPARAM@@41GwM8ClmaL[/ame]

et je te conseille vivement ce lien, et le bouquin associé si tu ne l'as pas déjà:
http://realtimerendering.com/intersections.html