%-*-LaTeX-*-

\clearpage
\part{Techniques et algorithmes}
\setcounter{section}{0}

\section{Calcul de distance d'un point par rapport \`a un \'emetteur}

\subsection{Distance d'un point par rapport \`a chaque type d'\'emetteur}
Comme nous l'avons vu plus haut, pour voir une m\'etaforme\index{M\'etaforme} il faut regarder en tout
point de l'espace (dans la th\'eorie) pour trouver la surface o\`u l'\'energie est \'egale au seuil.
\\L'\'energie de ces points est la somme
de l'\'energie re\c{c}ue de chaque \'emetteur\index{\'Emetteur}.
Cette \'energie re\c{c}ue d\'epend de la distance \`a l'\'emetteur,
il faut donc calculer la distance dans l'espace d'un point par rapport 
\`a chaque type d'\'emetteur :
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|}
\hline
 &\\
\textbf{Type de l'\'emetteur} &

\textbf{Distance d'un point P de l'espace par rapport \`a  l'\'emetteur}\\
 &\\
\hline
 &\\
Point & Trivial\\
\hline
 &\\
Segment &
Si le projet\'e P' du point P appartient au segment,
\\ &on prend la distance PP',
\\ &sinon on calcule la distance de P \`a chaque
\\ &extr\'emit\'e du segment et on prend la plus petite des 2.\\
\hline
 &\\
Triangle (facette) & Si le projet\'e P' de P appartient
\`a la facette,
\\ &on prend la distance PP',
\\ &sinon on calcule la distance de P \`a chaque segment
\\ &formant le triangle et on prend la plus petite des 3.\\
\hline
 &\\
Ligne bris\'ee & Pour chaque segment formant
la ligne bris\'ee,
\\ &on calcule la distance du segment par
rapport \`a P,
\\ &et on prend le minimum de ces distances.\\
\hline
 &\\
Le r\'eseau de facettes & Pour chaque facette
du r\'eseau,
\\ &on calcule la distance de la facette par
rapport  \`a P,
\\ &et on prend le minimum de ces distances.\\
\hline
\end{tabular}
\end{center}
\caption{Calcul de distances}
\end{table}
  
\subsection{Probl\`eme de la cassure}
Pour les lignes bris\'ees et le r\'eseau de facettes,
du ``c\^ot\'e interne`` de la pliure se forme un effet de cassure inesth\'etique.
Cette cassure se mat\'erialise par un angle vif, comme le montre la figure
\ref{cassure} page \pageref{cassure}.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.8]{graphics/cassure.ps} 
\end{center}
\caption{Illustration du probl\`eme de la cassure :
on voit bien l'angle vif.\label{cassure}}
\end{figure}
Pour gommer cette cassure nous devons raffiner notre m\'ethode de calcul de distance
par rapport \`a une ligne bris\'ee.
\\En effet la m\'ethode que nous venons de voir plus haut
produit un passage brutal entre 2 segments cons\'ecutifs.
\\Pour \'eviter cela nous avons une m\'ethode exp\'erimentale :

\begin{itemize}
\item{on fixe une valeur $\epsilon$,}
\item{On conserve les 2 distances minimales d1 et d2 avec $d_1 < d_2$,}
\item{si $(d_2 - d_1) < \epsilon$ cela veut dire que nous sommes proche de la cassure,
on renverra alors une distance inf\'erieure \`a d1 pour effectuer le lissage.}
\end{itemize}

Cette technique permet ``d'adoucir'' la cassure,
comme le montre la figure \ref{cassure-mieux}
page \pageref{cassure-mieux}.
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.8]{graphics/cassure-mieux.ps} 
\end{center}
\caption{R\'esolution du probl\`eme de la cassure :
l'angle a \'et\'e remplac\'e par une courbe.\label{cassure-mieux}}
\end{figure}


\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.
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}

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}

Ainsi 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
