J'ai un volume (qui n'est rien d'autre qu'un cube deforme) defini par ses 8 sommets. J'ai un point M.
 
Comment savoir si M est a l'interieur du volume, sachant que je n'ai aucune idee de la maniere dont les 8 sommets sont organises (en particulier je ne peux pas a priori reconstituer les 6 faces et faire des tests d'appartenance a des demi-espaces).
 
Merci

Quand tu dis : "je n'ai aucune idee de la maniere dont les 8 sommets sont organises " cela veut-il dire que tu ne connais pas leurs coordonées ? ? ?

Si je connais les coordonnees bien entendu, mais par exemple je ne connais pas a priori les points qu'il faut prendre 4 par 4 pour reconstituer les 6 faces...

Si tu est certain qu'il n'y a que 6 faces planes, il suffit de touver 4 points dans le même plan et ensuite de vérifier que les autres points sont tous dans le même demi-espace.
C'est peut-être pas la méthode la plus rapide, mais çà doit marcher non ?

Oui ca a l'air de marcher... mais il faut faire le boulot avec les 6 faces...  
Merci pour ta reponse

Oui, mais il faut voir aussi que chaque point fait partie de 3 faces, donc au fur et a mesure, le nombre de tests diminue.
 
Il y a d'autres propriétés, mais faut voir si elles peuvent servir.
 
Prendre 3 points, et chercher un 4eme qui colle (si possible, sinon changer de 3eme point et enfin de 2eme, mais là c'est pas de bol car y'a qu'une posibilité que 2 point n'ai pas de face en commun!). 4eme : Même plan et autres points dans le même demi-espace.
 
Ensuite, prendre 2 des points de la première face plus un troisième ( 2 chances sur 4 d'avoir bon !) et chercher le 4eme.
 
Ensuite, prendre 1 des deux point de la première face utilisé pour la 2eme, plus 1 des 2 autres de la 1ere ( 1 chance sur 2 !) et 1 des 2 autres de la 2eme ( 1 chance sur 2 !) et chercher le 4eme.
 
Là t'as 3 face, et il te reste 1 point qui te permet de construire 3 autres faces.
Parmis les 7 autres points :
1 est lié à 3 faces.
3 sont liés à 1 seule face.
3 sont liés à 2 faces.
 
Donc prendre le point tout seul, plus 2 points liés à une seule face et le point lié au 2 faces des deux autres points.
Faire l'opération 3 fois ! Bon là c'est un problème de programation car une fois la 4eme face définie, les conditions changent. Tout dépend de la façon d'organiser l'information...
 
Salut, c'était un plaisir !

Ton volume peut-il etre concave ?
Si non, calcule un jeu coefficients barycentriques, et s'il sont tous du meme signe, ton point est a l'interieur.

 
Le retour de la vengeance du produit mixte
 
Quand tu sauras comment est fait ton cube :
 
En gros le principe c'est que tu prends les coordonnes de trois points d'une face et aussi les coordonnées de ton point M et tu mets tout ca dans une matrice et tu fais un produits mixte magique qui te donne un resultat positif ou negatif suivant l'endroit ou se trouve ton point M.  
 
  pour savoir a quoi correspond le resultat (positif ou negatif) il faut aussi faire le produit mixte avec un point du cube ne faisant pas partis de la face pour savoir de quel cote se trouve l'interieur du cube.
 
  par exemple si l'interieur du cube donne un produit mixte negatif et que le produit mixte avec le point M, est aussi negatif, ca va dire que le point M et peut etre a l'interieur du cube, sinon si les signes sont different, tu es sur que le point M n'est pas a l'interieur du cube.
 
  Desole mais je crois que ce n'est pas tres clair, des que je rentre chez moi ce soir je vais faire un beau dessin et te donner la formule precise du produit mixte. J'ai deja utiliser cette methode en projet avec une pyramide (a 3 cotes, je ne connais plus le nom : terta... machin je crois), et ca marchait bien.

Mara's dad> Merci une nouvelle fois
 
BENB> non le volume est convexe. Je suis d'accord avec toi sur les coordonnees barycentriques, mais la question c'est : comment je les trouve ?
 
darkoli> Le produit mixte c'est pas tout simplement (a^b).c ? Avec a et b vecteurs d'une face, donc a^b donne la normale, et (a^b).c dit simplement de quel cote du demi-espace se trouve le point ??
Et effectivement si tu refais le test avec un point de l'interieur du cube, ca permet d'etre categorique

darkoli :  
La pyramide à 3 cotés (4 faces en fait !) est un tétraèdre !
 
Si je comprends bien la méthode, il faut faire 6 fois le test du produit mixte, non ?
 
Mais il me semble que TGRX est déjà capable de déterminer de quel coté d'un plan se trouve un point non ?

 
Ben c'est typiquement le cadre d'application du produit mixte

Pour trouver un jeu de coordonnee, tu a trois equations et huits inconnues, soit tu en fixes 5 et tu cherches les trois autres...
soit tu fais une minimistation, E = E1*E1 + E2*E2 + E3*E3
ensuite tu derive E par rapport a chacune des coordonnees et ca te donne 8 equations...
 
La meilleur solution est de resoudre a la main et d'exprimer 3 des coordonnees en fct des 5 autres puis de fixer les autres a 1 par exemple et de voir ce que ca de donne pour les 3 premieres, l'avantage par rapport a la premiere solution c'est que tu peux voir les solutions singulieres avant de resoudre (il n'est pas sur que tu puisse trouver une solution pour n'importe quel jeu de 5 valeurs, la derniere solution te permet de connaitre a l'avance les jeux qui ne sont pas solutions...)

Le pb est que dans son cas ces coeff ne sont pas uniques.
Tout comme en 2D, dans un carré ABCD, le centre du carré est l'isobarycentre mais aussi le barycentre de A(0.6), B(-0.1), C(0.6), D(-0.1).

 
ahhh.
 
plus d'infos sur le produit mixte :
 
  a.(b^c) ou a,b et c sont des vecteurs. ce qui donne aussi sous forme de matrice :

 
en fait en considerant le pallélépipède construit sur les trois vecteurs a,b,c le produit mixte donne en valeur absolue le volume du pallélépipède. En réalité, il est soit positif ou negatif suivant le sens dans lequel sont données les vecteurs.

bien sur ces coefs ne sont pas uniques, comme je le dit il faut poser 5 valeurs et calculer les 3 autres, en prenant les 5 premieres de meme signe, il est facile de voir le signe des trois valeurs calcules, en prenant les trois valeurs pour des point voisins les uns des autres, les risques de Pb sont limites.
En effet il possible d'avoir le point dans le volume et des coeffs negatifs mais il faut qu'il y en ait plusieurs et que les points associes soit de part et d'autre du barycentre...  
 
La methode que je preconise est a l'abri de ce genre de Pb... Et il faut chercher a avoir tous les signes positifs (par ex) ou tous sauf 1.

IL y a tout de meme un bug dans ton histoire
c'est de savoir comment est defini ton volume?
4 points quelconques n'ayant pas l'heur d'etre coplanaires, il te faut une info complementaire pour definir ton volume.
Par exemple, ta surface limite peut etre parametree selon deux scalaires, telle qu'a parametre fixe, cela definisse un segment de droite qui passe par deux aretes.
Tu peux definir ta surface comme l'union de deux triangles (plans) a partir de trois points choisis arbitrairement parmi les 4.
Tu peux definir ton volume comme l'enveloppe convexe de ton nuage de 8 points (une fois que tu as calculee ton enveloppe convexe, le probleme de l'appartenance devient trivial).
Tu peux dire que ta grille de points correspond a la matrice de points de controle d'une surface de subdivision.
Etc.. etc..
 
A+
LEGREG

[edit]--Message édité par legreg--[/edit]