22. Отсечение отрезков в трехмерном пространстве. Трехмерный алгоритм Кируса Бека. - p1xelse/CG GitHub Wiki

Вступление

Так же, как и в двумерном варианте алгоритма, в трехмерном может рассматриваться произвольный выпуклый отсекатель. Использовать будем все то же параметрическое уравнение:

P(t) = P1+ (P2 - P1)t, где 0 ≤ t ≤ 1

Но теперь все точки и векторы будут иметь три компоненты, соответственно все операции необходимо будет выполнять в трехмерном пространстве.

Видимость точек будем определять посредством ее рассмотрения относительно граней отсекателя, а не сторон, как было в двумерном алгоритме. Сам способ определения видимости не меняется. Рассмотрим определение видимости точки P относительно грани A1B1C1D1:

image

  • 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

image