Évitement des collisions 3D: trouver le vecteur de vitesse mis à jour (en dehors des cônes «collision-vitesses»)

J'essaie de comprendre et de mettre en œuvre le mécanisme d'un système d'évitement de collision (comportement de direction) entièrement en 3D pour le mouvement de vol (six degrés de liberté), se concentrant actuellement sur le contournement des obstacles statiques (tous ayant la forme d'une sphère).

Cependant, je ne sais pas très bien comment trouver le nouveau vecteur vitesse de l'agent en mouvement. La figure ci-dessous illustre la scène. L'agent en mouvement (vert) doit diriger trois objets statiques (bleu). La ligne rouge représente le vecteur de vitesse avant initial.

Notez qu'il existe également trois cônes blancs / semi-transparents. Ceux-ci représentent les "vecteurs de vitesse interdits" concernant chaque obstacle. Cela signifie, l'ensemble des vecteurs de vitesse qui, s'ils étaient utilisés comme nouveaux vecteurs avancés de l'agent, feraient entrer l'agent en collision avec un ou plusieurs des obstacles (notez également que le rayon de chaque cône est égal au rayon de l'obstacle donné plus le rayon de l'agent, afin de permettre un décalage pour que le joueur puisse se déplacer).

Afin de découvrir le nouveau vecteur avancé de l'agent mobile dans un tel environnement 3D, compte tenu des trois obstacles, une approche naïve serait de simplement porter en 3D la solution classique expliquée dans cet article souvent cité et illustrée par l'image 2D suivante:

Là, une nouvelle vitesse (flèche orange) est simplement calculée en normalisant la distance minimale (flèche noire) entre la vitesse d'origine et le centre de l'obstacle, puis en multipliant cette normale par la somme entre le rayon de l'obstacle et le rayon du agent de déménagement. Ensuite, une moyenne des nouvelles vitesses calculées pour chacun des obstacles donnerait la vitesse finale totale.

Dans de nombreux cas, cela suffit. Cependant, jetez un œil aux cas ci-dessous (illustrés en 2D pour faciliter la visualisation):

Dans chacun d'eux, l'approche naïve entraînera une collision. En a et b, la nouvelle vitesse finale coïncidera avec la vitesse d'origine (flèche rouge) et l'agent en mouvement avancera malgré qu'il soit partiellement ou complètement bloqué. En c) et d), la nouvelle vitesse (flèche orange) aura toujours la même conséquence.

Donc, ma question est: quelle est la façon la plus efficace sur le plan informatique de découvrir le nouveau vecteur avancé de l'agent en mouvement dans un tel environnement 3D, en tenant compte des trois obstacles, d'une manière qui évite les collisions? Ou, en d'autres termes, le nouveau vecteur avancé qui:

1) n'est à l'intérieur d'aucun des cônes;

2) est le plus proche possible du vecteur avant d'origine (ligne rouge sur l'image).

PS: De préférence, je ne cherche pas de bibliothèque, je cherche à apprendre comment faire.

Je ne pense pas qu'il existe un moyen efficace de résoudre le problème exactement, mais voici comment j'essaierais de le résoudre.

Tout d'abord, j'utiliserais des volumes englobants autour de chaque objet, au lieu des objets eux-mêmes. Cependant, chaque objet peut être approximé par l'union de plus d'un volume englobant.

La solution la plus simple serait de calculer un volume englobant unique qui contient tous les objets dont vous avez besoin pour éviter et calculer le cône à partir de ce volume.

Cela peut ne pas être suffisant si les objets ne sont pas relativement proches les uns des autres. Vous pouvez alors vouloir faire un clustering de manière à ce que deux objets appartiennent au même cluster si ce n'est pas possible, ou du moins pas trivial de passer entre eux. Calculez le groupe d'objets en tenant compte de leurs volumes englobants plus la taille du volume englobant du joueur plus une marge supplémentaire. Vous pourriez utiliser quelque chose comme ceci:

http://lab.polygonal.de/?p=120

Une fois que vous avez les clusters, trouvez le plus proche et calculez le cône pour éviter de le heurter. En raison de la façon dont les clusters ont été créés, si vous dirigez juste assez pour éviter de toucher un cluster, vous n'en toucherez pas un autre.

De plus, vous pouvez créer une structure récursive lors du calcul des clusters qui vous aidera à trouver le cluster le plus proche.

Il y a quelques choses avec lesquelles vous pouvez jouer. Par exemple, au lieu de choisir le cluster le plus proche, choisissez les deux clusters les plus proches et calculez un seul cône qui les évite tous les deux. Vous pouvez également essayer d'autres volumes englobants autres que des sphères.

Il y a deux façons de répondre à cette question que je peux voir. Tout d'abord, si vous voulez simplement trouver un moyen de piloter, il vous suffit d'implémenter le pathfinding ( je trouve cela très utile ). Ce serait la fin de cela (et c'est la bonne réponse pratique à cette question), mais je pense que vous êtes plus curieux de trouver une solution mathématique à votre problème.

Pour résoudre ce problème, examinons un problème équivalent. Prenez une tranche 2D de votre scène "devant" votre pilote d'un avion normal au vecteur d'origine. Vous obtiendrez un point qui représente votre vecteur d'origine et une série d'ellipses qui sont les projections 2D de vos cônes d'occlusion. Maintenant, ce que vous voulez faire est de trouver le point le plus proche de votre point d'origine (appelons-le P) qui se trouve à l'extérieur des ellipses qui ne se chevauchent pas. Il s'avère que c'est un problème assez difficile à résoudre. Il y a 3 étapes:

• Découvrez les points d'intersection de toutes vos ellipses
• Trouvez tous les trous dans l'union de toutes vos ellipses
• Déterminez le point le plus proche de Ptoutes vos ellipses en dehors de l'union (qui peut être à l'intérieur d'un trou)

D'accord, tout cela nécessite des multiplicateurs de Lagrange et une vérification d'angle et d'autres choses vraiment compliquées à résoudre. Examinons d'autres options. Si nous transformons plutôt notre problème en espace angulaire, nous voyons que ce que nous voulons réellement faire, c'est trouver la distance minimale entre un point et plusieurs cercles projetés sur la surface d'une sphère. En géométrie différentielle, cela est souvent appelé une sphère 2 et est utile ici. Donc, tout d'abord, nous devons trouver la distance entre deux points sur la surface de la sphère, que nous utiliserons pour trouver la métrique à 2 sphères. Heureusement, c'est assez facile: ds^2 = (R^2)*(dth^2) + (R^2)*(sin(th)^2)*(dph^2)où nous maintenons Rconstant le rayon de notre 2 sphères projeté dans 3 espaces. Venant de la physique, je prends thpour être l'angle du positif zet phpour être l'angle du positif xavecsétant la distance.

Qu'est-ce que cela fait? Il nous permet de supprimer l'utilisation des multiplicateurs de Lagrange pour minimiser la distance, et nous permet de travailler en coordonnées "natives" (puisque nous définissons nos cônes en termes d'angle d'occlusion). Alors maintenant, nous devons trouver le rayon de nos projections de cônes. Prenons un cône pour l'instant et appelons l'angle qui le définit a. Le rayon de la projection est alors simplement R*a. C'était assez facile - quelle autre quantité devons-nous savoir sur les cônes? Nous devons connaître le centre de la projection, qui est défini par le vecteur de regard de l'acteur. Tout d' abord nous convertir x, yet zen coordonnées sphériques où nous savons que nous sommes à une distance R, et résolvons pour thet phque nous pouvons faire en branchant simplement dans nos formules de conversion:th = acos(z/R)et ph = atan2(y/x)(utiliser atan2ici pour tenir compte des ambiguïtés du quadrant d'arctangent). Le processus est le même pour trouver la position de votre vecteur d'origine en coordonnées sphériques.

Le problème a donc été simplifié. Cependant, le problème est encore assez difficile à résoudre, mais maintenant vous n'avez plus qu'à vous soucier des cercles et des points au lieu des ellipses et des points ou des angles et des vecteurs. Le reste du processus est plutôt procédural. Vous devez essentiellement trouver une zone de délimitation formée par vos cercles, pour laquelle il existe plusieurs solutions. Je vais présenter une méthode qui n'est peut-être pas la meilleure, mais qui fonctionnera.

Je comparerais d'abord la somme des rayons de toutes les paires de cercles et la distance entre les centres, puis si leur somme est plus grande que la distance centrale, définissez-les égales et résolvez pour thetphpour trouver les intersections. Vous savez que chaque paire d'intersections décrit des "angles interdits" pour le cercle en question, que vous stockeriez comme un tableau d'angles de point d'intersection (à partir du centre du cercle) pour chaque cercle qui coupe celui-ci - vous devez absolument " fusionner "toutes les plages qui se chevauchent lorsque vous les ajoutez au tableau pour que la partie suivante fonctionne correctement. Ensuite, vous trouvez le point le plus proche sur le bord du cercle au point d'origine (ce qui est aussi simple que de tracer une ligne passant par le centre du cercle et le point d'origine, puis de trouver l'emplacement sur la ligne au rayon du cercle du centre). Parcourez ensuite votre tableau stocké et testez si cet angle est dans la plage de chaque angle interdit. Si c'est le cas, sélectionnez l'arête la plus proche. C'est le point le plus proche de l'extérieur décrit à l'intérieur de ce cercle. Répétez le processus pour tous les cercles (une certaine optimisation peut être effectuée dans le processus de sélection - vous n'avez pas réellement besoin de le calculer pour chaque cercle). Comparez maintenant toutes vos distances les plus courtes, trouvez la plus petite, et c'est votre réponse, décrite dans les anglesthet ph. N'oubliez pas que la distance est décrite avec la métrique à 2 sphères lors de l'exécution de ce calcul. Puisque vous ne vous souciez pas de la sphère sur laquelle tout cela se trouve, uniquement des angles, vous pouvez définir R=1et effectuer ces calculs sur la sphère unitaire.

C'est la façon la plus simple que je pourrais penser de le faire. Je ne suis pas sûr que ce soit le moyen le plus simple, mais cela fonctionnerait plutôt bien. Pratiquement pour un jeu, cependant, vous voulez simplement implémenter le pathfinding.