Вопросы к 15 - chrislvt/CG GitHub Wiki
Отсечение - это операция удаления изображения за пределами выделенной области, называемой окном.
Алгоритм отсекает отрезок произвольным выпуклым отсекателем.
Отрезок, вектор.
- Рассматриваем дирректрису(вектор направления отрезка)
- Вектор из произвольной точки ребра (обычно начальная) в начало определяемого отрезка "вектор, начинающийся в точке, лежащей на i - ом ребре окна отсечения, и заканчивающийся в любой точке исследуемого отрезка"
- Вектор внутренней нормали.
Анализируем скалярные произведения 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], то она не принадлежит отрезку. В этом случае мы отбрасываем точку пересечения.