%
%                      Code_Saturne version 1.3
%                      ------------------------
%
%     This file is part of the Code_Saturne Preprocessor, element of the
%     Code_Saturne CFD tool.
%
%     Copyright (C) 1998-2007 EDF S.A., France
%
%     contact: saturne-support@edf.fr
%
%     The Code_Saturne Preprocessor is free software; you can redistribute it
%     and/or modify it under the terms of the GNU General Public License
%     as published by the Free Software Foundation; either version 2 of
%     the License, or (at your option) any later version.
%
%     The Code_Saturne Preprocessor is distributed in the hope that it will be
%     useful, but WITHOUT ANY WARRANTY; without even the implied warranty
%     of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%     GNU General Public License for more details.
%
%     You should have received a copy of the GNU General Public License
%     along with the Code_Saturne Preprocessor; if not, write to the
%     Free Software Foundation, Inc.,
%     51 Franklin St, Fifth Floor,
%     Boston, MA  02110-1301  USA
%

\nopagebreak
%==================================
\section{Algorithmes géométriques\label{sec:algo}}
%==================================

Dans ce chapitre, on apportera des précisions sur les algorithmes
utilisés pour diverses opérations réalisées par le \pcs.

\subsection{Grandeurs géométriques\label{sec:grd_geo}}

Les normales des faces (de longueurs égales aux surfaces) ainsi
que les centres de gravité des faces et cellules sont calculés par
directement par le \noy, mais des normales de faces peuvent
aussi être calculées par le \pcs pour le recollement conforme.

\subsubsection{Normales et centres de gravité des faces%
                \label{sec:grd_geo.normales}}

L'algorithme utilisé pour le calcul des normales des faces
est valable pour tout polygone plan, même si celui-ci est
non convexe. Il consiste à prendre un point arbitraire $P_a$ dans
le plan du polygone, puis à calculer la somme des normales
de tous les triangles $\{P_a, P_i, P_{i+1}\}$ où
$\{P_1, P_2, ..., P_i, ..., P_n\}$ sont les sommets du polygone
et l'on considère $P_{n+1} \equiv P_0$. Comme on le voit sur la
figure \ref{fig:algo.norm_fac.principe}, certaines normales ont
une contribution \og positive \fg, et d'autres ont une contribution
\og négative \fg, à condition de bien respecter l'ordre des sommets
du polygone. La normale obtenue a pour longueur la surface de la face.

\begin{figure}[h]
\centerline{
\includegraphics*[height=4.5cm]{\repgraphics/surf_face.\extgraphics}}
\caption{Principe du calcul des normales des faces}
\label{fig:algo.norm_fac.principe}
\end{figure}

En pratique, on prend le point \og arbitraire \fg $P_a$ comme étant le
centre de gravité des sommets du polygone, ceci afin de limiter
les problèmes de précision dus aux erreurs de troncature et
de s'assurer que le point choisi est bien dans le plan du polygone.
Pour le polygone de la figure \ref{fig:algo.norm_fac.principe},
on obtient les triangles suivants~:

\begin{figure}[h]
\centerline{
\includegraphics*[height=3.5cm]{\repgraphics/grd_face.\extgraphics}}
\caption{Triangles pour le calcul des grandeurs aux faces}
\label{fig:algo.grd_fac.triangles}
\end{figure}

Le centre de gravité $G$ d'une face est égal au barycentre des
triangles $T_i$ définis par $\{P_a, P_i, P_{i+1}\}$ et dont les
barycentres sont notés $G_i$. Soit $O$ le centre du repère de
calcul et $\overrightarrow{n_f}$ la normale associée à la face, on a~:

\begin{displaymath}
\overrightarrow{OG}
= \frac{\sum_{i=1}^n \textrm{surf}(T_i).\overrightarrow{OG_i}}
       {\sum_{i=1}^n \textrm{surf}(T_i)}
\qquad \textrm {avec} \quad
\textrm{surf}(T_i) = \frac{\overrightarrow{n_{T_i}}.\overrightarrow{n_f}}
                          {\parallel \overrightarrow{n_f} \parallel}
\end{displaymath}

Il est important de bien tenir compte du signe associé à la surface
de chaque triangle pour que la formulation ci-dessous reste valide
pour des faces non convexes.

On remarquera qu'en réalité, certaines faces ne sont pas parfaitement
planes. Dans ce cas, le calcul comportera une légère erreur, mais
il est difficile de définir ce qu'est réellement la surface d'une
face polygonale lorsque toutes ses arêtes ne sont pas dans le même plan.
On pourrait par exemple considérer qu'il s'agit de la plus petite
surface limitée par ses arêtes (i.e. la surface que l'on obtiendrait
avec une maquette des arêtes et un film d'eau savonneuse), ou bien qu'il
s'agit de la surface définie par la face découpée en triangles (avec
une triangulation respectant le critère de Delaunay dans un plan médian
de la face, lui-même à préciser), ou choisir encore une autre définition.

Pour limiter les erreurs dues aux faces gauches, on compare la
contribution aux volumes des cellules voisines de la face à la contribution
(calculée à partir de la formule de Stokes) obtenue à partir
des triangles $\{P_a, P_i, P_{i+1}\}$, et l'on déplace le centre
de gravité initialement calculé dans l'axe de la normale à la face
de manière à obtenir la même contribution.

\subsubsection{Centres de gravité des cellules%
               \label{sec:grd_geo.cdgcel}}

Si l'on considère qu'en théorie, la méthode VF travaille sur des grandeurs
constantes par maille, il n'est pas indispensable pour le \noy de connaître
avec exactitude le centre de gravité d'une cellule donnée, un point
arbitraire contenu dans la cellule en question devant suffire. En fait,
pour la précision, la position du point assimilé au centre de gravité est
importante, car elle intervient dans le calcul des valeurs et gradients aux faces.

Considérons une cellule $\mathcal{C}$ comportant $p$ faces de centres
de gravité $G_k$ et de surfaces de norme $S_k$. Soit $O$ l'origine du
repère de calcul, le centre de gravité $G$ de $\mathcal{C}$ est défini par~:

\begin{displaymath}
\overrightarrow{OG}
= \frac{\sum_{k=1}^p S_k.\overrightarrow{OG_k}}
       {\sum_{k=1}^p S_k}
\end{displaymath}


Si la cellule $\mathcal{C}$ comporte $q$ sommets de coordonnées $X_l$,
une autre possibilité de définition du centre de gravité $G$ de $\mathcal{C}$
est la suivante~:

$$\overrightarrow{OG} = \sum_{l=1}^q \frac{\overrightarrow{OX_l}}{q}$$

Il est conseillé d'utiliser le calcul par défaut basé sur les centres de
gravité des faces; la deuxième définition correspond à celle qui
était utilisée par les versions 1.0 de \CS, et la possibilité d'y revenir
n'a été conservée que par précaution,\footnote {On craignait que le calcul
basé sur les centres de gravité et surfaces des faces ne puisse poser
problème dans le cas de maillages extrudés de faible épaisseur ou
semblables, comportant des faces de surfaces très faibles par rapport
à d'autres. On pouvait aussi s'inquiéter du comportement de l'algorithme
lorsque l'on a des faces gauches, et que les positions des centres de
ces faces sont incertaines d'un point de vue théorique. Jusqu'ici, il
semble que cet algorithme n'a jamais provoqué des difficultés,
et il améliore plutôt  la convergence dans certains cas comportant
des faces gauches.} et afin de pouvoir comparer des calculs effectués
avec diverses versions de \CS.

Sur la figure \ref{fig:algo.cdg_cel.loc}, on représente le centre
de gravité calculé selon les deux algorithmes sur une cellule
exemple bidimensionnelle (ou 3D issue d'une extrusion). À gauche,
la cellule n'est pas altérée ; à droite, on a ajouté des sommets
supplémentaires sur une face de la cellule, comme si cette cellule
se trouvait sur la frontière d'un recollement conforme \refpar{sec:recoll}.
On voit que la position du centre de gravité est stable selon la
formulation basée sur les centres de gravité des faces, alors que
ce point est décalé vers la face à laquelle on a ajouté des sommets
avec la formulation basée sur le centre de gravité des sommets.

\begin{figure}[h]
\centerline{
\includegraphics*[width=15.5cm]{\repgraphics/cdg_cel.\extgraphics}}
\caption{Centre de gravité d'une cellule}
\label{fig:algo.cdg_cel.loc}
\end{figure}

On montre l'effet possible sur la position des segments joignant
les centres de gravité de plusieurs cellules dans une situation
de recollement conforme sur la figure \ref{fig:algo.cdg_cel.nonorth}.

\begin{figure}[h]
\centerline{
\includegraphics*[height=4.5cm]{\repgraphics/cdg_cel_nonorth.\extgraphics}}
\caption{Orthogonalité des faces selon le centre de gravité}
\label{fig:algo.cdg_cel.nonorth}
\end{figure}

On voit ici que l'ancien algorithme basé sur les centres de gravité
des sommets à tendance à accentuer les non-orthogonalités des faces,
par rapport à l'algorithme actuel basé sur le barycentre des faces.
C'est la principale raison pour laquelle cet algorithme est déconseillé,
et n'est activable que par positionnement d'une variable d'environnement,
à fin d'utilisation exceptionnelle par les développeurs et experts.

{\bf Remarque}~: il n'y a pas de calcul d'un centre égal au centre
de la sphère circonscrite, qui n'existe pas pour tous les types de cellules.

\subsection{Recollement conforme\label{sec:recoll}}

Le recollement de maillages non conformes constitue une des fonctionnalités
les plus importantes du \pcs, et les algorithmes associés sont les
plus complexes de ce module. Le principe est de construire de nouvelles
faces correspondant aux intersections des faces à recoller, et de remplacer
les faces d'origine par leur recouvrement avec des faces issues de cette
intersection, comme le montre la figure \ref{fig:algo.recoll.principe}
(en coupe latérale 2D)~:

\begin{figure}[h]
\centerline{
\includegraphics*[height=5cm]{\repgraphics/rc_principe.\extgraphics}}
\caption{Principe du recollement conforme}
\label{fig:algo.recoll.principe}
\end{figure}

On parle de \emph{recollement conforme}, car le maillage issu de ce
recollement est bien conforme, la où le maillage d'origine ne l'était pas.

Le nombre de faces d'une cellule dont un bord a été recollé sera supérieur
ou égal au nombre de faces d'origine, et rien ne garantit que
les nouvelles faces issues du recollement ne soient des triangles ou
des quadrangles, même si les toutes les faces d'origine étaient de
l'un de ces types. C'est pourquoi le modèle de données du \pcs
(ainsi que celui du \noy) doit être adapté à la représentation de faces
polygonales et de cellules polyédriques quelconques, ou presque.
En effet, on se limite à des faces polygonales sans trous, comme
illustré par la figure \ref{fig:algo.recoll.possible}.
\footnote{La connectivité faces-arêtes utilisée permettrait des faces avec
trous, en supprimant simplement l'hypothèse selon laquelle le parcours
des arêtes dans l'ordre de leur définition correspond au parcours
du bord de la face dans le sens direct. Par contre, la connectivité
faces-sommets ne pourrait plus être représentée simplement, et ces faces
ne pourraient donc être visualisées sans découpage ni avec \ensight ni
avec un outil basé sur la librairie \vtk (et encore moins avec \ideas).
Certains algorithmes devraient être en outre être modifiés, notamment le
découpage de faces en triangles, et le calcul des normales et centres
de gravité.}

\begin{figure}[h]
\centerline{
\includegraphics*[height=5cm]{\repgraphics/rc_possible.\extgraphics}}
\caption{Cas de recollement possibles}
\label{fig:algo.recoll.possible}
\end{figure}

\subsubsection{Présentation des aspects influant sur la robustesse%
               \label{sec:recoll.robust}}

On a cherché à faire en sorte que l'algorithme de recouvrement puisse
fonctionner avec un minimum de paramètres utilisateur, et puisse traiter
une grande variété de cas.

Plusieurs critères sont importants~:

\begin{enumerate}
\item {\bf déterminisme}~: il est important de pouvoir prédire le comportement
de l'algorithme. Notamment, on a cherché à construire un algorithme
qui produira le même résultat indépendamment de la numérotation des mailles.
Si ce critère n'était pas respecté, le recollement d'un maillage $A$ concaténé
avec un maillage $B$ pourrait être différent du recollement de $B$ concaténé
avec $A$. L'algorithme final peut présenter une dépendance aux erreurs de
troncature sur de rares cas, mais cet impact est très limité et l'algorithme
théorique est bien indépendant de la numérotation (et donc l'ordre de parcours)
des diverses entités de maillage. L'utilisateur n'a donc pas à se poser de
questions sur l'ordre d'entrée des maillages par rapport au recollement
conforme.\footnote{La géométrie issue d'un recollement est en théorie
indépendante de l'ordre d'entrée des maillages, mais la numérotation des
mailles ne l'est pas. Un ordre d'entrée utilisé pour un calcul doit donc
être conservé pour toute reprise de ce calcul.}

\item {\bf surfaces non planes}~: On veut pouvoir recoller à la fois des
surfaces courbes et des surfaces correspondant à un ensemble de plans,
mais dont la normale n'est pas nécessairement une fonction continue de
l'espace.

\begin{figure}[h]
\centerline{
\includegraphics*[height=3cm]{\repgraphics/rc_non_plan.\extgraphics}}
\caption{Surfaces initiales}
\label{fig:algo.recoll.non_plan}
\end{figure}

\item {\bf jeu entre les maillages}~: Les surfaces à recoller peuvent
ne pas être strictement confondues. Ceci peut provenir de problèmes
d'arrondis lors de la génération des maillages, de cotes prises avec
un nombre de décimales différentes, ou simplement de l'approximation
d'une surface courbe par un ensemble de faces planes.
\end{enumerate}

\subsubsection{Principe de base\label{sec:recoll.principe}}

Considérons deux surfaces à recoller~:

\begin{figure}[h]
\centerline{
\includegraphics*[height=4cm]{\repgraphics/rec_couv_3d.\extgraphics}}
\caption{Recollement de deux surfaces}
\label{fig:algo.recoll.courb}
\end{figure}

On cherchera à déterminer les intersections entre les arêtes de ces deux
faces, et découper les arêtes en sous-arêtes s'appuyant sur ces intersections.
On décrira par la suite ce que l'on entend par \og intersection \fg entre
arêtes, la notion utilisée ici étant relative à un voisinage de l'arête.

\begin{figure}[h]
\centerline{
\includegraphics*[height=4cm]{\repgraphics/rec_couv_3d_2.\extgraphics}}
\caption{Après intersection des arêtes}
\label{fig:algo.recoll.courb2}
\end{figure}

Ensuite, on reconstruira des sous faces issues de chaque face initiale. Pour
ce faire, en partant d'une arête d'une face d'origine, on cherchera à construire
des cycles fermés, en choisissant à chaque sommet l'arête connectée à ce sommet
pointant le plus à gauche (vu du plan de la face, debout sur la face
normale vers le haut et en regardant dans la direction de l'arête courante),
jusqu'au point de départ, de manière à construire le cycle
le plus court possible en tournant dans le sens trigonométrique. Chaque face à
recoller est ainsi remplacée par son recouvrement constitué de sous-faces
construites de cette manière.

Lors du parcours des cycles on fera attention à rester proche du plan de la face
d'origine. On ne considérera que les arêtes appartenant à des faces dont la
normale a une direction voisine de la face en cours de subdivision (i.e. le
produit scalaire des normales unitaires doit être proche de 1 en valeur absolue).

\begin{figure}[h]
\centerline{
\includegraphics*[height=4.5cm]{\repgraphics/rec_couv_3d_3.\extgraphics}}
\caption{Construction de sous-faces}
\label{fig:algo.recoll.courb3}
\end{figure}

Une fois construites toutes les sous-faces, on devrait avoir pour deux faces
initiales en vis-à-vis deux sous-faces topologiquement identiques, héritant
chacune d'une des faces initiales et ainsi connectées à une cellule différente.
Il suffit alors de fusionner les faces topologiquement identiques, et la face
issue de la fusion sera connectée à deux cellules. Les faces de bord fusionnées
sont donc remplacées par des faces internes, et le recollement est effectif.

\subsubsection{Simplification du recouvrement\label{sec:recoll.simplif}}

Pour le \CS, il est préférable d'éviter d'avoir des faces
de dimensions très différentes appartenant à une même cellule.
Pourtant, cela peut se produire facilement lorsque l'on découpe les
faces de bord non conformes afin de reconstruire une interface conforme.
Sur l'exemple de recouvrement ci-dessous, on voit que si l'on découpe
les faces en fonction de leur recouvrement avec d'autres faces
non-conformes, on sera amené à créer des faces beaucoup plus petites que
d'autres.

Il est possible de simplifier le recouvrement de faces de manière à
éviter ou du moins réduire ce phénomène, en déplacant légèrement certains
des n\oe{}uds des maillages de part et d'autre du recouvrement. On cherchera
à déplacer les n\/oe{}uds de manière à simplifier le recouvrement tout en
déformant le moins possible le maillage.

Un exemple de recouvrement est représenté ci-dessous. On y montre quelques
possibilités de simplification. On remarquera que toutes ces possibilités
sont associées à une même arête. Les possibilités de même type associées
à d'autres arêtes ne sont pas représentées afin de ne pas surcharger
la figure~:

\begin{figure}[h]
\centerline{
\includegraphics*[height=5cm]{\repgraphics/recouv_1.\extgraphics}}
\caption{Possibilités de simplification}
\label{fig:algo.recoll.simpl1}
\end{figure}

Après simplification, on a la situation suivante~:

\begin{figure}[h]
\centerline{
\includegraphics*[height=5cm]{\repgraphics/recouv_2.\extgraphics}}
\caption{Faces après simplification}
\label{fig:algo.recoll.simpl2}
\end{figure}

\subsubsection{Traitement effectué\label{sec:recoll.traitement}}

Le point de départ de l'algorithme est la recherche d'intersections
entre arêtes. En 3D, on ne se limitera pas aux \og vraies \fg intersections,
mais on considérera que l'on a une intersection dès que la distance
minimale entre deux arêtes passe en dessous d'un certain seuil.

\begin{figure}[h]
\centerline{
\includegraphics*[height=3cm]{\repgraphics/int_are_3d.\extgraphics}}
\caption{Intersection d'arêtes dans l'espace}
\label{fig:algo.recoll.intare}
\end{figure}

À chaque sommet, on associera une distance maximale, proportionnelle
à la longueur de la plus petite arête connectée à ce sommet. Cette
distance sera toujours strictement inférieure à la moitié de la longueur
d'une arête (la valeur maximale autorisée pour la sous-option {\tt -fraction}
étant $0.49$).
On considérera un voisinage d'une arête constitué
de l'enveloppe rejoignant les deux sphères associées. En un point
de l'arête d'abscisse relative $s$, ce voisinage sera donc la
sphère de rayon $d_{max}(s) = (1-s)d_{max}\mid_{s=0} + s.d_{max}\mid_{s=1}$.

 On aura alors intersection entre arêtes $A1$ et $A2$ dès que le point
de $A1$ le plus proche de $A2$ se trouve à l'intérieur du voisinage
associé à $A2$, et que simultanément, le point de $A2$ le plus proche
de $A1$ se trouve simultanément dans le voisinage associé à $A1$.

\begin{figure}[h]
\centerline{
\includegraphics*[height=4cm]{\repgraphics/int_are_3d_eps.\extgraphics}}
\caption{Tolérances associées aux intersections d'arêtes}
\label{fig:algo.recoll.intare_eps}
\end{figure}

Si l'arête $A2$ passe dans le voisinage associé à un sommet de
l'arête $A1$, et que ce sommet se trouve dans le voisinage associé à
$A2$, on prendra pour définir l'intersection ce sommet plutôt que le
point de $A1$ le plus proche de $A2$. Ceci évitera de découper
inutilement les arêtes par la suite. On recherchera donc en priorité
les \og intersections \fg sommet-sommet, sommet-arête, puis arête-arête.
Si les voisinages associées à deux arêtes s'intersectent, mais
que le critère : $\exists P1 \in A1, \exists P2 \in A2, d(P1,P2)
 < min(d_{max}(P1), d_{max}(P2))$ n'est pas respecté, on n'aura pas
intersection. Ces cas sont représentés ici (vus de côté)~:

\begin{figure}[h]
\centerline{
\includegraphics*[height=5cm]{\repgraphics/int_are_3d_typ.\extgraphics}}
\caption{Types d'intersection}
\label{fig:algo.recoll.intare_typ}
\end{figure}

\subsubsection{Problèmes associés à la fusion de sommets voisins
               \label{sec:recoll.pb_fusion}}

Si l'on a déterminé qu'un sommet $S_1$ doit être fusionné avec un
sommet $S_2$, et qu'indépendamment, ce sommet $S_2$ doit être
fusionné avec un sommet $S_3$, alors par transitivité, $S_1$ et
$S_3$ devraient être agglomérés, même si ces sommets ne partagent
aucune intersection. On illustre figure \ref{fig:algo.fusion.pb}
des situations théoriques pouvant mener à ce problème.

\begin{figure}[h]
\centerline{
\includegraphics*[height=5cm]{\repgraphics/rc_fusion.\extgraphics}}
\caption{Transitivité de la fusion}
\label{fig:algo.fusion.pb}
\end{figure}

Sur la figure \ref{fig:algo.fusion.pb_1}, on représente des cas plus
représentatifs de ce que l'on peut obtenir couramment avec des maillages
réels, compte tenu de la prise en compte des tolérances locales.

\begin{figure}[h]
\centerline{
\includegraphics*[height=5cm]{\repgraphics/rc_fusion_1.\extgraphics}}
\caption{Transitivité de la fusion (cas réels)}
\label{fig:algo.fusion.pb_1}
\end{figure}

La figure \ref{fig:algo.fusion.pb_2} montre l'impact d'une
combinaison de fusions sur des sommets appartenant à une même arête.
On voit que dans ce cas, les arêtes passant initialement par les sommets
$G$ et $J$ sont très fortement déformées (i.e. découpées en arêtes
très mal alignées). Sans transitivité, des arêtes passant par des
sommets issus des seules fusions de $(G, H)$ d'une part  et $(L, J)$
d'autre part seraient beaucoup plus proches des arêtes d'origine.

Pour éviter des simplifications excessives du maillage liées à
des enchaînements de fusions, on vérifie pour chaque arête si
des situations de ce type se produisent. Si c'est le cas, on calcule
localement un facteur multiplicatif (inférieur à 1) des tolérances
de fusion/intersection pour les sommets appartenant à cette arête
de manière à déterminer un maximum de fusions
entre sommets d'intersection avec cette arête sans aller jusqu'à
provoquer des fusions non désirées par transitivité.

\begin{figure}[h]
\centerline{
\includegraphics*[height=6cm]{\repgraphics/rc_fusion_2.\extgraphics}}
\caption{Transitivité de la fusion sur une arête}
\label{fig:algo.fusion.pb_2}
\end{figure}

Finalement, sur la figure \ref{fig:algo.fusion.pb_3}, on  montre
l'effet possible de la transitivité de fusions sur des sommets appartenant
à plusieurs arêtes. Ici, même si la réduction de tolérance locale
permet d'éviter la fusion des sommets $(G, I)$ par combinaison
des regroupements $(G, H)$ et $(H, I)$, cette fusion pourrait être provoquée
par transitivité des agglomérations $(H, I)$, $(H, J)$, et $(G, J)$. De plus,
$I$ et $J$ seraient alors fusionnés alors qu'il ne devraient pas l'être.

Dans cet exemple précis, la réduction locale de tolérance sur chaque
arête devrait éviter la fusion $(H, I)$, car les tolérances associées à
$G$ et $H$ sont plus grandes que celle associée à $I$~; la réduction
locale de tolérance devrait donc conserver la fusion $(G,H)$ et
supprimer la fusion $(H,I)$. On n'aura donc pas d'agglomération $(I, J)$ par
transitivité, et seuls $(G, H, J)$ seront fusionnés.

\begin{figure}[h]
\centerline{
\includegraphics*[height=5cm]{\repgraphics/rc_fusion_3.\extgraphics}}
\caption{Transitivité évitée de la fusion sur plusieurs arêtes}
\label{fig:algo.fusion.pb_3}
\end{figure}

Cependant, dans la configuration de la figure \ref{fig:algo.fusion.pb_4},
où les tolérances associées aux sommets $G$, $H$, et $I$ sont différentes
de celles présentées figure \ref{fig:algo.fusion.pb_3},
la réduction de la tolérance locale évitera initialement la fusion $(G, H)$
en conservant $(H, I)$, dont la combinaison avec $(H, J)$ provoquera en fin
de compte une agglomération de $(G, H, I, J)$ en $G'$.

\begin{figure}[h]
\centerline{
\includegraphics*[height=5cm]{\repgraphics/rc_fusion_4.\extgraphics}}
\caption{Transitivité de la fusion sur plusieurs arêtes}
\label{fig:algo.fusion.pb_4}
\end{figure}

Ce dernier cas n'est pas traité, la réduction de tolérance
locale ne se faisant qu'au niveau des arêtes. Pour traiter tous les cas
en maintenant l'indépendance théorique de l'algorithme vis-à-vis de l'ordre
de parcours des faces et arêtes, il serait possible d'effectuer plusieurs
passes, en réduisant définitivement les tolérances locales. Cependant, s'il
n'est pas gênant vis-à-vis du parcours des arêtes d'une face pour la
reconstruction de faces conformes de ne pas fusionner certains de ses sommets
(le parcours n'étant pas fondamentalement modifié), une réduction de tolérance
inter-arêtes reviendrait par contre à supprimer certaines intersections
détectées.
Ceci aurait un impact moins prévisible sur le résultat de l'algorithme.
L'algorithme actuel n'ayant pas à ce jour posé de problèmes de robustesse
qui n'aient pu être traités par un ajustement de la tolérance par défaut,
on a préféré ne pas le rendre plus complexe, sachant que la
non-transitivité assurée des intersections sur une même arête semble éviter
la grande majorité des problèmes.

\subsubsection{Optimisation de l'algorithme\label{sec:recoll.optim}}

Un certain nombre de facteurs influent sur les performances à la fois
en coût calcul et mémoire. On cherchera toujours à optimiser les deux,
en cherchant toujours à ne pas augmenter trop sensiblement le coût mémoire 
d'une exécution du \pcs avec recollement par rapport à une exécution
sans recollement.

Lors de la recherche d'intersections entre arêtes, on cherche à limiter
au maximum le nombre d'essais. On calcule les boîtes englobantes
associées aux arêtes, et on n'appelle la fonction de calcul d'intersection
que si ces boîtes s'intersectent, dans quel cas la probabilité d'avoir
une intersection est élevée. Ces boîtes seront alignées avec les axes,
et de taille légèrement supérieures au minimum nécessaire pour contenir
les arêtes et le voisinage associé à la tolérance~:

\begin{figure}[h]
\centerline{
\includegraphics*[height=4cm]{\repgraphics/rc_boite.\extgraphics}}
\caption{Boîtes englobantes pour les arêtes}
\label{fig:algo.boite_englob}
\end{figure}

On effectuera alors une boucle sur les arêtes des faces sélectionnées,
avec un algorithme hybride dichotomie-parcours pour rechercher les
arêtes pouvant intersecter l'arête courante. Soit $i$ l'indice de
l'arête courante, on ne cherchera des intersections qu'avec des arêtes
d'indice $j$ tel que $j > i$, les autres ayant normalement dues être trouvées
lorsque $j$ était l'arête courante.

On pourrait aussi éviter de rechercher des intersections entre arêtes
partageant un sommet. Par exemple, sur le schéma suivant, il n'est pas
nécessaire de rechercher d'intersection entre les arêtes $A2$ et $A4$, ni
entre $A3$ et $A4$, car on devra dans tous les cas détecter l'intersection
de type \og sommet-sommet \fg entre $A1$ (qui partage ce sommet avec
$A2$ et $A3$) et $A4$.

\begin{figure}[h]
\centerline{
\includegraphics*[height=3cm]{\repgraphics/rc_lim_test.\extgraphics}}
\caption{Limitation possible des tests d'intersection d'arêtes}
\label{fig:algo.lim_test}
\end{figure}

Les intersections du même type que celle reliant le milieu de $A4$ avec un
sommet de $A2$ devraient donc être détectées indirectement. Ceci devrait
presque toujours être le cas, à moins de construire des cas pathologiques,
tels que l'on pourrait avoir sur le schéma ci-dessus en supprimant l'arête
$A1$, mais en conservant $A2$, $A3$, et $A4$. On aurait alors des faces
géométriquement superposées, mais ne comportant pas le même nombre
de sommets et d'arêtes.

Un cas plus probable est celui où l'on recolle des quadrangles déformés
avec des triangles. Le problème ne se pose qu'aux bords des surfaces à
recoller, et uniquement si des sommets sont communs aux deux surfaces
(ce qui peut se produire si l'on a concaténé ces maillages sous un outil
tel que \ideas ou \simail, et fusionné les n\oe{}uds voisins)~:

\begin{figure}[h]
\centerline{
\includegraphics*[height=3.5cm]{\repgraphics/rc_pb_lim_test.\extgraphics}}
\caption{Problème avec la limitation des tests d'intersection}
\label{fig:algo.pb_lim_test}
\end{figure}

Pour pouvoir traiter malgré tout ce type de cas, on doit permettre la
recherche d'intersections entre arêtes possédant un sommet commun.
Ce type de recherche n'ést en général pas utile sur les maillages
testés, mais on aussi observé que le surcoût induit par ce type de test était
négligeable à l'échelle de l'ensemble des opérations liées au recollement, et
on l'effectue doc systématiquement.

\subsubsection{Influence sur la qualité du maillage\label{sec:recoll.qualite}}

Il est préférable pour le noyau du \CS que le maillage soit le plus
\og orthogonal \fg possible (une face est parfaitement orthogonale lorsque
le segment rejoignant son centre de gravité au centre d'une cellule voisine
quelconque elle appartient est aligné avec sa normale).
Il est tout aussi important d'éviter des faces non planes.
\footnote {Le calcul des centres de gravité des faces comporte une correction
de manière à ce que la contribution d'une face gauche au calcul du volume
soit la même que celle des triangles joignant le centre de gravité des
sommets aux arêtes de la face, de manière à ne pas commettre d'erreur sur
le calcul des grandeurs linéaires, mais il n'est pas certain que cette
correction suffise pour les grandeurs d'ordre 2.}

Par principe même, des faces initialement orthogonales seront découpées
en plusieurs faces non orthogonales lors d'un recollement conforme.
De plus, plus la tolérance utilisée est importante, plus la fusion de
sommets voisins tendra à entraîner un gauchissement des faces latérales à
celles recollées.

Il est donc important d'être sensible à ces effets, et d'être conscient
qu'un maillage issu du recollement de maillages héxaédriques parfaitement
réguliers peut être de mauvaise qualité, notamment si l'on a utilisé un
paramètre de tolérance de fusion lâche et que les raffinements des maillages
recollés sont très différents. Il est donc fortement conseillé de visualiser
les critères de qualité sur le maillage final, et d'éviter les recollements
à l'intérieur des zones sensibles du maillage.

\section{Recherche de faces périodiques\label{sec:algo.perio}}

La construction de structures associées à la périodicité se fonde sur
le recollement périodique. Le principe de base, décrit par la
figure \ref{fig:algo.rc_perio}, est le suivant~:

\begin{itemize}

\item Soit un ensemble de faces de bord sélectionné, on duplique
      l'ensemble de ces faces (ainsi que les arêtes et sommets associés) et
      l'on déplace la copie selon le pas de périodicité indiqué par
      l'utilisateur. On conserve un lien d'historique entre les entités
      dupliquées et les entités d'origine.

\item On construit un recollement conforme sur l'ensemble
      \{{\it faces sélectionnées} $\cup$ {\it faces dupliquées}\}.
      Ce recollement déformera légèrement le maillage de manière à
      pouvoir fusionner des sommets très proches les uns des autres,
      et découpera les faces en vis-à-vis en sous-faces conformes
      (si les faces périodiques ne le sont pas).

\item On applique si nécessaire le découpage des faces copiées puis
      recollées aux faces dont elles sont la copie.

\item On supprime les entités dupliquées qui n'ont pas participé
      au recollement.

\end{itemize}

\begin{figure}[h]
\centerline{
\includegraphics*[height=8cm]{\repgraphics/rc_perio.\extgraphics}}
\caption{Principe du recollement périodique}
\label{fig:algo.rc_perio}
\end{figure}

Il n'est donc pas nécessaire pour utiliser des conditions de type
périodicité que les surfaces périodiques soient maillées de manière
identique, même s'il est préférable de ne pas abuser des possibilités
de ce type au regard de la qualité du maillage de calcul.

On remarquera qu'il peut sembler plus simple de séparer
les faces périodiques en un ensemble de faces \og amont \fg et
un ensemble de faces \og aval \fg, en ne dupliquant et transformant
que le premier ensemble, afin d'optimiser la recherche
de correspondants et de ne pas avoir à supprimer en fin de traitement
des faces copiées n'ayant pas participé à la périodicité.
L'algorithme utilisé a été conçu pour permettre une
sélection des faces périodiques au moyen de sous-options de ligne
de commande semblables à celles utilisées pour le recollement
conforme. Comme pour le recollement conforme,
la spécification d'un critère de sélection afin de ne traiter
que les faces effectivement périodiques ne s'avère en général pas utile
sur un maillage relativement simple.

\section{Découpage de faces en triangles\label{sec:dec_fac}}

Le découpage de faces en triangles se fait en deux passes. La
première passe est un algorithme du type \emph{ear cutting}, qui
peut découper tout type de polygone à peu près plan, convexe ou non.
Le découpage généré est arbitraire, et dépend notamment du sommet
du polygone choisi pour le début du parcours.

La deuxième passe consiste à permuter des arêtes deux à deux
jusqu'à ce que le découpage soit de type Delaunay contraint,
ce qui résulte généralement en un découpage plus régulier.

\subsection{Découpage initial\label{sec:dec_fac_ini}}

\begin{figure}[h]
\centerline{
\includegraphics*[width=14cm]{\repgraphics/decoup_fac_pcp.\extgraphics}}
\caption{Principe du découpage de faces en triangles}
\label{fig:algo.decoup_oreille}
\end{figure}

L'algorithme est basé sur celui décrit dans \cite{triangl1}.
Son principe est illustré figure \ref{fig:algo.decoup_oreille}.
On commence par vérifier si le triangle constituté des premiers sommets du
polygone, $(P_0, P_1, P_2)$ est une \og oreille \fg du polygone, c'est à
dire s'il est intérieur au polygone et ne l'intersecte pas. Comme c'est le
cas sur cet exemple, on obtient un premier triangle, et on doit traiter
la partie restante du polygone. À l'étape suivante, le triangle
constitué des premiers sommets du polygone restant, $(P_0, P_2, P_3)$
constitue lui aussi une oreille, et peut être supprimé.

Par contre, on voit à l'étape $2$ que le prochain triangle canditat au
découpage, $(P_0, P_3, P_4)$ n'est pas une oreille, car il n'est pas
contenu dans le polygone restant. On décale alors les indices des sommets
à considérer, et on voit étape $4$ que le triangle $(P_3, P_4, P_5)$
est bien une oreille et peut être supprimé.

L'algorithme est construit de manière telle qu'un triangle est sélectionné
par rapport au dernier sommet du dernier triangle considéré (en partant
du triangle $(P_0, P_1, P_2)$). Ainsi, on considère étape $5$
le triangle se terminant par $P_5$, soit $(P_0, P_3, P_5)$.
Une fois ce triangle supprimé, le polygone restant est un triangle, et
son traitement est immédiat.

\subsection{Amélioration du découpage\label{sec:dec_fac_delaunay}}

On montre sur les figures \ref{fig:algo.decoup_ex_1} et \ref{fig:algo.decoup_ex_2}
deux exemples du découpage produit sur deux polygones semblables mais
dont les sommets sont numérotés de manière différente.

\begin{figure}[h]
\centerline{
\includegraphics*[height=2.5cm]{\repgraphics/decoup_fac_1.\extgraphics}}
\caption{Exemple de découpage (1)}
\label{fig:algo.decoup_ex_1}
\end{figure}

\begin{figure}[h]
\centerline{
\includegraphics*[height=2.5cm]{\repgraphics/decoup_fac_2.\extgraphics}}
\caption{Exemple de découpage (2)}
\label{fig:algo.decoup_ex_2}
\end{figure}

\vfill

Non seulement le découpage obtenu n'est pas le même, mais il a tendance
à produire des triangles très aplatis. Une fois un premier découpage
obtenu, on applique donc un algorithme correctif, consistant à
permuter des arêtes séparant deux triangles adjacents
deux par deux de manière à respecter le critère de Delaunay.

\begin{figure}[h]
\centerline{
\includegraphics*[height=4cm]{\repgraphics/crit_delaunay.\extgraphics}}
\caption{Critère de Delaunay (2)}
\label{fig:algo.crit_delaunay}
\end{figure}

 Ce critère est illustré figure
\ref{fig:algo.crit_delaunay}. Dans le premier cas, l'arête
$\overline{P_i P_j}$ ne respecte pas le critère, car le sommet $P_l$
est contenu dans le cercle passant par $P_i, P_j, P_k$. Dans le second
cas, l'arête $\overline{P_k P_l}$ respecte bien ce critère, $P_i$
n'étant pas contenu dans le cercle passant par $P_j, P_k, P_l$.

Si les triangles $(P_i, P_k, P_j)$ et $(P_i, P_j, P_l)$ étaient issus
du découpage initial d'un même polygone en triangles, on les remplacerait
donc par les triangles $(P_i, P_k, P_l)$ et $(P_l, P_k, P_j)$, qui
respectent le critère de Delaunay. Dans le cas d'un quadrangle, on
aurait terminé, mais avec un polygone de départ plus complexe,
ces nouveaux triangles pourraient éventuellement être remplacés
par d'autres, en fonction de leurs autres voisins appartenant
au polygone.

\begin{figure}[H]
\centerline{
\includegraphics*[height=2.5cm]{\repgraphics/decoup_delaun_1.\extgraphics}}
\caption{Exemple de correction Delaunay (1)}
\label{fig:algo.delaunay_ex_1}
\end{figure}

\begin{figure}[H]
\centerline{
\includegraphics*[height=2cm]{\repgraphics/decoup_delaun_2.\extgraphics}}
\caption{Exemple de correction Delaunay (2)}
\label{fig:algo.delaunay_ex_2}
\end{figure}

Sur les figures \ref{fig:algo.delaunay_ex_1} et \ref{fig:algo.delaunay_ex_2},
on illustre cet algorithme sur les mêmes exemples que précédemment (figures
\ref{fig:algo.decoup_ex_1} et \ref{fig:algo.decoup_ex_2}). On voit
bien que le résultat final est le même. En théorie, l'algorithme
de transformation de la triangulation pour respecter l'algorithme
de Delaunay converge toujours. Pour éviter des problèmes dus à des
erreurs de troncature, on applique une tolérance avant de décider de permuter
deux arêtes. Ainsi, on accepte que le découpage final puisse simplement
\og presque \fg respecter le critère de Delaunay.

Dans certains cas, notamment celui de carrés parfaits, deux découpages
en triangles différents respectent le critère de Delaunay, aux erreurs
de troncature près. Pour la périodicité, on doit éviter que deux faces
périodiques puissent être découpées de manière non périodique (par exemple
selon les deux diagonales sur un quadrangle). On découpe donc une des faces,
et on applique ce découpage à sa face périodique, plutôt que de découper
les deux faces indépendamment.

\passepage

