Алгоритм Сазерленда-Коэна

Важность и постановка задачи двумерного отсечения

Задача растеризации

● Вход: надпись, шрифт, кодировка, координаты

● Выход: растр

Причины, по которым задача отрисовки важна:

1 Время. Если примитив выходит за пределы экрана, то он не будет виден, однако время на его отрисовку всё равно будет потрачено.

2 Артефакты. В памяти компьютера изображение хранится в виде последовательности массивов-строк. Если в программе отсутствуют проверки на выход за границы массива, то при попытке доступа к участку изображения за его пределами могут возникнуть графические артефакты. Например, при отрисовке пикселя, находящегося за пределами экрана справа, он будет нарисован слева строкой ниже.

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

Параметры отсечения:

● Отсекаемая фигура (примитив, который рисуем)

● Отсекающая фигура (примитив, который задаёт видимую часть; окно видимости)

● Вид отсечения:

○ Внешнее — оставляем всё, что вне отсекающей фигуры.

○ Внутреннее — оставляем всё, что внутри отсекающей фигуры.

Это алгоритм внутреннего отсечения отрезка прямоугольным окном. Продлевая границы окна видимости, получаем девять частей, каждая из которых кодируется четырёхбитным кодом: ● Бит #1 = (область строго левее отсекающего окна) ● Бит #2 = (область строго правее отсекающего окна) ● Бит #3 = (область строго выше отсекающего окна) ● Бит #4 = (область строго ниже отсекающего окна)

Пусть A и B — коды, соответствующие концам отрезка. Тогда:

Условие	Пояснение	Вывод
(A OR B) = 0	Коды содержат только нули, то есть оба кода — 0000.	Отрезок полностью виден
(A AND B) ≠ 0	Коды содержат единичный бит в одной и той же позиции.	Отрезок полностью не виден
(A AND B) = 0	В каждом разряде одного из кодов есть ноль.	Отрезок частично видим. Переносим точку, у которой код ≠ 0, в место пересечения отрезка с одной из границ (например, если включен 1й бит, то с левой, если 2й, то с правой и т.д.) и повторяем алгоритм.

В результате от отрезка останется только видимая часть.

Недостатки:

● При вычислении точки пересечения отрезка и прямой используется медленная вещественная арифметика

● В некоторых случаях для получения ответа требуется несколько итераций