Discussion :

[lyly8]

Bonjour à tous,

Je cherche un algorithme de champ de vision qui permette de savoir quels personnages sont visible par un observateur. La première solution envisagée était de faire une sorte de «*balayage*»du champ de vision de l'observateur. Cette technique consistait à lancer des rayons depuis cet observateur jusqu'à la fin de cette zone de champ de vision (les rayons correspondant à des segments tracés à l'aide de l'algorithme de Bresenham). Mais le temps de calcul utilisé par cette technique s'avère bien trop long.

J'ai schématiser le champ de vision de l'observateur lorsqu'il se trouve face à des obstacles(ici 3 caisses) et 3 personnages. Certaines zones ne sont pas visibles par l'observateur elles ont été hachurées sur le schéma. Dans ce cas là,l'algorithme devrait révéler que tous les personnages sont visibles sauf celui placé en haut à droite.


http://imageshack.us/photo/my-images...mpdevision.png

[alecool]

Ce que tu cherches à faire s'appelle "occlusion culling", si ca peut t'aider dans tes recherches.
Je vais avoir besoin de m'y pencher mais ne l'ai pas encore fait. Je ne connais pas d'algo spécialement réputé pour ce genre de problème, mais je n'ai pas encore cherché en profondeur...
Si tu trouves quelque chose, n'hésite pas à en faire part sur le forum!

[pseudocode]

La première solution envisagée était de faire une sorte de «*balayage*»du champ de vision de l'observateur. Cette technique consistait à lancer des rayons depuis cet observateur jusqu'à la fin de cette zone de champ de vision (les rayons correspondant à des segments tracés à l'aide de l'algorithme de Bresenham). Mais le temps de calcul utilisé par cette technique s'avère bien trop long.

Généralement on fait plutôt l'inverse : on lance des rayons depuis les objets vers l'observateur. Ou pour être plus exact, on projète les bounding-box des objets sur le plan de vision de l'observateur.

On a simplement besoin de projeter les sommets de la bounding-box sur le plan, ensuite il reste a remplir le polygone obtenu (si on est en 3D) ou le segment obtenu (si on est en 2D, comme ton image). Il y a des méthodes rapides pour estimer si une projection sera completement hors du plan (objet hors du champ de vision).

Ces projections s'empilent sur le plan, et on garde les points les plus proche de l'observateur (technique du Z-buffer). Une fois fini, le plan contient la projection des objets visibles.