-------------------------------------------
Comment faire des tunnels à direction libre
par  BlackAxe / KoLOr 1997
traduction par Starman (codefr@planet-d.net) (cdf par klang :)
-------------------------------------------

Dans les toutes dernières demos (en particulier dans presque chaque demo
de l'assembly 97) vous pouvez voir des tunnels 'Free direction'. C'est à
dire des tunnels dans lesquels vous pouvez bouger là où vous voulez
et faire des mouvement complexes de camera.
Pas mal de peuple sur IRC m'ont demandé comment faire de tels tunnels,
alors au lieu de gaspiller mon temps et mon argent à expliquer ça
online ,j'ai decidé d'écrire ce petit tutorial.
En fait cet effet est assez facile à faire mais il ne marche pas avec
des tables de precalcul mais plutôt avec du raycasting en temps réel.
Raycasting en temps réel ??! Mais n'est-ce pas lent ?? Non il y a quelques
trucs à savoir pour que ce soit rapide. Commençons par une petite
introduction sur le Raycasting.

1) Les bases du Raycasting
--------------------------

En fait le Raycasting est un algorithme très simple mais un bon nombre de personnes
pense que c'est très compliqué.. Cependant les bases sont tout de même assez simples pour ceux
qui ont un minimum de connaissances en maths.

La base de cette algo consiste à lancer un rayon à travers chaque pixel de l'écran
et de regarder les intersections entre le rayon et les objets de la scène.
Commençons par l'équation d'un rayon. Un rayon est défini par :
      Origine+p*direction

      où origine est le vecteur de la camera et direction est un vecteur normalisé de direction.
      p est un nombre indiquant une position sur le rayon.

Maintenant, pour lancer un rayon à travers un pixel on fait: (considérons que la camera soit a (0,0,-256) )
      Origine.x = 0;
      Origine.y = 0;
      Origine.z = -128;

Maintenant nous tirons le rayon à travers ce pixel:
      Direction.x = Pixel.X;
      Direction.y = Pixel.Y;
      Direction.z = 128;
      Direction.Normalize();

Bien sûr vous pouvez prendre une valeur différente pour z :)

Note: Le pixel du milieu doit être à (0,0) donc si vous etes en 320x200,
vous devez soustraire 160 de X et 100 de Y.

Voici maintenant comment normaliser un Vecteur :

void Vector::Normalize()
{
  float norme = sqrt(x*x + y*y + z*z);
  x /= norme;
  y /= norme;
  z /= norme;
}

Maintenant vous avez votre rayon et vous devez vérifier les intersections.
Pour cela vous devez les trouver.
On a : Intersection = Origin + p*Direction
Intersection représente un vecteur .

2) Appliquer un Raycasting a un tunnel
--------------------------------------

Donc qu'est-ce qu'un tunnel ? Un tunnel est un cylindre :)
Mais qu'est-ce qu'un cylindre ? C'est un ensemble de cercles concentriques.
A chaque Z correspond un cercle . Maintenant nous devons trouver
l'intersection entre notre rayon et le bon cercle.

Rappelons tout d'abord l'équation d'un cercle:
      (x-a)^2 + (y-b)^2 = r^2

      où (a,b) est le centre du cercle et r son rayon.

En supposant que le centre soit en (0,0) on a donc : 
      x^2 + y^2 = r^2
Facile, non ?

Maintenant remplaçons x et y par l'équation de notre rayon.
On obtient:
      Origin.x^2 + 2*Origin.x*p*Direction.x + p^2*Direction.x^2 +
      Origin.y^2 + 2*Origin.y*p*Direction.y + p^2*Direction.y^2 = r^2

Et si l'on factorise cette expression on obtient:
      p^2*(Direction.x^2 + Direction.y^2) + p*2*(Origin.x*Direction.x + Origin.y*Direction.y) +
      Origin.x^2 + Origin.y^2 - r^2 = 0;

C'est à dire une banale équation du 2eme degré de type ax² + bx + c :
      a*p^2 + b*p + c = 0

où:   a = Direction.x^2 + Direction.y^2
      b = 2*(Origin.x*Direction.x + Origin.y*Direction.y)
      c = Origin.x^2 + Origin.y^2 - r^2

Résolvons alors cette équation:
D'apres nos cours de maths il faut d'abord calculer delta tel que:
      delta = b^2 - 4*a*c

.Si Delta < 0 il n'y a pas de solution réele et nous pouvons mettre la couleur du Background.
.Si delta = 0 il y a une seule solution:

           -b
      p = -----
           2*a

.Si delta > 0 il y a 2 solutions:

           -b - sqrt(delta)
      p1 = ----------------
                 2*a

           -b + sqrt(delta)
      p2 = ----------------
                 2*a

Nous sommes seulement intéressés par la plus petite de ces intersections donc nous faisons:
      p = min(p1, p2);

Maintenant nous avons notre intersection entre le rayon et le cylindre:
      Intersection = Origin + p*Direction

Il reste une chose à faire .. Texturer le tunnel, ce qui est simple !
En effet il suffit d'appliquer un mapping cylindrique au point d'intersection.

      u = abs(Intersection.z)*0.2;
      v = abs(atan2(Intersection.y, Intersection.x)*256/PI);

3) Déplacer la camera 
---------------------

Vous voulez déplacer votre camera bien sûr :) sinon ce ne serait pas un tunnel free direction ! ..
C'est facile, il faut changer les coordonnées du vecteur Origine et si vous
voulez la faire roter (hum ... effectuer une rotation :) faisez juste
une rotation du vecteur direction en utilisant une matrice.

4) Faire cela en temps réel 
---------------------------

J'entend déjà vos cris ..... c'est IMPOSSIBLE de faire cela en temps réel
car il faudrait lancer les rayons pour chaque pixel. Mais vous n'avez
pas besoin de le faire. En fait vous devez juste les lancer pour quelques
pixels et procéder ensuite à une interpolation. Je pense qu'une table
d'interpolation de 40x25 devrait suffire.