Bonjour !

Dans le cadre de mon stage de fin d'études, on m'a assigné une tâche qui, après 10 jours de réflexion et recherche, reste encore sans solution convenable. J'aimerai donc avoir des avis de personnes ayant déjà été confronté à la même problématique !
Bref, j'explicationne :

Je planche sur la partie 3D de l'appli, basée sur le moteur de rendu OpenSceneGraph. Cette appli permet la visualisation de données en temps réel dans des domaines variés.
Il y a actuellement une fonction GoTo qui permet d'aller d'un point de l'espace à un autre automatiquement. Pour l'instant la trajectoire est une ligne droite et la camera passe à travers ce qui est sur sa route.

Il m'est demandé de rendre cette fonction GoTo un peu plus intelligente, c'est à dire qu'elle trouve un chemin en évitant les collisions jusqu'à la destination.
L'enoncé est simple, les contraintes suivantes le rendent moins simple :

==========================

I) Prendre en compte trois grand cas de scène :
- Dans l'espace : grands espaces vides et tout petits objets
- Reseau de tuyau : espace très cloisonné avec peu de liberté de direction
- Usine : notion de salles

II) Scenes statiques et dynamiques

On entend pas scène dynamique une scène dans laquelle certains objets peuvent être ammenés à bouger ( juste translations / rotations , pas morphologiquement ).

III) Prendre en compte un certain volume à la camera

Ici on se contente de donner une bounding sphere à la camera. Et ce dans le but de détecter si l'on pourrait déplacer une certain volume d'un point de la scène à un autre. En ajoutant donc une détection dans les cas où il n'existe aucun chemin.

IV) Efficace et pas cher ( mais pas la MAAF )

Il serait souhaitable d'avoir une recherche de chemin dynamique, c'est à dire sans prétraitement préalable. On clique sur le bouton goto, la fonction nous retourne un chemin si il existe et on y va. Le temps pris pour la recherche de chemin doit être ( le contraire aurait été étonnant ) minimal.

V) Graphe de scène pouvant ressembler à n'importe quoi

Le graphe de scène étant generé à partir de fichiers que les clients nous envoient, il peut ressembler à n'importe quoi. Par exemple dans le cas d'un airbus a380 la coque peut très bien être divisée en plusieurs parties n'étant pas à la même profondeur dans le graphe.
Ceci enlève la notion d'objet car on obtient des bouts de maillages un peu partout, logique géometriquement mais pas hierarchiquement.

==========================

Pour répondre à ça j'ai planché un peu sur :

- Du path fiding à base de graphe et algo de recherche de plus court chemin ( ou de chemin tout court ). Mais cela nécessite du prétraitement pour la construction du graphe, marche difficilement dans les cas de scène dynamique ( reconstruction ( en partie ) du graphe à chaque fois qu'un objet bouge => couteux et pas très temps réel ) et coup mémoire important dès qu'on a besoin de précision ( surtout dans le cas de l'espace où on va aller passer entre deux tuyaux d'un sattelite pomé dans l'espace sidéral )

- Du lancé de rayon basique. On lance des rayons jusqu'a récuperer une liste de point de controle qui permet d'arriver à destination en évitant tout objet. Mais les trajectoires sont assez imprévisibles et détecter qu'il n'existe pas de chemin est un chouilla ardu ou sera très peu significatif.

Chaque méthode a ses avantages et inconvénients et marchera mieux dans certains cas que d'autres ( espace , tuyaux, usine ).
Il n'est pas possible de séparer les objets statiques des objets dynamique, ce qui rend un partitionnement de l'espace délicat.
Et le fait d'être dans certain cas dans l'objet ( tuyau ) et dans d'autres en dehors corse les choses.

Je suis conscient qu'il n'y a pas de solution miracle polyvalente, il faudra surement faire une détection de cas ( automatique ) puis sélectionner l'algo adéquat au cas..
Mais je tourne un peu ... ( beaucoup ? ) ... en rond.
En tout cas merci d'avoir lu jusqu'au bout, c'est courageux

Cordialement,
Harold