Проверка пересечения отрезка прямой со сферой
Я пытаюсь определить, пересекает ли отрезок прямой (то есть между двумя точками) сферу. Меня не интересует положение пересечения, просто пересекает ли сегмент поверхность сферы. Есть ли у кого-нибудь предложения относительно того, какой наиболее эффективный алгоритм для этого был бы? (Мне интересно, есть ли какие-либо алгоритмы, которые проще, чем обычные алгоритмы пересечения лучей и сфер, поскольку меня не интересует положение пересечения)
4 ответа:
Я не знаю, каков стандартный способ сделать это, но если вы только хотите знать, пересекается ли он, вот что я бы сделал.
Общее правило ... избегайте выполнения sqrt () или других дорогостоящих операций. Когда это возможно, разберитесь с квадратом радиуса.
Определите, находится ли начальная точка внутри радиуса сферы. Если вы знаете, что это никогда не так, то пропустите этот шаг. Если вы находитесь внутри, ваш луч пересечет сферу.
С этого момента ваш отправная точка находится за пределами сферы.
Теперь представьте себе маленькую коробочку, в которую поместится сфера. Если вы находитесь вне этого поля, проверьте направление 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 = величина вектора в квадрате
Д = х^2 -2*хят + (я*т)^2 + У^2 - 2*ги Jт + (к*Т)^2 + З^2 - 2*Зкт + (к*Т)^2
D = (i^2 + j^2 + k^2) t^2 - (x i + yj + zk)*2 * t + (x^2 + y^2 + z^2)
ДД/DT = 0, а = 2*т*(я^2 + J в^2 + к^2) - 2*(хя + Ги J + г*к)
T = (x i + yj + z*k) / (i^2 + j^2 + k^2)
Штекер t обратно в уравнение для D = .... Если результат меньше или равен квадрату радиуса сферы, то получается пересечение. Если она больше, то нет никакого пересечения.
Если вы заинтересованы только в том, чтобы знать, пересекается ли он или нет, то ваш базовый алгоритм будет выглядеть следующим образом...
Считайте, что у вас есть вектор вашей лучевой линии, A - > B.
Вы знаете, что кратчайшее расстояние между этим вектором и центром сферы происходит на пересечении вашего лучевого вектора и вектора, который находится под углом 90 градусов к тому, который проходит через центр сферы.У вас, следовательно, есть два вектора, уравнения которых полностью полностью определенный. Вы можете вычислить точку пересечения векторов с помощью линейной алгебры, а следовательно, длину линии (или более эффективно квадрат длины линии) и проверить, если это меньше, чем радиус (или квадрат радиуса) вашей сферы.
На этой странице есть точное решение этой проблемы. По существу, вы подставляете уравнение для линии в уравнение для сферы, а затем вычисляете дискриминант результирующей квадратичной функции. Значения дискриминанта указывают на пересечение.