12. Двумерное отсечение. Простой алгоритм отсечения отрезка. - p1xelse/CG GitHub Wiki

Отсечение - это операция удаления изображения за пределами выделенной области, называемой окном. Отсечение может проводиться как на плоскости, так и в пространстве.
Регулярным (стандартным) отсекателем на плоскости является прямоугольник со сторонами, параллельными координатным осям объектного пространства или экрана. Такое окно задается левым, правым, верхним и нижним двумерными ребрами.
Произвольный отсекатель - это обычно многоугольник, который может быть как выпуклым, так и невыпуклым, а также может иметь отверстия.В результате отсечения должны получиться геометрические характеристики объектов, остающихся в пределах окна отсечения в результате выполнения рассматриваемой операции.
Видимый объект - объект, целиком лежащий в области.
Невидимый объект - объект, не лежащий в области.
Частично видимый объект - объект, частично лежащий в пределах отсекателя.

Где используется

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

Блок-схема

Простой алгоритм

Ввод координат отсекателя Xл, Xпр,Yн, Yв
Ввод координат концов отрезка P1(X1,Y1), P2(X2,Y2)
Вычисление кодов концов отрезка T1, T2. Вычисление сумм кодов концов отрезка S1, S2
Установка признака видимости отрезка pr=1 (pr=1 - отрезок видимый; pr=-1 - отрезок невидимый)
Задание начального значения тангенса угла наклона отрезка m=1e30 (большое число, предполагается, что отрезок вертикальный)
Проверка полной видимости отрезка: если (S1=0)&(S2=0)=true, то отрезок видимый; выполнение в этом случае следующих действий: занесение в результат координат концов отрезка R1=P1, R2=P2 и переход к п. 31
Вычисление логического произведения кодов концов отрезка P
Проверка тривиальной невидимости отрезка: если P=0, то отрезок невидим. В этом случае установка признака pr=-1 и переход к п. 31
Проверка видимости первого конца отрезка: если S1=0 (первый конец видим), то выполнение следующих действий: R1=P1 (занесение этой вершины в результат), Q=P2 (занесение координат другой вершины в рабочую переменную Q), i=2 (номер шага отсечения), переход к п.15
Проверка видимости второго конца отрезка: если S2=0 (первый конец видим), то выполнение следующих действий: R1=P2 (занесение этой вершины в результат), Q=P1 (занесение координат другой вершины в рабочую переменную Q), i=2 (номер шага отсечения), переход к п.15
Установка начального значения шага отсечения i=0
Вычисление текущего номера шага отсечения i=i+1
Проверка завершения процедуры отсечения: если i>2, то переход к п.31
Занесение в рабочую переменную Q координат i-ой вершины Q=Pi
Определение расположения отрезка: если X2=X1 (отрезок вертикальный), то переход к п.23 (не может быть пересечения с левой и правой границами отсекателя)
Вычисление тангенса угла наклона отрезка m=(Y2-Y1)/(X2-X1)
Проверка возможности пересечения с левой границей отсекателя: если Qx>Xл (пересечения нет), то переход к п.20
Вычисление ординаты точки пересечения отрезка с левой границей отсекателя: Yр=m(Xл-Qx)+Qy
Проверка корректности найденного пересечения: если (Yр>Yн)&(Yр<Yв)=true (пересечение корректное), то выполнение следующих действий: Ri.x=Xл, Ri.y=Yр (занесение полученных координат в результат), переход к п.12
Проверка возможности пересечения отрезка с правой границей отсекателя: если Q.x<Xп (пересечения нет), то переход к п.23.
Вычисление ординаты точки пересечения с правой границей: Yр=m(Xп-Q.x)+Q.y
Проверка корректности найденного пересечения: если (Yр>Yн)&(Yр<Yв)=true (пересечение корректно), то выполнение следующих действий : Ri.x=Xп, Ri.y=Yр (занесение полученных координат в результат), переход к п.12
Проверка горизонтальности отрезка: если m=0, то переход к п.12
Проверка возможности пересечения с верхней границей отсекателя: если Q.y<Yв (пересечения нет), то переход к п.27
Вычисление абсциссы точки пересечения с верхней границей: Xр=(Yв-Q.y)/m+Q.x
Проверка корректности найденного пересечения: если Xр>Xл)&(Xр<Xп)=true (пересечение корректно), то выполнение следующих действий: Ri.x=Xр; Riy=Yв (занесение полученных координат в результат); переход к п. 12
Проверка возможности пересечения с нижней границей отсекателя: если Q.x>Yн (пересечения нет), то переход к п. 30 (вершина невидима и ни одно пересечение не является корректным, следовательно отрезок невидим)
Вычисление абсциссы точки пересечения с нижней границей: Xр=(Yн-Q.y)/m+Q.x
Проверка корректности найденного пересечения: если (Xр>Xл)&(Xр<Xп)=true (пересечение корректно), то выполнение следующих действий: Ri.x=Xр; Riy=Yн (занесение полученных координат в результат); переход к п. 12
Установка признака видимости pr=-1 (отрезок невидим полностью, так как ни одно пересечение не оказалось корректным)
Проверка признака видимости: если pr=1, то вычерчивание отрезка R1R2
Конец

Пример

Как в простом алгоритме определяется невидимость отрезков? (объяснить на примере)

Рассмотрим случай, когда нельзя доказать тривиальную невидимость отрезка.
При поиске двух пересечений мы опираемся на тот факт, что прямая может пересечь выпуклый многоугольник в двух точках. В рабочую переменную заносим точку p3, будем искать точку пересечения с левой границей, потому что она лежит по невидимую сторону. Она окажется некорректной, т.к. не будет принадлежать границе отсекателя. C правой границей не будем искать точку пересечения, т к рабочая вершина расположена по видимую сторону. Переходим к поиску пересечения с нижней границей, вершина лежит по видимую сторону, поэтому точку пересечения искать не будем. Переходим к верхней границе, вершина расположена по видимую сторону, найти пересечения не можем. Значит, ни одного корректного пересечения не было найдено. На основе того, что не найдено ни одного корректного пересечения, в этом алгоритме делается вывод о полной невидимости отрезка.

В каком случае ищется пересечение с очередной границей отсекателя?

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

Надо ли особым образом обрабатывать вертикальные и горизонтальные отрезки?

Вертикальные отрезки требуют особой обработки при поиске точек пересечения с отсекателем. Если отрезок невертикальный: при поиске точек пересечения используется тангенс угла наклона прямой, содержащей отрезок. Если отрезок вертикальный: при таком же подходе получим деление на ноль при вычислении тангенса угла наклона. Поэтому проверяем отрезок на вертикальность перед вычислением тангенса угла наклона, и если отрезок вертикальный - находим точки пересечения с верхней и нижней границами отсекателя как (x_отр, y_верх) и (x_отр, y_низ).
Горизонтальные отрезки не требуют особого подхода.

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

В таком случае отрезок может быть частично видимым, или вообще не видимым, как в примерах выше

Чем данный алгоритм отличается от алгоритма Сазерленда-Коэна?

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

В алгоритме Сазерленда-Коэна, каждый раз находя точку пересечения отрезка со стороной отсекателя, мы никаких проверок на корректность не проводим, просто отбрасываем невидимую часть отрезка. Другими словам, мы невидимую вершину, P1, после нахождения точки пересечения, перемещаем в найденную точку пересечения

В чем различие простого от средней точки?

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