15. Отсечение. Алгоритм Кируса Бека отсечения отрезка. - p1xelse/CG GitHub Wiki

Увертюра

Описание алгоритма

Как распознаются полностью видимые отрезки

В случаях полностью видимого и полностью невидимого отрезков: параметр точки пересечения с границей отсекателя выходит за допустимый интервал [0, 1]. Не существует простого условия для определения полностью видимых и невидимых отрезков, они будут определяться в процессе выполнения алгоритма.

Представим полностью видимый отрезок P1 P2. Все значения, которые соответствуют точкам пересечения, лежат вне интервала 0<=t<=1. В процессе выполнения алгоритма все нижние параметры оказываются меньше 0, так как точка пересечения выходит за границы отрезка.

Мы выбираем max из нижних, и исходный параметр сохраняет своё значение tн = 0. Аналогично для верхних параметров. Выбираем min из верхних, исходный параметр не изменяется tв = 1.

После цикла отсечения пройдет проверка tн <= tв.

Возьмите простейший отсекатель – треугольник. Расположите невидимые отрезки, невидимость которых определяется всеми возможными способами и объясните определение невидимости.

1. Отрезок параллелен одной из сторон отсекателя и невидим относительно неё.

   

   Dcк в этом случае будет == 0 (отрезок параллелен текущей стороне). Проверяем Wск, Wск < 0 (точка P1 невидима относительно текущей границы). Цикл отсечения завершен, отрезок полостью невидим.

2. Параметр, соответствующий началу видимой части, расположен за концом отрезка.

   

   Так как Dск > 0, ищем нижний параметр. Найденный t > 1, следовательно отрезок невидим. Завершение работы алгоритма.

3. Параметр, соответствующий концу видимой части, расположен до начала отрезка.

   

   Так как Dск < 0, ищем верхний параметр. Найденный t < 0, следовательно отрезок невидим. Завершение работы алгоритма.

4. Параметр, соответствующий началу видимой части, расположен за параметром, соответствующим концу видимой части.

   

   Поиск пересечения с гранью 01. Вычислили Dск < 0 и ищем верхний параметр. Вычислили tв.

   Поиск пересечения с гранью 12. Вычислили Dск < 0. Вычисляем верхний параметр. Вычислили t (уходит за границы рисунка.) Сравниваем с предыдущим tв. Так как tв < найденного t, не меняем tв.

   Поиск пересечения с гранью 20. Вычислили Dск > 0. Ищем нижний параметр. Вычислили tн.

   После завершения цикла отсечения делаем проверку tн <= tв. Проверка не пройдена, отрезок невидимый.

---

Курову нравица!

Возьмите в качестве отсекателя треугольник (есть в отчете) и покажите все невидимые отрезки, невидимость которых определяется всеми разными способами. (жду рисунок и краткое, но полное объяснение).

1 . Случай параллельности отрезка одной из сторон отсекателя (Dск=0).

Если отрезок целиком невиден относительно одной границы, значит он в целом невиден.

Чтобы быть полностью видимым, надо быть видимым относительно каждой границы отсекателя.

Поскольку отрезок параллелен границе отсекателя, то достаточно проверить произвольную точку отрезка.

Анализируем знак Wск=(Ni*(p1-fi)), тем самым проверяем видимость первой вершины отрезка относительно границы отсекателя и, следовательно, видимость всего отрезка.

Если (Wск<0), то соответственно отрезок невидим.

2. Частный случай расположения отрезка

Выполняем процедуру нахождения точек пересечения с границами отсекателя.

В итоге получим 2 точки(отмечены на рисунке). Точка t2 определяет конец видимой части,

Т.к отрезок ориентирован от точки p3 к точке p4, а внутренняя нормаль ко 2ой границе будет направлена навстречу, значит произведение будет отрицательным и найденная точка пересечения будет определять

конец видимой части отрезка. Начало видимой части будет определять точка t1.

Формально будет получено 2 значения параметра, расположенные в интервале от 0 до 1.

Если не выполнить проверку, которая заключается в том, что начало видимой части должно располагаться до её конца, мы получим неверный результат.

То есть, найдя все точки пересечения, необходимо выполнить проверку, т. e убедиться в том, что tn<=tk.

3. Еще один случай

Рассматриваем отрезок p1p2.

При нахождении пересечения с первой границей, мы найдем значения параметра t>1.

Возникает вопрос.Найденная точка относится к началу или к концу видимой части отрезка?

Поскольку Dск>0, найденную точку пересечения надо отнести к началу видимой части.

Но начало видимой части определяется как максимальное значение из массива параметров t, определяющих начало видимой части отрезка. Раз берем максимум, в дальнейшем значение параметра, определяющее начало видимой части отрезка, будет сохранять своё значение t>1.

Из этого можно сразу сделать вывод о том, что отезок является полностью невидимым, т.к. начало видимой части расположено за концом отрезка.

Рассматриваем отрезок p3p4.

Ситуация схожа.

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

Найдем значение параметра t<0.Куда отнести найденную точку пересечения? Это пересечение надо отнести к концу видимой части отрезка.(Dск<0)

Концу видимой части отрезка будет соответствовать минимальное из тех параметров t, которые определяют конец видимой части. Если на данном шаге t<0, то и в дальнейшем t не сможет принять положительное или нулевое значение.

Видимая часть прямой, проходящей через отрезок, расположена до начала рассматриваемого отрезка. Отрезок является полностью невидимым.