\subsection{Algorithmes}

Le plus complexe des algorithmes de ce projet est celui de gestion des
collisions. Cependant, ce dernier est différent suivant que l'on utilise la
caméra de visualisation 3D (figure \ref{Coll3D}) ou celle d'édition du terrain
``2D'' (figure \ref{Coll2D}) . 

\begin{figure}
\begin{verbatim}
        Début
        Si la camera recule
           alors
               la faire tourner de 180 degrés horizontalement
               pour qu'elle fasse face aux obstacle potentiels;
           finsi

        Trouver le polygone le plus proche de la camera et face
	à elle;
        Calculer la distance qui le sépare de cette dernière;

        Si la camera recule
           alors
               la faire tourner de - 180 degrés horizontalement
               pour qu'elle reprenne son sens initial;
        finsi

        Si la distance calculée est plus petite que celle dont
           on veut avancer
          alors
              Retourner Collision := VRAI;
          sinon
              Retourner Collision := FAUX
        finsi

        fin
\end{verbatim}
\caption{algorithme de collision en rendu 3D\label{Coll3D}}
\end{figure}


\includeps{collision.ps}{Principe d'évitement de collision en rendu 3D \label{Coll}}

\begin{figure}
\begin{verbatim}
     Commentaire : Ne pas perdre de l'esprit que la camera est
                   toujours perpendiculaire à son déplacement

     Début

     Commentaire : On fait en sorte que la caméra fasse face aux
                   obstacles potentiels

     Cas déplacement
        nord  : Tourner la camera de 90 degrés horizontalement;
        sud   : Tourner la camera de 90 degrés horizontalement;
        est   : Tourner la camera de 90 degrés horizontalement;
                Tourner la camera de 90 degrés latéralement;
        ouest : Tourner la camera de - 90 degrés horizontalement;
                Tourner la camera de - 90 degrés latéralement;
     finCas

     Trouver le polygone le plus proche de la camera et face à elle;
     Calculer la distance qui le sépare de cette dernière;
	
     Cas déplacement
        nord  : Tourner la camera de - 90 degrés horizontalement;
        sud   : Tourner la camera de - 90 degrés horizontalement;
        est   : Tourner la camera de - 90 degrés latéralement;
                Tourner la camera de - 90 degrés horizontalement;
        ouest : Tourner la camera de 90 degrés latéralement; 
                Tourner la camera de 90 degrés horizontalement;
     finCas

     Si la distance calculée est plus petite que celle dont on veut
        avancer,
        alors
            Retourner Collision := VRAI;			
        sinon
            Retourner Collision := FAUX
     finsi


        fin

\end{verbatim}
\caption{Algorithme d'évitement de collision en rendu 2D\label{Coll2D}}
\end{figure}

En ce qui concerne les autres algorithmes, il est interessant de voir celui qui
permet d'eviter que les caméras ne sortent du terrain qu'elles visualisent
(figure \ref{Sortie}).

\begin{figure}
\begin{verbatim}

     Début

        On récupère les points qui forment les deux angles inferieur 
         arrière et supèrieur avant de la boîte englobante du terrain 
         pour connaitre les limites de celui-ci.

        Cas Caméra
           Camera 2D :

             Si la distance qui sépare l'extrémité qu'atteint la
                caméra
                et
                que cette même distance  est plus petite que celle
                dont on veut se déplacer
               alors
                 On bloque la camera
               sinon
                  On effectue le déplacement
             Finsi

           Caméra 3D :

             On duplique la Caméra, on effectue le déplacement désiré,
             Si plus rien n'est en dessous de ce clône, on est sorti
               alors
                   On est sorti, la Camera 3D restera immobile
	       sinon
                   On effectue le déplacement
	     Finsi

     fin

\end{verbatim}
\caption{Test de débordement du terrain visualisé\label{Sortie}}
\end{figure}

Il est toutefois évident qu'il est nécessaire pour mener a bien un déplacement
de caméra que les deux algorithmes, collision et sortie de terrain soit
combinés pour obtenir un résultat cohérent. L'organigramme des decisions de la
figure \ref{Organi} présente ce type de liaisons.

\includeps{organigramme.ps}{Organigramme des décisions prises lors d'un ordre
de déplacement \label{Organi}}

\subsection{Problèmes rencontrés et Solutions choisies}

Malheureusement, \RW impose pour implémenter ces types de tests des
contraintes incontournables. La première est évidemment : comment se repérer
dans le monde vis-à-vis des objets environnants. Cette librairie graphique
offre deux fonctions permettant de le faire, mais de prime abord, une seule a
été suffisante : RwPickScene. D'un clic sur un des polygones de la scène
affichée par une caméra, on récupère un grand nombre de caractéristiques
correspondantes (par exemple, le polygone en question, mais aussi le vertex le plus proche, la distance qui le sépare du clic...).
Un paradoxe apparait alors. Avant de l'ennoncer, voyons une donnée imposée non
pas par \RW, cette fois-ci, mais par toutes les librairies graphiques
qui disposent de caméras. Pour afficher, on définit des plans de clipping (un
"far" ainsi qu'un "near") qui sont, en résumé, les distances entre lesquelles
la caméra est capable de distinguer des objets. Cependant, et ceci est à
imputer à la version 1.3 de \RW, il n'est possible de fixer que la
distance à partir de laquelle la caméra n'est plus "aveugle". A ajouter à cela,
il apparait que dans cette même version, nous soyons contraints d'être légèrement astygmate. En effet, il est impossible de préciser que l'on veut repérer tout ce qui est à proximité immédiate.
Voici donc notre paradoxe : Comment savoir que l'on est trop près d'une paroi si l'on ne voit pas cette même paroi.
Lors de déplacements rectilignes, ceci ne pose pas de problèmes (figure
\ref{Coll}), puisqu'avant d'avancer, on cherche à savoir si l'on n'atterrira
pas trop près ou au delà du décor. Cependant, si il vient à l'utilisateur
l'idée de s'arrêter , cette fois-ci, rien ne garanti que s'il fait tourner la
caméra, elle ne se retrouvera pas nez collé au sol, ou en se placant au niveau
des plans de clipping avec une distance objectif-sol plus petite que la valeur
minimale autorisée par la caméra.

Pour régler ceci, il aurait été possible de maintenir les mouvements à une
distance minimale et suffisante du sol. Inconvénient alors, obtenir des
écartements trop grands, éloignant de la réalité.

Une autre solution possible, et c'est celle que nous avons retenu, est de
tester une collision de déplacement même lors des rotations statiques. Si un
point qui n'est pas directement sous la caméra est déja trop près, celui qui y
est l'est encore plus. La caméra prend alors un mouvement de balancier arrière
plus proche, selon nous, de la réalité(figure \ref{RotColl}).
\includeps{organigramme.ps}{Mouvement de balancier lors de rotations statiques\label{RotColl}}

Dans le cas de la caméra d'édition, le problème ne se pose pas, les déplacements sont uniquement transversaux et sans rotation.

Un dernier problème directement raccroché au mouvement est : quand faut-il
s'arrêter ? Nous avons décidé d'empêcher que l'on puisse sortir du terrain que l'on visualise. A cet effet, les approches on été différentes. La caméra 2D, de
par son orthogonalité permanente avec le sol, ne pose pas de problème,
puisqu'il suffit de tester sa position par rapport aux limites du relief. La
difficulté apparait avec la caméra de rendu 3D. Comment se repérer par rapport
aux bords. Là encore, une solution envisagée, et c'est celle pour laquelle nous
avons opté, est de se repérer vis-à-vis du sol immédiatement au dessous. On duplique cette caméra en une autre, "cobaye" , on lui fait effectuer le déplacement prévu (avec test de collision, bien-sûr) et on teste si à l'arrivée, elle ne se trouve pas dans le vide. Dans ce cas, on ne fait rien, sinon, rien n'empêche d'avancer.

