M1 – ASDSI

Cf. http://moodle.univ-tlse3.fr/course/view.php?id=1571

Algorithmique des Structures de Données en Synthèse d’images

Implémentation d’un lancer de rayon

En reprenant la base de code développée en IG3D, vous allez implémenter un algorithme de lancer de rayons.

Implémentez un loader de maillages basique (sources et explications sur www.learnopengl.com). Attention, le chargement de la matrice « local vers monde » a été oublié dans le tutoriel.

Définissez les paramètres de la caméra :

  • Position 3D
  • Repère orthonormé : direction, right et up
  • Ouverture horizontale (fov)
  • Format d’image (ratio w/h)
  • Dimensions de l’image : l_max et h_max

Calculez la taille de l’image dans le repère monde :

  • largeur = 2 * tan(0.5 * fov)
  • hauteur = largeur / format d’image

Calculez, pour chaque pixel (i,j), la direction du rayon à lancer : 

Algorithme de raytracing général :

Pour chaque pixel(i,j), 
    Initialiser le rayon r d'origine o et de direction d
    Pour chaque objet de la scène
        Calculer l'intersection entre r et l'objet
        Garder l'objet le plus proche
    FPour
    pixel(i,j) = Calculer l'éclairage pour l'objet intersecté
FPour

Calcul d’intersection rayon / triangle : Lien
Calcul d’intersection en tout genre : Lien

Ajoutez un raccourci clavier pour alterner entre le rendu OpenGL et le rendu raytracer. Pour l’afficher, le rendu raytracer peut écrire dans un bloc mémoire, utilisé comme texture d’entrée d’un rendu OpenGL qui se contente d’afficher la texture sur l’écran.

Accélération par boites englobantes

Les boites englobantes (bounding box = bbox) sont des boites de dimension quelconque définissant un volume minimal comprenant un ensemble de données à n-dimensions.
Dans notre cas, nous nous intéressons à des boites à 3-dimensions permettant de regrouper des sommets géométriques.

Nous allons utiliser des boites englobantes alignées avec les axes (axis-aligned bounding box = aabb).
Vous pouvez utiliser les AABB d’Eigen (Eigen::AlignedBox), ou reprendre le code du minimalRenderer (sur Moodle), ou bien même les coder.
Le principe est assez simple. Il faut stocker (au minimum) deux points représentatifs de la boite. Ces deux points définissent un pavé droit (parallélépipède rectangle) et sont calculés ainsi :

  • p_min = (x_min, y_min, z_min), dont les 3 coordonnées sont les minimaux des données englobées
  • p_max = (x_max, y_max, z_max), dont les 3 coordonnées sont les maximaux des données englobées

Ensuite, pour chaque objet à afficher, avant de tester l’intersection avec chacun de ses triangles, on teste d’abord l’intersection avec sa boite englobante.
Si l’intersection est valide, on teste l’intersection avec les triangles. Sinon, on invalide directement l’objet.
Cela permet de simplement supprimer des tests inutiles.

Le calcul d’intersection rayon/aabb peut se trouver ici : Lien

Les boites englobantes peuvent être hiérarchisées, en ayant une bbox pour la géométrie totale, puis des sous-bbox pour des géométries plus petites, etc.

Accélération par kd-tree