L'objectif de ce TD est de construire un lancer
de rayon minimaliste utilisant une représentation des objets par
arbre de construction. La réalisation pratique sera vraisemblablement
repartie sur plusieurs séances. Dans un premier temps, le lancer
de rayon se limitera à déterminer les parties visibles de la
scène (ray-casting). De même, afin de simplifier l'architecture
et de limiter la taille du programe, nous ne nous interresserons qu'à
quelques primitives élémentaires : sphère et demi-espace,
par exemple.
Plusieurs éléments doivent être
mis en place avant de pouvoir visualiser un arbre de construction :
un repère global
une caméra : un centre de projection et le type de projection
(orthographiqe, perspective, etc.)
une génération de rayons partant du centre de projection
et passant par la surface d'un pixel du plan de projection
des primitives géométriques : paramètres
et fonction d'intersection par un rayon
opérations booléennes sur les intersections avec
les primitives
élimination des faces cachées
éclairement
Les parties suivantes détaillent chaque étape.
Partie 1. Visualisation : repères, projection et génération
de rayons
La visualisation d'une scène peut se représenter
de manière générale par l'algorithme suivant :
positionner les objets dans un repère
décrire la projection dans le même repère
pour chaque pixel de l'image à calculer :
déterminer l'objet visible à travers ce pixel
déterminer la couleur de l'objet (et du pixel)
pour déterminer
quel objet est visible à travers un pixel :
déterminer la direction d'un rayon passant par le centre de
projection et par le centre du pixel
déterminer l'objet dont l'intersection avec le rayon est la
plus proche du centre de projection
Le plus simple est de définir un repère
local pour la caméra, c'est à dire que le centre de projection
se trouve en (0, 0, 0) et que la direction de visée est (0, 0, -1)
(même convention qu'openGL). Dans ce cas, la direction du rayon associé
au pixel ( i, j ) d'une image de dimensions (Nx, Ny) est simplement :
u( i )= Au + (Bu -
Au) * i / (Nx -1)
v( j )= Av + (Bv - Av) * j / (Ny
-1)
Les points A ( Au, Av, -s ) et B ( Bu, Bv, -s ) définissent
le coin inférieur gauche (Au et Av sont négatifs) et le coin
supérieur droit (Bu et Bv sont positifs) du plan de projection situé
à la distance s du centre de projection. Le rayon R( i, j ) est donc
définit par ( u( i ), v( j ), -s ).
Une méthode simple pour définir une
caméra dans un repère global consiste à calculer le
repère UVW définit à partir d'un centre de projection
(noté E), d'un vecteur de visé (noté G) et d'un vecteur
indiquant une orientation (vers le haut, par convention) (noté Vup)
:
W= - G / || G ||
U= Vup * W / || Vup * W ||
V= W * U
Le rayon R( i, j ) dans le repère UVW est
toujours : ( u( i ), v( j ), -s ). On peut aussi le décrire par :
R( t )= E + t ( u( i ).U + v( j ).V - s.W )
remarque : '*' représente un produit
vectoriel, et '.' un produit scalaire
Partie 2. Intersection rayon/primitive
Pour chaque primitive que vous voulez utiliser, il
faut fournir une méthode d'intersection prenant en paramètre
un rayon (origine, direction) et déterminant l'existance d'une intersection
avec la forme paramétrée du rayon. Cette methode devra également
renvoyer le paramètre t correspondant à l'intersection ainsi
que la normale à la primitive au point d'intersection (cf. élimination
des parties cachées).
Partie 3. Arbre de construction et opération booléennes
Un arbre de construction est un arbre général
(facteur de branchement quelconque) dont les noeuds internes décrivent
les opérations booléennes et les feuilles décrivent
les primitives. Par exemple, une scène composée d'un plan
infini et d'une sphère posée dessus, sera représentée
par l'union des deux primitives. L'union sera le seul noeud interne de l'arbre
(sa racine, également), les deux feuilles seront les opérandes
de l'union, c'est à dire la sphère et le plan.
Partie 4. Intersection rayon/arbre de construction
Un arbre de construction est considéré
comme une primitive, son intersection avec un rayon doit fournir des renseignements
identiques. Un parcours récursif de bas en haut permet de calculer
l'intersection des primitives avec le rayon puis de déterminer le
résultat de chaque opération booléenne jusqu'à
la racine. En général, le parcours en profondeur de l'arbre
construit une liste d'intersections qui est modifiée par les opérations
booléennes en remontant vers la racine.
Partie 5. Elimination des parties cachées
Il suffit de trier la distance des intersections
calculées en parcourant l'arbre de construction ou la liste de primitives.
L'objet visible est le plus proche du centre de projection.
Partie 6. Eclairement
Dans un premier temps, on se contentera d'un éclairement
local diffus, la couleur d'un point dépend de la normale à
la surface, elle sera donc atténuée par le produit scalaire
de la normale et de la direction désignant la source de lumière.
Cette approximation correspond à une source de lumière directionnelle.
Pour simuler une source de lumière ponctuelle, il suffit de connaître
la position de la source et de calculer la direction entre le point de la
surface et la source de lumière.
Le calcul des ombres portées est relativement
simple à ajouter dans ce cas, il suffit de déterminer si
un objet intercepte le rayon émis par le point de la surface dans
la direction de la source de lumière.
Réalisation
Installez ce squelette
de programme dans un répertoire et définissez les primitives
qui vous interressent (sphère et plan sont donnés en exemple).
Une caméra pseudo-openGL et son générateur de rayons
primaires sont également fournis. La plus grosse partie du travail
consiste à écrire les fonctions d'intersections des primitives
ainsi que des opérations booléennes. La fonction de visualisation
est également à compléter. Par contre, toute la manipulation
et la construction de l'arbre csg est fournie (les structures de données
génériques ne sont pas toujours très intuitives à
programmer en C ...)
Les types de données a priori nécessaires
sont définis dans struct.h et un certain nombre de fonctions utilitaires
sont disponibles dans les différents sources.
Attention : ce squelette n'est qu'un point de départ,
il peut très bien contenir quelques erreurs (involontaires) et vous
aurez très certainement besoin d'écrire de nouvelles fonctions.
Essayez de les répartir sur différents fichiers en les regroupant
de manière logique. Le Makefile fourni est également très
simple à modifier et détail interressant, il gère
de manière automatique les dépendances des sources et des
fichiers de définition (.h).
Question Subsidaire :
Visualisez les primitives à l'aide d'openGL,
choississez le point de vue et la direction de visée de manière
interactive et calculez la visualisation de l'arbre de construction.
Est-il possible de visualiser un arbre de construction
(c'est à dire le résultat des opérations booléennes)
en n'utilisant uniquement openGL ?
Exemples :
à gauche : une union de 2 sphères, à droite, l'intersection
des mêmes sphères
le plan rouge délimite un demi espace que l'on peut également
utiliser lors d'une opération booléenne (intersection, différence,
etc.)
