Выбор отрезка в пространстве курсором -> Форум на Исходниках.RU [Powered by Invision Power Board]

Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум на Исходниках.RU > Алгоритмы > Выбор отрезка в пространстве курсором

Автор: Moorka 17.08.17, 13:51

Здравствуйте.
Есть проблемка. Необходимо программно реализовать выбор отрезка курсором.
Т.е. имеем: в пространстве произвольно расположены отрезки, координаты известны.
Также в пространстве произвольно располагается камера. Координаты, угол взгляда тоже известны.
Нужно сделать выбор отрезка, который ближе всего (визуально) расположен к курсору:

Скрытый текст

shot0000.jpg (, : 562)

shot0002.jpg (, : 543)

Насколько я понимаю, алгоритм должен быть примерно такой:

Скрытый текст

scheme.png (, : 544)

Дано: P1 - точка наблюдения; вектор V - задает угол наклона камеры; отрезок 1-2.
Находим плоскость, образованную точками P1-1-2, затем перпендикулярную ей плоскость, проходящую через отрезок 1-2. Потом находим точку P2 пересечения линии, заданной вектором V и этой перпендикулярной плоскостью. Дальше находим расстояние (d) от точки P2 до отрезка. Ну и как бы всё.
Всё это проделываем для каждого отрезка и находим отрезок с минимальным расстоянием d.

На словах всё хорошо, но с практикой у меня туговато. Можете популярно разжевать дураку как это реализовать?
А то не очень дружу со всеми этими формулами.

Ну с плоскостью P1-1-2 вроде понятно - нормальный вектор будет векторным произведением векторов (P1,1)x(P1,2). А дальше как?

Автор: MBo 17.08.17, 16:27

Цитата

Потом находим точку P2 пересечения линии, заданной вектором V и этой перпендикулярной плоскостью. Дальше находим расстояние (d) от точки P2 до отрезка.

Это не минимальное расстояние (хотя и близко к нему).

Для поиска минимального расстояния между скрещивающимися прямыми в пространстве:

Задать параметрически луч зрения как

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>

P = P1 + unitV * u

Задать параметрически прямую, содержащую отрезок как

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>

L = StartPoint + (EndPoint - StartPoint) * v

Минимальный отрезок между этими прямыми перпендикулярен обеим

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>

(L - P) .dot. unitV = 0

(L - P) .dot. (EndPoint - StartPoint) = 0

Решается система уравнений для неизвестных u и v.
u должно быть положительным, v в пределах 0..1, иначе ближайшая точка отрезка - один из концов.

Есть ещё особый случай - прямые параллельны.

Автор: Moorka 17.08.17, 19:07

Спасибо, вроде разобрался.

Если P - точка наблюдения, v - вектор взгляда, AB - заданный отрезок, то:

нормальный вектор плоскости, проходящей через P и вектор v и параллельной AB:

n = [v x AB]

И расстояние от прямой v до отрезка AB:

dist = abs(P_x*n_x + P_y*n_y + P_z*n_z - n_x*A_x - n_y*A_y - n_z*A_z) / sqrt(n_x² + n_y² + n_z²)

или так:

dist = abs(Dot(P,n) - Dot(n,A)) / sqrt(Dot(n,n))

Автор: OpenGL 18.08.17, 07:08

Цитата MBo @ 17.08.17, 16:27

Есть еще особые случаи - прямые пересекаются, прямые параллельны.

"Прямые пересекаются" не является особым случаем и решается в рамках вышеописанного алгоритма - просто получится расстояние 0, и всё.

Автор: MBo 18.08.17, 13:08

OpenGL

Я было подумал, что делитель и для пересекающихся может быть нулевым, но нет.