В 1987 г. Собков, Поспишил и Янг [37] предложили алгоритм, названный ими FC-алгоритмом (Fast Clipping), также использующий кодирование, но не конечных точек, а линий целиком. Приведенное далее изложение алгоритма следует статье [7].
Схема кодирования близка к используемой в алгоритме Коэна-Сазерленда (рис. 0.2.4). Пространство разбивается на 9 неперекрывающихся областей, пронумерованных арабскими цифрами от 1 до 9. Коды, назначаемые концам отрезков, попавших в ту или иную область, приведены в двоичном и шестнадцатиричном виде (запись вида 0xD).
Рис. 0.2.4: Задание кодов для FC-алгоритма
Отрезок видим только в области 5, т.е. отрезок, координаты которого удовлетворяют условиям:
Xлев ? X ? Xправ и Yниз ? Y ? Yверх. |
|
Каждая конечная точка отрезка V0V1 окажется с одной из этих областей. Комбинация кодов концов отрезка, называемая кодом линии, используется для определения возможных вариантов расположения отрезка и, следовательно, отсечения. Код линии формируется из кодов концов отрезка следующим образом:
LineCode (V0,V1) = (Code(V0) ×16) + Code (V1), |
|
здесь Code(V1) обозначает код конечной точки V1, Code(V0) × 16 означает сдвиг кода начальной точки V0 влево на 4 разряда.
Так как каждый код может принимать одно из 9 значений, то всего имеется 81 возможный вариант расположения отрезка. Но, если Code(V0) равен Code(V1), то LineCode(V0,V1) равен LineCode V1,V0). Имеется всего 9 таких случаев: 1-1, 2-2, ? 9-9. Следовательно, число различных случаев уменьшается до 72.
Каждый LineCode требует своего набора вычислений для определения отсечения отрезка за минимальное время. Всего имеется 8 основных случаев отсечения, а остальные симметричны к ним. Рассмотрим эти 8 основных случаев. При этом будут использоваться следующие обозначения:
начальная точка отрезка считается точкой номер 0 (V0),
конечная точка отрезка считается точкой номер 1 (V1),
ClipA_B обозначает алгоритм расчета перемещения конечной точки номер А на сторону окна B (расчет пересечения прямой линии, на которой расположен отсекаемый отрезок со стороной окна B).
Иллюстрации к случаям 1-7 приведены на рис. 0.2.5, для случая 8 - на рис. 0.2.6.
Начальная и конечная точки отрезка обе в области 5 (отрезок JK). Это простой случай принятия отрезка.
Начальная и конечная точки отрезка обе в области 4 (отрезок LA). Отрезок не пересекает видимую область, так что это простой случай отбрасывания.
Начальная точка в области 4, конечная - в области 1 (отрезок LB). Отрезок не пересекает видимую область, так что это простой случай отбрасывания.
Начальная точка в области 4, конечная - в области 2 (отрезки LC и LD). Отрезки явно пересекает Xлев, так что вначале надо определить соответствующую координату, используя алгоритм Clip0_Xleft. Для отрезка LC это дает V0y > Yверх, так что отрезок должен быть отброшен без дальнейших вычислений. Отрезок LD входит в окно с левой стороны и может выходить через верх. Следовательно, следующее отсечение должно быть Clip1_Top, после которого отрезок принимается.
Начальная точка в области 4, конечная - в области 3 (отрезки LE, LF и LG). Отрезки явно пересекает Xлев. Так же как и для случая 4 вначале применяется Clip0_Xleft и отрезок LE отбрасывается если V0y > Yверх. Если же получаем V0y ? Yверх, то отрезок должен выйти из области видимости через верхнее или правое ребро. Применяем отсечение Clip1_Top и сравниваем новое значение X-координаты конечной точки - V1x c Xправ. Если V1x ? Xправ, то отрезок (LF) проходит через верхнюю сторону, отрезок принимается и дальнейшие вычисления не нужны. Иначе отрезок (LG) проходит через правую сторону и требуется отсечение Clip1_Right. Отсечение закончено, отрезок принимается.
Начальная точка в области 4, конечная - в области 6 (отрезок LH). Данный отрезок видим. Вначале используем Clip0_Xleft затем Clip1_Right и принимаем отрезок.
Начальная точка в области 4, конечная - в области 5 (отрезок LI). Данный отрезок видим. Просто используем Clip0_Xleft и принимаем отрезок.
Начальная точка V0 (R, S, T или U) в области 7, конечная точка V1 (W, X, Y или Z) - в области 3 (см. рис.0.2.6).
В этом случае могут быть отброшены только два типа отрезков. Для минимизации вычислений используем Clip0_Xleft. Если V0y > Yверх, то это первый случай отбрасывания (отрезок RW). Clip1_Xright и проверка V1y < Yниз задают второй случай отбрасывания (отрезок UZ). Все другие отрезки должны быть видимы. Если V0y < Yниз, тогда V0 = T, иначе V0 = S. Если V0y < Yниз, то Clip1_Ybottom даст точку V0 на ребре окна. Аналогично, если V1y > Yверх, то V1=X и здесь требуется Clip1_Ytop перед приемом отрезка. Если V1y < Yверх, тогда V1 = Y.
Рис. 0.2.5: Варианты расположения отрезка для неугловых областей
Рис. 0.2.6: Случай угловых областей
Из этих восьми случаев легко симметрично сгенерировать все остальные.
Главное отличие FC-алгоритма от алгоритма Коэна-Сазерленда состоит в упорядочивании действий по отсечению. Эффективность алгоритма Коэна-Сазерленда ограничивается последовательным характером и фиксированным порядком действий по отсечению. Как пример (см. рис. 0.2.6) отрезок RW будет отсекаться в порядке: сверху, снизу, справа и слева. Число же отсечений для определения видимости равно 2 - снизу и слева. В FC-алгоритме, напротив, для каждого значения LineCode имеется свой набор действий по отсечению. Для приведенного выше примера потребуется только одно отсечение для определения невидимости отрезка RW. Кроме этого, повышению эффективности FC-алгоритма по сравнению с CS-алгоритмом способствует отсутствие ненужных циклов и, следовательно, перевычислений кодов конечных точек.
В Приложении 7 приведена C-подпрограмма V_FCclip, реализующая FC-алгоритм и свободная от ошибок в подпрограмме, приведенной в [37]. Можно заметно сократить объем ее программного кода учтя симметрию и использовав указатели на данные либо переставляя данные. Например, в подпрограмме V_FCclip для отрезка LH (см. рис. 0.2.5, если он идет слева-направо вначале выполняется отсечение для начальной точки по левой стороне окна и затем для конечной - по правой. Если же отрезок идет справа-налево, то вначале вычисляется отсечение начальной точки по правой стороне и затем конечной - по левой. Очевидно, что эти два случая идентичны если поменять местами координаты начальной и конечной точек.
8 8 8
| |