Logiciel de construction d’un matériau virtuel
Projet de fin d'étude
Résumé: L’objectif du projet est de réaliser un logiciel de construction de matériaux virtuels. Le matériau virtuel doit synthétiser toutes les caractéristiques importantes du matériau réel de manière à pouvoir ensuite être étudié par des séries d’expériences virtuelles. On doit pouvoir passer d’une description géométrique complexe d’une structure à sa représentation, ou à une de ses représentations en 3D, interactive et « interrogeable » par la souris.
SOMMAIRE
ANNNEXES
A. Diagramme de Voronoi et triangulation de Delaunay
La triangulation de Delaunay d’un ensemble de points est une triangulation ayant la principale propriété qu’aucun point se trouve à l’intérieur de la circonférence de tous les triangles de la triangulation à part, bien sur, les points des sommets de ce triangle. Sur la figure 11, nous pouvons voir en vert l’ensemble des points, en bleu, la triangulation 2D de Delaunay et en rouge, quelque circonférence de triangles. Une autre propriété de la triangulation de Delaunay est qu’elle maximise le plus petit angle de l’ensemble des triangles. Nous obtenons ainsi une triangulation régulière.
Figure 11: Triangulation 2D de Delaunay
Pour des raisons de compréhension, toutes les figures sont en 2D. Par contre, lors du projet, ces algorithmes ont été utilisés en 3D. Nous avons donc une dimension en plus. Les triangles en 2D deviennent des tétraèdres en 3D, et les cercles des sphères, …
La triangulation de Delaunay a un dual géométrique, le diagramme de Voronoi. Un diagramme de Voronoi d’un ensemble de point est une sous division de plans à l’intérieur de régions polygonales dont quelques-unes unes peuvent être infinies. Sur la figure 12, nous pouvons voir le diagramme de Voronoi de la triangulation de Delaunay précédente. Nous pouvons noter que les sous divisions à la périphérie de la triangulation de Delaunay sont infinis.
Figure 12: Triangulation de Delaunay (bleu) et diagramme de Voronoi (Rouge)
B. Algorithme de vérification qu’un point est à l’intérieur d’un volume
Pour vérifier si un point est à l’intérieur d’un volume 3D, j’ai implémenté un algorithme qui trace un rayon ayant pour source ce point. La destination de ce rayon est sans importance mais s’il est parallèle à un axe, certains calculs peuvent être simplifiés.
Figure 13: Tracé de rayon
Comme le montre la figure 13, lorsqu’un rayon coupe un nombre pair de face alors la source de ce rayon est à l’extérieur. Par contre, si le rayon coupe un nombre impair de face alors la source du rayon est à l’intérieur. Ce principe fonctionne de même en 3D pour les volumes.
Maintenant, il reste à savoir comme calculer si un rayon coupe une face. Pour cela, je calcul l’intersection entre ce rayon et chaque plan des faces de ce volume. Pour vérifier si le point de l’intersection entre le rayon et le plan se trouve à l’intérieur du polygone (la face), j’effectue un test d’angle. C’est à dire, si la somme des angles P[i] Q P[i+1] est égale à 2PI alors le point se trouve à l’intérieur de ce polygone (figure 14). Lorsqu’un point est la l’extérieur de ce polygone la somme des angles tend vers 0 plus le point est éloigné de la face.
Figure 14: Calcul des angles
La difficulté de cet algorithme sont les erreurs de calculs numériques. En effet, lorsque nous calculons l’intersection entre le rayon et le plan des erreurs numériques se produits et nous obtenons rarement 2PI lors du calcul des angles. La solution a été de mettre un epsilon d’erreur sur la somme des angles. Mais cela a conduit à accepter des points juste à la périphérie du polygone mais à l’extérieur. La solution a donc été de calculer la distance entre le point source et le point d’intersection. Si celle-ci est trop petite, nous supposons que le point est à l’extérieur.
Planning du projet