Site26
Faites CTRL+D ou cliquez ici pour ajouter ce site à vos favoris. Last Update 20 mai 2008
Menu



counter

Meteo

OpenGL Logo

Debian Linux

Menu
Curriculum Vitae
Rapports Stage
Projets
Documentation
- online
- download
Contact

Photos

Petite annonce immobilier maison terrain appartement

Téléchargement du rapport en Microsoft Word, de la présentation en version Microsoft PowerPoint.

Rapport mis à jour ici




UNIVERSITE NICE SOPHIA ANTIPOLIS
Ecole Supérieure
En
Sciences Informatiques










PROJET DE FIN D’ETUDE

Logiciel de construction
d’un matériau virtuel







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.








ESSI 3ème année
LOG
Encadrant:
Roland LOGE

Entreprise:
Ecole des Mines de Paris – CEMEF

Année 2003






SOMMAIRE




INTRODUCTION
1.1. Présentation du laboratoire
1.2. Présentation du contexte du projet
2. Description du cahier des charges
2.1. Construction du matériau virtuel
2.2. Visualisation du matériau virtuel
2.3. Extraction de données
3. Description du travail effectué
3.1. Le cahier des charges
3.2. Etude des différentes librairies
3.3. Le développement du projet
3.3.1. Algorithme de remplissage de matériau
3.3.2. Conception de l’IHM
4. Planning du projet
CONCLUSION
BIBLIOGRAPHIE
ANNNEXES
A. Diagramme de Voronoi et triangulation de Delaunay
B. Algorithme de vérification qu’un point est à l’intérieur d’un volume




Figure 1: Schéma générale de fonctionnement.
Figure 2: Description de divisions et de joints.
Figure 3: Hiérarchie de la structure d'une division.
Figure 4: Diagramme de classe.
Figure 5: Libraires CGAL (http://www.cgal.org).
Figure 6: Algorithme de remplissage de matériau.
Figure 7: Capture d'écran du logiciel; Visualisation du matériau plein.
Figure 8: Capture d’écran du logiciel;Visualisation du matériau en fil de fer.
Figure 9: Capture d’écran du logiciel; Visualisation du matériau en mettant certaines divisions en transparence.
Figure 10: Capture d’écran du logiciel; Sélection d’une division.
Figure 11: Triangulation 2D de Delaunay.
Figure 12: Triangulation de Delaunay (bleu) et diagramme de Voronoi (Rouge).
Figure 13: Tracé de rayon.
Figure 14: Calcul des angles.





INTRODUCTION





1.1. Présentation du laboratoire.

      Mon projet s’est déroulé dans le laboratoire du CEMEF de l’école des Mines de Paris à Sophia-Antipolis. Le Centre de Mise en Forme des Matériaux, créé à Paris en 1974, est l'un des 18 centres de recherche de l'Ecole Nationale Supérieure des Mines de Paris. Installé à Sophia-Antipolis en 1976 avec la volonté de participer à l'élaboration d'un nouveau pôle de haute technologie sur la Côte d'Azur, il s'est associé au CNRS (UMR 7635) en 1979.
  • Sa vocation est triple:
    • La transmission du savoir et du savoir-faire du CEMEF aux étudiants ingénieurs ou chercheurs en formation au Centre,
    • La recherche appliquée,
    • La collaboration active avec l'Industrie.
  • Le CEMEF est leader européen dans le domaine de la recherche sur la mise en forme des matériaux. Près de 150 personnes dont plus de soixante doctorants travaillent sur des thèmes essentiels à la compréhension des procédés de mise en forme. Les activités de recherche du CEMEF concernent tous les types de matériaux (métaux, polymères, composites, verre, matières agroalimentaires, ...). Elles s'articulent autour de quatre axes scientifiques :
    • La matière s'écoule, les outils doivent résister : axe thermomécanique des milieux continus;
    • La matière s'oriente cristallise ou se texture : axe relations écoulement - cristallisation - morphologie; (relations entre la mise en oeuvre, la structure et les propriétés d'emploi);
    • La matière frotte sur les outils : axe surfaces et mécanique du contact, usure, transfert thermique, lubrification;
    • La modélisation numérique aux différentes échelles dans les procédés.
[ Sommaire ]



1.2. Présentation du contexte du projet.

      L’objectif du projet est de réaliser un logiciel de construction de matériaux virtuels. Par matériau virtuel, on entend une représentation numérique le plus fidèle possible d’un matériau réel, à la fois au point de vue géométrique (représentation 3D) et au point de vue de ses propriétés physiques et mécaniques, stockées dans la structure logicielle sous forme hiérarchique. 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, principalement en utilisant la méthode des éléments finis. Ceci évite de coûteuses expériences réelles avec pour objectif l’optimisation des caractéristiques du matériau par rapport à des applications industrielles spécifiques.

      Actuellement, des efforts sont entrepris au CEMEF pour étudier de manière très précise la structure à l’échelle mésoscopique où la longueur caractéristique est de l’ordre de la dizaine de microns, des alliages métalliques qui sont mis en forme et utilisés dans l’industrie automobile, aéronautique, …

      Le but est de passer d’une description géométrique complexe d’une structure (sous forme d’images, de plans, de fonctions statistiques éventuellement) à sa représentation, ou à une de ses représentations en 3D, interactive et « interrogeable » par la souris. La programmation orientée objet est donc plus simple, avec de plus un soucis d’établir des hiérarchies entre les objets qui correspondent aux hiérarchies multi-échelles que l’on observe physiquement entre les éléments de la structure.

[ Sommaire ]





2. Description du cahier des charges.

   Le projet peut se diviser en 3 parties:
  • Construction du matériau virtuel à partir de courbes statistiques.
  • Visualisation du matériau virtuel.
  • Extraction de données à partir du matériau virtuel construit.


Figure 1: Schéma générale de fonctionnement.


[ Sommaire ]



2.1. Construction du matériau virtuel.

      Tout d’abord, un matériau (comme une division et les sous divisions de celui-ci) est composé d’un ensemble de plans, eux-mêmes composés de lignes, puis de points. Lors de la construction, le matériau peut être divisé en grains qui eux-mêmes peuvent être encore divisés en sous divisions. On aura ainsi plusieurs niveaux d’imbrications:
  • Niveau 0: matériau.
  • Niveau 1: grains.
  • Niveau 2: cellules.
  • Niveau 3: arrangement de dislocations.
  • Niveau 4: arrangement des atomes.

      Toutes les constructions d’un matériau virtuel se font à partir de courbes statistiques décrivant des propriétés géométriques mais aussi d’autres propriétés physiques. Le matériau virtuel est construit à partir de courbes statistiques sur la base des propriétés géométriques du matériau. Celles-ci doivent être obligatoirement fournies:
  • Courbes statistiques sur la taille des grains. La taille correspond à la distance entre les 2 points d’un rayon coupant un grain. Pour le calcul de la distance, nous effectuerons un quadrillage de droites ayant un angle d’inclinaison et un écart entre elles. Pour que la taille des grains correspond le plus possible à la courbe, nous pouvons utiliser le calcul de la moyenne, de la variance, du « skewness » (degré de symétrie) et du « kurtosis » de la courbe. Dans un premier temps, seule la moyenne, puis la variance sera prise en compte, les autres moments de la courbe étant plus difficiles à prendre en compte.
  • Courbes statistiques sur la forme des grains (rapport de forme = grand diamètre / petit diamètre).
  • Proportion de phases, avec les compositions chimiques associées. Les phases sont des régions de l’espace qui ont des propriétés physiques différentes.

      Les autres propriétés sont physiques et optionnelles. Elles seront définies par l’utilisateur en fournissant leur nom et la courbe statistique associée. Il faudra aussi indiquer si elles s’appliquent aux joints (plan inter-granulaire) ou aux grains. La distribution des valeurs des propriétés se fera toujours de la même façon, par tirage aléatoire de nombres compris entre 0 et 1 et en utilisant la courbe de probabilités cumulées fournie. Pour chaque propriété, la courbe statistique d’un matériau doit se rapprocher au maximum de la courbe statistique d’entrée. A titre d’exemple, les principales courbes seront:
  • Courbes statistiques sur la disposition des atomes: plus spécifiquement sur l’orientation cristallographique du réseau des atomes, définie par 3 angles d’Euler (ou une matrice de rotation).
  • Distribution spatiale des précipités et distribution de leur taille.
  • Densité de dislocations.
  • Fraction recristallisée et/ou taille des cellules de restauration.



Figure 2: Description de divisions et de joints.



      Pour chaque courbe statistique, une propriété intervalle de probabilité peut être définie. Cette propriété indique que la partie de la courbe de l’intervalle doit être propagée aux divisions pour être utilisé lors de la sous divisions.

      Toutes les propriétés doivent être hiérarchisées. Pour la visualisation à un niveau n, on ne doit pouvoir utiliser que les propriétés du niveau n (géométriques ou physiques), et celles des niveaux supérieurs (n+1, n+2…).

      Toutes les sous divisions (par exemple : matériau en grains) sont construit avec l’algorithme de Voronoi. Mais, dans le futur, d’autres algorithmes doivent pouvoir facilement être ajoutés. En plus des informations de la structure géométriques du matériau, les points de Voronoï doivent être conserver pour effectuer des modifications sur le matériau lors des diverses itérations.

      La construction des différents niveaux du matériau se fera l’un après l’autre. Un menu «construction» aura tous les niveaux d’un matériau et tant que celle précédant n’est pas construit, elles seront grisées. Si l’on choisit de construire un niveau, une boite de dialogue sera affiché permettant de paramétrer la construction en insérant les courbes sur les propriétés.

[ Sommaire ]



2.2. Visualisation du matériau virtuel.

      La visualisation permettra de manipuler le matériau (rotation, zoom, …) et voir les grains du matériau. Pour faciliter la visualisation des divisions, des coupes pourront être faites dans le matériau. Une sélection de divisions pourra aussi être faite, à partir de critères booléens (< = > …) sur les propriétés diverses. Seuls les divisions correspondantes à ces critères seront affichées.

      Chaque division aura des propriétés, ainsi que chaque zone séparant 2 divisions (ces zones sont appelées joints de divisions). Ces propriétés seront accessibles après sélection d’un joint et seront définies grâce aux courbes statistiques données lors de la construction du matériau. Lors d’une sélection, il y a aussi interaction avec l’interface homme machine.

      L’IHM (Interface Homme Machine) se composera de deux parties : la partie visualisation 3D et la partie navigation. Cette dernière partie sera un onglet composé de feuilles : grains, plans, points. Dans chacune de ces feuilles, on aura une hiérarchie indiquant les liens entre les grains, plans et points. Lors d’une sélection dans la hiérarchie, une boite de dialogue sera affiché avec les propriétés de l’objet. Lorsqu’un double-clique est effectué sur un joint dans la zone de visualisation, une boite de dialogue sera affiché avec toutes les propriétés ainsi que les divisions dont le joint appartient. En parallèle, dans la zone de navigation, le joint sera sélectionné.

      La partie visualisation permet de voir seulement un niveau à la fois. Il sera donc possible de naviguer entre les différents niveaux. Pour visualiser une division (grain, cellules, …), il faudra sélectionner ce niveau.

[ Sommaire ]



2.3. Extraction de données.

    Des données sur le matériau construit pourront être extrait sous la forme de courbes statistiques:
  • Taille des grains.
  • Disposition des atomes, les orientations cristallographiques (angles d’Euler).
  • L’ensemble des propriétés, géométriques ou non.
  • Courbes statistiques sur les désorientations cristallographiques (entre grains).
  • Etc.
      On doit pouvoir extraire soit des courbes statistiques d’une propriété, soit la valeur particulière d’une propriété en une région de l’espace qui a été sélectionnée. Si les propriétés sont géométriques comme dans le cas de la sauvegarde de la structure du matériau, il faut fournir une liste hiérarchisée des divisions/plans/points qui constituent et permettent de représenter les objets concernés. Si les propriétés ne sont pas géométriques, il faut pouvoir dresser leur liste associée aux objets auxquels ils appartiennent qui, eux, ont une représentation géométrique.




Figure 3: Hiérarchie de la structure d'une division.


[ Sommaire ]





3. Description du travail effectué.

3.1. Le cahier des charges.

      La première étape du projet fut de réaliser le cahier des charges. Ce fut une étape de réflexion de façon globale sur le projet. Il fallait mettre sur papier toutes les idées et vérifier si elles étaient techniquement faisables et cohérentes dans l’ensemble du logiciel.

      Après la phase d’écriture du cahier des charges, j’ai réfléchi à la conception du logiciel. Pour cela, j’ai utilisé Rational Rose pour créer le diagramme de classe (Figure 4).



Figure 4: Diagramme de classe.



      La conception du logiciel doit être le plus général possible. On doit pouvoir ajouter ou modifier des algorithmes le plus facilement possible.

[ Sommaire ]



3.2. Etude des différentes librairies.

      La plus grosse partie de ce projet était de développer un algorithme pour remplir un matériau avec des grains et des cellules. Pour cela, je devais utiliser l’algorithme de Voronoi (Annexe A). Etant donné que cet algorithme est très compliqué à implémenter, j’ai dû étudier dans un premier temps toutes les librairies permettant de créer des diagrammes de Voronoï en 3D. Après de nombreuses recherches sur Internet, seulement trois librairies ont retenu mon attention (LEDA, CGAL et Qhull) mais seulement deux me permettait de faire des tests. En effet, LEDA était seulement disponible en version de démonstration avec une très vielle version. J’ai donc effectué mes tests avec Qhull et CGAL afin de choisir la plus performante.

      Après plusieurs tests, les performances des deux librairies étaient pratiquement identiques. Mais CGAL avait l’avantage d’être plus robuste (moins d’erreur numérique et fonctionne même dans des cas très particuliers) et pouvait beaucoup plus facilement s’intégrer dans un programme. En effet, Qhull est un programme DOS. Je devais donc passer par des fichiers pour pouvoir l’utiliser.



Figure 5: Libraires CGAL (http://www.cgal.org).



      CGAL est une librairie spécialisée dans les algorithmes de calcul géométrique. Elle est écrite en C++ et développé dans un projet ESPRIT LTR dont fait partie l’INRIA. Le but de cette librairie est de fabriquer un large corps d’algorithme géométrique se retrouvant dans des applications industrielles.

[ Sommaire ]



3.3. Le développement du projet.

3.3.1. Algorithme de remplissage de matériau.

      La principale difficulté dans le développement de ce logiciel était la création d’un algorithme permettant de remplir un volume 3D avec un diagramme de Voronoï (Annexe A) tout en gardant la hiérarchie de la structure (c’est à dire, par exemple, une face est la même face pour les deux divisions l’appartenant).

      Après une longue réflexion, l’algorithme retenu était d’abord de générer des points à l’intérieur de ce volume 3D (Annexe B). Ensuite, je calcule la symétrie de chaque point avec chaque plan du volume. Enfin, j’insère tous ces points dans la triangulation de Delaunay, puis je calcul son dual (le diagramme de Voronoï) de chaque segment de Delaunay ayant un point qui n’est pas un point de symétrie. J’obtiens ainsi le matériau avec les grains et les cellules ayant les mêmes frontières que le matériau de départ.


Figure 6: Algorithme de remplissage de matériau



      Le figure 6 montre le fonctionnement de cet algorithme. En noir, nous avons le matériau dont les divisions doivent avoir les mêmes frontières. En vert, ce sont les points générés aléatoirement à l’intérieur du matériau ainsi que les symétries de ces points. En calculant, la triangulation de Delaunay (en bleu) à partir des points, nous obtenons le diagramme de Voronoï en rouge. Sur la figure, la triangulation de Delaunay est limitée à l’intérieur du matériau pour des raisons de compréhension, mais normalement, la triangulation s’étend sur tous les points. Par contre, seul le diagramme de Voronoï à l’intérieur du matériau est calculé.

      Le problème de cet algorithme est qu’il fonctionne que sur des volumes convexes. La solution pour remplir un volume concave a été d’utiliser un algorithme qui divise le volume en plusieurs volumes convexes enfin de lui appliqué cet algorithme. Mais faute de temps, cet algorithme est resté sous forme de réflexion.

      Les principales difficultés de cette étape ont été de voir en 3D ce qu’il fallait faire. De plus, ce genre d’algorithme entraîne de nombreuses erreurs numériques d’où la difficulté de corriger les erreurs de programmation. Je ne savais jamais si une erreur était produite par une erreur dans mon algorithme ou alors par des erreurs numériques. Ces erreurs ont été résolues en utilisant des types numériques autre que «double» (plus grand type réel que les processeurs calculs matériellement). J’ai utilisé des types numériques de la librairie CGAL. Liés à ces problèmes numériques, j’avais le problème de la rapidité de cet algorithme. En effet, ce dernier a une complexité assez grande donc l’utilisation de types numériques de la librairie CGAL faisait ralentir encore plus, puisque ceux-ci sont calculés en logiciel. Donc, il a fallut que je trouve un équilibre entre performance et résultat juste.

[ Sommaire ]



3.3.2. Conception de l’IHM.




Figure 7 : Capture d'écran du logiciel; Visualisation du matériau plein.



      L’étape suivante était le développement de l’interface homme machine. Le logiciel devait fonctionner sous Windows avec Visual C++. Dans un premier temps, j’ai développé une grosse partie de l’interface homme machine. La partie la plus importante est la zone de visualisation 3D du matériau. Nous pouvons effectuer des rotations, des transformations et des zooms sur cette zone. Différents modes de visualisation sont disponibles. Nous avons la possibilité de voir le matériau plein (figure 7), en fil de fer (figure 8), ou sous forme plein mais en mettant en transparence certaines divisions pour permettre de voir l’intérieur du matériau (figure 9).




Figure 8: Capture d’écran du logiciel; Visualisation du matériau en fil de fer.





Figure 9: Capture d’écran du logiciel; Visualisation du matériau en mettant certaines divisions en transparence.



      J’ai aussi implémenté l’onglet permettant l’affichage de la hiérarchie de la division en cours. Cet onglet a la particularité de pouvoir être redimensionné, détaché de la fenêtre et même fermé comme une barre d’outil (figure 10). Ceci permet d’avoir une zone d’affichage plus grand si cela est nécessaire.

      Comme décrit dans le cahier des charges, nous avons aussi la possibilité de sélectionner une face des divisions (grains ou cellules) avec la souris. Lorsqu’une face est sélectionnée, une boîte de dialogue est affichée montrant les propriétés de la face et aussi les propriétés des divisions appartenant à cette face (figure 10).




Figure 10:Capture d’écran du logiciel; Sélection d’une division


[ Sommaire ]





4. Planning du projet.

      Le projet a commencé à partir du 15 octobre. Jusqu'à début décembre, je me suis concentré sur l’écriture du cahier des charges (Chapitre 1). Ce fut une période d’échange entre mon encadreur et moi. Au fur et à mesure des réunions, je complétais le cahier des charges. Puis, je l’envoyais à mon encadreur pour qu’il puisse vérifier le contenu. Et lors de la réunion suivante, l’on discute de ce qui n’allait pas ou de ce qui fallait compléter.

      Au cours du mois de décembre et de mi-janvier, j’ai étudié les différentes librairies pour permettre de créer des diagrammes de Voronoi en 3D. J’ai aussi effectué plusieurs tests pour me permettre de choisir.

      De la mi-janvier à la mi-mars, j’ai réfléchi puis implémenter l’algorithme de remplissage d’un matériau avec le diagramme de Voronoi. Certaines parties de l’IHM comme la visualisation 3D ont été nécessaire d’être développer tout de suite pour me permettre de tester mon algorithme.

      Enfin, depuis la mi-mars, je me suis concentré principalement sur IHM. J’ai développé la sauvegarde et le chargement des fichiers dans l’application. Je me concentrerais aussi sur les propriétés et les courbes statistiques. C’est à dire, tout ce qui concerne la lecture de ces courbes et l’application des propriétés liées à ces courbes sur les divisions et les joints de divisions. Pendant le mois de mars,  j’ai finit le remplissage de la hiérarchie de la structure dans l’onglet, et la création de l’assistant de création de matériau.

      Enfin, le mois avril a été principalement utilisé pour la correction des erreurs, à la rédaction de documentation et à la modification de petites parties. Plus aucun gros développement n’a été entreprit pour  terminer avec un logiciel qui fonctionne même s’il n’est pas tout à fait complet.

[ Sommaire ]





CONCLUSION



      En définitive, ce projet me permet de participer à un projet important et concret. J’ai ainsi appris de nouveaux outils et langages comme la programmation IHM sous Windows. J’ai aussi développé mes connaissances en C++ et en conception logiciel. En plus du travail de programmation, il y a un gros travail de communication pour comprendre ce que veut exactement mon encadreur. L’une des difficultés est que ce logiciel est appliqué au domaine de la mécanique, domaine que je ne connais pas bien. Mais la principale difficulté fut la complexité des algorithmes et surtout les erreurs numériques que je n’imaginais pas aussi importante avant d’effectuer ce projet. En définitive, ce projet a donc été fort captivant et enrichissant sous tous rapports.

[ Sommaire ]





BIBLIOGRAPHIE




Ivor Horton, ‘Visual C++ 6’, Eyrolles-Wrox, 2002

http://www.cgal.org/ (CGAL est une librairie de calcul géométrique utilisé dans le projet).

http://www.geom.umn.edu/software/qhull/ (Qhull est un programme permettant en autre de calculer le diagramme de Voronoi).

http://www.cs.cornell.edu/Info/People/chew/Delaunay.html (Applet pour visualiser en 2D le comportement de l’algorithme de Voronoi).

http://www.magic-software.com/Intersection3D.html (Liste des algorithmes d’intersection géométrique).

[ 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)


[ Sommaire ]





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.

[ Sommaire ]






Copyright © 2000, 2006