exam12

12. Двумерное отсечение. Простой алгоритм отсечения отрезка.

Отсечение

Отсечение – операция удаления части изображения, находящейся за пределами выделенной области, называемой отсекателем. Отсечение используется в алгоритмах удаления невидимых линий поверхностей и в некоторых алгоритмах учёта теней, поэтому от нас не только требуется скопировать или сохранить изображение, расположенное в пределах отсекателя, но и решить геометрическую задачу нахождения геометрических характеристик изображения, чтобы использовать их при решении других задач. Также существует понятие стирания изображения – это операция удаления части изображения, находящейся в пределах заданной области (то есть отсекателя).

Само по себе отсечение может проводиться в двумерном или трёхмерном пространствах. При этом, трёхмерный случай является обобщением двумерного случая. То есть, умея решать задачу в двумерном пространстве, не составит труда реализовать и решить её и в трёхмерном пространстве.

Существует следующая классификация двумерных отсекателей:

Регулярный (стандартный) отсекатель – это отсекатель прямоугольной формы со сторонами, параллельными координатным осям.
Нерегулярный отсекатель – отсекатель формы произвольного выпуклого многоугольника.
Более сложные отсекатели – отсекатели формы произвольного невыпуклого многоугольника.

Также не будет лишним привести классификацию трёхмерных отсекателей:

Отсекатели формы прямоугольного параллелепипеда
Отсекатели формы четырёхгранной усечённой пирамиды.

Следует отметить, что границу отсекателя принято относить к внутренней области отсечения.

Отсечение отрезков регулярным отсекателем

Перед тем, как обратиться к простому алгоритму отсечения отрезка регулярным отсекателем, нам потребуется решить задачу определения принадлежности заданного отрезка к области отсечения.

На следующей картинке определены три отрезка:

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

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

x_л≤x≤x_п и y_н≤y≤y_в

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

Каждый разряд в таком коде определяет положение точки относительно каждой из границ отсекателя. Обозначим такой код буквой T.

В таком коде для каждой точки будем иметь:

T_1=1,если x<x_л,а иначе:0
T_2=1,если x>x_п,а иначе: 0
T_3=1,если y<y_н,а иначе: 0
T_4=1,если y>y_в,а иначе: 0

Стоит отметить, что в координатах экрана в условиях для T_3 и T_4 знаки строгого неравенства поменяются между собой местами, так как в этом случае y_н>y_в.

Таким образом, точка будет видима в том случае, если поразрядная сумма её кода будет равна нулю. Получается, что и отрезок будет полностью видим в том случае, если поразрядные суммы кодов концов этого отрезка равны нулю: S_1=0 и S_2=0.

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

Ниже приведены два вида полностью невидимых отрезков:

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

Для определения полной невидимости отрезков, которые располагаются относительно отсекателя вполне определённым способом (Рисунок 2: полностью ниже нижней границы отсекателя, полностью левее левой границы, полностью правее правой границы, полностью выше верхней границы), достаточно провести следующий простой тест:

Если T_I&T_II≠0,то отрезок полностью невидимый, где & - поразрядное логические «и», а T_I- код первого конца отрезка и T_II- код второго конца отрезка.

При этом мы также имеем возможность определить частичную видимость следующим простым тестом:

Если S_1=0 и S_2≠0,то отрезок заведомо частично видимый
Если S_2=0 и S_1≠0,то отрезок заведомо частично видимый

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