Discussion :

[tarekphp]

Bonjour
voila j'ai une application que je fait avec c++; opengl et j'affiche un maillage
maintenant j'ai besoin de remplir une matrice pour dire avec des valeurs 0 si le point est en dehors du maillage et autres si il est dedans

j'ai trouvé dans un site Geomtric tool une façon de calculer la distance entre un point et un triangle (face) mais ca j'ai lu le code et ya toujours une valeur positive pour exprimer la distance et donc je ne saurait pas si le point est dans l'objet ou a l'exterieur

voila j'espere avoir eté clair

merci

[Emmanuel Deloget]

Bonjour
voila j'ai une application que je fait avec c++; opengl et j'affiche un maillage
maintenant j'ai besoin de remplir une matrice pour dire avec des valeurs 0 si le point est en dehors du maillage et autres si il est dedans

j'ai trouvé dans un site Geometric tool une façon de calculer la distance entre un point et un triangle (face) mais ca j'ai lu le code et ya toujours une valeur positive pour exprimer la distance et donc je ne saurait pas si le point est dans l'objet ou a l'exterieur

voila j'espere avoir eté clair

merci

Une distance est toujours positive, c'est sûr.

La technique que j'emploierais est un lancé de rayon qui passe par le point considéré et un des sommets du mesh - ce qui ne marche que si le mesh 3D est complètement fermé. Deux cas à considérer:

* soit le point considéré est l'un des sommets du modèle 3D. A toi de voir si tu considère ça comme étant à l'intérieur ou à l'extérieur.

* Si le point n'est pas un des sommets du modèle 3D, alors l'intersection entre le rayon et le modèle 3d est un ensemble de point de cardinalité paire. Il suffit alors de compter le nombre de points d'intersection d'un coté ou de l'autre du point considéré. Si il y un nombre d'intersection paire sur l'une des demi-droites, alors le point considéré est à l'extérieur du modèle 3D. Si le nombre de d'intersection est impair, alors le point est à l'intérieur du modèle 3D.

L'algorithme est relativement touffu, notamment si tu n'a prévu aucune structure d'accélération pour effectuer le lancer de rayon. Tu peux notamment accélérer le processus en calculant la bounding box de ton maillage, ce qui te permettra d'éliminer rapidement les points qui sont loin à l'extérieur. Une librairie qui te permet de calculer les intersection entre une droite et un ensemble de triangles serait de bon aloi (il en existe 3 tonnes; je crois même que geometric tools donne un peu de code qui va dans ce sens).

Ceci dit, c'est l'algorithme général. Dans certains cas particulier, d'autres algorithmes peuvent fonctionner très bien. Si le modèle 3D est convexe, il est possible de limiter les calculs en considérant que si un point est à l'intérieur alors il fait face à toutes les faces interne du modèle. Autrement dit,
* quelque soit un point P,
* pour tout les triangles T(i), soit C(i) le centre du triangle et N(i) la normale à ce triangle
* le produit scalaire de N(i) avec le vecteur partant de P pour aller à C(i) est positif.

Les calculs sont quand même relativement lourd, mais (à priori (1)) moins que dans le cas général (et surtout, l'algorithme est linéaire).

Si le mesh n'est pas convexe, il existe peut être une manière simple de le découper en autant d'ensemble convexe (en créant par exemple un BSP tree).


(1): pas testé, pas mesuré, donc moi pas savoir. Mais j'en ai l'intuition (qui peut être fausse).

[shenron666]

si ton maillage est complexe, je te conseille de commencer par simplement générer une AABB (Axis Aligned Bounding Box) qui englobe ton objet
c'est très facile de calculer si un point est dans une boite alignée sur les axes

ensuite, si tu cherches de la précision, il te faudra tester ce point avec tous les triangles de ton maillage

nb : si ton maillage est vraiment très complexe, tu peux aussi subdiviser la bounding box et effectuer des tests récursifs afin de gagner du temps

[tarekphp]

merci de vos reponses
mais ça parait un peu compliqué tout ça
si je doit faire une intersection ligne- riangle il y aura enormement de ligne a tester c'est a dire faire(parcourir) une sphere avec des ligne et doonc ça me fera 360*360 ligne pour chaque point sachant que ma matrice est de 128^3 (au cube).
je suppose que bounding box veut dire boite englobante que j'ai déja creer;
normalement mes objets sont tous convex
par contre j'ai pas bien compris le AAAB

merci

[shenron666]

si tu cherches sur le net tu trouveras des informations au sujet des bounding boxes, notamment le fait qu'il en existe 2 modèles fondamentaux :

AABB = Axis Aligned Bounding Box
c'est une boite englobante qui ne tourne pas avec l'objet
désavantage : elle doit être recalculée lorsque l'objet est tourné
avantage : les calculs de collision sont simples car elle est alignée sur les axes d'origine, ce sont juste des calculs de position

OBB = Oriented Bouding Box
celle ci est une boite englobante crée avec l'objet
lorsque l'ojet tourne, elle tourne avec lui
avantages : ses dimensions peuvent être optimisées avec la forme de l'objet et est donc plus précise pour les tests de collision et elle ne doit pas être recalculée à chaque fois
inconvénient : les calculs de collision sont plus complexes qu'avec une AABB, il faut faire des calculs d'intersection de plan

[tarekphp]

ok merci
j'utilise la deuxieme obb
comment je pourait calculer l'intersection avec les plans
merci

[Emmanuel Deloget]

ok merci
j'utilise la deuxieme obb
comment je pourait calculer l'intersection avec les plans
merci

google "separate axis theorem"

[tarekphp]

oh lala
c'est trop math et anglais ça

je réexplique mon probleme en detail peut etre que ya une solution plus simple
voila le sujet : http://www.irit.fr/~Mathias.Paulin/T...ObjetsVaporeux

je suis a la derniere etape ou il faut afficher la vache sous forme de nuage

il me faut tout d'abord recuperer une matrice 3d de l'objet afficher en premier; donc le prof nous a parler de calcul de distance j'ai vu sur le site: geometrictools.com et il y a un truc entre vertex et triangle (mais je pense que c'est des calculs en 2d meme si ils disent en 3d apres avoir lu le code)

donc voila si je fait comme eux j'aurais que des distance positive et moi j'ai besoin de faire une matrice ou tout ce qui est dehors de l'objet est un 0 et ce qui est a l'interieur je lui donne une certaine densité

mais voila ça fait plusieurs jours que j'essaye de réflechir dedans et je bloque ( j'avoue que l'univers 3d et bie et tres difficile et je suis nouveau dans le domaine)

donc pour le moment j'ai fait la matrice 3d OBB qui bouge avec l'objet et j'essaye de faire la fameuse matrice 3d en essayant de comprendre le code proposer par Geometrique tools car je ne peut pas l'appliquer directement puisque chaque classe appelle une autre


donc voila si quelqu'un a une solution simple a comprendre et a appliquer a me proposer

merci

[tarekphp]

j'ai une nouvelle idée que je pense est plus facile a programmé et dites moi si elle peut m'aider

je fait une detection d'intersection entre une ligne et une facette (c'est le meme principe dont ma parler Emmanuel Deloget)

c'est a dire je prends le point je crée une ligne dans laxe ax et je verifie si il ya au moins 1 point qui touche dans le cas contraire le point est en dehors de l'objet. donc si ya eu un point qui touche je verifie sur l'axe negatif -ax (si aucun point -> exterieur )

sinon donc jai un point a gauche et un autre a droite bein je refait le meme truc sur le l'axe aY et je pense que ça marchera pour tout objet convexe.

je fait le test sur ax et ay pour etre sur car par exemple si je test sur un animal a 4 pattes et je suis au mileu entre les deux pattes, sur laxe ax j'aurais 2 points mais pourtant le point est en dehors de l'animal don quand je fait sur l'axe ay je retrouve la verité (cest a dire que le point est en dehors)

voila si quelqu'un a une idée comment faire pour ce lancer de rayons merci

[TNT89]

Sans répondre à ta question (désolé désolé...)

Il suffit d'utiliser les équations cartésiennes des plans correctement orientés (normale orienté vers l'intérieur du volume considéré) ensuite tu passes les coordonnées du point en paramètres de ces équations. Si pour toutes ces équations les résultats sont positifs (du 'bon' côté de la face) ou nuls ('sur' la face) alors le point est à l'intérieur. Sinon il est à l'extérieur.

On obtient l'équation d'un plan grâce à sa normale et en connaissant au moins un point contenu dans ce même plan. Ainsi avec trois point il suffit d'utiliser deux vecteurs formés (par ces trois points) de calculer leur produit vectoriel qui donne la normale au plan formé (attention à l'orientation des vecteurs) et puis tu peux retrouver l'équation cartésienne facilement avec a = Normale.X, b = Normale.Y, c = Normale.Z d un paramètre à définir en connaissant un point de ce plan, l'équation caractéristique est alors :

f : (X, Y, Z) |-> a*X+b*Y+c*Z+d
f( X', Y', Z') = 0 si le point de coordonnées (X', Y', Z') appartient au plan
>0 s' il est situé dans le demi-espace 1
<0 s' il est situé dans le demi-espace 2

Voilà, bon courage

[tarekphp]

merci de ta reponse
mais si tu calcul un point par rapport au plan et tu trouve que c'est dans l'espace 2 par exemple rien ne te dit qu'il est a l'interieur de l'objet, pour le savoir il te faut recalculer l'autre extrémité mais que tu connais pas car j'utilise les faces et tu ne sais pas qui est parallele par rapportla nouvelle face.

merci

[TNT89]

Oui mais si tu appliques cet algorithme à chacune des faces tu sauras si ton point est bien à l'intérieur de l'objet (objet défini entièrement par les faces)

En gros :

Code :

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

1
2
3
4
5
6
7
res = vrai
  Pour chaque face et tant que res==vrai faire
         trouver l équation de la face courante
         si le signe de l équation avec en paramètre le point est négatif
               res = faux;
   FinPour/TantQue
   retourne res

[screetch]

pour les formes convexes :

pour chaque triangle ABC de l'objet, il doit etre orienté de la meme facon (clockwise ou counter-clockwise). dans ce cas, soit ABC le triangle (si c'est CCW alors dis ACB).

tu peux calculer le produit vectoriel de AB,AC, ce qui te donnera le vecteur orthogonal au triangle, orienté vers l'interieur de l'objet, AN
ensuite, il faut calculer le produit scalaire entre AM et AN. si il est >0 alors M et N sont du meme coté du triangle (donc vers l'interieur), sinon il est de l'autre coté.

note bien que ca ne marche qu'avec des convexes. si tu n'as pas des convexes, il faut decomposer la forme en convexes, ce qui est plus dur. c'est pas non plus une methode tres tres rapide.



Une methode qui ferait usage de la carte graphique, serait de rendre la scene en plusieurs passes.

target : depth buffer 1
passe 1: rendre la scene a l'endroit, update simplement de la profondeur
target : depth buffer 2
passe 2: rendre la scene a l'envers, update de la profondeur.
desormais, les points dont la profondeur est entre les deux est "a l'interieur" du volume.

refaire la meme operation n fois, en utilisant cette fois le depth buffer precedent pour ecarter les couches deja mises en places. cela permet de rendre une partie de la scene qui etait cachée par une autre partie.

utiliser ces n textures :
pour chaque point que tu veux tester, envoie le en rendu. si la profondeur de ce point est entre la profondeur 1 et 2, ou entre la 3 et 4, ou entre la 5 et 6, ou entre la 7 et 8... alors il est a l'interieur du volume. sinan, nan.

il faut prevoir assez de couches, c'est ca le probleme. ca depend de la difficulté de l'objet, mais c'est ce qu'il y a de plus rapide.

[screetch]

en fait je viens de voir que tu peux le faire en un nombre de passes qui depend juste de la complexité.

Code :

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

1
2
3
4
5
6
 
repeter
  rendre scene a l'endroit dans une texture, stocker le resultat (profondeur) dans texture 1, utiliser le "depth" de l'etape precedente (si il y en a une)
  rendre scene a l'envers dans une texture, stocker le resultat (profondeur) dans texture 2, mettre a jour le depth
  rendre tous les pixels, si la profondeur est entre profondeur1 et profondeur2 lors le pixel est a l'interieur
tant que des pixels ont ete rendus dans l'etape 1

il y a possibilité de realiser cela en opengl (tu peux demander le nombre de pixels qui ont effectivement ete rendus)

[shenron666]

je déconseille l'utilisation du gpu pour un simple test de collision
la nécessité de transférer les données du gpu vers le cpu fait perdre tout le gain que le gpu pourrait apporter étant donné que le cpu va devoir attendre que le gpu ait terminé son travail pour qu'ils se synchronisent et qu'ensuite le gpu transfère au cpu les données

la meilleure méthode bien plus simple également étant celle de TNT89

[screetch]

je ne vois pas ou est le probleme dans ce que j'ai dit etant donné qu'il ne s'agit pas de recuperer le resultat mais bel et bien de l'afficher en temps réel.

[screetch]

la meilleure méthode bien plus simple également étant celle de TNT89

celle avec les produits vectoriels ets plus simple, et les deux souffrent du probleme des formes non convexes.

[shenron666]

je ne vois pas ou est le probleme dans ce que j'ai dit etant donné qu'il ne s'agit pas de recuperer le resultat mais bel et bien de l'afficher en temps réel.

tu veux afficher une collision ?
je comprend pas ta pensée

[tarekphp]

la methode de TNT est bien mais la mienne avec les intersection marche sauf que maintenant j'ai un petit pb

si je fait un cube ça marche

mais quand j'essaye avec un elephant ya tt qui va apart les oreilles il me fait que le nbr d'intersection ==1 c'est normal puisque elles ne sont pas convex mais il me faut une methode pour gerer ces oreilles

merci

(pour les trucs complique j'y arriverai pas car je n'ai plus beaucoup de temps et que je ne suis pas tres fort en opengl ni en gpu ni en geometrie ) lol

[shenron666]

je ne connait pas d'autre solution à part décomposer ton mesh concave en autant de meshes convexes que nécessaires