%-*-LaTeX-*-

\section{Algorithme de partitionnement de l'espace : le Marching Cube}

\subsection{Du Marching Cube \dots{}}

Pour visualiser nos m\'etaformes\index{M\'etaforme} \`a l'\'ecran (dans les modes de rendu\index{rendu} temps r\'eel
c'est \`a dire non \textit{Raytracing}) il faut r\'eussir \`a construire
un r\'eseau de facettes qui les approximent le plus fid\`element possible
(une metaforme n'existant  que par sa representation mathematique).
Il n'y a pas de moyen simple d'y parvenir.
\\Une premi\`ere approche pour l'obtention du r\'eseau de facettes est l'algorithme
du ``Marching Cube'' propos\'e en 1987 par Lorensen et Cline.
Cette m\'ethode se base sur une division de l'espace dans lequel il y a un objet
\`a "triangulariser". Cet espace va \^etre divis\'e en un certain nombre
de cubes de tailles \'egales \footnote{Metagrid} comme le montre
la figure \ref{metagrid1} page \pageref{metagrid1}.
\begin{figure}[h]
\begin{center}
\includegraphics[scale=1]{graphics/grid1.ps} 
\end{center}
\caption{Une \textit{metagrid} \label{metagrid1}}
\end{figure}

Dans notre cas, nous allons calculer l'\'energie dans les coins de chaque cube
divisant l'espace. Voir la figure \ref{metagrid2} page \pageref{metagrid2}.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=1]{graphics/grid2.ps} 
\end{center}
\caption{\textit{Metagrid} englobant une m\'etaforme\index{M\'etaforme} \label{metagrid2}}
\end{figure}

Si l'\'energie d'un point P du cube est inf\'erieure au seuil \'energetique
de la m\'etaforme\index{M\'etaforme}
et que l'\'energie d'un point Q, contigu \`a P, est sup\'erieure \`a ce seuil alors
on conclut qu'une facette passe entre ces deux points.
On calcule un rapport entre les \'energies et le seuil pour savoir
de mani\`ere plus fine o\`u passe la facette entre ces 2 points.
\\Cette approche pr\'esente des probl\`emes :
\begin{itemize}
\item{l\'eg\`eres turbulences non vues car trop petites par rapport \`a la taille des cubes}
\item{si la m\'etaforme\index{M\'etaforme} est compos\'ee d'\'emetteurs\index{\'Emetteur} relativement
\'eloign\'es, les cubes sont gros
ce qui fait diminuer le niveau de d\'etails, dans des proportions
parfois catastrophiques.}
\end{itemize}

Le moyen de parer \`a cette situation
serait d'augmenter le nombre de cubes dans l'espace de la m\'etaforme\index{M\'etaforme}
mais cette technique serait beaucoup trop gourmande en calculs inutiles.


\subsection{\dots{} au Marching Cube Adaptatif}

\subsubsection{M\'ethode, algorithme}
La solution se mat\'erialise par un deriv\'e de l'algorithme du
Marching Cube : le Marching Cube Adaptatif (MCA), \'elabor\'e
par Renben Shu, Chen Zhou, Mohan S. Kankanhalli
(voir \cite{MCadaptatif}).
Cette m\'ethode se diff\'erencie du marching cube traditionnel par
une approche r\'ecursive dans la division de l'espace,
chaque cube pouvant diviser son espace en une autre s\'erie de cubes
et ainsi de suite. Voir la figure \ref{adapt} page \pageref{adapt}.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=1]{graphics/adapt.ps} 
\end{center}
\caption{Approche r\'ecursive de la division de l'espace \label{adapt}}
\end{figure}

Le MCA g\'en\`ere des facettes a un niveau
n de recursivit\'e puis regarde les angles form\'es entre les normales des 3 coins de chaque facette.
Si les angles sont superieurs \`a une certaine valeur seuil on decide de descendre d'un niveau de
recursivit\'e pour affiner les facettes r\'esultantes.
\\Algorithme:
\begin{enumerate}

\item{$\epsilon$ = angle maximal tol\'er\'e entre 2 normales} %1
\item{construction de la cellule initiale qui sera en fait "coll\'ee" \`a la boite englobante}%2
\item{TraiteCellule(cellule initiale)}%3
\\
\item{$\rightarrow{}$Procedure TraiteCellule(Cellule)} %4
\item{\hspace{5pt}on divise l'espace renferm\'e par la grille en un ensemble de sous-cellules
(cubes) toutes de taille \'egale}%5
\item{pour toutes les sous-cellules}%6
\item{\hspace{10pt}si la sous-cellule contient une surface}%7
\item{\hspace{15pt}calcul de l'intersection de la surface avec les ar\^etes de
la cellule et g\'en\'eration des facettes}%8

\item{\hspace{5pt}si profondeur de recursivit\'e maximale n'est pas atteinte}%9
\item{\hspace{10pt}calcul des normales de tous les coins des facettes g\'en\'er\'ees}%10

\item{\hspace{10pt}pour toutes les sous-cellules}%11
\item{\hspace{15pt}pour toutes les facettes de la sous cellule}%12
\item{\hspace{20pt}soit n0, n1, n2 les normales de chaque coin de la facette}%13
\item{\hspace{20pt}si $(\arccos{n_i*n((i+1)modulo3)} < \epsilon) pour i \in (0,1,2)$}%14
\item{\hspace{25pt}conserver la facette}%15
\item{\hspace{20pt}sinon}%16
\item{\hspace{25pt}TraiteCellule(sous-cellule)}%17
\item{\hspace{20pt}fin si}%18
\item{\hspace{15pt} fin pour tout}%19
\item{\hspace{10pt}fin pour tout}%20
\item{\hspace{5pt}fin si}%21
\item{$\rightarrow{}$ fin TraiteCellule}%22
\end{enumerate}

Le test employ\'e en 7  est aussi utilis\'e pour l'algorithme de calcul d'intersection
de rayon avec la m\'etaforme et est d\'ecrit dans cette partie.


Cet algorithme entra\^ine un probl\`eme qu'illustre la figure
\ref{crack} page \pageref{crack} :
il appara\^it une cassure (\textit{crack problem})
lors du maillage adaptatif lorsque une cellule de la grille de taille n 
est \`a proximit\'e d'une cellule de taille $t < n$, la cassure est une discontinuit\'e dans le r\'eseau
de facette, les facettes ne sont pas jointes et il en resulte des trous dans la forme gen\'er\'ee.
Ce probleme n'est pas enti\`erement r\'esolu en temps interactif.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.7]{graphics/crack.eps} 
\end{center}
\caption{Le \textit{crack problem} \label{crack}}
\end{figure}


\subsubsection{Int\'er\^ets}
Des cubes de petites tailles sont g\'en\'er\'es dans les endroits de la
m\'etaforme\index{M\'etaforme} qui turbulent et qui ont donc besoin de plus de d\'etails,
pour les zones "calmes" des cubes plus gros suffisent.
\\Cette m\'ethode pr\'esente plusieurs int\'er\^ets :
\begin{itemize}
\item{une bonne rapidit\'e d'\'execution.}
\item{un nombre de facettes r\'eduits, beaucoup aux endroits n\'ecessaires, peu ailleurs.}
\item{un niveau de d\'etail relativement \'elev\'e.}
\end{itemize}

\endinput