22. Отсечение отрезков в трехмерном пространстве. Трехмерный алгоритм Кируса Бека. - chrislvt/CG GitHub Wiki
Вступление
Так же, как и в двумерном варианте алгоритма, в трехмерном может рассматриваться произвольный выпуклый отсекатель. Использовать будем все то же параметрическое уравнение:
P(t) = P1+ (P2 - P1)t, где 0 ≤ t ≤ 1
Но теперь все точки и векторы будут иметь три компоненты, соответственно все операции необходимо будет выполнять в трехмерном пространстве.
Видимость точек будем определять посредством ее рассмотрения относительно граней отсекателя, а не сторон, как было в двумерном алгоритме. Сам способ определения видимости не меняется. Рассмотрим определение видимости точки P относительно грани A1B1C1D1:
-
Ni - вектор внутренней нормали к i-й грани отсекателя
-
f - произвольная точка любой грани отсекателя. Для удобства можно использовать любые угловые точки граней
Видимость точки относительно выпуклого трехмерного отсекателя
Для определения видимости вычислим скалярное произведение двух векторов: Ni и (P - f). Второй вектор - это вектор соединяющий произвольную точку грани отсекателя и рассматриваемую точку. Скалярное произведение для трехмерных векторов можно посчитать по формуле:
a * b = ax * bx + ay * by + az * bz
Анализируя знак произведения Ni(P - f) можем сделать выводы о видимости точки P относительно грани отсекателя. Если произведение:
-
> 0 - точка видима
-
< 0 - точка невидима
-
= 0 - точка лежит на грани
Для отсечения целого отрезка будем анализировать вектор направления отрезка(директрису)
D = P2 - P1
Так же для определения точек пересечения с гранями отсекателя нам потребуется значение параметра t, которое считается по аналогии с двумерным алгоритмом отсечения
t = -Wск / Dск, где
-
Wск - скалярное произведение вектора Wi = (P - f) на вектор нормали i-й грани Ni
-
Dск - скалярное произведение директрисы на на вектор нормали i-й грани Ni
Частные случаи
Так же по аналогии с двумерным алгоритмом рассмотрим несколько частных случаев
-
D = 0 - отрезок вырождается в точку
-
Dск = Ni * D = 0 - отрезок параллелен i-й грани отсекателя
-
Wск = Ni * Wi ≥ 0 - отрезок расположен по видимую сторону отсекателя
-
Wск = Ni * Wi < 0 - отрезок расположен по невидимую сторону отсекателя, и тогда отрезок является полностью невидимым
Теперь рассмотрим способ нахождения параметров t, необходимых для нахождения точек пересечения отсекателя с отрезком. Данный способ аналогичен способу, представленному в двумерном алгоритме
Точки пересечения
Анализируя знак Dск можно сказать о положении точки пересечения относительно начала и конца отрезка. Если:
-
Dск > 0 - точка расположена ближе к началу отрезка
-
Dск < 0 - точка расположена ближе к концу отрезка
-
Dск = 0 - точка расположена посередине отрезка
Соответственно в случае, если Dск > 0, текущее значение t выбирается, как максимальное между текущим и вычисленным t = -Wск / Dск. Иначе же значение t выбирается, как минимальное между текущим и вычисленным.
-
Dск > 0 -> tн = max(tн, t)
-
Dск ≤ 0 -> tв = min(tв, t)
После нахождения точек пересечения необходимо выполнить проверку tн ≤ tв, чтобы убедиться в том, что начало видимой части не расположено за концом отрезка
Описание алгоритма будет полностью аналогично описанию двумерного алгоритма с тем уточнением, что скалярное произведение, а так же разность векторов будет считаться уже для трех компонент - x, y, z