Пересечение одной сферы и множества отрезков

Question

Я знаком с BSP, KD-деревом и BVH для общей задачи поиска пересечения примитивных лучей. Существуют ли более эффективные алгоритмы и структуры данных для поиска пересечений только между одной сферой и множеством отрезков? Обратите внимание, что сфера является объектом запроса.

Answer 1

Одним из решений будет:

• Определите ограничивающие прямоугольники отрезков и создайте из них BVH или kd-дерево.
• Определите ограничивающий прямоугольник сферы запроса.
• В вашем алгоритме пересечения проведите сферу по дереву, проверив перекрытие между BB сферы и текущим узлом.
  • Если нет перекрытия, BB сферы не пересекает ни один отрезок линии в данном узле, и вы можете пропустить дочерние узлы.
  • Если есть совпадение, пройдитесь по дочерним узлам.
  • В конечных узлах вы должны выполнить тест пересечения лучей для каждого отрезка линии в узле и сфере (это не ясно из вашего вопроса, но я предполагаю, что несколько сегментов могут пересекать сферу, и что вас интересуют все такие пересечения). Вы можете оптимизировать тест пересечения, например, так:

Предположим, что

• Сфера имеет радиус R и его центр находится в точке C,
• отрезок имеет концы в точках P0 а также P1,
• D0 это расстояние между C а также P0, а также
• D1 это расстояние между C а также P1,

Затем:

• Если D0 < R а также D1 < Rотрезок прямой содержится полностью внутри сферы и не пересекает поверхность.

• Если D0 < R исключающее D1 < Rотрезок пересекает поверхность сферы.

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

Дальнейшая оптимизация будет состоять в том, чтобы сравнивать квадратные расстояния с квадратным радиусом, чтобы избежать укоренения.