Новосибирский Государственный Технический Университет. Факультет автоматики и вычислительной техники Кафедра вычислительной техники (специальность 220100). учебное пособие

Вид материала

Учебное пособие

Содержание 0.6.1  Двумерный алгоритм Коэна-Сазерленда 0.6.2  Двумерный FC-алгоритм

Подобный материал:

• Новосибирский Государственный Технический Университет. Факультет автоматики и вычислительной, 1650.9kb.
• Рабочая программа для специальности: 220400 Программное обеспечение вычислительной, 133.96kb.
• Государственный Технический Университет. Факультет: Автоматики и Вычислительной Техники., 32.46kb.
• Образования Республики Молдова Колледж Микроэлектроники и Вычислительной Техники Кафедра, 113.64kb.
• Постоянное развитие и углубление профессиональных навыков в области информационных, 54.56kb.
• «Программное обеспечение вычислительной техники и автоматизированных систем», 1790.14kb.
• Задачи дисциплины: -изучение основ вычислительной техники; -изучение принципов построения, 37.44kb.
• Лекция №2 «История развития вычислительной техники», 78.1kb.
• Система контроля и анализа технических свойств интегральных элементов и устройств вычислительной, 582.84kb.
• Московский государственный инженерно-физический институт (технический университет), 947.05kb.

0.6.1  Двумерный алгоритм Коэна-Сазерленда

Этот алгоритм позволяет быстро выявить отрезки, которые могут быть или приняты или отброшены целиком. Вычисление пересечений требуется когда отрезок не попадает ни в один из этих классов. Этот алгоритм особенно эффективен в двух крайних случаях:

 большинство примитивов содержится целиком в большом окне,

 большинство примитивов лежит целиком вне относительно маленького окна.

Идея алгоритма состоит в следующем:

Окно отсечения и прилегающие к нему части плоскости вместе образуют 9 областей (рис. 0.2.3). Каждой из областей присвоен 4-х разрядный код.

Две конечные точки отрезка получают 4-х разрядные коды, соответствующие областям, в которые они попали. Смысл разрядов кода:

1 рр = 1 - точка над верхним краем окна;

2 рр = 1 - точка под нижним краем окна;

3 рр = 1 - точка справа от правого края окна;

4 рр = 1 - точка слева от левого края окна.

Определение того лежит ли отрезок целиком внутри окна или целиком вне окна выполняется следующим образом:

 если коды обоих концов отрезка равны 0 то отрезок целиком внутри окна, отсечение не нужно, отрезок принимается как тривиально видимый (отрезок AB на рис. 0.2.3);

 если логическое & кодов обоих концов отрезка не равно нулю, то отрезок целиком вне окна, отсечение не нужно, отрезок отбрасывается как тривиально невидимый (отрезок KL на рис. 0.2.3);

 если логическое & кодов обоих концов отрезка равно нулю, то отрезок подозрительный, он может быть частично видимым (отрезки CD, EF, GH) или целиком невидимым (отрезок IJ); для него нужно определить координаты пересечений со сторонами окна и для каждой полученной части определить тривиальную видимость или невидимость. При этом для отрезков CD и IJ потребуется вычисление одного пересечения, для остальных (EF и GH) - двух.

При расчете пересечения используется горизонтальность либо вертикальность сторон окна, что позволяет определить координату X или Y точки пересечения без вычислений.




Рис. 0.2.3: Отсечение по методу Коэна-Сазерленда

При непосредственном использовании описанного выше способа отбора целиком видимого или целиком невидимого отрезка после расчета пересечения потребовалось бы вычисление кода расположения точки пересечения. Для примера рассмотрим отрезок CD. Точка пересечения обозначена как P. В силу того, что граница окна считается принадлежащей окну, то можно просто принять только часть отрезка PD, попавшую в окно. Часть же отрезка CP, на самом деле оказавшаяся вне окна, потребует дальнейшего рассмотрения, так как логическое И кодов точек C и P даст 0, т.е. отрезок CP нельзя просто отбросить. Для решения этой проблемы Коэн и Сазерленд предложили заменять конечную точку с ненулевым кодом конца на точку, лежащую на стороне окна, либо на ее продолжении.

В целом схема алгоритма Коэна-Сазерленда следующая:

1. Рассчитать коды конечных точек отсекаемого отрезка.
   

В цикле повторять пункты 2-6:

2. Если логическое И кодов конечных точек не равно 0, то отрезок целиком вне окна. Он отбрасывается и отсечение закончено.
   
3. Если оба кода равны 0, то отрезок целиком видим. Он принимается и отсечение закончено.
   
4. Если начальная точка внутри окна, то она меняется местами с конечной точкой.
   
5. Анализируется код начальной точки для определения стороны окна с которой есть пересечение и выполняется расчет пересечения. При этом вычисленная точка пересечения заменяет начальную точку.
   
6. Определение нового кода начальной точки.
   

Эта схема реализована в процедуре V_CSclip, приведенной в Приложении 7.

0.6.2  Двумерный FC-алгоритм

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

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




Рис. 0.2.4: Задание кодов для FC-алгоритма

Отрезок видим только в области 5, т.е. отрезок, координаты которого удовлетворяют условиям:

Xлев  X  Xправ     и    Yниз  Y  Yверх.

Каждая конечная точка отрезка V₀V₁ окажется с одной из этих областей. Комбинация кодов концов отрезка, называемая кодом линии, используется для определения возможных вариантов расположения отрезка и, следовательно, отсечения. Код линии формируется из кодов концов отрезка следующим образом:

LineCode (V0,V1)    =   (Code(V0) ×16) + Code (V1),

здесь Code(V₁) обозначает код конечной точки V₁,
Code(V₀) × 16 означает сдвиг кода начальной точки V₀ влево на 4 разряда.

Так как каждый код может принимать одно из 9 значений, то всего имеется 81 возможный вариант расположения отрезка. Но, если Code(V₀) равен Code(V₁), то LineCode(V₀,V₁) равен LineCode(V₁,V₀). Имеется всего 9 таких случаев: 1-1, 2-2,  9-9. Следовательно, число различных случаев уменьшается до 72.

Каждый LineCode требует своего набора вычислений для определения отсечения отрезка за минимальное время. Всего имеется 8 основных случаев отсечения, а остальные симметричны к ним. Рассмотрим эти 8 основных случаев. При этом будут использоваться следующие обозначения:

 начальная точка отрезка считается точкой номер 0 (V₀),

 конечная точка отрезка считается точкой номер 1 (V₁),

 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 это дает V₀y > Yверх, так что отрезок должен быть отброшен без дальнейших вычислений. Отрезок LD входит в окно с левой стороны и может выходить через верх. Следовательно, следующее отсечение должно быть Clip1_Top, после которого отрезок принимается.

5. Начальная точка в области 4, конечная - в области 3 (отрезки LE, LF и LG). Отрезки явно пересекает Xлев. Так же как и для случая 4 вначале применяется Clip0_Xleft и отрезок LE отбрасывается если V₀y > Yверх. Если же получаем V₀y  Yверх, то отрезок должен выйти из области видимости через верхнее или правое ребро. Применяем отсечение Clip1_Top и сравниваем новое значение X-координаты конечной точки - V₁x c Xправ. Если V₁x  Xправ, то отрезок (LF) проходит через верхнюю сторону, отрезок принимается и дальнейшие вычисления не нужны. Иначе отрезок (LG) проходит через правую сторону и требуется отсечение Clip1_Right. Отсечение закончено, отрезок принимается.

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

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

8. Начальная точка V₀ (R, S, T или U) в области 7, конечная точка V₁ (W, X, Y или Z) - в области 3 (см. рис.0.2.6). В этом случае могут быть отброшены только два типа отрезков. Для минимизации вычислений используем Clip0_Xleft. Если V₀y > Yверх, то это первый случай отбрасывания (отрезок RW). Clip1_Xright и проверка V₁y < Yниз задают второй случай отбрасывания (отрезок UZ). Все другие отрезки должны быть видимы. Если V₀y < Yниз, тогда V₀ = T, иначе V₀ = S. Если V₀y < Yниз, то Clip1_Ybottom даст точку V₀ на ребре окна. Аналогично, если V₁y > Yверх, то V₁=X и здесь требуется Clip1_Ytop перед приемом отрезка. Если V₁y < Yверх, тогда V₁ = 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, если он идет слева-направо вначале выполняется отсечение для начальной точки по левой стороне окна и затем для конечной - по правой. Если же отрезок идет справа-налево, то вначале вычисляется отсечение начальной точки по правой стороне и затем конечной - по левой. Очевидно, что эти два случая идентичны если поменять местами координаты начальной и конечной точек.