Construction de l'association Atome-Element

Une telle association est utile car elle diminue la recherche de l'élément conteneur d'un atome à une opération constante. Cette association est présentée par la figure 3.5.

L'algorithme naïf de construction de cette association, consisterait en une double boucle dont la compléxité serait en $\mathcal{O} (m \times n_{el})$, avec $m$ le nombre d'atomes présents dans le recouvrement et $n_{el}$ le nombre d'élément présent dans le recouvrement. Dans le cas tri-dimentionel le problème atteint des proportions non négligeable^3.1, et il faut à tout prix réduire la compléxité de cet algorithme.

Afin d'obetenir cette accélération, il faudrait faire un présélection sur critère spatial. La solution choisie porte sur la construction d'une grille, partition de l'espace, qui permet d'obtenir en temps constant une liste d'éléments d'un maillage qui intersectent l'élement de la grille qui contient une coordonnée de l'espace donnée. On définit cette grille par :

• Une boite englobante de la zone que l'on veut utiliser.
• Le pas de discrétisation, qui sera le même dans toutes les directions.
  

Figure 3.6: Découpage de l'espace en grille. La recherche spatiale des éléments est alors à compléxité réduite. L'insertion d'un élément dans la grille se fait par tests des noeuds de ce dernier.

On fournit par la figure 3.6 un exemple de grille 2D et 3D. Le remplissage de cette grille peut se faire lors du parcours de sélection (et de pondération) des éléments.

La taille de la grille sera telle que la longueur maximum des triangles sera strictement plus petite que la taille des éléments de la grille. Cela évitera bien sûr la duplication trop importante des éléments du maillage à répertorier, mais également les cas de détection à problèmes. Par exemple, le cas ou un triangle contiendrait plusieurs éléments de la grille ne permet pas (sauf à utilisation d'un algorithme plus couteux) la dectection de ces dernière. Dans ce cas des éléments de la grille ne répertorieraient pas ce triangle, ce qui serait enlève tout interêt quant à l'utilisation de cette grille. La figure 3.7 illustre ce cas de figure.

Figure 3.7: Dans le cas ou la taille des éléments de la grille est inférieur à la longueur caractéristique des éléments du maillage, le cas de figure suivant peut être encontré et la recherche de cet élément ne sera pas toujours résolue. En effet les deux blocs colorés de la grille sur la figure sont entièrement contenus par le triangle présenté.

Néanmoins même quand ce dernier critère de taille se voit respecté, il faut distinguer les cas où tous les sommets d'un élement du maillage se trouve dans le même block de la grille, et les autres cas. Dans le premier cas, on enregistre l'élément concerné uniquement dans le seul bloc de la grille qui le contient. Dans les autres cas, la démarche la moins couteuse fut celle de construire une boite englobante de cet élément et d'enregistrer tous les sommet de cette dernière. la figure illustre ce deuxième cas de figure.

Figure 3.8: Dans le cas présent, il ne suffit pas d'inscrire le triangle présenté uniquement dans les blocs qui contiennent ses noeuds. En effet, un point présent dans la zone hachurée est bien à l'intérieur du triangle, mais pas dans les mêmes blocs que les noeuds de ce dernier. La méthode utilise la boite englobante du triangle : on inscrit tous ses sommets dans la grille.

Afin de construire l'association dont il est question, on parcours l'ensemble des atomes. Pour chaqun d'entre eux, on demande à la grille la liste des éléments dont l'intersection avec le bloc que l'atome concerné est non vide. En pratique, le réglage de la finesse de la grille permet d'accélérer la boucle, tant que l'on reste dans le critère de taille précisé plus haut. La compléxité de l'algorithme de construction de cette association devient par conséquent $\mathcal{O} (m)$ avec m le nombre d'atomes présents dans le recouvrement.