Question 5 - Intersection boule / demi-espace

Pour simplifier, nous allons considérer le cas d'un mur infini (i.e., un demi-espace). Commencez par compléter la fonction intersectionSphereDemiEspace(Sphere s, Vecteur3 point, Vecteur3 normale) de la classe TD67, qui renvoie true si et seulement si la sphère s (plus exactement, la boule correspondante) est au moins partiellement contenue dans le demi-espace défini par un point et une normale, c'est-à-dire l'ensemble { x : (x-point).normale<=0) }, où le . désigne le produit scalaire (en d'autres termes, la frontière du demi-espace est le plan passant par point, et orthogonal à normale). Notez qu'avec cette définition, la normale est à l'extérieur du demi-espace. Par la suite, toutes les normales considérées seront de norme 1.

 

Indice 1 Indice 1: Faites un dessin ! On n'oubliera pas de prendre en compte le rayon de la sphère !

 

Indice 2 Indice 2: N'oubliez pas que (x-point).normale représente la distance signée (i.e. positive ou négative) entre le point x et le plan passant par point et orthogonal au vecteur normale.

 

Indice 3 Indice 3 : n'hésitez pas à utiliser les méthodes moins et produitScalaire de la classe Vecteur3 pour simplifier l'écriture de la fonction.

 

Dépose

Déposez le fichier TD67.java comportant la fonction intersectionSphereDemiEspace(...) complétée.

Question 6 - Ça passe ou pas ?

Grâce à la fonction écrite à la question précédente, écrivez une fonction récursive de parcours de l'arbre de sphères englobantes qui retourne true lorsque la surface est partiellement contenue dans un demi-espace. On l'a dit, ce genre de fonctions est notamment utilisé dans les jeux vidéo pour détecter des collisions entre les joueurs (ou les objets de la scène), et les murs du décor. 

Plus précisément, complétez la fonction récursive intersectionSurfaceMurVraiFaux(ArbreSpheres arbre, Vecteur3 point, Vecteur3 normale) de la classe TD67, qui parcourt l'arbre associé à la surface. Comme indiqué précédemment, on ne descendra que dans les parties de l'arbre susceptibles de contenir des triangles qui pénètrent le mur, c'est-à-dire les noeuds de l'arbre dont la sphère pénètre le mur. Pour les feuilles de l'arbre qui pénètrent le demi-espace, on détectera une collision entre le triangle référencé par la feuille et le demi-espace.

 

Indice 1 Indice 1: il suffit de programmer l'algorithme décrit en introduction de la partie II.

 

Indice 2 Indice 2 : parce qu'il est convexe, un triangle est au moins partiellement contenu dans un demi-espace si et seulement si au moins l'un de ses points est dans le demi-espace (rappel: les sommets (de type Vecteur3) du triangle référencé par une feuille arbre sont arbre.triangle.a, arbre.triangle.b, et arbre.triangle.c).

 

Indice 3 Indice 3 : si votre fonction n'a pas le résultat attendu, peut-être que le problème vient de la fonction intersectionSphereDemiEspace(...).

 

 

 

On pourra vérifier le résultat en cliquant sur le bouton "Intersection plan V/F", qui génère un demi-espace aléatoire et appelle la fonction intersectionSurfaceMurVraiFaux(...), et en faisant tourner la surface. Lorsqu'il y a collision, la surface devient entièrement verte (Figure 3). Notez que la normale au mur est dessinée à l'extérieur du demi-espace.

 

Figure 3. Détection de collisions entre une surface et un mur (demi-espace). a : la surface ne pénètre pas le mur. b: collision.

Dépose

Déposez le fichier TD67.java, qui comporte maintenant la fonction intersectionSurfaceMurVraiFaux(...) complétée.

Question 7 - Triangles, au rapport !

On cherche maintenant à connaître l'ensemble des triangles qui pénètrent le demi-espace. En vous inspirant de la fonction précédente, complétez la fonction intersectionSurfaceMur(ArbreSpheres arbre, Vecteur3 point, Vecteur3 normale, FileTriangles file) de la classe TD67. Notez que, contrairement à la fonction précédente, il ne sera pas possible de terminer dès que l'on détectera une interpénétration entre un triangle de la surface et le demi-espace.

 

On utilisera la fonction insererTriangles(...) de la file passée en paramètre. Ainsi, si l'on détecte une interpénétration entre le triangle arbre.triangle et le demi-espace, on utilisera l'instruction file.insererTriangles(arbre.triangle,null,null,0.0); pour insérer le triangle dans la file.

 

On pourra vérifier le résultat en cliquant sur le bouton "Intersection plan", qui génère un demi-espace aléatoire et appelle la fonction intersectionSurfaceMur(...), et en faisant tourner la surface. Lorsqu'il y a collision, les triangles qui pénètrent le demi-espace s'affichent en vert (Figure 4).

Figure 4. Détection de collisions entre une surface et un mur (demi-espace). Les triangles qui pénètrent le mur s'affichent en vert.

Dépose

Déposez le fichier TD67.java, qui comporte maintenant la fonction intersectionSurfaceMur(...) complétée.

Question 8 - Poly...? Poly...? Polyèdre !

En vous inspirant de la fonction précédente, complétez la fonction intersectionSurfacePolyedre(ArbreSpheres arbre, int nFaces, Vecteur3[] point, Vecteur3[] normale, FileTriangles file) de la classe TD67, qui retourne l'ensemble des triangles d'une surface qui sont entièrement contenus dans un polyèdre convexe.

 

Le polyèdre est défini comme l'intersection des demi-espaces 0, 1, ..., nFaces-1 (i.e., le demi-espace i est défini par le point point[i] et la normale normale[i]). Lisez bien la question ! On cherche les triangles entièrement contenus dans le polyèdre.

 

Attention : une approche consisterait à faire nFaces appels à la fonction implémentée à la question précédente, et à faire l'intersection des files retournées... Pourquoi cette approche est-elle fausse (soyez attentifs) ? Pourquoi, de plus, cette approche serait-elle inefficace ?

 
 

On pourra vérifier le résultat en cliquant sur le bouton "Intersection polyedre", qui génère un polyèdre aléatoire et appelle la fonction intersectionSurfacePolyedre(...), et en faisant tourner la surface. Lorsqu'il y a collision, les triangles entièrement contenus dans le polyèdre s'affichent en vert (Figure 5).

Figure 5. Calcul des triangles contenus dans un polyèdre. a : pas d'intersection. b: les triangles entièrement contenus dans le polyèdre sont affichés en vert.

Dépose

Déposez le fichier TD67.java, qui comporte maintenant la fonction complétée intersectionSurfacePolyedre(...).

Question 9 - Au minimum...

Il est parfois nécessaire de calculer le point extrémal d'une surface dans une direction (par exemple pour calculer un volume englobant la surface, ou pour détecter une collision entre la surface et un demi-espace). Complétez la fonction récursive minimumSurface(ArbreSpheres arbre, Vecteur3 minimumCourant, Vecteur3 normale) de la classe TD67, qui parcourt l'arbre associé à la surface pour déterminer le sommet s de la surface qui minimise le produit scalaire s.normale. On s'arrangera pour que, lorsque la fonction termine, la (mémoire référencée par la) variable minimumCourant contienne une copie des coordonnées du sommet recherché.

 

Attention : vous devez essayer d'éviter un parcours exhaustif de l'arbre ! Pour cela, vous pouvez éviter de parcourir les parties de l'arbre dont on est certain qu'elles ne contiennent pas de meilleur candidat que minimumCourant. Bien sûr, ceci peut être détecté grâce à la sphère englobante associée au noeud arbre.

 

Note : la fonction minimumSurface(ArbreSpheres arbre, Vecteur3 minimumCourant, Vecteur3 normale) prend une référence minimumCourant à un vecteur. Ce vecteur doit contenir une copie des coordonnées du sommet qui correspond au minimum courant. Lorsque la fonction minimumSurface(...) est appelée pour la première fois, minimumCourant contient une copie des coordonnées du premier sommet de la surface.

 

Indice 1 Indice 1 : la fonction cherche récursivement un meilleur minimum que le minimumCourant, tout en évitant de perdre du temps dans les régions de la surface inintéressantes.

 

On pourra vérifier le résultat en cliquant sur le bouton "Minimum", qui génère une direction aléatoire et appelle la fonction minimumSurface(...), et en faisant tourner la surface. Le plan dessiné devra être tangent à la surface (Figure 6). NB : la fonction minimumSurface est appelée (lorsque l'on clique sur "Minimum ") en passant en premier minimumCourant le sommet 0 de la surface affichée.

 

 

Figure 6. Calcul du point extrémal dans une direction.

Une fois la fonction minimumSurface écrite, on pourra également cliquer sur le bouton "Ajuster sol", qui modifie la position du sol pour l'amener en contact avec la surface (Figure 7).

 

 

Figure 7. La fonction minimumSurface permet également d'ajuster la position du sol (en cliquant sur "Ajuster sol").

Dépose

Déposez le fichier TD67.java, qui comporte maintenant la fonction complétée minimumSurface(...).

Partie III - Lancer de rayons

Introduction

Une méthode classique de calcul d'images de synthèse est celle du lancer de rayons (ray-tracing). Cette méthode simule le parcours inverse des rayons lumineux, en partant de l'oeil de l'observateur jusqu'aux sources de lumière, afin de déterminer la couleur de chaque point de l'écran. Afin de calculer rapidement des images de synthèse de cette façon, il est important d'être capable de rechercher très efficacement l'ensemble des triangles d'une surface traversés (touchés) par un rayon lumineux. Vous l'avez deviné, nous allons utiliser les arbres de sphères englobantes pour effectuer ces recherches.

 

Pour cela, nous allons utiliser la classe Rayon pour représenter un rayon lumineux. Un rayon lumineux est simplement une demi-droite, qui a un pointDeDepart (de type Vecteur3) et une direction (de type Vecteur3 également).

 

Question 10 - Aïe, ça pique !

Complétez la fonction intersectionSurfaceRayonVraiFaux(ArbreSpheres arbre, Rayon rayon) de la classe TD67, qui renvoie true si et seulement si le rayon rayon coupe la surface. Cette fonction sera utilisée par le lanceur de rayons pour déterminer si un point est dans une zone d'ombre (il suffit de savoir si une surface est entre la source de lumière et le point).

 

Lorsque le rayon coupera une sphère feuille, on utilisera la fonction intersectionTriangle(Vecteur3 a, Vecteur3 b, Vecteur3 c, Vecteur3 i) de la classe Rayon, qui renvoie true lorsqu'il y a intersection entre le rayon et le triangle abc, et qui, le cas échéant, copie dans i le point d'intersection. On utilisera donc cette fonction de la façon suivante:

 

Vecteur3 pointIntersection=new Vecteur3();

boolean intersection=rayon.intersectionTriangle(a,b,c,pointIntersection);

et l'on récupèrera, si intersection vaut true, la position du point d'intersection dans pointIntersection (qui ne sert que dans la question suivante). 

On utilisera la fonction intersectionSphere(Sphere s) de la classe Rayon, qui renvoie true lorsque le rayon coupe la sphère s. Bien sûr, on ne descendra que dans les parties de l'arbre qui contiennent des triangles susceptibles d'être coupés par le rayon.

 

On pourra vérifier le résultat en cliquant sur le bouton "Intersection rayon V/F", qui génère un rayon aléatoire et appelle la fonction intersectionSurfaceRayonVraiFaux(...), et en faisant tourner la surface (Figure 7).

Figure 7. Détection d'une intersection entre un rayon et une surface.

Egalement, on pourra tester la fonction en cliquant sur "Ray-trace Mono", qui appelle le lanceur de rayon "monochrome". Ce lanceur de rayons utilise la fonction intersectionSurfaceRayonVraiFaux(...) et peut donc seulement déterminer si le rayon qui part de l'oeil coupe une surface ou non. Si le rayon coupe la surface, le lanceur de rayons affiche un point de la couleur de l'objet; sinon, il affiche un point bleu (le ciel) (Figure 8). Ce lanceur est donc appelé "monochrome" puisque l'objet est uniformément coloré.

NB : il est possible de changer le "pas" du ray-tracer afin d'accélérer les calculs.

Figure 8. Le lanceur de rayons "monochrome" utilise la fonction intersectionSurfaceRayonVraiFaux(...) pour calculer une image simple.

Dépose

Déposez le fichier TD67.java, qui comporte maintenant la fonction complétée intersectionSurfaceRayonVraiFaux(...).

Question 11 - Ça pique ? Où ça ?

Afin de calculer des images plus réalistes, il est nécessaire de connaître la position des points d'intersection entre le rayon et la surface. Plus exactement, il est nécessaire de connaître le point de la surface le plus proche de l'oeil.

 

En vous inspirant de la fonction précédente, complétez la fonction intersectionSurfaceRayon(ArbreSpheres arbre, Rayon rayon, FileTriangles file) de la classe TD67, qui insère les triangles coupés par le rayon dans la file. Contrairement à la question précédente, il ne suffira donc plus d'arrêter la recherche dès qu'un triangle a été trouvé.

 

Parce que le lanceur de rayons a besoin de connaître à la fois la position du point d'intersection et une référence au triangle, on insèrera les triangles dans la file de la façon suivante:

 

file.insererTriangles(arbre.triangle,null,pointIntersection,d);

 

où d est la distance (que l'on aura calculée) du point d'intersection à l'oeil (i.e., le pointDeDepart du rayon).

 

Indice Indice : On pourra utiliser... Euh, non, pour cette question, vous ne devriez pas avoir besoin d'indices...

On pourra vérifier le résultat en cliquant sur le bouton "Intersection rayon", qui génère un rayon aléatoire et appelle la fonction intersectionSurfaceRayon(...), et en faisant tourner la surface (Figure 9). Les triangles coupés par le rayon s'afficheront en vert.

Figure 9. Détection d'une intersection entre un rayon et une surface. Les triangles coupés par le rayon sont affichés en vert.

On pourra enfin tester la fonction en cliquant sur "Ray-trace Normal", qui appelle le lanceur de rayon pour calculer une image (les curieux pourront examiner la fonction rayTraceSurface(Graphics g, int surfaceIndex) de la classe InterfaceA). Contrairement au lanceur de rayons monochrome, ce lanceur de rayons utilise les deux fonctions précédentes pour déterminer la couleur de chaque point et les zones d'ombres (Figure 10).

Rappel : il est possible de changer le "pas" du ray-tracer afin d'accélérer les calculs.

Figure 10. Le lanceur de rayons utilise les deux fonctions précédentes pour calculer la couleur de chaque point de l'écran, et les zones d'ombres.

On pourra utiliser les boutons "Rotation surface" (et, éventuellement, "Ajuster sol") pour modifier l'orientation de la surface et faire varier les images.

Dépose

Déposez le fichier TD67.java, qui comporte maintenant la fonction complétée intersectionSurfaceRayon(...).

Question 12 - En effet...

Afin d'apprécier l'apport des arbres de sphères englobantes, réécrivez les deux fonctions précédentes en utilisant chaque fois un algorithme linéaire, qui parcourt la liste entière des triangles pour effectuer la recherche.

 

Complètez ainsi les deux fonctions intersectionSurfaceRayonVraiFauxLineaire(Surface surface, Rayon rayon) et intersectionSurfaceRayonLineaire(Surface surface, Rayon rayon, FileTriangles file) de la classe TD67. Une fois ces deux fonctions écrites, on comparera la vitesse d'exécution des deux types de lanceurs de rayons (optimisé et linéaire) en utilisant les boutons "Ray-trace Normal" et "Ray-trace Lineaire" (Figure 11).

Figure 11. Le lanceur de rayons linéaire est beaucoup plus lent que le lanceur de rayons utilisant les arbres de sphères englobantes. Même avec un "pas" de 5, le lanceur linéaire prend 175 secondes, contre 0.7 secondes pour le lanceur optimisé.

Dépose

Déposez le fichier TD67.java, qui comporte maintenant les fonctions complétées intersectionSurfaceRayonVraiFauxLineaire(...) et intersectionSurfaceRayonLineaire(...).

Partie IV - Détection de collisions avancée

Introduction - Ça se complique...

Dans les questions précédentes, il existait des algorithmes linéaires simples pour effectuer les recherches demandées (puisqu'il suffit de parcourir la liste des triangles de la surface). Nous allons maintenant accélérer des recherches de complexité quadratique : la détection de collisions entre deux surfaces triangulées.  

 

Soient deux surfaces triangulées A et B composées respectivement de nA et nB triangles. On cherche à déterminer la liste des paires ("triangle tA de la surface A","triangle tB de la surface B") de triangles dont l'intersection est non vide. La complexité de ce problème est bien quadratique, puisque dans le cas le pire le nombre d'intersections est nA x nB.

 

Question 13 - Détection de collisions entre sphères

Commencez par compléter la fonction boolean intersectionSphereSphere(Sphere sA, Sphere sB) de la classe TD67, qui renvoie true si et seulement si la sphère sA recouvre la sphère sB (plus exactement, on souhaite détecter une intersection entre les boules correspondantes).

 

Indice Indice: Faites un dessin.

Dépose

Déposez le fichier TD67.java, qui comporte maintenant la fonction complétée intersectionSphereSphere(...).

Question 14 - Bim, bam, boum...

Complétez la fonction intersectionSurfaceSurface(ArbreSpheres arbreA, ArbreSpheres arbreB, FileTriangles file) de la classe TD67, qui détecte une collision entre deux surfaces et renvoie une liste de paires de triangles en collision. Plus précisément, écrivez une fonction récursive qui traverse simultanément les deux arbres de sphères englobantes, afin de déterminer la liste des paires de triangles en collision. Pour deux arbres donnés, la fonction effectuera un test de recouvrement entre les sphères situées à la racine des arbres, afin de déterminer si une collision entre les géométries englobées par les arbres peut exister. Si c'est le cas, la fonction raffinera la recherche si c'est possible (en traversant les descendants des arbres) ou bien effectuera un test d'intersection entre les triangles contenus dans les arbres (qui seront alors des feuilles).

 

Afin de déterminer s'il y a intersection entre deux triangles, on utilisera la fonction intersectionTriangleTriangle(Vecteur3 a, Vecteur3 b, Vecteur3 c, Vecteur3 d, Vecteur3 e, Vecteur3 f) de la classe Triangle, qui renvoie true si et seulement s'il existe une intersection entre les triangles abc et def. Cette fonction est déjà écrite et on l'utilisera en écrivant, par exemple :

 

boolean intersection=Triangle.intersectionTriangleTriangle(a,b,c,d,e,f);

 

Le cas échéant, on signalera cette intersection en l'insérant dans la file de la façon suivante:

 

file.insererTriangles(arbreA.triangle,arbreB.triangle,null,0.0);

 

Indice Indice : mmmm... Non.

On pourra vérifier le résultat en cliquant sur le bouton "Intersection surface / surface", qui génère une position aléatoire pour la seconde surface et appelle la fonction intersectionSurfaceSurface(...), et en modifiant le point de vue (Figure 12). Les paires de triangles en intersection s'afficheront en vert.

Figure 12. Détection de collisions entre deux surfaces. Les paires de triangles en intersection sont affichées en vert.

Dépose

Déposez le fichier TD789.java, qui comporte maintenant la fonction complétée intersectionSurfaceSurface(...).

Continuer?

Voulez-vous programmer quelques problèmes plus avancés? Continuer ici.

La conception de méthodes de recherche géométrique est un thème de recherche encore actif (objets complexes, objets déformables, détection de collisions continue, etc.), par exemple pour concevoir des méthodes de qualité utilisables dans les jeux vidéo, dans les logiciels de conception assistée par ordinateur, de simulation de dynamique moléculaire, etc. Ces TDs n'ont fait qu'aborder la question (tout en vous donnant une solide introduction au problème et aux méthodes employées). Si ce sujet vous intéresse, vous trouverez facilement plus d'informations en traînant sur Google.

 

Stéphane Redon - 2005-2012 - stephane.redon@inria.fr - http://nano-d.inrialpes.fr/~redon