polyèdre -> vecteurs normaux aux surfaces

Pause Café
#1

Plop all,

J’essaie, à partir d’un polyèdre, de trouver les vecteurs normaux à chaque surface, orientés vers l’extérieur. Mais j’ai quelques difficultés pour trouver un algorithme convenable.

Une méthode qui fonctionne pour les polyèdres convexes :

  1. Calculer le vecteur normal de la surface concernéee
  2. Faire le produit scalaire de ce vecteur, avec le vecteur partant de la moyenne des sommets du polyèdre (le centre, quoi :p), vers un des points de la surface.
  3. Si le produit scalaire est positif, le vecteur normal est dans le bon sens. S’il est négatif, on prend bien sûr l’opposé du vecteur calculé.

Et on réitère pour chaque surface.

Mais cette méthode ne fonctionne que pour les polyèdres convexes. Pour l’étendre aux polyèdres non convexes, j’ai pensé “découper” le polyèdre en polyèdre plus petits, et convexes. Mais le découpage doit être fait convenablement… Et c’est là que le bât blesse.

Je suis preneur de toute idée, quelle que soit son origine, quelle que soit sa teneur. Les pires conneries ont parfois engendré les plus grandes inventions. Vous pouvez me conseiller sur ce fameux découpage, sur la méthode pour trouver ces vecteurs normaux, dans le cadre d’un polyèdre non convexe. (Et même si cette méthode ne fonctionne que dans le cas convexe, proposez-là. Il y a peut-être moyen de l’adapter facilement.) Vous pouvez aussi proposer des propriétés sur les polyèdres convexes, ou tout autre chose qui puisse faire avancer la science. Si vous n’avez pas compris, demandez des éclaircissements sur les points obscurs. Bref, participez, c’est comme ça que la solution sera trouvée :wink:

Merci d’avance
Duna

EDIT :
Précision pour les curieux : je cherche à faire ceci dans le cadre d’une réécriture d’un algorithme des parties cachées, et plus généralement, d’un moteur 3D. Je sais, ça n’a aucun intérêt, mais c’est pour le fun, et pour apprendre.

#2

Ça n’est pas un problème local, donc il est impossible de définir l’extérieur de ta surface. (Tu aurais du mal avec la bouteille de Klein en plus).La meilleure façon est de procéder par continuité du vecteur normal: tu prends une triangle de ta surface comme référence, fixe arbitrairement ou choisis l’extérieur pour ce triangle et propage par continuité le vecteur normal aux facettes voisines jusqu’à avoir parcouru toute ta surface.

#3

Et, oui, pas facile d’orienter les surfaces fermées. Cela dit pour choisir l’intérieur de l’extérieur lorsque c’est possible il suffit de déterminer où est la composante connexe non bornée.

Une idée pour choisir entre l’extérieur et l’intérieur pas sur de mon coup mais bon, je propose et on discute avec des contres-exemples, comme dans Imre LAKATOS…

  1. Déterminer grossièrement l’enveloppe convexe de ton solide (histoire de borner la prolongation de la droite qui est présentée dans le point 2) et choisir un point A à l’intérieur d’une face, déterminer un vecteur normal.
  2. Prolonger la droite engendrée par ton vecteur normal, compter le nombre de fois que chacune des demis-droites rencontre le solide (danger, une rencontre avec le solide peut être le long d’une arête ou d’une face, dans ce cas, déplacer légèrement le point de départ A sur la surface jusqu’à ce que ce ne soit plus le cas.)
  3. raisonner sur ce nombre d’intersection. Par exemple:

Exple a
Demi-droite 1: 0 intersection --> elle va vers l’extérieur
Demi-droite 2: 1 intersection --> elle va vers l’intèrieur

Exple b
Demi-droite 1: 2 intersection --> elle va vers l’extérieur
Demi-droite 2: 1 intersection --> elle va vers l’intèrieur

à voir quoi… vous en pensez quoi? Il y a certainement plus simple?

#4

C’est bien parce-que le problème n’est pas local que je fais l’étude sur le polyèdre complet, et non sur une seule face. Pour ce qui est des polyèdres non orientables… Hum, je préfère ne pas envisager cette situation pour le moment :stuck_out_tongue:

Pas mal comme idée, à ceci près que mon polyèdre est un assemblage de faces, et je ne vois pas comment utiliser une continuité du vecteur normal sur les arrêtes, puisqu’il n’est justement pas continu. Ça pourrait fonctionner pour une ellipsoïde, ou autre surface paramétrée par une fonction C¹, mais pas sur un cube, par exemple. Je pense n’avoir pas compris la notion de conitnuité dans ce cas-là.

Ta méthode ziouplaboum, est difficile à mettre en place pour des polyèdres, car déterminer si un segment coupe une surface n’est pas une mince affaire. J’ai néanmoins utilisé ton idée pour savoir si un point appartient ou non à un polygone. C’est bien plus facile à faire en 2D.

#5

Grossièrement tu as un objet continu mais pas une variété différentielle C^1. Tu as des coins, des arêtes, ça te gêne. Pour savoir que faire de ton orientation lorsque tu passes sur une arête ou un sommet(mettons en un point A), tu n’as qu’à choisir une boule centrée en A de rayon suffisamment petit pour que la boule soit coupée en exactement deux morceaux par la surface, par continuité c’est toujours possible. Ensuite tu as un morceau de ta boule qui est à l’intérieur et l’autre qui est à l’extérieur, tu n’as plus qu’à voir comment ça se passe sur l’autre face, celle où tu n’as pas encore défini l’orientation. Par contre à implémenter alors là…???

[quote=“Dunatotatos”]
Ta méthode ziouplaboum, est difficile à mettre en place pour des polyèdres, car déterminer si un segment coupe une surface n’est pas une mince affaire.[/quote]
Quel est le problème en 3D? Il y a plus de variables? Déterminer si une droite coupe un plan, c’est trop dur? Déterminer où une droite coupe un plan, c’est pas bien dur non plus, déterminer si le point en question est sur une face de ton polyèdre ça se fait aussi non?

Sinon il y aurait une autre méthode plus facile à implémenter, qui se base sur l’idée que tu vas “remplir d’eau” les composantes connexes de IR^3 moins ta surface et voir laquelle à un volume non borné. Pour faire cela:

  1. Inclure la surface dans une boule (plutôt un grand cube) afin d’avoir un majorant du volume délimité à l’intérieur de la surface. (appelons ce nombre INFINI)
  2. Choisir une façon de paver l’espace, par exemple avec des petits cubes, changer la taille du maillage si celui-ci est trop grossier. Par exemple en subdivisant le grand cube de 1) avec des cubes de côtés (1/2^n)x(le côté du grand cube), n “assez grand”.
  3. Choisir un cube du maillage quelque part hors de la surface. Remplir l’espace de proche en proche, cube par cube (quand un cube est plein d’eau, on remplit parmi tous ces voisins ceux qui ne touchent pas le polyèdre), et ce jusqu’à ce que tout les cubes remplissables de proche en proche soient pleins ou jusqu’à ce que le volume total remplit dépasse INFINI.
  4. Quand c’est fini, de deux choses l’une si le volume remplit a dépassé INFINI, c’est que l’on a commencé dehors, si le volume remplit n’a pas dépassé INFINI, c’est que l’on a commencé depuis l’intérieur.

A) Comment choisir n pour que le maillage soit suffisamment fin et que "ça marche"
B) est-ce que dans l’absolu ça marche cette technique?

Franchement je viens d’y penser, si ça marche, quelqu’un l’a sûrement déjà implémenté!

#6

L’implémentation me paraît effectivement plutôt difficile à mettre en œuvre. Mais en te lisant, une idée a traversé mon esprit. Le temps de la comprendre suffisamment pour pouvoir l’exprimer clairement, et je viens poster cette idée.

Le problème ne vient pas du nombre de variables, mais des cas limites. En 2D, les cas limites ne se rencontrent que lorsque la droite passe par une extrémité du segment. On peut facilement détecter ces cas limites, puisque les sommets sont les renseignements que l’on a sur les segments. Le test de cas limite se réduit à une simple égalité.
En 3D, par contre, les cas limites se rencontrent lorsque la droite coupe une arrête. Mais nous n’avons pas simplement accès à l’arrête, puisque celle-ci est donnée par deux sommets. Le test du cas limite n’est plus une simple égalité.

[quote]Sinon il y aurait une autre méthode plus facile à implémenter, qui se base sur l’idée que tu vas “remplir d’eau” les composantes connexes de IR^3 moins ta surface et voir laquelle à un volume non borné. Pour faire cela:
A) Comment choisir n pour que le maillage soit suffisamment fin et que "ça marche"
B) est-ce que dans l’absolu ça marche cette technique?[/quote]

A) Le maillage n’a en fait, pas besoin d’être fin. Il suffit que INFINI soit assez grand. Si le maillage est trop gros, on ne pourra mettre aucun cube à l’intérieur du polyèdre, mais INFINI à l’extérieur.
B) Le problème est maintenant de savoir si un point est ou non à l’intérieur d’un polyèdre. Facile pour un polyèdre convexe. Plus dur pour un polyèdre complexe.

#7

[quote=“Dunatotatos”]Pas mal comme idée, à ceci près que mon polyèdre est un assemblage de faces, et je ne vois pas comment utiliser une continuité du vecteur normal sur les arrêtes, puisqu’il n’est justement pas continu. Ça pourrait fonctionner pour une ellipsoïde, ou autre surface paramétrée par une fonction C¹, mais pas sur un cube, par exemple. Je pense n’avoir pas compris la notion de conitnuité dans ce cas-là.
[/quote]
Tu dois manipuler des facettes (=triangles) ABC. Tu définies ta normale par AB ^ AC (produit vectoriel). Ta facette ABC touche 3 autres facettes, mettons A(C’)B, B(A’)C, et AC(B’) (l’ordre des points à un sens justement) dont les vecteurs normaux par continuité sont AC’ ^ AB, BA’ ^ BC et AC ^ AB’ et tu recommences avec chacune des 3 nouvelles facettes.

#8

Effectivement. Il ne reste donc qu’à établir un seul vecteur orienté vers l’extérieur. Ça revient à répondre au problème B de mon précédent message.

#9

Là tu ne pourras pas mis à part par des classements de points extrémaux. Tu devrais t’orienter vers la recherche de l’enveloppe convexe d’un ensemble de points. J’avais donné ça en TP à mes élèves. Essayes de trouver la facette ayant un point le plus «en bas»…

#10

Ah oui ! Comment ai-je pu ne pas y penser… Je l’ai aussi fait en TP l’année dernière, il me semble.
Je vais recherche le-dit TP et y jeter un œil.

Il me semble donc que cet algorithme est terminé :smiley:
Merci pour votre aide :wink: