Вопросы к 15 - p1xelse/CG GitHub Wiki

Отсечение - это операция удаления изображения за пределами выделенной области, называемой окном.

Алгоритм отсекает отрезок произвольным выпуклым отсекателем.

Отрезок, вектор.

1. Рассматриваем дирректрису(вектор направления отрезка)
2. Вектор из произвольной точки ребра (обычно начальная) в начало определяемого отрезка "вектор, начинающийся в точке, лежащей на i - ом ребре окна отсечения, и заканчивающийся в любой точке исследуемого отрезка"
3. Вектор внутренней нормали.

Анализируем скалярные произведения 1 и 3, 2 и 3.

Да, может. Если отсекаемый отрезок параллелен рассматриваему ребру.(или если отрезок вырожденный)

В самом начале алгоритма t_down = 0, t_up = 1 (отрезок считается полностью видимым).

Далее во время работы алгоритма
при вычислении начала видимой части будем получать t < 0
при вычислении конца видимой части t > 1.

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

Концом видимой части считается минимальное значение среди всех параметров,
определяющих конец видимой части, а так как они все получаться t ≥1, то
минимальное значение конца видимой части будет равно 1.

Получается, что t_down = 0, t_up = 1 и выполняется условие
фактической видимости отрезка t_down <= t_up
(начало видимой части отрезка расположено до конца видимой части),
поэтому отрезок является полностью видимым.

А при невидимом
При проверке пересечения с какой-то из сторон значение t
получится больше 1, а значение D * Ni (scalarD) будет больше 0.
Значит начало границы видимости расположено ближе к началу отрезка (scalarD > 0),
но при этом на продолжении отрезка (t > 1) => отрезок невиден

Задача - отсечение выпуклым отсекателем отрезков.

Параметрическое уравнение отрезка, векторы: директриса(вектор направления отрезка), вектор из произвольной точки ребра (на самом деле выбирается одна из вершин ребра) в начало определяемого отрезка "вектор, начинающийся в точке, лежащей на i - ом ребре окна отсечения, и заканчивающийся в любой точке исследуемого отрезка", вектор внутренней (но можно реализовать и со внешней) нормали. С векторами - векторное произведение (для проверки на выпуклость ещё до алгоритма) и скалярные в самом алгоритме.

Не очень понятно, что Куров вообще хочет услышать на эту тему, но вот типа два подхода (озвучьте оба): 1) В целом может быть не более двух точек пересечения отрезка с отсекателем. 2) Для каждого ребра отсекателя может быть найдено пересечение отрезка с самим ребром или его продолжением (или не найдено вообще). То есть всего будет найдено не более n точек пересечения (где n - кол-во рёбер отсекателя).

Суть в том, что в итоге для отрезка у нас получается два набора точек пересечения (две группы). Они называются верхней и нижней. Нижняя - точки пересечения, ближе к началу отрезка - определяют начало видимости отрезка. Верхняя - ближе к концу - определяют конец видимости отрезка. Из нижней группы мы выбираем максимум. Из верхней - минимум. Это и будут границы видимости. То есть по сути нужна сортировка, но она не происходит явно, так как на каждом шаге мы релаксируем (обновляем) значение миниму и максимума.

К: Какая задача с помощью него решается?
С: Задача отсечения выпуклым отсекателем отрезков.

К: Какие математические объекты в нем используются?
С: Отрезок (заданный параметрически), три вектора:

• вектор внутренней нормали,
• вектор, который соединяет первую точку отрезка с произвольной точкой ребра отсекателя, в качестве произвольной берем первую точку ребра отсекателя,
• директриса отрезка (отсекаемого)

К: Какие операции проводили с векторами?
С: Два скалярных произведения: нормали на директрису и директрисы на вектор, соединяющий первую точку отрезка с первой точкой ребра. Анализ знаком скалярного произведения.

К: Сколько точек пересечения мы можем найти по ходу алгоритма?
С: Столько же, сколько ребер отсекателя.
К: А в результате алгоритма?
С: Две. Начало и конец видимой части.

К: Все найденные точки пересечения мы должны как-то отсортировать на две группы. Как мы их сортируем?
С: По скалярному произведению векторов директрисы и нормали. Если знак произведения больше 0 - относим данную точку пересечения к начальным, если меньше - к конечным.

К: Вот разбили на две групп. Из каждой группы надо выбрать одну итоговую точку. Как?
С: Из группы нижних точек берем наибольшую, из группы верхних - наименьшую.

К: Как распознается невидимость отрезка какой-то пример с бланка.
С: Тут параметр начальной точки видимой части больше 1.

К: А что с видимым еще пример - как распознается полная видимость.
С: По ходу алгоритма начальные значения для параметров начала и конца - 0 и 1 - сохранятся. Потому что найденные точки пересечения-начала будут <= 0 - наибольшим останется 0 - исходное значение, соответствующее первой точке отрезка. Найденные точки пересечения-конца будут >= 1 - наименьшей останется 1 - исходное значение, соответствующее концу отрезка.

К: Как определяется параметр t?
С:

К: Что такое Dck и Wck?
С: Dck - скалярное произведение директрисы отрезка на внутреннюю нормаль к текущей границе отсекателя. Wck - скалярное произведение внутренней нормали к текущей границе отсекателя на вектор, соединяющий первую точку отрезка с произвольной точкой текущей границы отсекателя.

К: Как обрабатывается когда отрезок ребру параллелен?
C: Необходимо узнать, расположен он по видимую или по невидимую сторону от текущей границы: если отрезок расположен по невидимую сторону от текущей границы – он полностью невидим, мы можем завершать алгоритм.
Для определения видимости отрезка, параллельного текущей границе отсекателя, достаточно определить видимость относительно этой границы произвольной точки отрезка. Поскольку к этому моменту у нас уже посчитано Wi – воспользуемся им для определения видимости всего параллельного отрезка: если Wi < 0, то отрезок, параллельный текущей границе отсекателя невидим.

К: является ли точка частным случаем отрезка
С: Да
К: Что в таком случае будет делать алгоритм?
С: Этот случай может быть обработан до запуска цикла отсечения или уже внутри: проверяем точку на видимость, в случае видимости – выводим и завершаем алгоритм. В случае невидимости - просто завершаем алгоритм.

К: Может возникнуть ситуация когда t ∉ [0, 1] - почему так случается?
С: Алгоритм ищет t как точку пересечения прямых, проходящих через вектор директрисы и границу отсекателя. Если полученная точка пересечения этих прямых не принадлежит интервалу [0,1], то она не принадлежит отрезку. В этом случае мы отбрасываем точку пересечения.