6 . Алгоритмы отсечения отрезков
Ц ель: Изучить алгоритмы отсечения отрезков
Отсечение – процесс выделения некоторой базы данных.
Используется:
при выделении окна;
при выходе изображения за границы экрана;
для устранения ступенчатости изображения.
Отсекаемые отрезки могут быть трех классов: целиком видимые, целиком невидимые и пересекающие окно. Очевидно, что целесообразно возможно более рано, без выполнения большого объема вычислений принять решение о видимости целиком или отбрасывании. По способу выбора решения существует два основных типа алгоритмов отсечения – алгоритмы, использующие кодирование концов отрезка или всего отрезка (алгоритм Коэна-Сазерленда (Cohen-Sutherland, CS-алгоритм) и FC-алгоритм (Fast Clipping-алгоритм)) и алгоритмы, использующие параметрическое представление отрезков и окна отсечения (алгоритм Кируса-Бека (Curus-Beck, CB-алгоритм) и алгоритм Лианга-Барски (Liang-Barsky, LB-алгоритм)). Алгоритмы с кодированием применимы для прямоугольного окна, стороны которого параллельны осям координат, а алгоритмы с параметрическим представлением применимы для произвольного окна.
6.1. Двумерный алгоритм Коэна-Сазерленда
Вся область экрана делится на 9 частей (рис. 6.1). Для определения, к какой из девяти областей принадлежит конец отрезка, вводится 4-х битовый код; биты считаются справа и единица ставится в бит, если:
1 бит – точка левее окна;
2 бит – точка правее окна;
3 бит – точка ниже окна;
4 бит – точка выше окна.
Центральная область имеет код – 0000.
1001 |
1000 |
1010 |
0001 |
0000 |
0010 |
0101 |
0100 |
0110 |
Рис. 6.1. Задание кодов областей для алгоритма Коэна-Сазерленда
Отсюда алгоритм: если коды обоих концов отрезка равны 0000, то отрезок полностью видим (и мы изображаем его), если побитовое логическое произведение кодов концов отрезка не равно нулю, то отрезок полностью невидим (и мы отбрасываем его), иначе – отрезок или виден частично, или целиком невидим. В последнем случае ищется пересечение отрезка со сторонами окна либо параметрическим способом, либо методом разбиения средней точкой.
6.2. Двумерный fc-алгоритм
В данном алгоритме кодируется весь отрезок целиком. Схема кодирования близка к используемой в алгоритме Коэна-Сазерленда. Все пространство экрана разбивается на 9 частей и они кодируются цифрами от 1 до 9 (рис. 6.2). Отрезок кодируется следующим образом:
LineCode(V0V1) = Code(V0)*16 + Code(V1),
где Code(V1) – код конечной точки;
Code(V0) – код начальной точки,
*16 – означает сдвиг влево на 4 разряда,
LineCode(V0V1) – код отрезка.
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Рис. 6.2. Задние кодов областей для FC-алгоритма
Так как каждый код может принимать только девять значений, то имеется 81 возможный вариант расположения отрезка и требуется свой набор вычислений для определения отсечения отрезка за минимальное время. Однако, имеется всего 8 основных случаев отсечения, остальные симметричны им. Иллюстрации для случаев 1-7 приведены на рис. 6.3, а для случая 8 – на рис. 6.4. Итак:
Случай 1 – начальная и конечная точки отрезка находятся в области 4 (отрезок LA, LineCode(V0V1) = 44). Отрезок не пересекает видимую область и отбрасывается.
Случай 2 – начальная точка находится в области 4, конечная – в области 1 (отрезок LB, LineCode(V0V1) = 41). Отрезок не пересекает видимую область и отбрасывается.
Случай 3 – начальная точка находится в области 4, конечная – в области 2 (отрезки LC и LD, LineCode(V0V1) = 42). Отрезок явно пересекает Xлев. Вычисляем точку пересечения отрезка с левым ребром – (Xлев, Yп). Eсли Yп > Yверхн, то
Рис. 6.3 Варианты расположения отрезка для неугловых областей (FC-алгоритм)
Рис. 6.4. Варианты расположения отрезка для угловых областей (FC-алгоритм)
это отрезок LC, он не пересекает видимую область и отбрасывается. Иначе, это отрезок LD, пересекающий видимую область и необходимо вычислить точку пересечения отрезка с Yверхн и изобразить видимую часть отрезка.
Случай 4 – начальная точка находится в области 4, конечная – в области 3 (отрезки LE, LF и LG, LineCode(V0V1) = 43). Вычисляем точку пересечения с левым ребром – (Xлев, Yп1). Eсли Yп1 > Yверхн, то это отрезок LE, он не пересекает видимую область и отбрасывается, иначе это отрезки LF или LG. Вычисляем точку пересечения с правым ребром (Xправ, Yп2). Eсли Yп2 > Yверхн, то это отрезок LF и необходимо вычислить точку пересечения с верхним ребром и изобразить видимую часть отрезка. Иначе это отрезок LG, точки пересечения с левым и правым ребрами известны, следовательно, изображаем видимую часть отрезка.
Случай 5 – начальная точка находится в области 4, конечная – в области 6 (отрезок LH, LineCode(V0V1) = 46). Вычисляем точки пересечения с левым и правым ребрами и изображаем видимую часть отрезка.
Случай 6 – начальная точка находится в области 4, конечная – в области 5 (отрезок LI, LineCode(V0V1) = 45). Вычисляем точку пересечения с левым ребром и изображаем видимую часть отрезка.
Случай 7 – начальная точка находится в области 5, конечная – в области 5 (отрезок JK, LineCode(V0V1) = 55). Отрезок полностью видим, изображаем его.
Случай 8 – начальная точка находится в области 7, конечная – в области 3 (отрезки RW, SX, SY, TX,TY,UZ LineCode(V0V1) = 73). Вычисляем точку пересечения с левым ребром – (Xлев, Yп1). Eсли Yп1 > Yверхн, то это отрезок RW, он не пересекает видимую область и отбрасывается. Вычисляем точку пересечения с правым ребром ребром – (Xправ, Yп2). Eсли Yп2 < Yнижн, то это отрезок UZ, он не пересекает видимую область и отбрасывается. Если Yп1 > Yнижн, то начальная точка S и если Yп2 < Yвехн, то это отрезок SY и мы изображаем его видимую часть, иначе, это отрезок SX, вычисляем точку пересечения с верхней стороной и также изображаем видимую часть отрезка. Оставшийся вариант – начальная точка T и если Yп2 < Yвехн, то это отрезок TY и мы изображаем его видимую часть, иначе, это отрезок TX, вычисляем точку пересечения с верхней стороной и также изображаем видимую часть отрезка.