IRT : un ray tracer interactif - Partie 4

Matthieu Brucher

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.

Commentez

- Titre : IRT : un ray tracer interactif - Partie 4

- Auteur : Matthieu Brucher

- Parution : 17 juin 2009

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

Sommaire

- I. Objectifs

- II. Utilisation d'une Bounding Box

- III. Suréchantillonnage

- III-A. Echantillonage uniforme

- III-B. Echantillonage aléatoire

- III-C. Echantillonage jittered

- III-D. Echantillonage n-rooks

- III-E. Echantillonage multi-jittered

- III-F. Comparaison

- III-G. Implémentation

- IV. Résultats

- V. Conclusion

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

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

sphere.cpp

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

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

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

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

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 originale

Zoom sur l'image, permettant de visualiser le crênelage

Image suréchantillonnée (2,2)

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 :

Echantillonnage uniforme (4,4)

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

Oversampling (2,2)

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.

Echantillonnage aléatoire (4,4)

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

Oversampling (2,2)

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.

Echantillonnage jittered (4,4)

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

Oversampling (2,2)

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.

Placement d'un échantillon dans les cases diagonales

Permutation selon ligne ou colonne

Oversampling (2,2)

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.

Placement d'un échantillon par sous-case

Permutation selon les lignes et les colonnes

Oversampling (2,2)

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.

Comparaison des différentes techniques pour un oversampling (2,2)

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