Алгоритм Коэна-Сазерленда эффективно решает задачу отсечения. Эта задача заключается в удалении элементов изображения, лежащих вне заданной прямоугольной области (рис. 1), называемой далее окном вывода.
Рис. 1. Задача отсечения: а - коды областей; б - решение задачи отсечения
В случае полигональных моделей отсечение выполняется многократно и для большого числа отрезков, поэтому важно, чтобы алгоритм отсечения обладал высоким быстродействием.
Изображение выводится на растровую плоскость с целочисленными координатами, что позволяет употребить для них тип INTEGER(2).
Окно вывода разбивает своими сторонами и их продолжениями растровую плоскость на 9 областей. В алгоритме Коэна-Сазерленда для каждой области разбиения устанавливается 4-битовый код (см. рис. 1, а), в котором:
Пусть 1 и 2 - номера вершин отрезка; c1 и c2 - коды областей расположения этих вершин. Пусть также XL, XR, YB, YT - координаты границ указанного в видовом порте окна вывода. Очевидно, что
Для сокращения кода прежде выполняются все отсечения для вершины 1, а затем нумерация вершин изменяется: вершине 2 дается номер 1, а вершине 1 - номер 2. Далее вновь продолжается исследование вершины 1.
Запишем алгоритм отсечения в виде линейной схемы.
Интерфейс.
Входные данные.
XL, XR - x-координаты правой и левой границ окна вывода;
YB, YT - y-координаты нижней и верхней границ окна вывода;
x1, y1 и x2, y2 - координаты вершин отрезка.
Выходные данные.
x1, y1 и x2, y2 - координаты вершин усеченного отрезка (или исходного, если отрезок целиком принадлежит окну вывода) после решения задачи отсечения. В случае расположения отрезка вне окна вывода выведем сообщение "Отрезок вне окна".
Промежуточные данные.
c1 и c2 - коды областей расположения первой и второй вершин отрезка;
x1, y1 и x2, y2 - координаты вершин отрезка на линиях отсечения;
fl есть истина, если выполнен обмен номерами вершин отрезка.
Алгоритм.
Программа содержит две процедуры: подпрограмму swap, выполняющую обмен значений двух переменных, и функцию code, возвращающую код области, в которой расположена исследуемая вершина отрезка.
! Фортран-реализация алгоритма Коэна-Сазерленда
program clip
integer(2) :: XL = 15, XR = 60, YB = 15, YT = 60
integer(2) :: XL = 15, XR = 60, YB = 15, YT = 60
integer(2) :: x1 = 10, y1 = 10, x2 = 65, y2 = 65
integer(2) c1, c2, code
logical :: fl = .false.
c1 = code(x1, y1, XL, XR, YB, YT)
c2 = code(x2, y2, XL, XR, YB, YT)
do while(iand(c1, c2) == 0 .and. ior(c1, c2) > 0)
if(c1 == 0) then
fl = .not. fl ! Обмен вершинами отрезка
call swap(x1, x2); call swap(y1, y2); call swap(c1, c2)
endif
if(x1 < XL) then ! Отсечение слева
y1 = y1 + dfloat(y2 - y1) * dfloat(XL - x1) / dfloat(x2 - x1)
x1 = XL
else if(y1 < YB) then ! Отсечение снизу
x1 = x1 + dfloat(x2 - x1) * dfloat(YB - y1) / dfloat(y2 - y1)
y1 = YB
else if(x1 > XR) then ! Отсечение справа
y1 = y1 + dfloat(y2 - y1) * dfloat(XR - x1) / dfloat(x2 - x1)
x1 = XR
else if(y1 > YT) then ! Отсечение сверху
x1 = x1 + dfloat(x2 - x1) * dfloat(YT - y1) / dfloat(y2 - y1)
y1 = YT
endif
c1 = code(x1, y1, XL, XR, YB, YT) ! Код вершины 2 не изменился
enddo
if(fl) then ! Обмен номерами вершин отрезка
call swap(x1, x2)
call swap(y1, y2)
call swap(c1, c2)
endif
if(ior(c1, c2) == 0) then
write(*, 1) x1, y1, x2, y2 ! x1, y1: 15, 15; x2, y2: 60, 60
else
write(*, *) ' Отрезок вне окна вывода '
endif
1 format(' x1, y1:', i4,',',i4, '; x2, y2:', i4,',',i4)
end program clip
subroutine swap(a, b)
integer(2) a, b, hold
hold = a; a = b; b = hold
end subroutine swap
! Вычисление кода области расположения вершины с координатами x, y
function code(x, y, XL, XR, YB, YT) result(vcode)
integer(2) x, y, XL, XR, YB, YT, vcode
vcode = 0
if(x < XL) vcode = ior(vcode, 2#1000)
if(y < YB) vcode = ior(vcode, 2#0001)
if(x > XR) vcode = ior(vcode, 2#0010)
if(y > YT) vcode = ior(vcode, 2#0100)
end function code
Шикин Е. В., Боресков А. В. Компьютерная графика. Полигональные модели. - М.: ДИАЛОГ-МИФИ, 2000. - 464 с.