Problème de concavité

[invitebe08d051]

Bonjour,

Ça fait plaisir de revenir sur le forum. It's been a while !

Je travaille actuellement sur un petit problème de projection.

Je dispose d'une surface fermée (une sphère, un cube, une surface modélisant une forme géométrique plus complexe...).

En réalité, je dispose d'un maillage de cette surface, autrement dit, un repère fixe, un ensemble de points appartenant à cette surface et un ensemble de triangles dont les sommets sont ces points. (Les habitués des éléments finis savent de quoi je parle)

Le pas du maillage est fixe. Je ne peux pas le modifier. J'ai besoin d'assigner à chaque triangle sa normale "sortante". Je peux facilement calculer la normale à chaque triangle au signe près. C'est là où surgit mon problème. J'ai besoin de trouver une méthode (et la coder bien sûr ) qui fasse qu'automatiquement mon programme puisse choisir la bonne orientation de la normale. Par bonne orientation, j'entends que tous mes triangles doivent avoir des orientations de leurs normales compatibles avec la forme de ma surface.

Je ne sais si ce que je dis est compréhensible. En fait, il faut que les normales des triangles dont les sommets appartiennent à une portion assez petite de ma surface ayant une concavité constante (dans le sens que convexe ou que concave) soit orientées "dans le même sens", ou bien mathématiquement que les angles les séparant soient inférieurs à .

De là, je me pose la question est ce que je peux déterminer la concavité locale d'une surface à partir des coordonnés des points...A mon avis non, puisque ces points ne définissent pas une unique surface...

Bref, ce problème me casse un peu la tête depuis un moment.

Vous en pensez quoi ?

Merci à vous.

Cordialement,
-----

[inviteea028771]

Si jamais tu veux toujours orienter les normales vers l’extérieur, je vois plusieurs solutions.

Par exemple, compter le nombre d'intersections d'une des deux normales avec les autres faces. Si le nombre d'intersections est paire, la normale est dans ce sens là, si il est impair, la normale est dans l'autre sens (probablement lourd en calcul ^^)

Autre méthode, probablement plus efficace : parcourir tout les sommets dans une direction (par exemple l'axe des z, des positifs vers les négatifs), et :
- pour les faces auquelles ce sommet appartient et qui n'ont pas de voisin, mettre la normale vers "le haut"
- pour les faces auquelles ce sommet appartient qui ont une face voisine, mettre dans un sens compatible avec les voisins (vu qu'il y a 2 sommets en commun, un voisin détermine l'orientation de toutes les normales des voisins)

Cette deuxième méthode me parait jouable si tu as à calculer l'orientation des normales une fois pour toutes

Alors après ça suppose que l'objet est cohérent


Sinon, je pense que ce problème a probablement déjà du être traité, avec des algorithmes efficaces

[Médiat]

Bonjour,

Sans aucune garantie (ce n'est qu'une idée non testée), de plus je suppose le maillage "complet" :

1) On choisit un point arbitrairement ()
2) On dresse la liste des triangles ayant ce point pour sommet
3) On choisit un de ces triangles et donc son troisième côté que l'on oriente arbitrairement (ou non)
4) On oriente uniformément la courbe constituée des "troisièmes côtés" (donc chaque "troisième côté)
5) On calcule les normales des triangles issus du point initial () en calculant le produit scalaire du "troisième côté" orienté () et du vecteur .
6) On réitère en choisissant l'un des "troisième côté" précédent qui est donc orienté, si ce côté appartient à un autre triangle (sinon on en prend un autre), le troisième point de ce triangle sert de nouveau point initial, mais cette fois la ligne des troisièmes côtés est déjà orienté.

Il existe peut-être des configurations où cela ne marche pas, et en tout état de cause l'exploration des triangles non encore pris en compte est sans doute assez pénible, et bien sûr, cela ne marche que pour des surfaces connexes (et pas seulement par un point).

[invite179e6258]

on peut toujours orientér une triangulation. Il suffit de choisir arbitrairement une orientation sur l'un des triangles et ensuite, une arête appartenant à exactement deux triangles, il suffit que cette arête soit orientée dans des sens opposés dans les deux triangles.

[A voir en vidéo sur Futura]

[Médiat]

La solution de toothpick-charlie est bien plus simple que la mienne !

[invitebe08d051]

Bonjour,

L'idée d'orienter les triangles me semblent très bien adaptée.
De plus, je dispose de la liste des triangles par la donnée de leurs sommets et donc une orientation déjà stockée.

Merci beaucoup.