MPIL(3I008)
Anne 2016/2017
Mini-projet : lancer
de rayons partie 2
Objectifs
1. Chargement dune scne
2. Plus dobjets
3. Parcours darbre
4. Plus de phnomnes physiques
Plusieurs questions ou exercices sont facultatifs mais per-
mettent dobtenir un bonus de points.
Exercice 1 : Chargement dune scne
Au lieu de dcrire vos scnes en OCaml, et davoir recom-
piler chaque changement de scne, il est plus pratique de
dfinir ses scnes dans un fichier et de lancer le programme
dessus.
Nous allons utiliser le format (trs simple) suivant :
Chaque ligne correspond un lment de la scne
Les lments peuvent tre une camra, un objet, un ma-
terial, une lumire.
Chaque ligne commence par un mot cl qui indique ll-
ment, suivi de paramtres pour prciser cet lment.
Les lments sont :
camera x0 y0 z0 xA yA zA alpha width height o (x0, y0, z0) est
lorigine de la camra, x1, yA, zA est le point de vise,
alpha le champ de vision, width et height les dimensions de
la fentre de rendu.
material name r g b ka kd ks alpha o name est le nom du ma-
terial, (r, g, b) est sa couleur, (ka, kd, ks) les coefficients
pour lillumination ambiante, diffuse, et spculaire, et
alpha, lexposant dans le modle de Blinn-Phong.
sphere xC yC zC radius material o (xC, yC, zC) est le centre
de la sphre, radius le rayon, material le nom du material
appliquer sur la sphre.
light x y z r g b i o (x, y, z) est la direction de la lumire
distante, (r, g, b) est la couleur de la lumire, et i est son
intensit.
Q.1.1 Un module OCaml vous est fourni pour parser de tels
fichiers de description de scne ladresse https://drive.
google.com/file/d/0BzuP8lg-Dqt6R1JTSndzbnNrelE.
Adaptez le module vos propres types et fonction pour
manipuler les vecteurs et les lments de la scne.
Faire en sorte que votre lanceur de rayon puisse tre appel
en ligne de commande avec un fichier de description de scne
en argument.
Q.1.2 Tester votre lanceur de rayon sur la description de
scne suivante :
camera 0. 0. 0. 0. 0. 5. 2.0943951 700 500
material sphereMat 255 0 0 1. 0.6 0.7 10.
sphere 1. 1. 5. 0.4 sphereMat
light -10. -30. 20. 255 255 255 0.1
Q.1.3 Facultatif crire une fonction pour sauvegarder une
scne dans un fichier dans le format dcrit ci-dessus.
Exercice 2 : Plus dobjets
Q.2.1 Dans cette question, nous rajoutons les plans comme
objets possibles afficher (on rappelle quon na que les
sphres pour linstant). Un plan est dfini par un point p0 sur
le plan et un vecteur normal 1 au plan ~p. crire le type plane.
Ainsi, tout point P sur le plan vrifie lquation suivante :
p0P ~p = 0
Intersection Lquation paramtrique dun rayon (voir
partie 1) est :
P = O + t~v
do (O + t~v p0) ~p = 0 et donc :
t =
(p0 O) ~p
~v ~p
Un rayon a donc une intersection avec le plan si le dnomina-
teur est non nul, cest–dire si ~v ~p 6= 0, en dautres termes,
si le rayon et le plan sont parallles. Par ailleurs, il faut aussi
vrifier que t 0. Dans le cas contraire, cela signifie que le
plan se trouve derrire la camra.
Ajouter une fonction (ou une mthode) intersect pour le
plan.
Q.2.2 Rajouter le triangle comme objet reprsentable dans
notre lanceur de rayon. Le triangle est un objet qui est trs
utile quand il est agrg avec dautres triangles pour former
des objets complexes. Un triangle est dfini par trois points.
crire son type.
Intersection Pour vrifier lintersection entre un rayon
et un triangle, nous allons utiliser lalgorithme de Mller-
Trumbore. On suppose que le triangle a pour sommets,
v0, v1, v2. Le rayon a pour direction ~d et comme origine O.
On calcule le produit mixte :
m = (~d v0v2) v0v1
Si m = 0 alors il ny a pas intersection.
Sinon, on calcule :
u =
v0O (~d v0v2)
m
Si u < 0 ou u > 1 alors il ny a pas intersection.
Sinon on calcule :
v =
~d (
v0O v0v1)
m
Si v < 0 ou u+ v > 1, alors il ny a pas intersection.
Sinon, il y a bien intersection et la distance lorigine est :
t =
v0v2 (
v0O v0v1)
m
crire intersect pour un triangle.
Q.2.3 Facultatif. Les objets disponibles pour linstant
rendent difficile le rendu dune scne complexe, avec des ob-
jets qui auraient des formes gomtriques arbitraires, par
1. Perpendiculaire.
1
https://drive.google.com/file/d/0BzuP8lg-Dqt6R1JTSndzbnNrelE
https://drive.google.com/file/d/0BzuP8lg-Dqt6R1JTSndzbnNrelE
exemple issus dun logiciel de modlisation 3D comme Blen-
der. Rajouter une gestion basique du format Wavefront Obj.
Une faon de faire est dinterfacer avec OCaml une biblio-
thque C, tinyobjloader-c pour charger les .obj : https:
//github.com/syoyo/tinyobjloader-c
Une autre faon est de parser un sous-ensemble du format
.obj, par exemple, seulement la dfinition des sommets et des
faces. Le format .obj est un format textuel simple parser,
o chaque lment est dfini ligne par ligne. Les faces dun
.obj sont triangulaires.
#Un commentaire
# Un sommet de cordonnes (2.3, 4.5, 10)
v 2.3 4.5 10
v 1.0 0.34 0.5
v 0.34 -0.3 -2.456
# Une face, compose des artes dfinies
# en premier, en deuxime, et en troisime
f 1 2 3
Vous devez pouvoir charger un sous-ensemble de ce format,
crire un type ou une classe pour le reprsenter, et ajouter
une fonction (ou mthode) intersect qui vrifie lintersection
entre un tel objet et un rayon.
Q.2.4 Facultatif. Ajouter la gestion des plans, des triangles,
et des Wavefront obj, dans notre format de description de
scne.
Exercice 3 : Parcours darbre
Parmi les nombreuses optimisations existantes dun lanceur
de rayon, on trouve lutilisation dune structure visant orga-
niser les objets de la scne intersecter. Nous allons appliquer
pour cette question une version simple du kd-tree [2, 3, 4] pour
optimiser le rendu dune scne lorsque le nombre dobjet pr-
sent devient consquent.
Lide simple est illustre sur limage 1 et consiste sparer
lespace dune scne en k plans et ainsi entourer ses objets par
des boites reprsentant les bornes min/max des coordonnes
dun objet. Ainsi, si un rayon nintersecte pas cette boite alors
le ou les objets contenus dans cette boite ne sont pas intersec-
ts. Cette structure ajoute galement une notion de distance
et le premier objet ayant t intersect est le plus proche de
lorigine du rayon (les autres objets pouvant tre intersects
aprs ne seront donc pas calculs).
Q.3.1 Avant de commencer, il faut dfinir quelques types
et interfaces (.mli) pour pouvoir manipuler notre kd-tree sans
contraindre les objets dj dfinis dans votre projet. Remar-
quer quun kdtree est un objet (ou forme)comme une sphre
et doit donc prsenter la mme interface objet. Lcrire ou
la complter avec les fonctions :
intersect, tant la fonction dintersection code dans
la phase 1 du projet,
min, retournant la valeur du point minimal de la forme
max, retournant la valeur du point maximal de la forme
Ainsi, nous avons le point minimum et maximum dune
forme.
Q.3.2 Un kd-tree est un simple arbre binaire, son type est
un objet et ses nuds sont soit une feuille (une liste de ob-
jets), soit un nud intermdiaire reprsent par une boite
limitant la zone contenue par ses deux sous arbres. Pour
cela notre boite limitante doit avoir deux points (ses deux
points extrmes c1 et c2). Dfinissez les types kd-tree et
cut c2c1
y
x mdmg
cut
Figure 1 Phase de construction dun kd-tree (reprsente
par le premier point de dcoupe cut et les bornes du plan c1
c2 projetes sur laxe des x). La phase suivante est reprsente
uniquement par son point de dcoupe cut et son mdian.
boitelimite.
Q.3.3 (construction) Pour construire un kd-tree partir
dune scne (une liste de formes pour tre prcis), il faut consi-
drer la notion de projection. En effet, chaque dcoupage est
calcul sur un certain axe et chang pour ltape suivante, ceci
permet dobtenir des plans aligns simplifiant les calculs et la
structure de larbre. Pour ce projet nous allons projeter nos
calculs sur la suite daxes x, y, z, x, y, z . . . qui est la stratgie
gnralement utilise. La construction dun arbre ce fait donc
suivant ces tapes :
decoupe, pour un plan courant (c1-c2) le point mdian
est calcul selon laxe courant (le point cut sur limage 1)
rpartition, la liste des objets restants trier est s-
pare en deux listes :
lgauche, la liste o le point minimum dun objet est
plus petit que le mdian (i.e. les objets se trouvant
gauche du milieu du plan)
ldroit, la liste o le point maximum dun objet est
plus grand que le mdian (i.e. les objets se trouvant
droite du milieu du plan)
Il peut y avoir bien videmment le mme objet dans les
deux listes si le mdian coupe cet objet en deux, notez
que cette tape calcule galement maxgauche (mg) et
mindroit (md) le point maximum des objets de gauche
(sans que ce soit plus grand que le mdian) et inverse-
ment le point minimum des objets de droite
boucle, finalement la fonction se rappelle pour chaque
ct si la profondeur k nest pas atteinte et si la taille
de la sous-liste de objets est suprieure 1. Lappel
incrmente la profondeur k, change laxe de projection
et sapplique sur une des sous listes avec la nouvelle
boite limitante construit ainsi :
(c1, maxgauche) pour celle de gauche et
(mindroit, c2) pour celle de droite.
Q.3.4 (parcours) Pendant le lancement de rayon, le kd-tree
va devoir tre travers selon lorigine du rayon et jusqu ce
quune feuille de larbre soit rencontre ou que la boite limite
soit traverse. Limage 2 rsume les diffrentes possibilits.
Cette traverse deux initialisions distinctes selon si lorigine
2
https://github.com/syoyo/tinyobjloader-c
https://github.com/syoyo/tinyobjloader-c
Figure 2 Un rayon au travers dune boite limitante.
du rayon est dans ou hors du plan. Les tapes dune traverse
sont les suivantes :
le point dentre (A) est calcul et est soit lorigine (si
le rayon part dans le plan) ou lintersection du rayon et
de la boite racine.
selon si ce point dentre est plus petit ou plus grand que
le mdian dune boite, le parcours entre dans les noeuds
gauche ou droite du kd-tree. Ceci jusqu atteindre une
feuille.
Si cette feuille contient des objets alors lintersection est
calcule avec toutes ses objets.
Si il y a une intersection (dans le plan courant) alors le
parcours termine pour ce rayon et le reste de la fonction
peut sappliquer (illumination)
Si il ny a pas de objets, pas dintersection ou que cette
intersection nest pas dans le plan courant, alors le point
de sortie (B) est calcul.
Le parcours continue avec comme point dentre le nou-
veau point B.
Finalement si le point de point de sortie est calcul pour
le plan racine alors le rayon nintersecte aucun objet.
Q.3.5 Comparer le temp de rendu avec kd-tree et sans kd-tree
pour la scne de la fin de la partie 1.
Exercice 4 : Plus de phnomnes physiques
Cette partie est facultative. Nous allons ajouter deux ph-
nomnes physiques courants : la rflexion (miroir) et la r-
fraction (comme pour de leau).
Q.4.1 Chaque matriau possde un coefficient de rflexion
r, qui est la quantit de lumire quil va renvoyer. Un ma-
triau non rflchissant a donc un coefficient valant 0. Aug-
menter le type material avec r.
Le rayon rflchi ~R est renvoy par rapport la normale ~N
au point incident, avec le mme angle que le rayon incident
~I, comme montr sur la Fig. 3.
Le rayon rflchi ~R est donc donn par lquation suivante :
~R = ~I 2( ~N ~I) ~N
A
~N
~I~R
Figure 3 Le rayon incident de direction ~I est rflchi par
rapport la normale ~N . Le rayon rflchi est ~R. Les angles
incidents et rflchis sont gaux.
Ce que lon voit dans la surface rflchissante dpend du
point de vue : dplacez-vous devant un miroir ; vous ne verrez
pas la mme chose. On va donc envoyer un nouveau rayon
rcursivement ayant pour direction le rayon rflchi ~R, appel
aussi rayon spculaire. La couleur du point incident est alors
la couleur obtenue partir de ce rayon rflchi, multipli par
r 1. En cas de deux miroirs face face, le nombre dappels
rcursifs est potentiellement infini.
A chaque rflexion, lintensit de lumire rflchie diminue,
si r < 1. Dans ce cas, on peut stopper les appels rcursifsquand la quantit est sous un certain . On peut aussi limi-ter un nombre donn, 15 par exemple, le nombre dappelsrcursifs. Il faut se rendre compte que plus on autorise desappels rcursifs, plus le temps de rendu sera long.Ajouter la rflexion votre lanceur de rayons.Q.4.2 Quand un rayon passe dun milieu transparent unautre, le rayon est dvi, comme montr sur la Fig. 4. Ladviation dpend de lindice de rfraction du milieu, r. Leverre a typiquement un indice de 1.5, lair, de 1, et leau, de1.3. Ajouter dans le type material lindice de rfraction.~N~I~R~TFigure 4 Le rayon incident de direction ~I est rflchi parrapport la normale ~N . Le rayon rflchi est ~R. Le rayonrfract est ~T . Les angles incidents et rflchis sont gaux,alors que langle rfract est et suit les lois de Descartes.Les angles incident et rfract suivent la loi de Descartes :i sin = r sin On en dduit ~T . On pose c1 = ~N ~I etc1 =1 (ir)2 sin2()et on a :~T =ir~I (irc1 c2) ~N3Si le terme sous la racine dans c2 est ngatif, on a unerflexion totale, et pas de rfraction.Ajouter la rfraction au lanceur de rayons.*Rfrences[1] Pharr, Matt and Jakob, Wenzel and Humphreys, Greg,Physically based rendering : From theory to implementa-tion. Morgan Kaufmann, 3rd Edition, 2016[2] https://en.wikipedia.org/wiki/K-d_tree[3] https://www.scratchapixel.com/lessons/advanced-rendering/introduction-acceleration-structure/bounding-volume-hierarchy-BVH-part1[4] https://www.cs.unc.edu/~rademach/xroads-RT/RTarticle.html4https://en.wikipedia.org/wiki/K-d_treehttps://www.scratchapixel.com/lessons/advanced-rendering/introduction-acceleration-structure/bounding-volume-hierarchy-BVH-part1https://www.scratchapixel.com/lessons/advanced-rendering/introduction-acceleration-structure/bounding-volume-hierarchy-BVH-part1https://www.scratchapixel.com/lessons/advanced-rendering/introduction-acceleration-structure/bounding-volume-hierarchy-BVH-part1https://www.scratchapixel.com/lessons/advanced-rendering/introduction-acceleration-structure/bounding-volume-hierarchy-BVH-part1https://www.cs.unc.edu/~rademach/xroads-RT/RTarticle.htmlhttps://www.cs.unc.edu/~rademach/xroads-RT/RTarticle.html
Reviews
There are no reviews yet.