Maintenant qu'il est possible de créer une scène simple, il est nécessaire d'améliorer sa qualité et de l'accélérer. Pour cela, il va falloir :

• lancer plusieurs rayons pour un seul pixel de l'image,
• ne lancer un rayon que sur la zone utile (définie par la BoundingBox de la scène)

Chaque objet occupe une certaine place dans la scène. En les conjuguant, il est possible d'obtenir la taille globale de la scène. Pour cela, on va ajouter aux primitives de retourner leur BoundingBox :

  struct BoundingBox
  {
    /// coin droit
    Point3df corner1;
    /// coin gauche
    Point3df corner2;
  };

  BoundingBox Sphere::getBoundingBox() const
  {
    BoundingBox bb;
    
    bb.corner1 = center - radius;
    bb.corner2 = center + radius;
    
    return bb;
  }

Maintenant, il est possible de modifier le code d'ajout d'une primitive, avec bb la BoundingBox propre à la scène :

  SimpleScene::SimpleScene()
    :primitives(), lights()
  {
    bb.corner1 = std::numeric_limits<float>::max();
    bb.corner2 = std::numeric_limits<float>::min();
  }

  unsigned long SimpleScene::addPrimitive(Primitive* primitive)
  {
    if(std::find(primitives.begin(), primitives.end(), primitive) != primitives.end())
      throw std::out_of_range("Primitive already added");

    BoundingBox primitive_bb = primitive->getBoundingBox();
    min(bb.corner1, primitive_bb.corner1);
    max(bb.corner2, primitive_bb.corner2);

    primitives.push_back(primitive);
    return primitives.size() - 1;
  }

Dans le cas présent, les fonctions min et max ont été modifiées pour permettre de calculer le vecteur minimum ou maximum de deux vecteurs.

On ajoute aussi la possibilité de recalculer la BoundingBox (même si cela ne sera pas forcément utilisé tout de suite).

  const BoundingBox& SimpleScene::getBoundingBox() const
  {
    return bb;
  }
  
  void SimpleScene::computeBoundingBox()
  {
    std::vector<Primitive*>::iterator it = primitives.begin();
    bb = (*it)->getBoundingBox();
    
    for(++it; it != primitives.end(); ++it)
    {
      BoundingBox bb_bis = (*it)->getBoundingBox();
      min(bb.corner1, bb_bis.corner1);
      max(bb.corner2, bb_bis.corner2);
    }
    
    return;
  }

Maintenant, cette BoundingBox permet de savoir si un rayon doit être tiré ou non. Pour cela, une fonction spécifique mustShoot() va être développée, et elle appelera une nouvelle méthode de la BoundngBox.

  bool Raytracer::mustShoot(const Ray& ray, const BoundingBox& bb) const
  {
  	for ( int i = 0; i < 3; ++i )
    {
      if (ray.direction()(i) < 0) 
	    {
		    if (ray.origin()(i) < bb.corner1(i))
        {
          return false;
        }
      }
    	else if (ray.origin()(i) > bb.corner2(i))
      {
        return false;
      }
    }
  }

    bool getEntryExitDistances(const Ray& ray, DataType& tnear, DataType& tfar) const
    {
      tfar = std::numeric_limits<float>::max();
      tnear = std::numeric_limits<float>::epsilon();
      for(int i = 0; i < 3; ++i)
      {
        float pos = ray.origin()(i) + tfar * ray.direction()(i);
        float pos_near = ray.origin()(i) + tnear * ray.direction()(i);
        if(ray.direction()(i) < 0)
        {
          if(pos < corner1(i))
          {
            tfar = (corner1(i) - ray.origin()(i)) / ray.direction()(i);
          }
          else if(pos > corner2(i))
          {
            tfar = std::numeric_limits<float>::epsilon();
          }
          if(pos_near > corner2(i))
          {
            tnear = (corner2(i) - ray.origin()(i)) / ray.direction()(i);
          }
          else if(pos_near < corner1(i))
          {
            tnear = std::numeric_limits<float>::max();
          }
        }
        else if (ray.direction()(i) > 0)
        {
          if(pos > corner2(i))
          {
            tfar = (corner2(i) - ray.origin()(i)) / ray.direction()(i);
          }
          else if(pos < corner1(i))
          {
            tfar = std::numeric_limits<float>::epsilon();
          }
          if(pos_near < corner1(i))
          {
            tnear = (corner1(i) - ray.origin()(i)) / ray.direction()(i);
          }
          else if(pos_near > corner2(i))
          {
            tnear = std::numeric_limits<float>::max();
          }
        }
        
        if (tnear > tfar)
        {
          return false;
        }
      }

      return true;
    }

Avec cette BoundingBox, il va être possible d'implémenter une primitive de type parallélépipède droit, aligné sur les axes. Cela va permettre d'ajouter un peu de diversité dans les scènes.

Un rayon unique échantillonne l'image en un point. En revanche, l'oeil humain ne fonctionne pas comme ça. Il moyenne l'information reçue sur une surface en un seul "pixel" qui sera envoyé au cerveau. L'objectif du suréchantillonnage est de permettre d'approcher ce moyennage sur la surface, en approchant l'intégrale de tous les rayons possibles par la somme de quelques uns.

L'impression donnée pour un seul rayon est un crênelage, aussi appelé aliasing. En fait, cet effet est dû à un échantillonnage trop faible par rapport à la fréquence maximale de l'image, qui est infinie dans le cas d'une image réelle. L'effet est d'autant plus visible sur une image avec beaucoup de détails.

III-A. Echantillonage uniforme▲

L'échantillonnage uniforme est la première méthode présentée. Au lieu de travailler sur une image de taille (w, h), on travaille sur une image de taille plus importante (m*w, n*h), puis chaque bloc de taille (m, n) sera moyenné en un seul pixel.

Logiquement, la performance est divisée par m*n, en revanche l'image devient plus naturelle.

Au lieu de n'envoyer qu'un seul rayon sur une maille, on va en envoyer plusieurs comme indiqué dans la figure suivante :

Les résultats pour un facteur 2 et un facteur 4 sont les suivants :

Un oversampling faible améliore le résultat, mais le crênelage reste visible. Avec un oversampling plus important, l'effet disparaît.

III-B. Echantillonage aléatoire▲

L'oversampling uniforme a l'avantage de la facilité, mais cela n'empêche qu'il reste un aliasing. On va maintenant envisager d'autres méthodes d'échantillonnage, donc l'échantillonnage aléatoire.

Le premier example sera de choisir un certain nombre de points au hasard autour du rayon central.

Les résultats pour un facteur 2 et un facteur 4 sont les suivants :

L'inconvénient de cette solution est qu'il est possible que les points tirés aléatoirement laissent de grosses surfaces vides, comme c'est le cas dans l'image précédente, ce qui veut dire que des détails peuvent être manqués.

III-C. Echantillonage jittered▲

Pour pallier cet inconvénient, on va repartir sur l'échantillonnage uniforme, mais cette-fois-ci, on va tirer un point dans chaque sous-case.

Les résultats pour un facteur 2 et un facteur 4 sont les suivants :

III-D. Echantillonage n-rooks▲

L'échantillonnage précédent est très performant. En revanche, si on regarde ce qui se passe sur une dimension, on se rend compte que la répartition n'est pas idéale. En effet, on peut obtenir des trous, tout comme c'était le cas en 2D.

Pour résoudre ce problème, on va découper les deux dimensions en n morceaux et on va placer un échantillon au hasard dans les cases diagonales. Par la suite, on effectue une permutation des lignes. On obtiendra toujours sur chaque ligne et colonne un échantillon par case. En revanche, on va retrouver des trous en 2D.

III-E. Echantillonage multi-jittered▲

Ce mode d'échantillonnage reprend les avantages des deux méthodes précédentes. Un échantillon par ligne ou colonne, mais aussi un échantillon par case en 2D.

Le résultat, tout comme pour le cas précédent, ne peut pas se différencier dans ce cas précis d'un échantillonnage jittered. Leurs avantages sont surtout importants s'il est nécessaire d'utiliser un échantillonneur de même type sur des lumières ou des ombres, ce qui n'est pas fait pour le moment.

III-F. Comparaison▲

Voici deux images regroupant les comparaisons. De gauche à droite, on a l'échantillonnage uniforme, puis aléatoire, jittered, n-rooks et multi-jittered.

III-G. Implémentation▲

Comme prévu, le suréchantillonnage ralentit la construction de l'image. On constate aussi qu'à partir d'un échantillonnage jittered, les résultats semblent visuellement meilleurs. Le surcoût d'utilisation d'un système plus complexe que l'échantillonnage uniforme est faible et donc ces échantillonnages peuvent être envisagés. En revanche, pour chaque pixel, on utilise la même répartition. Il est possible de complexifier les échantillonneurs pour générer à chaque appel de nouveaux échantillons.

En ce qui concerne la BoundingBox, les résultats sont flagrants dans le cas test. Il est clair que si l'oeil se situe dans la scène, ces tests auront un impact négatif. Dans le cas de la scène des précédents tutoriels, avec 3 sphères et 3 lumières, on gagne 10% de temps de calcul sous Windows (.5 s à .45 s).

Maintenant que le concept de BoundingBox a été introduit, et vu la perte de vitesse, il est intéressant de tester des structures accélératrices.

Il est aussi à noter que selon les cas (i.e. selon le découpage des fonctions, ou simplement le fait de retourner une variable par référence constante, même si cela ne se produit qu'une seule fois pendant un calcul), le compilateur de Microsoft peut s'emmêler les pinceaux. Dans les meilleurs cas, la vitesse d'exécution passe sous la seconde. Les raisons exactes de ce comportement me sont inconnues...