IRT : un ray tracer interactif - Partie 4

Niveau débutant/avancé

Quatrième partie de la série de tutoriels dédiée au raytracing (voir ici pour la table des matières).

Suréchantillonnage et bounding box.

14 commentaires Donner une note à l'article (5)

Article lu   fois.

L'auteur

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

I. Objectifs

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)

II. Utilisation d'une Bounding Box

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 :

bounding_box.h
Sélectionnez

  struct BoundingBox
  {
    /// coin droit
    Point3df corner1;
    /// coin gauche
    Point3df corner2;
  };
sphere.cpp
Sélectionnez

  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 :

simple_scene.cpp
Sélectionnez

  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).

simple_scene.cpp
Sélectionnez

  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.

raytracer.cpp
Sélectionnez

  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;
      }
    }
  }
bounding_box.h
Sélectionnez

    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.

III. Suréchantillonnage

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.

Image non disponible
Image originale
Image non disponible
Zoom sur l'image, permettant de visualiser le crênelage
Image non disponible
Image suréchantillonnée (2,2)
Image non disponible
Zoom sur l'image

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 :

Image non disponible
Echantillonnage uniforme (4,4)

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

Image non disponible
Oversampling (2,2)
Image non disponible
Oversampling (4,4)

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.

Image non disponible
Echantillonnage aléatoire (4,4)

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

Image non disponible
Oversampling (2,2)
Image non disponible
Oversampling (4,4)

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.

Image non disponible
Echantillonnage jittered (4,4)

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

Image non disponible
Oversampling (2,2)
Image non disponible
Oversampling (4,4)

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.

Image non disponible
Placement d'un échantillon dans les cases diagonales
Image non disponible
Permutation selon ligne ou colonne
Image non disponible
Oversampling (2,2)
Image non disponible
Oversampling (4,4)

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.

Image non disponible
Placement d'un échantillon par sous-case
Image non disponible
Permutation selon les lignes et les colonnes
Image non disponible
Oversampling (2,2)
Image non disponible
Oversampling (4,4)

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.

Image non disponible
Comparaison des différentes techniques pour un oversampling (2,2)
Image non disponible
Comparaison des différentes techniques pour un oversampling (4,4)

III-G. Implémentation

L'implémentation a été effectuée à l'aide de templates C++. Le raytracer est devenu une structure template où le paramètre est le type de sampler à utiliser.

Dans la méthode draw(), au lieu d'appeler directement computeColor(), on passe par le sampler (instantié comme une variable de la structure) qui possède lui aussi cette méthode. Dans cette méthode, on parcourt les différents échantillons vus précédemment pour créer plusieurs rayons, et la couleur résultante sera la couleur moyenne de ces différents rayons.

Pour les détails de chaque sampler, je vous invite à regarder le code source sur Launchpad.

D'autres méthodes d'échantillonnage existent, comme la méthode Quasi Monte Carlo.

IV. Résultats

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).

V. Conclusion

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

Références

IRT, un ray tracer interactif
1. Introduction
2. Reflets
3. GUI
4. Oversampling et BoundingBox
5. Kd-tree
  

Copyright © 2008 Matthieu Brucher. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.