Проверка того, пересекает ли отрезок сферу

Question

Я пытаюсь определить, пересекает ли отрезок отрезка (т.е. между двумя точками) сферу. Меня не интересует положение пересечения, просто пересекает ли сегмент поверхность сферы. Кто-нибудь есть какие-либо предложения относительно того, какой алгоритм будет наиболее эффективным для этого? (Мне интересно, существуют ли какие-либо алгоритмы, которые проще, чем обычные алгоритмы пересечения лучевой сферы, поскольку меня не интересует положение пересечения)

Answer 1

Если вас интересует только то, знает ли он, пересекается или нет, тогда ваш базовый алгоритм будет выглядеть следующим образом ...

Считайте, что у вас есть вектор вашей лучевой линии, A -> B.

Вы знаете, что кратчайшее расстояние между этим вектором и центром сферы происходит на пересечении вектора вашего луча и вектора, который находится под углом 90 градусов к этому, который проходит через центр сферы.

Следовательно, у вас есть два вектора, уравнения которых полностью определены. Вы можете определить точку пересечения векторов, используя линейную алгебру, и, следовательно, длину линии (или, более эффективно, квадрат длины линии) и проверить, меньше ли это радиуса (или квадрат радиуса). ) вашей сферы.

Answer 2

Я не знаю, каков стандартный способ сделать это, но если вы хотите знать только, если он пересекается, вот что я бы сделал.

Общее правило ... избегайте выполнения sqrt () или других дорогостоящих операций. По возможности разберитесь с квадратом радиуса.

1. Определите, находится ли начальная точка внутри радиуса сферы. Если вы знаете, что это никогда не так, пропустите этот шаг. Если вы внутри, ваш луч пересечет сферу.

С этого момента ваша отправная точка находится за пределами сферы.

2. Теперь представьте маленькую коробочку, которая будет соответствовать сфере. Если вы находитесь за пределами этого поля, проверьте направление x, y и z луча, чтобы увидеть, будет ли он пересекать сторону бокса, с которой начинается ваш луч. Это должна быть простая проверка знака или сравнение с нулем. Если вы находитесь снаружи и удаляетесь от него, вы никогда не пересечете его.

С этого момента вы находитесь в более сложной фазе. Ваша отправная точка находится между воображаемой коробкой и сферой. Вы можете получить упрощенное выражение, используя исчисление и геометрию.

Суть того, что вы хотите сделать, это определить, является ли кратчайшее расстояние между вашим лучом и сферой меньше радиуса сферы.

Пусть ваш луч будет представлен как (x0 + i t, y0 + j t, z0 + k t), а центр вашей сферы будет в (xS, yS, zS) , Итак, мы хотим найти t таким, чтобы оно давало наименьшее из (xS - x0 - i t, yS - y0 - j t, zS - z0 - k t).

Пусть x = xS - x0, y = yX - y0, z = zS - z0, D = величина квадрата вектора

D = x ^ 2 -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)

Вставьте t обратно в уравнение для D = .... Если результат меньше или равен квадрату радиуса сферы, у вас есть пересечение. Если оно больше, то пересечения нет.

Answer 3

На этой странице есть точное решение этой проблемы. По сути, вы подставляете уравнение для линии в уравнение для сферы, а затем вычисляете дискриминант полученного квадратичного. Значения дискриминанта указывают на пересечение.

Answer 4

Вы должны работать с этой позицией, если хотите точности. Единственный способ улучшить скорость алгоритмически - это перейти от пересечения лучевой сферы к пересечению ограничивающей луч.

Или вы можете пойти глубже и попытаться улучшить sqrt и другие вызовы внутренних функций

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