Discussion :

[loufoque]

D'abord je tiens à préciser que j'ai très peu de connaissances en 3D ou même en programmation de jeu, même si je connais bien l'algèbre linéaire et les quaternions.
Je sais bien programmer et suis un habitué du forum C++.

Donc voilà, j'ai décidé de faire un petit projet personnel de jeu en 3D, et avant même de commencer je suis face à un petit problème algorithmique.

Soit un espace en 3 dimensions vide avec des personnes dedans, modélisés disons par un parallélépipède (une boîte), et un champ de vision (typiquement, une pyramide de 45°).
Je voudrais pouvoir déterminer, à tout instant, l'ensemble des personnes qui ont une certaine personne A dans leur champ de vision, avec A pouvant varier et être n'importe quelle personne de l'espace.
(Et ce de manière le plus efficace possible, sachant que l'espace et le nombre de personnes qu'il y a dedans peuvent être arbitrairement grand.)

Idéalement il me faudrait je pense une structure me permettant de parcourir les personnes des plus proches au plus lointaines, en pouvant éliminer tout l'espace se situant derrière une personne à chaque fois, puis en testant si le champ de vision contient bien les coordonnées de A.

À terme l'algorithme devrait pouvoir s'étendre pour aussi prendre en compte la topologie du terrain dans la visibilité.

En ayant parlé vite fait avec des programmeurs de jeu, on m'a conseillé d'utiliser un kd-tree et de faire du raytracing, mais j'avoue ne pas bien connaître ces outils ni voir comment ils s'appliquent de manière pertinente à ce problème.
Toute aide, idée et conseils seraient donc appréciés. Merci.

[screetch]

a vue de nez je dirai la même chose que tes collègues, lancer de rayon entre A et B et voir quels sont les obstacles. c'est en général une tache effectuée par le moteur physique

je dirai donc que poiur chaque personnage, tu peux verifier si ils sont dans la pyramide de vision puis lancer un rayon pour voir si il y a un obstacle entre. c'est évidemment imprécis car si un obstacle cache la tête mais pas le reste du corps, et que tu lances un rayon vers la tête, tu auras un resultat negatif.

Si c'est pour de l'IA, je pense que le mieux est de lancer un rayon par seconde (du coup, 4 rayons par seconde en visant plusieurs parties du corps) et de stocker la vitesse de l'objet, et d'interpoler durant une seconde (en considérant que si tu sais ou il etait il y a une seconde, il a pas dû bouger trop)
et comme tu sembles aussi partir du principe que tu souhaites globalement représenter un modèle humain, je sais que moi je peux difficilement garder en mémoire deux positions ou plus.

Il y a ce que je regarde précisément, qui est donc très précis (si c'est ce que je regarde, je peux par exemple avoir accès a toute les variables)
Il y a ce qui entre dans mon champs de vision, je ne sais encore rien dessus, des updates peu fréquent sont donc parfait
et ce qui sort de mon champs de vision, plus d'update.

je ne peux pas gérer une foule non plus, donc a tout casser je peux regarder précisément 2 a 3 personnes, et je peux noter quand une personne rentre dans mon champs de vision. Les autres, bien que techniquement visibles, je ne peux pas me concentrer dessus.

Exemple sur un match de foot : combien de joueurs à la fois peux tu voir ? peut etre un attaquant et les deux défenseurs autour de lui, plus des "choses" autour sans savoir dans quels camps ils jouent



Pour résumer, la technique c'est le lancer de rayon, l'optimisation c'est que lorsque tu as noté quelque chose de visible tu le considère comme visible un certain temps sans revérifier

[HanLee]

Est-ce que tu imposes une distance limite au delà de laquelle on ne peut plus voir quelqu'un ?
Dans ce cas ce serait peut-être intéressant d'avoir une structure type octree ou une grille 3D pour diviser l'espace.

[loufoque]

je dirai donc que poiur chaque personnage, tu peux verifier si ils sont dans la pyramide de vision

Il semble y avoir incompréhension, car cela n'a pas de sens pour ma question.
Je ne cherche pas à savoir ce que voit A, mais qui voit A. Chaque personne a sa pyramide de vision, et la pyramide de vision de A on s'en fiche. (après bon, ça reste similaire)

Donc la solution que tu proposes, ce serait plutôt que pour chaque personnage, je vérifie si A est dans sa pyramide.
Sauf que déjà, ça, ça ne va pas, car ça me fait parcourir tous les personnages, qui peuvent être en un nombre arbitrairement grand et se trouver à des milliers de "kilomètres" de là.

Est-ce que tu imposes une distance limite au delà de laquelle on ne peut plus voir quelqu'un ?

La pyramide a une taille finie, oui.

Dans ce cas ce serait peut-être intéressant d'avoir une structure type octree ou une grille 3D pour diviser l'espace.

L'espace est vide, il n'y a que des gens dedans, qui peuvent bouger en permanence.
Je vois pas comment je peux quadriller dynamiquement l'espace pour obtenir quelque chose d'utile pour ce que je veux faire.

[Mindiell]

Si la pyramide est finie, tu limites la première solution aux personnes inclues dans une sphère de rayon la taille la plus grande la pyramide autour de A. Tu limites bien le nombre de personnes là.
Ensuite, tu dois pouvoir virer facilement les gens qui lui tournent trop le dos.
Enfin, tu n'as plus qu'à tester si A est dans la pyramide de vision de chaque personne trouvée.

[HanLee]

L'espace est vide, il n'y a que des gens dedans, qui peuvent bouger en permanence.
Je vois pas comment je peux quadriller dynamiquement l'espace pour obtenir quelque chose d'utile pour ce que je veux faire.

Pour reprendre la réponse de Mindiell, ton espace "vide" est borné, il y a des gens qui se déplacent dedans.

Tu as partitionné ton espace en une grille tridimensionnelle statique.
Une personne est toujours incluse dans la grille, donc dans une cellule de la grille.

Chaque fois qu'une personne se déplace, on met à jour sa position dans la grille.

Maintenant tu cherches à savoir qui voit A. Alors, étant donné la position de A, on sait depuis quelles cellules il est possible de voir A, tu prends le voisinage de la cellule de A.

Ca évite de parcourir tout. Concrètement c'est toujours du n², mais avec une constante bien plus faible.

[loufoque]

Donc en gros je parcoure tout l'espace, en partant de A, à la recherche de gens.

[HanLee]

Donc en gros je parcoure tout l'espace, en partant de A, à la recherche de gens.

Pas tout, une partie. Imagine que ta grille (supposée diviser la boite de manière uniforme dans chaque direction) fasse 50*50*50 = 125000 cases, et qu'on ne puisse pas voir au dela de 5 cases on va dire.

Pour une personne A, tu ne vas considérer qu'un voisinage centré sur A de taille 10*10*10 = 1000 cases max, c'est quand même une réduction énorme, 2 ordres de grandeur!

Bon, une grille ça monte vite en consommation mémoire et en général ya beaucoup de gaspillage, alors c'est là que l'octree peut intervenir. Mais le voisinage sur un octree c'est quand même beaucoup moins pratique en contrepartie, puis il faut mettre à jour dynamiquement l'octree.

[screetch]

le test pour savoir si il est dans la pyramide (plutot dans le cone) est relativement simple; il s'agit d'un simple produit scalaire de vecteur 3D.
un octree ne t'aidera effectivement pas beaucoup car il faudra quand meme passer sur tous les personnages



mais le fait que a voie B n'est pas reversible ? tu ne peux pas calculer dans l'autre sens? ce que B voit ? et tu dois avoir un resultat exact?

[Mindiell]

un octree ne t'aidera effectivement pas beaucoup car il faudra quand meme passer sur tous les personnages

Pour quelle raison ? Il ui suffit de passer uniquement sur les personnages qui peuvent potentiellement le voir, et donc pas trop éloignés. Un octree ou une sphère doivent amplement suffire, non ?

mais le fait que a voie B n'est pas reversible ? tu ne peux pas calculer dans l'autre sens? ce que B voit ? et tu dois avoir un resultat exact?

Ben si B est derrière A, A ne le voit pas et B peut le voir. De même si B est de dos, A peut le voir, mais B ne voit pas A

[screetch]

non mais euh

si on veut savoir qui peut voir A, alors il faut chercher dans toute les directions autour de A. un partitionnement de l'espace ne changera rien, car quelqu'un derriere A peut quand meme voir A. donc, un octree est assez inutile
le test de visibilité est excessivement simple, un octree ne ferait qu'alourdir.

si on veut savoir qui B peut voir, alors un octree ou tout hierarchisation de l'espace aide, car alors on verifiera si la case est potentiellement visible ou pas. Une grosse moitié de l'espace sera eliminée rien qu'au premier pas.

[bafman]

perso, je partirait sur une structure de PVS (potentialy visibility set) pour gérer le monde.

ainsi, a tout moment, tu peut savoir quelles zones peuvent voir la zone ou se trouve A, et du coup, tu n'a à effectuer les test que sur les perso présents dans ces zones.
Bien entendu, ceci marche bien pour des mondes assez fermé à base de BSP ou de portal, pas pour des mondes très ouverts ou tout le monde peut voir tout le monde

[Frifron]

On veut savoir qui peut voir une seule personne définie ou bien qui peut voir qui parmi toute les personnes ?

Si c'est une seule personne, la préselection se fait de maniere très rapide :

_ test de norme au carré pour selectionner uniquement les personne qui ont A a portée de vue (test 1)
_ si ca passe produit scalaire pour selectionner uniquement les personne qui ont A dans leur champ de vision (test 2)

Le probleme est ensuite de determiner si A est visible ou derriere un obstacle (qui peut très bien etre une autre personne). On peut faire du lancer de rayon mais on ne vas bien evidemment pas tester le rayon sur chaque personne dans l'univers (la ca devient lourd). Le truc c'est qu'on a deja préselectionner les personnes a portée, on utilise donc le test 1 pour selectionner les personnes qui peuvent potentiellement se trouver entre la personne qui voit et A et on fait un test segment/OBB uniquement sur elles.

Donc je pense qu'il n'y a pas besoin de partitionner l'espace pour cet algo. Maintenant si l'espace DOIT être partionné pour servir dans un autre algo autant l'utiliser pour réduire le nombre de test 1 a faire.

[bafman]

(Et ce de manière le plus efficace possible, sachant que l'espace et le nombre de personnes qu'il y a dedans peuvent être arbitrairement grand.)

donc il y a bien besoin de faire de l'élagage en amont pour éviter d'avoir à raytracer des millions de fois l'univers

[deadalnix]

On peut maibtenir un graphe au déplacement des personnages sinon. Ça me parrait plus malin que de se demander après coup qui voit A.

[loufoque]

Si je comprends bien l'idée, il faudrait lancer n rayons dans toutes les directions autour de A (pour approximer une sphère j'imagine qu'il faut un gros n), de tester pour toutes les entités de la plus proche à la plus lointaine si elles intersectent un de ces rayons; si oui, et que cette entité est une personne, elle peut voir A si elle est bien orientée et on arrête la propagation du rayon.

Bref, c'est pas vraiment performant cette histoire, même en prenant une bounding box.

Je veux bien maintenir un graphe de qui voit qui et empêche de voir qui, mais je vois pas ce que ça permet de gagner...

[Frifron]

Nan l'idée ce n'est pas de lancer des rayons dans toutes les directions comme ca mais plutot de lancer un rayon de la personne qui peut potentiellement voir A jusqu'a A. Si ce rayon n'intersecte rien avant A, la personne voit A. En fonction de la précision de repérage voulu, tu peux lancer plusieurs rayons par personne par exemple 4 chacun vers un des 4 coins d'un "plan englobant" de A, ca permettra d'etre plus précis (par exemple A est detecté si on voit ses pieds seulement) sans etre beacoup plus lourd puisque si un des rayons atteint A on ne test pas les suivant puisque A est vu (en gros c'est plus lourd uniquement dans le cas de A partiellement obstrué).

Après pour la selection d'une personne qui peut potentiellement voir A, a toi de voir s'il faut partitionner l'espace, conserver les infos... Je pense que ca dépend grandement du contexte. Le test de selection étant très rapide, un partitionement ne fera pas forcément gagner.

[loufoque]

Donc en fait, pour toutes les personnes, je lance plusieurs rayons vers A (suffisamment pour que l'écart entre deux rayons soit inférieur à la taille minimum d'un objet) et je regarde s'ils arrivent jusqu'au bout.
Ça, ça va être très lent.

[Okdokey]

Si c'est un modele simple style 1 personne = 1 rectangle (ou plutot 1 cylindre) alors ca doit suffire de mesurer l'angle au sol de A et de comparer avec l'angle au sol fait par les personnes situees entre deux.

[Frifron]

Donc en fait, pour toutes les personnes, je lance plusieurs rayons vers A (suffisamment pour que l'écart entre deux rayons soit inférieur à la taille minimum d'un objet) et je regarde s'ils arrivent jusqu'au bout.
Ça, ça va être très lent.

Pas pour toute personne, pour toute personnes ayant A dans son champs de vision et étant a portée, ca réduit tout de meme le nombre de rayons a lancer. Un rayon par personne me parit suffisant et tu ne test pas ce rayon sur toutes les personnes mais idéalement uniquement celles étant potentiellement entre A et le lanceur du rayon. Le test de rayon est bourré d'"early outs" : des qu'un rayon est bloqué on passe a l'autre, des qu'un rayon passe on passe a l'autre personne, ceux dans le test d'intersection...

Après le rayon n'est peut être pas la solution la meilleur. C'est la plus intuitive mais peut être qu'une technique a base de produit scalaire ferait le boulot, a voir.

Ca va être très lent ? Tu gère une foule de plusieurs milliers d'individu ? Si oui dans ce cas il faut oublier le repérage précis