Parcourt de faces et intérieur d'un polyèdre.

**méphistopheles** · 15/05/2007, 11h00

Bonjour.

Je rencontre le problème suivant en essayant de déterminer l'intérieur d'un polyèdre comme évoqué sur ce sujet.

J'ai pensé à trouver les faces et à chercher quand est-ce que je les traversait en partant du centre, mais je n'arrive pas à déterminer ces dernières.

En effet, en faisant un parcours sur les arêtes, on peut soit tomber sur une face, soit sur un parcourt qui couperais le polyèdres:

Par exemple, sur une bipyramide, en parcourant les points du plan de symétrie qui passe par la base commune aux deux pyramides, on n'a pas de faces, mais juste un parcourt qui n'indique qu'un changement d'angle...

Si vous pouviez m'aider à trouver les faces, ou mieux, à déterminer l'interieur du polyèdre par un autre moyen...

merci

**SpaceFrog** · 15/05/2007, 11h06

sur le même principe tu dois pouvoir le faire pour un polyèdre non ?
http://www.developpez.net/forums/sho...light=polygone

une droite et l'étude des intersections ...

tout dépend de si ton polyèdre possède des faces concaves et convexes ???

**ToTo13** · 15/05/2007, 11h44

Bonjour,

pour savoir si un point est à l'intérieur du polyèdre, il y a une méthode simple mais pas rapide :
- tester pour toutes les faces si le point est du même coté de cette face que barycentre du polyèdre.

**méphistopheles** · 15/05/2007, 12h23

Malheureusement, mon polyèdre est quelquonque (enfin pas tout à fait, mais il paut être concave, convexe ou aucuns des deux).

la methode de toto marcherais si le polyèdre étais convexe et si je conaissait l'équation de ces faces, mais comme je l'ai précisé avec l'exemple de la bipyramide, je n'arrive pas à déterminer si un parcours coplanaire représente une face... sachant que je n'as que les segments reliant les points entre eux...

merci

**ToTo13** · 16/05/2007, 13h41

Bonjour,

si ton polyèdre est non convexe, le problème devient très difficile !!!

Est ce que tu travailles dans un espace discret ?
si oui, il te reste la solution du remplissage de polyèdre.

**méphistopheles** · 16/05/2007, 18h08

heu espace discret ?

sinon, je pourrais peut-être à la limite tricher et suprimmer des points pour obtenir un polyèdre convexe, mais je vois pas comment faire...

**pseudocode** · 20/05/2007, 17h04

Tu cherches toujours a calculer le volume d'un polyedre quelconque ?

Je reviens sur ce sujet car je me suis probablement mal exprimé sur le post precedent. Je vais essayer de faire plus simple...

Pour calculer le volume d'un polygone 2D, on peut additionner les aires algebriques (= signés) des trapezes droits formés par 2 points consecutifs du contour et l'axe X. C'est en gros le principe utilisé pour calculer l'integrale d'une fonction par la methode des trapezes.

On etend ensuite ce principe a la 3D:

Pour calculer le volume d'un polyedre 3D, on peut additionner les volumes algebriques (= signés) des prismes droits formés par une face et le plan Z.

Calculer le volume "non signé" d'un prisme droit est simple: V = surface au sol * hauteur moyenne.

Pour calculer le signe du volume, il faut regarder le signe de chacun des 2 termes "surface au sol" et "hauteur moyenne". Pour simplifier, on peut translater le polyedre vers le haut afin qu'il ne coupe pas le plan Z. Ansi toutes les "hauteurs moyennes" sont positives.

Il ne reste alors que le calcul du signe de la "surface au sol". On peut le calculer en regardant si la normale sur Z de la face et la normale de la "surface au sol" ont le meme sens.

voila, j'espere que c'est plus clair

**Nemerle** · 21/05/2007, 00h19

oui, c'est tout bien clair

**méphistopheles** · 21/05/2007, 00h21

heu... je n'ai peut-être pas bien compris, mais n'est-ce pas un calcul de surface que tu propose ici ?

sinon, je suis toujours comfronté au problème de détermination des faces ...

en tout cas, merci beaucoup pour le temps que tu à pris pour moi, je m'excus de te prendre la tête comme ça.

**pseudocode** · 21/05/2007, 09h59

Envoyé par méphistopheles

heu... je n'ai peut-être pas bien compris, mais n'est-ce pas un calcul de surface que tu propose ici ?

En 2D c'est le calcul de la surface, et en 3D c'est le calcul du volume.

Si tu translates le polyedre vers le haut (Z+) pour qu'il ne coupe pas le plan Z, le calcul du volume peut s'ecrire comme suit:

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
 
Volume_Polyedre = Somme    [ Volume_Algebrique_Prisme(f) ]
                 (f:faces)
 
et
 
Volume_Algebrique_Prisme(f) = Signe(f) * Surface_au_sol(f) * Hauteur_moyenne(f)
 
 
avec:
 
Signe(f) = signe de la composante Z de la normale de la face 
 
Surface_au_sol(f) = aire du polygone formé par la projection des sommets sur le plan Z=0
 
Hauteur_moyenne(f) = moyenne des composantes Z des sommets

sinon, je suis toujours comfronté au problème de détermination des faces ...

?! heu... ben... c'est toi qui le construit le polyedre. Tu dois savoir ou sont les sommets, les arêtes et les faces, non ?

**méphistopheles** · 21/05/2007, 11h20

ha d'accord. je n'avais pas compris le coup de la hauteur moyenne.

en fait, pour je détermine mon polyèdre à partir d'un certains nombre de points... et je ne connait que les arretes et les points...

**pseudocode** · 21/05/2007, 12h18

Envoyé par méphistopheles

en fait, pour je détermine mon polyèdre à partir d'un certains nombre de points... et je ne connait que les arretes et les points...

Ok. Il faut d'abord construire le mesh. La hierarchie habituelles d'un mesh est:

1 Mesh = List< (Face,Normale) >
1 Face = List < Edge > (contenant 3 elements dans le cas des triangles)
1 Edge = List < Vertex > (contenant 2 elements car c'est un segment)

Tant que tu n'as pas contruit cette structure de données, tu ne pourra rien faire (calculs, affichage, ...).

Si ton polyedre est quelconque (non convexe), ca ne va pas etre simple de calculer les Faces et les Normales a partir des Edges, sans passer par une triangulation. Un moyen de savoir si le mesh a été construit correctement, c'est de verifier les propriétés suivantes:

Dans le cas des polyedres, on a toujours:

Chaque "Edge" est utilisé par 2 et seulement 2 "Face"
Chaque "Vertex" est utilisé par au moins 3 "Edge"
Les seules intersections entre les "Face" sont les "Edge"

**méphistopheles** · 21/05/2007, 14h14

donc les vertext sont les angles (ou les neuds) les Edges les arretes, mais ce qui est appelé faces, ce sont des faces réelles ou un ensemble de segment coplanaire ? (quand au mesh, j'ai pas compris

)

**pseudocode** · 21/05/2007, 14h25

Envoyé par méphistopheles

donc les vertext sont les angles (ou les neuds)

oui

les Edges les arretes

oui

Envoyé par méphistopheles

mais ce qui est appelé faces, ce sont des faces réelles ou un ensemble de segment coplanaire ?

Les faces, ce sont les facettes qui constituent le "maillage". Ces facettes sont planes, donc constituées de segments coplanaires.

(quand au mesh, j'ai pas compris

)

Le Mesh c'est l'objet 3D complet. Donc c'est un ensemble de faces (jointives dans le cas d'un polyedre).

(ici body=mesh)

**méphistopheles** · 21/05/2007, 15h33

dans ce cas, j'ai déjà mes "faces".

il me suffit donc d'apliquer ta technique à chacune ?

par-ce que j'ignore si cette methode s'applique pour une face qui ne comuniquerais pas avec l'exterieur...

**pseudocode** · 21/05/2007, 16h21

Envoyé par méphistopheles

par-ce que j'ignore si cette methode s'applique pour une face qui ne comuniquerais pas avec l'exterieur...

Non !!!! Les faces doivent "communiquer avec l'exterieur" comme tu dis.

Les "Face" sont composées a partir des "Edge". Et les "Edge" sont les segment qui rejoignent les sommets adjacents.

Le mot adjacent est important ! Cela empeche justement de creer des segments "interieurs" a la forme, et donc d'avoir des faces "non visibles de l'exterieur".

**méphistopheles** · 21/05/2007, 17h22

il me semble pourtant que non!

regarde sur ton polygone:
Nom : faceinterne.jpg
Affichages : 359
Taille : 10,8 Ko

le parcourt en rouge est bien fait de segments coplanaires et adjacents. pourtant, il ne forment qu'une face interne non ?

ou alors, il y as un truc que je n'ai pas compris...

**pseudocode** · 21/05/2007, 19h14

Envoyé par méphistopheles

le parcourt en rouge est bien fait de segments coplanaires et adjacents. pourtant, il ne forment qu'une face interne non ?

ou alors, il y as un truc que je n'ai pas compris...

Non, tu as bien compris. C'est juste que j'ai dit:

Le mot adjacent est important ! Cela empeche justement de creer des segments "interieurs" a la forme, et donc d'avoir des faces "non visibles de l'exterieur".

C'est une condition necessaire mais pas suffisante !

Necessaire: si tu as un "Edge" qui rejoint 2 sommets non adjacents, tu es sur que tu n'aura pas un polyedre valide.

Pas suffisante: ton exemple !

C'est bien pour ca qu'un polyedre est defini par l'ensemble face+edge+vertex. Parcequ'avec seulement les edge+vertex on ne peut pas en déduire facilement les faces.

**méphistopheles** · 22/05/2007, 07h35

je suis donc bien parti on dirait, par-ce que franchement, je vois pas comment faire la différence. il doit pourtant bien y avoir un critere... par exemple que la face soit commune à deux "polygones fermés" (deux pyramides) dans l'exemple... sauf que je ne vois pas comment déterminer ce qu'est un "polygone fermé"...

je détermine mes faces en faisant un parcourt coplanaire. Pour déterminer un polygone fermé il faudrais déterminer un parcourt dont la dernière face ne passe que par des points appartenant déjà aux autres... sauf qu'on ne sait pas vraiment si c'est la dernière (et pas l'avant-dernière...)

merci

**pseudocode** · 22/05/2007, 09h45

Je crois me souvenir que c'est un probleme NP complet. Donc il n'y a pas d'autre solution que de tester toutes les configurations possibles. Une configuration est valide si:

Dans le cas des polyedres, on a toujours: