Работа в координатах мирового пространства (или, что еще лучше, трехмерные декартовы координаты с началом в центре камеры, но в любой трехмерной системе координат у вас есть все данные, представленные в ней). Предположим, что вы знаете декартовы координаты A и B в мировом пространстве (в основном делите их однородные координаты на их соответствующие четвертые компоненты и избавьтесь от четвертого компонента, который теперь равен 1). Предположим, что вы знаете декартовы координаты центра камеры, назовите эту точку O.
Идея состоит в том, чтобы пересекать плоскость, определенную точками A, B, O, с каждым треугольником, начиная с того, который содержит A, и заканчивая тем, который содержит B.
Сначала найдите вектор нормали N к плоскости ABO, который является перекрестным произведением
векторы О.А. и О.Б.
Теперь начнем с треугольника, который содержит A.
- Пусть треугольник имеет вершины U, V и W, снова записанные в декартовых мировых координатах.
- Затем вычислите вектор перекрестных произведений векторов UV и UW.
- После этого вычислите перекрестное произведение N и M, которое даст вам вектор K.
- Проверка, положительно ли произведение K dot с вектором AB. Если нет, умножьте K на -1.
- Начиная с точки A, следуйте вектору K, пока не пересечете край треугольника UVW. Обозначим эту точку через P.
- В результате этих шагов вы выбрали точку P вместе с треугольником, который разделяет с треугольником UVW ребро, на котором расположен P.
Выполните следующую процедуру: предположим, что вы находитесь в треугольнике UVW и у вас есть точка P на одном из его ребер (см., Например, предыдущий шаг 2).
- Возьмем вектор перекрестных произведений M векторов UV и UW.
- Возьмем вектор кросс-произведения векторов N и M.
- Начиная с точки P, следуйте вектору K, пока не пересечете край треугольника UVW (или, если вы находитесь в последнем треугольнике, пока не достигнете точки B). Обозначим эту новую точку пересечения через P.
- Точка P лежит на одном из трех ребер треугольника UVW. Возьмите следующий треугольник, который является треугольником, который разделяет с UVW край, на котором расположен P. Назовите этот новый треугольник UVW.
- Продолжайте повторять шаг 3, пока не достигнете треугольника UVW, в котором лежит точка B.
Редактировать 1: (Объяснение геометрической конструкции в алгоритме) У вас есть вектор N = OA x OB перпендикулярно плоскости OAB и вектор M = UV x UW перпендикулярно плоскости UVW. Тогда линия пересечения L двух плоскостей OAB и UVW лежит на обеих из них. С одной стороны, L лежит в плоскости OAB и, следовательно, проецируется из точки O на экран как линия. С другой стороны, L лежит на плоскости треугольника UVW. Следовательно, линия L перпендикулярна обоим векторам N и M. Следовательно, вектор перекрестного произведения K = N x M векторов N и M перпендикулярен им обоим и, следовательно, параллелен линии L (то есть вектор K выровнен по линии L). Поэтому прямая L (лежащая на плоскости треугольника UVW) определяется точкой P и вектором K.
Редактировать 2: (возможно, упрощение алгоритма)
Опять же, работайте в координатах мирового пространства (или, что еще лучше, в трехмерных декартовых координатах с началом в центре камеры, но в какой бы трехмерной системе координат у вас не были представлены все данные). Предположим, что вы знаете декартовы координаты A и B в мировом пространстве, а также все мировые координаты вершин триангуляции. Предположим, что вы знаете и декартовы координаты центра камеры, назовите эту точку O.
Идея состоит в том, чтобы пересекать плоскость, определенную точками A, B, O, с каждым треугольником, начиная с того, который содержит A, и заканчивая тем, который содержит B.
Вот геометрическое обоснование.Начните с треугольника, который содержит A. Пусть треугольник имеет вершины U, V и W, снова записанные в декартовых мировых координатах.Идея состоит в том, чтобы найти, какой из трех ребер UVW пересекает плоскость OAB в точке P, так что скалярное произведение AP.AB из AP с AB является положительным числом.Это в основном формула для пересечения линии в 3D и плоскости в 3D.Линия здесь, скажем, определяется точками V и W, а плоскость - OAB.Тогда уравнение плоскости равно N. (XA) = 0 для любой точки X на плоскости OAB.Вот '.'это скалярное произведение.Уравнение линии имеет вид X = V + t * (WV).Таким образом, точка пересечения определяется путем решения для t, когда мы вставляем уравнение прямой в уравнение плоскости: N.(V + t*(W-V) - A) = 0 Это очень легко решить для t: t = ( N.(A-V) )/( N.(W-V) )
И, следовательно, точка пересечения P междуOAB и UV P = V + ((N.(A-V))/( N.(W-V)))*(W-V) Чтобы быть уверенным, что P на краю, то есть между U и V, мы должны проверить, что N. (WV) / = 0 и 0 <= t <= 1. В противном случае мы переходим кдругой край.</p>
Сначала найдите вектор нормали N к плоскости ABO, который является перекрестным произведением N = OA x OB векторов OA и OB.
Начните с треугольника, который содержит A. Пусть треугольник имеет вершины U, V и W, снова записанные в декартовых координатах мира .:
- Рассчитатьскалярное произведение
N.(W-V) и убедитесь, что оно не равно нулю.Если это так, выберите другой край треугольника и начните снова с начала шага 2; - Рассчитать
t = ( N.(A-V) )/( N.(W-V) ).Если t> 1 или t <0, выберите другой край UVW и начните снова с начала шага 2; </li> - Вычислить
P = V + t*(W-V); - Выполните следующие проверки: (i) вычислитевекторы перекрестных произведений OA x OP и OP x OB;(ii) Рассчитать их точечное произведение
(OA x OP).(OP x OB);(iii) проверить, что (OA x OP).(OP x OB) > 0.Если нет, выберите другое ребро и начните заново с начала шага 2; - Нарисуйте точку соединения отрезка линии A с точкой P;
- Возьмите треугольник, который совпадает с треугольником UVW краяна котором расположен P.
- В результате этих шагов вы выбрали точку P вместе с треугольником, который разделяет с треугольником UVW край, на котором расположен P.
Повторяйте следующую процедуру: предположим, что вы находитесь в треугольнике UVW и вы определили точку P на одном из его ребер, скажем VW (см., Например, предыдущий шаг 2),Нам нужно найти, какой из двух ребер UV или UW пересекает плоскость OAB (она должна пересекаться в одном из них).Начните, скажем, с края UV:
- Рассчитайте
N.(V-U) и убедитесь, что оно не равно нулю.Если это так, выберите другой край UW и начните снова с начала шага 3; - Рассчитать
t = ( N.(A-U) )/( N.(V-U) ).Если t> 1 или t <0, выберите другое ребро UW и начните снова с начала шага 3; </li> - Вычислить
P = U + t*(V-U); - Нарисуйте отрезок линии, соединяющий старый сновая точка P (первая на ребре VW и вторая на ребре UV в нашем примере);
- Возьмите треугольник, который разделяет с треугольником UVW ребро, на котором расположен P.
- Точка P лежит на одном из трех ребер треугольника UVW.Возьмите следующий треугольник, который является треугольником, который разделяет с UVW край, на котором расположен P.Назовите этот новый треугольник UVW.
- Продолжайте повторять шаг 3, пока не достигнете треугольника UVW, в котором лежит точка B.