Test d'intersection d'un segment de ligne avec une sphère

Question

J'essaie de déterminer si un segment de droite (c'est-à-dire entre deux points) intersecte une sphère. La position de l'intersection ne m'intéresse pas, que le segment intersecte ou non la surface de la sphère. Est-ce que quelqu'un a des suggestions quant à l'algorithme le plus efficace pour cela? (Je me demande s'il y a des algorithmes plus simples que les algorithmes d'intersection rayon-sphère habituels, puisque la position d'intersection ne m'intéresse pas)

Answer 1

Je ne sais pas ce que la manière standard de le faire est, mais si vous voulez seulement savoir si il croise, voici ce que je ferais.

Règle générale ... évitez de faire des opérations sqrt() ou d'autres opérations coûteuses. Lorsque cela est possible, traitez le carré du rayon.

1. Déterminez si le point de départ se trouve à l'intérieur du rayon de la sphère. Si vous savez que ce n'est jamais le cas, passez cette étape. Si vous êtes à l'intérieur, votre rayon intersectera la sphère.

A partir d'ici, votre point de départ est en dehors de la sphère.

2. Maintenant, imaginez la petite boîte qui s'adaptera à la sphère. Si vous êtes à l'extérieur de cette case, vérifiez la direction x, la direction y et la direction z du rayon pour voir si elle va croiser le côté de la boîte sur laquelle commence votre rayon. Cela devrait être une simple vérification de signe, ou une comparaison par rapport à zéro. Si vous êtes à l'extérieur et que vous vous en éloignez, vous ne l'entrecouperez jamais.

À partir de maintenant, vous êtes dans la phase la plus compliquée. Votre point de départ est entre la boîte imaginaire et la sphère. Vous pouvez obtenir une expression simplifiée en utilisant le calcul et la géométrie. L'essentiel de ce que vous voulez faire est de déterminer si la distance la plus courte entre votre rayon et la sphère est inférieure au rayon de la sphère.

Laissez votre rayon être représenté par (X0 + i t, y0 + j t, Z0 + k t), et le centre de votre sphère à être (Xs, Ys, ZS). Donc, nous voulons trouver t tel qu'il donnerait le plus court de (xS - xo - i t, yS - y0 - j t, zS - z0 - k t).

Soit x = xS - x0, y = yx - y0, z = ZS - Z0, D = amplitude du vecteur carré

D = -2 x^2 * x i t + (i * t)^2 + y^2 - 2 * y j t + (j * t)^2 + z^2 - 2 * z k t + (k * t)^2

D = (i^2 + j^2 + k^2) t^2 - (x i + y j + z k) * 2 * t + (x^2 + y^2 + z^2)

dD/dt = 0 = 2 * t * (i^2 + j^2 + k^2) - 2 * (x i + y j + z * k)

t = (x i + y j + z * k)/(i^2 + j^2 + k^2)

Replacer t dans l'équation pour D = .... Si le résultat est inférieur ou égal au carré du rayon de la sphère, vous avez une intersection. Si c'est plus grand, alors il n'y a pas d'intersection.

Answer 2

vous devez travailler de telle sorte que la position soit correcte . La seule façon d'améliorer la vitesse algorithmiquement est de passer de l'intersection de la sphère de rayon à l'intersection de la boîte de délimitation des rayons.

Ou vous pourriez aller plus loin et essayer d'améliorer les appels sqrt et d'autres fonctions internes

http://wiki.cgsociety.org/index.php/Ray_Sphere_Intersection

Answer 3

This page a une solution exacte pour ce problème. Essentiellement, vous substituez l'équation de la ligne dans l'équation de la sphère, puis calculez le discriminant du quadratique résultant. Les valeurs du discriminant indiquent une intersection.

Answer 4

Si vous ne souhaitez se savoir si elle croise ou non, votre algorithme de base ressemblera à ceci ...

Considérez-vous le vecteur de votre ligne de rayon, A -> B.

Vous savez que la plus petite distance entre ce vecteur et le centre de la sphère se produit à l'intersection de votre vecteur de rayon et d'un vecteur qui est à 90 degrés de celui qui traverse le centre de la sphère.

Vous avez donc deux vecteurs dont les équations sont complètement définies. Vous pouvez calculer le point d'intersection des vecteurs en utilisant l'algèbre linéaire, et donc la longueur de la ligne (ou plus efficacement le carré de la longueur de la ligne) et tester si elle est inférieure au rayon (ou au carré du rayon) de votre sphère.