%-*-LaTeX-*-

\section{Le mode de repr\'esentation r\'ealiste : algorithme de lanc\'e de rayons sur des surfaces implicites}

\subsection{Principes du lanc\'e de rayons : le \textit{raytracing}}
\index{Raytracing}
\subsubsection{D\'efinition d'un rayon}
Un rayon est d\'efini par son point de d\'epart (en g\'en\'eral la cam\'era), sa direction et une liste d'objets
avec lesquels il rentre en collision. : voir la figure \ref{ray-def} page \pageref{ray-def}.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.5]{graphics/ray-def.eps} 
\end{center}
\caption{Intersection d'un rayon et de la surface de la m\'etaforme\label{ray-def}}
\end{figure}

Cette liste d'intersections avec les objets contient le point d'intersection
ainsi que la distance par rapport au point de d\'epart du rayon.
Ainsi, on peut trier la liste pour r\'ecuperer le premier objet intersect\'e par le rayon et calculer la couleur
du point de collision.

\subsection{Lanc\'e de rayons sur les m\'etaformes}

Comme nous l'avons vu pr\'ec\'edemment, les m\'etaformes sont d\'efinies \`a l'aide d'une formule
math\'ematique d'\'energie dissip\'ee en fonction de la distance.
Notre but, pour calculer l'image finale, va donc \^etre de trouver l'intersection entre
les rayons envoy\'es de l'oeil vers les m\'etaformes pr\'esentent dans l'espace de vision.
\newline
Le principe utilis\'e pour trouver l'intersection entre un rayon et la m\'etaforme se base sur l'analyse num\'erique
des fonctions d\'efinissant les \'emetteurs de
la m\'etaforme dans les points de l'espace.
Ceci nous permet de pouvoir modeliser tr\`es pr\'ecisemment la surface, dans ses moindres d\'etails, ce qui n'est
pas possible avec la repr\'esentation par facettes ou par des algorithmes simples d'illumination.
\newline
L'analyse de la fonction se base sur un bornage de sa variation en certaines parties de l'espace.
La valeur {\bf{L}} sera
utilis\'ee plus tard, et correspond \`a la variation maximale d'\'energie dans un cube de l'espace. Une autre valeur
{\bf{G}} sera utilis\'ee plus tard et correspond \`a la variation maximale du gradiant d'\'energie sur un
intervalle donn\'e.
\newline
La m\'ethode pour trouver l'intersection entre la surface et le rayon se divise en trois parties :
\begin{enumerate}
\item{Subdivision r\'ecursive de la surface pour chaque m\'etaforme, \`a partir de sa m\'etagrille\footnote{\textit{metagrid.}} pour une repr\'esentation par octries\footnote{\textit{octree.}}
: voir figure \ref{octrie} page \pageref{octrie}
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.5]{graphics/octrie.eps} 
\end{center}
\caption{Construction d'une octrie par cube de la m\'etagrille\label{octrie}}
\end{figure}
}

\item{Intersection du rayon avec les octants constituants les octries g\'en\'er\'ees au dessus, puis choix de
l'octant dans lequel le rayon va rencontrer la surface :
voir figure \ref{octrie-ray} page \pageref{octrie-ray}.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.5]{graphics/octrie-ray.eps} 
\end{center}
\caption{Octrie g\'en\'er\'ee pour la surface et intersection du rayon avec les octants\label{octrie-ray}}
\end{figure}
}
\item{Recherche de la premi\`ere intersection entre le rayon et la surface dans l'octant :
voir figure \ref{inter} page \pageref{inter}.
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.5]{graphics/inter.eps} 
\end{center}
\caption{Intersection des rayons avec la m\'etaforme dans l'octant. \label{inter}}
\end{figure}
}
\end{enumerate}

\subsubsection{Construction de l'octrie :}
Une octrie est un arbre constitu\'e d'octants, la racine de l'arbre correspond \`a un cube de la m\'etagrille
de la m\'etaforme. Pour chaque cube de la m\'etagrille, nous allons g\'en\'ener l'octrie correspondante
\`a la subdivision de la surface dans ce cube.
Chaque noeud de l'arbre peut \^etre le p\`ere de huit fils, ces fils \'etant la division du cube du noeud en
huit sous-cubes de r\'esolution plus fine.
\newline
La construction de l'octrie nous permet d'optimiser les calculs pour l'intersection du rayon avec la surface
puisqu'on est certain que la surface passe dans chaque octant de l'arbre (les feuilles de l'arbre en fait).
\newline
Pour trouver la subdivision de la surface en octant, il nous faut effectuer certains tests,
voici l'algorithme :
\newline
Soit b le rayon d'un cube (c'est-\`a-dire la longueur de sa demi diagonale), et C son centre.
\begin{itemize}
\item{Si $|f(C)-Treshold|>b*L$ alors il ne peut pas y avoir d'intersection car le cube est enti\`erement
dans la surface ou \`a l'\'exterieur.}
\item{Si l'octant est d'une r\'esolution assez fine, et que le test des valeurs \'energ\'etiques aux huit coins
du cube nous montre que la surface passe forc\'ement dans le cube, alors l'octant est rang\'e dans l'arbre sous
forme de feuille, et les valeurs de L et G sont sauvegard\'ees. Ce test permet l'arr\^et de la r\'ecursivit\'e dans
la construction de l'arbre.}
\item{Si aucuns des crit\`eres ci-dessus n'ont \'et\'e choisis alors le cube est divis\'e en huit sous cubes, et
une exploration est lanc\'ee r\'ecursivement dans chacun des nouveaux cubes.}
\end{itemize}

Le premier test utilise les propri\'et\'es des fonctions avec la constante de Lipschitz, pour borner la fonction 
et voir sa variation de valeurs dans un intervalle.

\subsubsection{Chercher les octants intersect\'es par le rayon puis trouver le premier dans lequel le rayon va toucher la surface }
Il suffit tout simplement dans cette partie l\`a, de regarder, pour chaque octrie de chaque cube de la
m\'etagrille, si
le rayon intersecte le cube ou pas, puis d'inserer dans une liste tri\'ee la position de
l'intersection et la distance d'intersection sur le rayon.
\newline
Pour trouver ensuite dans quel octant de la liste le rayon va croiser la surface de la m\'etaforme,
il faut appliquer
une serie de tests sur les octants dans l'ordre d'apparition sur le chemin du rayon.
\newline
Voici l'algorithme utilis\'e :
\begin{itemize}
\item{Calculer la valeur de G dans la bo\^ite correspondant \`a notre cellule d'octrie,
puis regarder le r\'esultat
de $|g(tm)|>G$. La fonction g \'etant la fonction deriv\'ee de f dans la direction du rayon,
et tm \'etant la position
du centre du segment AB cr\'e\'e par le rayon dans la bo\^ite.
A et B sont les points d'intersection du rayon avec la bo\^ite.}
\item{Si c'est vrai alors on regarde les signes de $|f(A)-Treshold|$ et $|f(B)-Treshold|$ pour voir si
d'une extr\'emit\'e \`a l'autre on est dans la surface ou pas.
Si les signes sont differents alors il n'y a qu'une seule intersection dans cette cellule entre le rayon
et la surface, et
on peut entammer un proc\'edure de recherche dichotomique de la solution dans le cube.}
\item{Si les signes sont \'egaux alors il ne peut pas y avoir d'intersection dans la cellule et dans ce cas la,
nous passons \`a la suivante.}
\item{Sinon, c'est que le premier test a \'echou\'e et dans ce cas, il peut y avoir plus d'une intersection entre
le rayon et la surface. A ce moment l\`a, on subdivise l'intervalle d'intersection en deux, puis on recommence
r\'ecursivement les tests sur les deux nouveaux intervalles.}
\end{itemize}

Cette m\'ethode, optimis\'ee gr\^ace \`a l'utilisation d'un octrie pour approximer la surface, nous permet d'avoir un
rendu\index{Rendu} tr\`es r\'ealiste des objets de type m\'etaforme ou plus g\'en\'eralement de type surfaces implicites.

\endinput