Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Графика / Отсечение отрезка /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Двумерный FC-алгоритм - Программирование от RIN.RU
Двумерный FC-алгоритм

В 1987 г. Собков, Поспишил и Янг [37] предложили алгоритм, названный ими FC-алгоритмом (Fast Clipping), также использующий кодирование, но не конечных точек, а линий целиком. Приведенное далее изложение алгоритма следует статье [7].


Схема кодирования близка к используемой в алгоритме Коэна-Сазерленда (рис. 0.2.4). Пространство разбивается на 9 неперекрывающихся областей, пронумерованных арабскими цифрами от 1 до 9. Коды, назначаемые концам отрезков, попавших в ту или иную область, приведены в двоичном и шестнадцатиричном виде (запись вида 0xD).



Рисунок 30
Рис. 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.



  1. Начальная и конечная точки отрезка обе в области 5 (отрезок JK). Это простой случай принятия отрезка.

  2. Начальная и конечная точки отрезка обе в области 4 (отрезок LA). Отрезок не пересекает видимую область, так что это простой случай
    отбрасывания.

  3. Начальная точка в области 4, конечная - в области 1 (отрезок LB). Отрезок не пересекает видимую область, так что это простой случай
    отбрасывания.

  4. Начальная точка в области 4, конечная - в области 2 (отрезки LC и LD). Отрезки явно пересекает Xлев, так что вначале надо определить
    соответствующую координату, используя алгоритм Clip0_Xleft. Для отрезка LC это дает V0y > Yверх, так что отрезок должен быть отброшен без дальнейших вычислений. Отрезок LD входит в окно с левой стороны и может выходить через верх. Следовательно, следующее отсечение должно быть Clip1_Top, после которого отрезок принимается.

  5. Начальная точка в области 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. Отсечение закончено, отрезок принимается.

  6. Начальная точка в области 4, конечная - в области 6 (отрезок LH). Данный отрезок видим. Вначале используем Clip0_Xleft затем Clip1_Right и принимаем отрезок.

  7. Начальная точка в области 4, конечная - в области 5 (отрезок LI). Данный отрезок видим. Просто используем Clip0_Xleft и принимаем
    отрезок.

  8. Начальная точка 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.



Рисунок 31
Рис. 0.2.5: Варианты расположения отрезка для неугловых областей





Рисунок 32
Рис. 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  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь