 |
Графика и обработка изображений. Фракталы.
Отсечение отрезка.
Алгоритмы взяты из прекрасной книги
П.В.Вельтмандер "Машинная графика"
Если изображение выходит за пределы экрана, то на части дисплеев увеличивается время построения за счет того, что изображение строится в "уме". В некоторых дисплеях выход за пределы экрана приводит к искажению картины, так как координаты просто ограничиваются при достижении ими граничных значений, а не выполняется точный расчет координат пересечения (эффект "стягивания" изображения). Некоторые, в основном, простые дисплеи просто не допускают выхода за пределы экрана. Все это, особенно в связи с широким использованием технологии просмотра окнами, требует выполнения отсечения сцены по границам окна видимости.
В простых графических системах достаточно двумерного отсечения, в трехмерных пакетах используется трех и четырехмерное отсечение. Последнее выполняется в ранее рассмотренных однородных координатах, позволяющих единым образом выполнять аффинные и перспективные преобразования.
Программное исполнение отсечения достаточно медленный процесс, поэтому, естественно, в мощные дисплеи встраивается соответствующая аппаратура. Первое сообщение об аппаратуре отсечения, использующей алгоритм отсечения делением отрезка пополам и реализованной в устройстве Clipping Divider, появилось в 1968 г. [38]. Этот алгоритм был рассмотрен при изучении технических средств. Здесь мы рассмотрим программные реализации алгоритма отсечения.
Отсекаемые отрезки могут быть трех классов - целиком видимые, целиком невидимые и пересекающие окно. Очевидно, что целесообразно возможно более рано, без выполнения большого объема вычислений принять решение об видимости целиком или отбрасывании. По способу выбора простого решения об отбрасывании невидимого отрезка целиком или принятия его существует два основных типа алгоритмов отсечения - алгоритмы, использующие кодирование концов отрезка или всего отрезка и алгоритмы, использующие параметрическое представление отсекаемых отрезков и окна отсечения. Представители первого типа алгоритмов - алгоритм Коэна-Сазерленда (Cohen-Sutherland, CS-алгоритм) [4] и FC-алгоритм (Fast Clipping - алгоритм) [37]. Представители алгоритмов второго типа - алгоритм Кируса-Бека (Curus-Beck, CB - алгоритм) и более поздний алгоритм Лианга-Барски (Liang-Barsky, LB-алгоритм) [32].
Алгоритмы с кодированием применимы для прямоугольного окна, стороны которого параллельны осям координат, в то время как алгоритмы с параметрическим представлением применимы для произвольного окна.
Вначале мы рассмотрим алгоритм Коэна-Сазерленда, являющийся стандартом де-факто алгоритма отсечения линий и обладающий одним из лучших быстродействий при компактной реализации. Затем рассмотрим наиболее быстрый, но и чрезвычайно громоздкий FC-алгоритм. Далее рассмотрим алгоритм Лианга-Барски для отсечения прямоугольным окном с использованием параметрического представления. Быстродействие этого алгоритма сравнимо с быстродействием алгоритма Коэна-Сазерленда при большей компактности и наличии 3D и 4D реализаций. Последним рассмотрим алгоритм Кируса-Бека, который использует параметрическое представление и позволяет отсекать произвольным выпуклым окном. В заключение сравним быстродействие различных алгоритмов.
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 точки пересечения без вычислений.
При непосредственном использовании описанного выше способа отбора целиком видимого или целиком невидимого отрезка после расчета пересечения потребовалось бы вычисление кода расположения точки пересечения. Для примера рассмотрим отрезок CD. Точка пересечения обозначена как P. В силу того, что граница окна считается принадлежащей окну, то можно просто принять только часть отрезка PD, попавшую в окно. Часть же отрезка CP, на самом деле оказавшаяся вне окна, потребует дальнейшего рассмотрения, так как логическое И кодов точек C и P даст 0, т.е. отрезок CP нельзя просто отбросить. Для решения этой проблемы Коэн и Сазерленд предложили заменять конечную точку с ненулевым кодом конца на точку, лежащую на стороне окна, либо на ее продолжении.
В целом схема алгоритма Коэна-Сазерленда следующая:
- Рассчитать коды конечных точек отсекаемого отрезка.
В цикле повторять пункты 2-6:
- Если логическое И кодов конечных точек не равно 0, то отрезок
целиком вне окна. Он отбрасывается и отсечение закончено.
- Если оба кода равны 0, то отрезок целиком видим. Он принимается
и отсечение закончено.
- Если начальная точка внутри окна, то она меняется местами с
конечной точкой.
- Анализируется код начальной точки для определения стороны окна с
которой есть пересечение и выполняется расчет пересечения. При
этом вычисленная точка пересечения заменяет начальную точку.
- Определение нового кода начальной точки.
Эта схема реализована в процедуре V_CSclip, приведенной в Приложении 7.
0.6.2 Двумерный FC-алгоритм
В 1987 г. Собков, Поспишил и Янг [37] предложили алгоритм, названный ими FC-алгоритмом (Fast Clipping), также использующий кодирование, но не конечных точек, а линий целиком. Приведенное далее изложение алгоритма следует статье [37].
Схема кодирования близка к используемой в алгоритме Коэна-Сазерленда (рис. 0.2.4). Пространство разбивается на 9 неперекрывающихся областей, пронумерованных арабскими цифрами от 1 до 9. Коды, назначаемые концам отрезков, попавших в ту или иную область, приведены в двоичном и шестнадцатиричном виде (запись вида 0xD).
Отрезок видим только в области 5, т.е. отрезок, координаты которого удовлетворяют условиям:
|
Каждая конечная точка отрезка V0V1 окажется с одной из этих областей. Комбинация кодов концов отрезка, называемая кодом линии, используется для определения возможных вариантов расположения отрезка и, следовательно, отсечения. Код линии формируется из кодов концов отрезка следующим образом:
|
здесь 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.
Из этих восьми случаев легко симметрично сгенерировать все остальные.
Главное отличие FC-алгоритма от алгоритма Коэна-Сазерленда состоит в упорядочивании действий по отсечению. Эффективность алгоритма Коэна-Сазерленда ограничивается последовательным характером и фиксированным порядком действий по отсечению. Как пример (см. рис. 0.2.6) отрезок RW будет отсекаться в порядке: сверху, снизу, справа и слева. Число же отсечений для определения видимости равно 2 - снизу и слева. В FC-алгоритме, напротив, для каждого значения LineCode имеется свой набор действий по отсечению. Для приведенного выше примера потребуется только одно отсечение для определения невидимости отрезка RW. Кроме этого, повышению эффективности FC-алгоритма по сравнению с CS-алгоритмом способствует отсутствие ненужных циклов и, следовательно, перевычислений кодов конечных точек.
В Приложении 7 приведена C-подпрограмма V_FCclip, реализующая FC-алгоритм и свободная от ошибок в подпрограмме, приведенной в [37]. Можно заметно сократить объем ее программного кода учтя симметрию и использовав указатели на данные либо переставляя данные. Например, в подпрограмме V_FCclip для отрезка LH (см. рис. 0.2.5, если он идет слева-направо вначале выполняется отсечение для начальной точки по левой стороне окна и затем для конечной - по правой. Если же отрезок идет справа-налево, то вначале вычисляется отсечение начальной точки по правой стороне и затем конечной - по левой. Очевидно, что эти два случая идентичны если поменять местами координаты начальной и конечной точек.
0.6.3 Двумерный алгоритм Лианга-Барски
В 1982 г. Лианг и Барски [32] предложили алгоритмы отсечения прямоугольным окном с использованием параметрического представления для двух, трех и четырехмерного отсечения. По утверждению авторов, данный алгоритм в целом превосходит алгоритм Коэна-Сазерленда. Однако в работе [37] показывается, что это утверждение справедливо только для случая когда оба конца видимого отрезка вне окна и окно небольшое (до 50×50 при разрешении 1000×1000). Приведенное далее изложение двумерного варианта алгоритма следует, основном, работе [32].
Как уже говорилось, при 2D отсечении прямые отсекаются по 2D области, называемой окном отсечения. В частности, внутренняя часть окна отсечения может быть выражена с помощью следующих неравенств (рис. 0.2.7).
| (0.2.1) | |||||||||||||||||||||
#tth_closerowВнутренняя часть окна отсечения
Продолжим каждую из четырех границ окна до бесконечных прямых. Каждая из таких прямых делит плоскость на 2 области. Назовем "видимой частью" ту, в которой находится окно отсечения, как это показано на рис. 0.2.8. Видимой части соответствует внутренняя сторона линии границы. Невидимой части плоскости соответствует внешняя сторона линии границы.
Таким образом, окно отсечения может быть определено как область, которая
находится на внутренней стороне всех линий границ.
Отсекаемый отрезок прямой может быть преобразован в параметрическое
представление следующим образом. Пусть конечные точки отрезка есть V0
и V1 с координатами (x0,y0) и (x1,y1), соответственно. Тогда
параметрическое представление линии может быть задано следующим образом:
| (0.2.2) |
| (0.2.3) |
Или в общем виде для отрезка, заданного точками V0 и V1:
| (0.2.4) |
Для точек V0 и V1 параметр t равен 0 и 1, соответственно. Меняя t от 0 до 1 перемещаемся по отрезку V0V1 от точки V0 к точке V1. Изменяя t в интервале от -Ґ до +Ґ, получаем бесконечную (далее удлиненную) прямую, ориентация которой - от точки V0 к точке V1.
Однако вернемся к формальному рассмотрению алгоритма отсечения.
Подставляя параметрическое представление, заданное уравнениями (0.2.2) и (0.2.3), в неравенства (0.2.1), получим следующие соотношения для частей удлиненной линии, которая находится в окне отсечения:
| (0.2.5) | |||||||||||||||||||||||||||||
Заметим, что соотношения (0.2.5) - неравенства, описывающие внутреннюю часть окна отсечения, в то время как равенства определяют его границы.
Рассматривая неравенства (0.2.5), видим, что они имеют одинаковую форму вида:
| (0.2.6) |
Здесь использованы следующие обозначения:
| (0.2.7) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Вспоминая определения внутренней и внешней стороны линии границы (см. рис. 0.2.8), замечаем, что каждое из неравенств (0.2.6) соответствует одной из граничных линий (левой, правой, нижней и верхней, соответственно) и описывает ее видимую сторону. (Например, для i=1 имеем: P1·t Ј Q1 Ю -dx·t Ј x0 - XлевЮ x0 + dx·t і Xлев). Удлиним V0V1 в бесконечную прямую. Тогда каждое неравенство задает диапазон значений параметра t, для которых эта удлиненная линия находится на видимой стороне соответствующей линии границы. Более того, конкретное значение параметра t для точки пересечения есть t = Qi/Pi. Причем знак Qi показывает на какой стороне соответствующей линии границы находится точка V0. А именно, если Qi і 0, тогда V0 находится на видимой стороне линии границы, включая и ее. Если же Qi < 0, тогда V0 находится на невидимой стороне.
Рассмотрим Pi в соотношениях (0.2.7). Ясно, что любое Pi может быть меньше 0, больше 0 и равно 0.
Если Pi < 0, тогда соответствующее неравенство становится:
| (0.2.8) |
Для пояснения на рис. 0.2.10 показано пересечение с левой и правой границами при Pi < 0.
Очевидно, что диапазон значений параметра t, для которых удлиненная линия находится на видимой стороне соответствующей граничной линии, имеет минимум в точке пересечения направленной удлиненной линии, заданной вектором V0V1 и идущей с невидимой на видимую сторону граничной линии (так как только на границе t равно Qi / Pi, а в остальной части видимой стороны больше).
Аналогично, если Pi > 0, тогда соответствующее неравенство становится:
| (0.2.9) |
Для пояснения на рис. 0.2.11 показано пересечение с левой и правой границами при Pi > 0.
Так как значения параметра t только на границе равны Qi/Pi, а в остальной видимой части меньше Qi/Pi, то значение параметра t имеет максимум на границе.
Наконец, если Pi = 0, тогда соответствующее неравенство превращается в:
| (0.2.10) |
Заметим, что здесь нет зависимости от t, т.е. неравенство выполняется для всех t, если Qi і 0 и не имеет решения при Qi < 0. Для пояснения на рис. 0.2.12 иллюстрируется случай Pi = 0.
Геометрически, если Pi = 0, то нет точек пересечения
удлиненной линии, определяемой точками V0V1, с линиями границы.
Более того, если Qi < 0, то удлиненная линия находится на
внешней стороне линии границы, а при Qi і 0 находится на
внутренней стороне (включая ее). В последнем случае отрезок V0V1
может быть видим или нет в зависимости от того где находятся точки
V0V1 на удлиненной линии. В предыдущем же случае нет видимого
сегмента, так как удлиненная линия вне окна, т.е. это случай
тривиального отбрасывания.
Все эти случаи суммированы на блок-схеме, представленной на рис. 0.2.13.
Итак, рассмотрение четырех неравенств дает диапазон значений параметра t, для которого удлиненная линия находится внутри окна отсечения. Однако, отрезок V0V1 только часть удлиненной линии и он описывается значениями параметра t в диапазоне: 0 Ј t Ј 1. Таким образом, решение задачи двумерного отсечения эквивалентно решению неравенств (0.2.6) при условии 0 Ј t Ј 1. Решение этой задачи сводится к далее описанному отысканию максимумов и минимумов.
Вспомним, что для всех i таких, что Pi < 0, условие видимости имеет вид: t і Qi / Pi. Из условия принадлежности точек удлиненной линии отрезку V0V1 имеем t і 0. Таким образом, нужно искать:
| (0.2.11) |
Аналогично, для всех i таких что Pi > 0, условие видимости - t Ј Qi / Pi и, следовательно, Ј 1.
| (0.2.12) |
Наконец, для всех i, таких что Pi = 0 следует проверить знак Qi. Если Qi < 0, то это случай тривиального отбрасывания, задача отсечения решена и дальнейшие вычисления не нужны. Если же Qi і 0, то информации, даваемой неравенством, недостаточно и это неравенство игнорируется.
Правая часть неравенств (0.2.11) и (0.2.12) - значения параметра t, соответствующие началу и концу видимого сегмента, соответственно. Обозначим эти значения как t0 и t1:
| (0.2.13) | |||||||||||||||||||||
Если сегмент отрезка V0V1 видим, то ему соответствует интервал параметра:
| (0.2.14) |
Следовательно, необходимое условие видимости сегмента:
| (0.2.15) |
Но это недостаточное условие, так как оно игнорирует случай тривиального отбрасывания при Pi = 0, если Qi < 0. Тем не менее это достаточное условие для отбрасывания, т.е. если t0 > t1, то отрезок должен быть отброшен. Алгоритм проверяет, если Pi = 0 c Qi < 0, или t0 > t1 и в этом случае отрезок немедленно отбрасывается без дальнейших вычислений.
В алгоритме t0 и t1 инициализируются в 0 и 1, соответственно. Затем последовательно рассматривается каждое отношение Qi/Pi.
Если Pi < 0, то отношение вначале сравнивается с t1 и, если оно больше t1, то это случай отбрасывания. В противном случае оно сравнивается с t0 и, если оно больше, то t0 должно быть заменено на новое значение.
Если Pi > 0, то отношение вначале сравнивается с t0 и, если оно меньше t0, то это случай отбрасывания. В противном случае оно сравнивается с t1 и, если оно меньше, то t1 должно быть заменено на новое значение.
Наконец, если Pi = 0 и Qi < 0, то это случай отбрасывания.
На последнем этапе алгоритма, если отрезок еще не отброшен, то t0 и t1 используются для вычисления соответствующих точек. Однако, если t0 = 0, то конечная точка равна V0 и не требуется вычислений. Аналогично, если t1 = 1, то конечная точка - V1 и вычисления также не нужны.
Геометрический смысл этого процесса состоит в том, что отрезок удлиняется для определения где эта удлиненная линия пересекает каждую линию границы. Более детально, каждая конечная точка заданного отрезка V0V1 используется как начальное значение для конечных точек отсеченного отрезка C0C1. Затем вычисляются точки пересечения удлиненной линии с каждой линией границы (эти вычисления соответствуют вызову процедуры LB_tclip в программе). Если для данной линии границы направление, определяемое V0V1, идет с невидимой на видимую сторону линии границы, то эта точка пересечения вначале сравнивается с С1. Если точка находится далее вдоль линии, тогда C1 (и таким образом, С0С1) должна быть на невидимой стороне линии, поэтому отрезок должен быть отброшен. В противном случае точка пересечения сравнивается с С0; если точка далее вдоль линии, тогда С0 перемещается вперед к этой точке.
С другой стороны, если направление с видимой на невидимую сторону, тогда точка пересечения вначале сравнивается с С0. Если С0 далее вдоль линии, чем точка пересечения, тогда C0 (и, следовательно C0C1) находится на невидимой стороне линии границы, т.е. отрезок должен быть отброшен. В противном случае точка пересечения сравнивается с С1 и, если С1 далее вдоль линии, тогда С1 перемещается назад к точке пересечения.
Наконец, если удлиненная линия параллельна граничной линии и она на невидимой стороне, то отрезок отбрасывается. В конце алгоритма, если отрезок не отброшен, тогда C0 и С1 используются как конечные точки видимой части отрезка.
В Приложении 7 приведена C-подпрограмма V_LBclip, реализующая описанный выше алгоритм.
0.6.4 Двумерный алгоритм Кируса-Бека
Все рассмотренные выше алгоритмы проводили отсечение по прямоугольному окну, стороны которого параллельны осям координат. Это, конечно, наиболее частый случай отсечения. Однако, во многих случаях требуется отсечение по произвольному многоугольнику, например, в алгоритмах удаления невидимых частей сцены. В этом случае наиболее удобно использование параметрического представления линий, не зависящего от выбора системы координат.
Из предыдущего пункта ясно, что для выполнения отсечения в параметрическом представлении необходимо иметь способ определения ориентации удлиненной линии, содержащей отсекаемый отрезок, относительно линии границы - с внешней стороны на внутреннюю или с внутренней на внешнюю, а также иметь способ определения расположения точки, принадлежащей отрезку, относительно окна - вне, на границе, внутри.
Для этих целей в алгоритме Кируса-Бека [29], реализующем отсечение произвольным выпуклым многоугольником, используется вектор внутренней нормали к ребру окна.
Внутренней нормалью Nв в точке А к стороне окна называется нормаль, направленная в сторону области, задаваемой окном отсечения.
Рассмотрим основные идеи алгоритма Кируса-Бека.
Так как многоугольник предполагается выпуклым, то может быть только две точки пересечения отрезка с окном. Поэтому надо найти два значения параметра t, соответствующие начальной и конечной точкам видимой части отрезка.
Пусть Ni - внутренняя нормаль к i-й граничной линии окна, а P = V1 - V0 - вектор, определяющий ориентацию отсекаемого отрезка, тогда ориентация отрезка относительно i-й стороны окна определяется знаком скалярного произведения Pi = Ni ·V, равного произведению длин векторов на косинус наименьшего угла, требуемого для поворота вектора Ni до совпадения по направлению с вектором V:
| (0.2.16) |
| (0.2.17) | ||||||||||||||||||
a) |
б) |
в) |
Для определения расположения точки относительно окна вспомним параметрическое представление отсекаемого отрезка:
| (0.2.18) |
Рассмотрим теперь скалярное произведение внутренней нормали Ni к i-й границе на вектор Q(t) = V(t) - Fi, начинающийся в начальной точке ребра окна и заканчивающийся в некоторой точке V(t) удлиненной линии.
| (0.2.19) |
Аналогично предыдущему имеем (рис. 0.2.15):
| (0.2.20) | ||||||||||||
a) |
б) |
в) |
Подставляя в (0.2.19) параметрическое представление (0.2.18), получим условие пересечения отрезка с границей окна:
| (0.2.21) |
Раскрывая скобки, получим:
| (0.2.22) |
Используя (0.2.16) и (0.2.19) перепишем (0.2.21):
| (0.2.23) |
Разрешая (0.2.22) относительно t, получим:
| (0.2.24) |
Это уравнение и используется для вычисления значений параметров, соответствующих начальной и конечной точкам видимой части отрезка.
Как следует из (0.2.17), Pi равно нулю если отрезок либо вырожден в точку, либо параллелен границе. В этом случае следует проанализировать знак Qi и принять или не принять решение об отбрасывании отрезка целиком в соответствии с условиями (0.2.17).
Если же Pi не равно 0, то уравнение (0.2.24) используется для вычисления значений параметров t, соответствующих точкам пересечений удлиненной линии с линиями границ.
Алгоритм построен следующим образом:
Искомые значения параметров t0 и t1 точек пересечения инициализируются значениями 0 и 1, соответствующими началу и концу отсекаемого отрезка.
Затем в цикле для каждой i-й стороны окна отсечения вычисляются значения скалярных произведений, входящих в (0.2.23).
Если очередное Pi равно 0, то отсекаемый отрезок либо вырожден в точку, либо параллелен i-й стороне окна. При этом достаточно проанализировать знак Qi. Если Qi < 0, то отрезок вне окна и отсечение закончено иначе рассматривается следующая сторона окна.
Если же Pi не равно 0, то по (0.2.24) можно вычислить значение параметра t для точки пересечения отсекаемого отрезка с i-й границей. Так как отрезок V0V1 соответствует диапазону 0 Ј t Ј 1, то все решения, выходящие за данный диапазон следует отбросить. Выбор оставшихся решений определяется знаком Pi.
Если Pi < 0, т.е. удлиненная линия направлена с внутренней на внешнюю стороны граничной линии, то ищутся значения параметра для конечной точки видимой части отрезка. В этом случае определяется минимальное значение из всех получаемых решений. Оно даст значение параметра t1 для конечной точки отсеченного отрезка. Если текущее полученное значение t1 окажется меньше, чем t0, то отрезок отбрасывается, так как нарушено условие t0 Ј t1.
Если же Pi > 0, т.е. удлиненная линия направлена с внешней на внутреннюю стороны граничной линии, то ищутся значения параметра для начальной точки видимой части отрезка. В этом случае определяется максимальное значение из всех получаемых решений. Оно даст значение параметра t0 для начальной точки отсеченного отрезка. Если текущее полученное значение t0 окажется больше, чем t1, то отрезок отбрасывается, так как нарушено условие t0 Ј t1.
На заключительном этапе алгоритма значения t0 и t1 используются для вычисления координат точек пересечения отрезка с окном. При этом, если t0 = 0, то начальная точка осталась V0 и вычисления не нужны. Аналогично, если t1 = 1, то конечная точка осталась V1 и вычисления также не нужны.
Все эти случаи пояснены на блок-схеме, представленной на рис. 0.2.16.
Вычисления значений параметров t0 и t1 выполняются в соответствии с выражениями (0.2.25).
| (0.2.25) | |||||||||||||||||||||
В Приложении 7 приведена C-подпрограмма V_CBclip, реализующая описанный выше алгоритм.
Проверка выпуклости и определение нормалей
Как видно из описания, алгоритм Кируса-Бека отсекает только по выпуклому окну. Кроме этого требуются значения внутренних нормалей к сторонам окна. Естественно выполнить эти вычисления в момент задания окна, так как следует ожидать, что одним окном будет отсекаться достаточно много отрезков.
Алгоритм с использованием векторных произведений
Проверка на выпуклость может производиться анализом знаков векторных произведений смежных ребер (рис. 0.2.17).
Если знак векторного произведения равен 0, то вершина вырождена, т.е. смежные ребра лежат на одной прямой (см. рис. 0.2.17 б), вершина Q).
Если все знаки равны 0, то многоугольник отсечения вырождается в отрезок.
Если же векторные произведения имеют разные знаки, то многоугольник отсечения невыпуклый (см. рис. 0.2.17 б)).
Если все знаки неотрицательные, то многоугольник выпуклый, причем обход вершин выполняется против часовой стрелки (см. рис. 0.2.17 а)), т.е. внутренние нормали ориентированы влево от контура. Следовательно вектор внутреннего перпендикуляра к стороне может быть получен поворотом ребра на +90° (в реализации алгоритма вычисления нормалей на самом деле вычисляется не нормаль к стороне, а перпендикуляр, так как при вычислении значения t по соотношению (0.2.22) длина не важна).
Если все знаки неположительные, то многоугольник выпуклый, причем обход вершин выполняется по часовой стрелке, т.е. внутренние нормали ориентированы вправо от контура. Следовательно вектор внутреннего перпендикуляра к стороне может быть получен поворотом ребра на -90°.
Описанный алгоритм реализован в процедуре V_SetPclip, приведенной в Приложении 7 и предназначенной для установки многоугольного окна отсечения.
Разбиение невыпуклых многоугольников
Одновременное проведение операций проверки на выпуклость и разбиение простого невыпуклого многоугольника на выпуклые обеспечивается методом переноса и поворотов окна.
Алгоритм метода при обходе вершин многоугольника против часовой стрелки состоит в следующем:
- Для каждой i-й вершины многоугольник сдвигается для переноса упомянутой вершины в начало координат.
- Многоугольник поворачивается против часовой стрелки
для совмещения (i+1)-й вершины с положительной полуосью X.
Вектор внутреннего перпендикуляра к ребру, образованному вершинами i-й и (i+1)-й, вычисляется поворотом ребра на -90° против часовой стрелки. - Анализируется знак Y-координаты (i+2)-й вершины.
Если Yi+2 і 0, то в (i+1)-й вершине выпуклость.
Если Yi+2 і 0, то в (i+1)-й вершине невыпуклость.
Если имеется невыпуклость, то многоугольник разрезается на два вдоль положительной полуоси X.
Для этого вычисляется пересечение положительной полуоси X с первой из сторон. Формируются два новых многоугольника: первый многоугольник - вершины с (i+1)-й до точки пересечения - вершины 2, 3, 4, 6, 7, [7\tilde] на рис. 0.2.18 б);
второй многоугольник - все остальные вершины - вершины [7\tilde], 8, 0, 1 на рис. 0.2.18 б)
Так как вновь полученные многоугольники могут в свою очередь оказаться невыпуклыми, алгоритм применяется к ним, пока все многоугольники не станут выпуклыми.
a) |
б) |
в) |
Повторное применение алгоритма в многоугольнику, образованному вершинами 2, 3, 4, 6, 7, [7\tilde], показано на рис. 0.2.18 в).
Данный алгоритм не обеспечивает минимальность числа вновь полученных выпуклых многоульников и некорректно работает если имеется самопересечение сторон, как это показано на рис. 0.2.19.
0.6.5 Сравнение алгоритмов двумерного отсечения
Во многих работах приводятся качественные соображения по быстродействию различных алгоритмов отсечения. В части работ, например, [32] или [37] приводятся результаты численных экспериментов по измерению скорости. Как правило, авторы работ этими экспериментами подтверждают преимущество своих алгоритмов.
В целом можно отметить несколько методических неточностей проведения таких экспериментов:
· неясно насколько одинаково хороши реализации собственного и
сравниваемых алгоритмов,
· эксперименты ([32] и [37] проводились в среде OC
UNIX и нет убедительных свидетельств отсутствия влияния окружения
на результаты,
· неясно насколько правильно выбиралось число повторений одного
отсечения относительно минимального измеряемого кванта
времени.
Исходя из этих соображений были проведены численные эксперименты по измерению быстродействия алгоритмов отсечения Коэна-Сазерленда, FC-алгоритма, Лианга-Барски и Кируса-Бека.
Использовались подпрограммы, приведенные в Приложении 7 при отсечении окнами различных размеров при полном разрешении
1000×1000. Процедуры транслировались и исполнялись на 486/DX4/100 в среде на Turbo C под управлением MS DOS 6.22.
Аналогично [37] были подготовлены 5 наборов данных по 1000 отрезков каждый со случайной генерацией конечных точек при следующих ограничениях:
1. Обе конечные точки отрезка внутри окна.
2. Одна конечная точка отрезка в окне, другая вне.
3. Обе конечные точки вне окна но с видимым сегментом.
4. Обе конечные точки вне окна и отрезок невидим.
5. Обе конечные точки генерировались случайно без ограничений.
Сгенерированные данные сохранялись в файлах и считывались в оперативную память перед очередным прогоном теста. Процедуры отсечения использовали данные из оперативной памяти. Для исключения временных затрат, связанных с организацией циклов и запросом координат отрезков, предварительно прогонялся тест с использованием "пустой" процедуры отсечения. Отсечение каждого отрезка проводилось 1000 раз. Измерение времени проводилось перед началом цикла по координатам.
Результаты измерений приведены в таблицах 0.2.3, 0.2.4, 0.2.5, 0.2.6, 0.2.7. Первая колонка таблиц - мои измерения. Вторая колонка таблиц - данные из [37]. Последние проводились на DEC VAX 8600 с ускорителем плавающей арифметики, транслировались C-компилятором без оптимизации и исполнялись под управлением ULTRIX V 1.1 (C).
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
0.18 Приложение 7. Процедуры отсечения отрезка
В данном приложении приведены процедуры, обеспечивающие выполнение отсечения по прямоугольному и многоугольному выпуклому окну и тестовая программа проверки работы процедур отсечения.
/*=================================================== V_CLIP.C
*
* Подрограммы, связанные с отсечением:
*
* V_SetPclip - установить размеры многоугольного окна
* отсечения
* V_SetRclip - установить размеры прямоугольного окна
* отсечения
* V_GetRclip - опросить размеры прямоугольного окна
* отсечения
* V_CSclip - отсечение по алгоритму Коэна-Сазерленда
* прямоугольное окно, кодирование
* концов отсекаемого отрезка
* V_FCclip - отсечение по алгоритму быстрого отсечения
* Алгоритм Собкова-Поспишила-Янга -
* прямоугольное окно, кодирование
* отсекаемого отрезка
* V_LBclip - отсечение по алгоритму Лианга-Барски
* прямоугольное окно, параметрическое
* представление линий
* V_CBclip - отсечение по алгоритму Кируса-Бека
* окно - выпуклый многоугольник,
* параметрическое представление линий
*/
/* Глобальные скаляры для алгоритмов отсечения по
* прямоугольному окну - Коэна-Сазерленда, Fc-алгоритм,
* Лианга-Барски
*/
static float Wxlef= 0.0, /* Координаты левого нижнего и */
Wybot= 0.0, /* правого верхнего углов окна */
Wxrig= 7.0, /* отсечения */
Wytop= 5.0;
/* Глобальные скаляры для алгоритма Кируса-Бека
* отсечения по многоугольному окну
*/
/* Координаты прямоугольного окна */
static float Wxrect[4]= {0.0, 0.0, 7.0, 7.0 };
static float Wyrect[4]= {0.0, 5.0, 5.0, 0.0 };
/* Перепендикуляры к сторонам прямоугольного окна */
static float WxNrec[4]= {1.0, 0.0, -1.0, 0.0 };
static float WyNrec[4]= {0.0, -1.0, 0.0, 1.0 };
/* Данные для многоугольного окна */
static int Windn=4; /* Кол-во вершин у окна */
static float *Windx= Wxrect, /* Координаты вершин окна */
*Windy= Wyrect;
static float *Wnormx= WxNrec, /* Координаты нормалей */
*Wnormy= WyNrec;
0.18.1 V_SetPclip - установить многоугольник отсечения
/*------------------------------------------------- V_SetPclip
* Устанавливает многоугольное окно отсечения
* kv - количество вершин в окне
* wx - X-координаты вершин
* wy - Y-координаты вершин
* nx - X-координаты нормалей к ребрам
* ny - Y-координаты нормалей к ребрам
*
* Проверяет окно на выпуклость и невырожденность
*
* Если окно правильное, то
* 1. Обновляет глобалы описания многоугольного окна:
* Windn= kv;
* Windx= wx; Windy= wy; --Координаты вершин окна
* Wnormx= nx; Wnormy= ny; --Координаты перпендикуляров
*
* 2. Вычисляет координаты перепендикуляров к сторонам окна
*
* Возвращает:
* 0 - норма
* 1 - вершин менее трех
* 2 - многоугольник вырожден в отрезок
* 3 - многоугольник невыпуклый
*/
int V_SetPclip (kv, wx, wy, nx, ny)
int kv; float *wx, *wy, *nx, *ny;
{ int ii, jj, sminus, splus, szero, otw;
float r,
vox, voy, /* Координаты (i-1)-й вершины */
vix, viy, /* Координаты i-й вершины */
vnx, vny; /* Координаты (i+1)-й вершины */
/* Проверка на выпуклость
* для этого вычисляются векторные произведения
* смежных сторон и определяется знак
* если все знаки == 0 то многоугольник вырожден
* если все знаки >= 0 то многоугольник выпуклый
* если все знаки <= 0 то многоугольник невыпуклый
*/
otw= 0;
if (--kv < 2) {++otw; goto all; }
sminus= 0;
splus= 0;
szero= 0;
vox= wx[kv]; voy= wy[kv];
vix= *wx; viy= *wy;
ii= 0;
do {
if (++ii > kv) ii= 0; /* Следующая вершина */
vnx= wx[ii]; vny= wy[ii]; /* Координаты (i+1)-й */
r= (vix-vox)*(vny-viy) - /* Вект произв ребер */
(viy-voy)*(vnx-vix); /* смежных с i-й верш */
if (r < 0) ++sminus; else
if (r > 0) ++splus; else ++szero;
vox= vix; voy= viy; /* Обновлен координат */
vix= vnx; viy= vny;
} while (ii);
if (!splus && !sminus) /* Все векторные равны нулю */
{otw= 2; goto all; } /* Многоугольник вырожден */
if (splus && sminus) /* Знакопеременн. векторные */
{otw= 3; goto all; } /* Многоугольник невыпуклый */
/* Установление глобалов для правильного окна */
Windn= kv+1; /* Количество вершин у окна */
Windx= wx; Windy= wy; /* Координаты вершин окна */
Wnormx= nx; Wnormy= ny; /* Координ. перпендикуляров */
/* Вычисление координат перпендикуляров к сторонам */
vox= *wx; voy= *wy;
ii= 0;
do {
if (++ii > kv) ii= 0;
vix= wx[ii]; viy= wy[ii]; /* Текущая вершина */
vnx= viy-voy; vny= vox-vix; /* Поворот по часовой */
if (splus) { /* Внутр нормали влево */
vnx= -vnx; vny= -vny;
}
*nx++= vnx; *ny++= vny;
vox= vix; voy= viy; /* Обновление координат */
} while (ii);
all:
return (otw);
} /* V_SetPclip */
0.18.2 V_SetRclip - установить прямоугольник отсечения
/*------------------------------------------------- V_SetRclip
* Устанавливает прямоугольное окно отсечения
* Возвращает 0/1 - нет/есть ошибки в задании окна
*/
int V_SetRclip (xleft, ybottom, xright, ytop)
float xleft, ybottom, xright, ytop;
{ int otw;
otw= 0;
if (xleft >= xright || ybottom >= ytop) ++otw; else {
Windn= 4;
Windx= Wxrect; Windy= Wyrect; /* Вершины */
Wxlef= Wxrect[0]= Wxrect[1]= xleft;
Wybot= Wyrect[0]= Wyrect[3]= ybottom;
Wxrig= Wxrect[2]= Wxrect[3]= xright;
Wytop= Wyrect[1]= Wyrect[2]= ytop;
Wnormx= WxNrec; Wnormy= WyNrec; /* Нормали */
WxNrec[0]= 1; WyNrec[0]= 0;
WxNrec[1]= 0; WyNrec[1]= -1;
WxNrec[2]= -1; WyNrec[2]= 0;
WxNrec[3]= 0; WyNrec[3]= 1;
}
return (otw);
} /* V_SetRclip */
0.18.3 V_GetRclip - опросить прямоугольник отсечения
/*------------------------------------------------- V_GetRclip
* Возвращает текущее прямоугольное окно отсечения
*/
void V_GetRclip (xleft, ybottom, xright, ytop)
float *xleft, *ybottom, *xright, *ytop;
{
*xleft= Wxlef; *ybottom= Wybot;
*xright= Wxrig; *ytop= Wytop;
} /* V_GetRclip */
0.18.4 V_CSclip - отсечение Коэна-Сазерленда
/*--------------------------------------------------- V_CSclip * Реализует алгоритм отсечения Коэна-Сазерленда с * кодированием концов отсекаемого отрезка * * int V_CSclip (float *x0, float *y0, float *x1, float *y1) * * Отсекает отрезок, заданный значениями координат его * точек (x0,y0), (x1,y1), по окну отсечения, заданному * глобальными скалярами Wxlef, Wybot, Wxrig, Wytop * * Конечным точкам отрезка приписываются коды, * характеризующие его положение относительно окна отсечения * по правилу: * * 1001 | 1000 | 1010 * -----|------|----- * | Окно | * 0001 | 0000 | 0010 * -----|------|----- * 0101 | 0100 | 0110 * * Отрезок целиком видим если оба его конца имеют коды 0000 * Если логическое И кодов концов не равно 0, то отрезок * целиком вне окна и он просто отбрасывается. * Если же результат этой операции = 0, то отрезок * подозрительный. Он может быть и вне и пересекать окно. * Для подозрительных отрезков определяются координаты их * пересечений с теми сторонами, с которыми они могли бы * пересечься в соответствии с кодами концов. * При этом используется горизонтальность и вертикальность * сторон окна, что позволяет определить одну из координат * без вычислений. * Часть отрезка, оставшаяся за окном отбрасывается. * Оставшаяся часть отрезка проверяется на возможность его * принятия или отбрасывания целиком. Если это невозможно, * то процесс повторяется для другой стороны окна. * На каждом цикле вычислений конечная точка отрезка, * выходившая за окно, заменяется на точку, лежащую или на * стороне окна или его продолжении. * * Вспомогательная процедура Code вычисляет код положения * для конца отрезка. * */
static float CSxn, CSyn; /* Координаты начала отрезка */
static int CScode (void) /* Определяет код точки xn, yn */
{ register int i;
i= 0;
if (CSxn < Wxlef) ++i; else
if (CSxn > Wxrig) i+= 2;
if (CSyn < Wybot) i+= 4; else
if (CSyn > Wytop) i+= 8;
return (i);
} /* CScode */
int V_CSclip (x0, y0, x1, y1)
float *x0, *y0, *x1, *y1;
{
float CSxk, CSyk; /* Координаты конца отрезка */
int cn, ck, /* Коды концов отрезка */
visible, /* 0/1 - не видим/видим*/
ii, s; /* Рабочие переменные */
float dx, dy, /* Приращения координат*/
dxdy,dydx, /* Наклоны отрезка к сторонам */
r; /* Рабочая переменная */
CSxk= *x1; CSyk= *y1;
CSxn= *x1; CSyn= *y1; ck= CScode ();
CSxn= *x0; CSyn= *y0; cn= CScode ();
/* Определение приращений координат и наклонов отрезка
* к осям. Заодно сразу на построение передается отрезок,
* состоящий из единственной точки, попавшей в окно
*/
dx= CSxk - CSxn;
dy= CSyk - CSyn;
if (dx != 0) dydx= dy / dx; else {
if (dy == 0) {
if (cn==0 && ck==0) goto out; else goto all;
}
}
if (dy != 0) dxdy= dx / dy;
/* Основной цикл отсечения */
visible= 0; ii= 4;
do {
if (cn & ck) break; /* Целиком вне окна */
if (cn == 0 && ck == 0) { /* Целиком внутри окна */
++visible; break;
}
if (!cn) { /* Если Pn внутри окна, то */
s= cn; cn= ck; ck= s; /* перестить точки Pn,Pk и */
r=CSxn; CSxn=CSxk; CSxk=r; /* их коды, чтобы Pn */
r=CSyn; CSyn=CSyk; CSyk=r; /* оказалась вне окна */
}
/* Теперь отрезок разделяется. Pn помещается в точку
* пересечения отрезка со стороной окна.
*/
if (cn & 1) { /* Пересечение с левой стороной */
CSyn= CSyn + dydx * (Wxlef-CSxn);
CSxn= Wxlef;
} else if (cn & 2) { /* Пересечение с правой стороной*/
CSyn= CSyn + dydx * (Wxrig-CSxn);
CSxn= Wxrig;
} else if (cn & 4) { /* Пересечение в нижней стороной*/
CSxn= CSxn + dxdy * (Wybot-CSyn);
CSyn= Wybot;
} else if (cn & 8) { /*Пересечение с верхней стороной*/
CSxn= CSxn + dxdy * (Wytop-CSyn);
CSyn= Wytop;
}
cn= CScode (); /* Перевычисление кода точки Pn */
} while (--ii >= 0);
if (visible) {
out: *x0= CSxn; *y0= CSyn;
*x1= CSxk; *y1= CSyk;
}
all:
return (visible);
} /* V_CSclip */
0.18.5 V_FCclip - Fast Clipping-алгоритм
/*--------------------------------------------------- V_FCclip * Реализует алгоритм отсечения FC (Fast Clipping) * Собкова-Поспишила-Янга, с кодированием линий * * int V_FCclip (float *x0, float *y0, float *x1, float *y1) * * Отсекает отрезок, заданный значениями координат его * точек (x0,y0), (x1,y1), по окну отсечения, заданному * глобальными скалярами Wxlef, Wybot, Wxrig, Wytop * * Возвращает: * -1 - ошибка в задании окна * 0 - отрезок не видим * 1 - отрезок видим */
static float FC_xn, FC_yn, FC_xk, FC_yk;
static void Clip0_Top(void)
{FC_xn= FC_xn + (FC_xk-FC_xn)*(Wytop-FC_yn)/(FC_yk-FC_yn);
FC_yn= Wytop; }
static void Clip0_Bottom(void)
{FC_xn= FC_xn + (FC_xk-FC_xn)*(Wybot-FC_yn)/(FC_yk-FC_yn);
FC_yn= Wybot; }
static void Clip0_Right(void)
{FC_yn= FC_yn + (FC_yk-FC_yn)*(Wxrig-FC_xn)/(FC_xk-FC_xn);
FC_xn= Wxrig; }
static void Clip0_Left(void)
{FC_yn= FC_yn + (FC_yk-FC_yn)*(Wxlef-FC_xn)/(FC_xk-FC_xn);
FC_xn= Wxlef; }
static void Clip1_Top(void)
{FC_xk= FC_xk + (FC_xn-FC_xk)*(Wytop-FC_yk)/(FC_yn-FC_yk);
FC_yk= Wytop; }
static void Clip1_Bottom(void)
{FC_xk= FC_xk + (FC_xn-FC_xk)*(Wybot-FC_yk)/(FC_yn-FC_yk);
FC_yk= Wybot; }
static void Clip1_Right(void)
{FC_yk= FC_yk + (FC_yn-FC_yk)*(Wxrig-FC_xk)/(FC_xn-FC_xk);
FC_xk= Wxrig; }
static void Clip1_Left(void)
{FC_yk= FC_yk + (FC_yn-FC_yk)*(Wxlef-FC_xk)/(FC_xn-FC_xk);
FC_xk= Wxlef; }
int V_FCclip (x0, y0, x1, y1)
float *x0, *y0, *x1, *y1;
{ int Code= 0;
int visible= 0; /* Отрезок невидим */
FC_xn= *x0; FC_yn= *y0;
FC_xk= *x1; FC_yk= *y1;
/*
* Вычисление значения Code - кода отрезка
* Биты 0-3 - для конечной точки, 4-7 - для начальной
*
*/
if (FC_yk > Wytop) Code+= 8; else
if (FC_yk < Wybot) Code+= 4;
if (FC_xk > Wxrig) Code+= 2; else
if (FC_xk < Wxlef) Code+= 1;
if (FC_yn > Wytop) Code+= 128; else
if (FC_yn < Wybot) Code+= 64;
if (FC_xn > Wxrig) Code+= 32; else
if (FC_xn < Wxlef) Code+= 16;
/* Отсечение для каждого из 81-го случаев */
switch (Code) {
/* Из центра */
case 0x00: ++visible; break;
case 0x01: Clip1_Left() ; ++visible; break;
case 0x02: Clip1_Right(); ++visible; break;
case 0x04: Clip1_Bottom(); ++visible; break;
case 0x05: Clip1_Left() ;
if (FC_yk < Wybot) Clip1_Bottom();
++visible; break;
case 0x06: Clip1_Right();
if (FC_yk < Wybot) Clip1_Bottom();
++visible; break;
case 0x08: Clip1_Top(); ++visible; break;
case 0x09: Clip1_Left() ;
if (FC_yk > Wytop) Clip1_Top();
++visible; break;
case 0x0A: Clip1_Right();
if (FC_yk > Wytop) Clip1_Top();
++visible; break;
/* Слева */
case 0x10: Clip0_Left(); ++visible;
case 0x11: break; /* Отброшен */
case 0x12: Clip0_Left(); Clip1_Right();
++visible; break;
case 0x14: Clip0_Left();
if (FC_yn < Wybot) break; /* Отброшен */
Clip1_Bottom();
++visible;
case 0x15: break; /* Отброшен */
case 0x16: Clip0_Left();
if (FC_yn < Wybot) break; /* Отброшен */
Clip1_Bottom();
if (FC_xk > Wxrig) Clip1_Right();
++visible;
break;
case 0x18: Clip0_Left();
if (FC_yn > Wytop) break; /* Отброшен */
Clip1_Top();
++visible;
case 0x19: break; /* Отброшен */
case 0x1A: Clip0_Left();
if (FC_yn > Wytop) break; /* Отброшен */
Clip1_Top();
if (FC_xk > Wxrig) Clip1_Right();
++visible;
break;
/* Справа */
case 0x20: Clip0_Right(); ++visible; break;
case 0x21: Clip0_Right(); Clip1_Left(); ++visible;
case 0x22: break; /* Отброшен */
case 0x24: Clip0_Right();
if (FC_yn < Wybot) break; /* Отброшен */
Clip1_Bottom();
++visible;
break;
case 0x25: Clip0_Right();
if (FC_yn < Wybot) break; /* Отброшен */
Clip1_Bottom();
if (FC_xk < Wxlef) Clip1_Left();
++visible;
case 0x26: break; /* Отброшен */
case 0x28: Clip0_Right();
if (FC_yn > Wytop) break; /* Отброшен */
Clip1_Top();
++visible;
break;
case 0x29: Clip0_Right();
if (FC_yn > Wytop) break; /* Отброшен */
Clip1_Top();
if (FC_xk < Wxlef) Clip1_Left();
++visible;
case 0x2A: break; /* Отброшен */
/* Снизу */
case 0x40: Clip0_Bottom(); ++visible; break;
case 0x41: Clip0_Bottom();
if (FC_xn < Wxlef) break; /* Отброшен */
Clip1_Left() ;
if (FC_yk < Wybot) Clip1_Bottom();
++visible;
break;
case 0x42: Clip0_Bottom();
if (FC_xn > Wxrig) break; /* Отброшен */
Clip1_Right();
++visible;
case 0x44:
case 0x45:
case 0x46: break; /* Отброшен */
case 0x48: Clip0_Bottom();
Clip1_Top();
++visible;
break;
case 0x49: Clip0_Bottom();
if (FC_xn < Wxlef) break; /* Отброшен */
Clip1_Left() ;
if (FC_yk > Wytop) Clip1_Top();
++visible;
break;
case 0x4A: Clip0_Bottom();
if (FC_xn > Wxrig) break; /* Отброшен */
Clip1_Right();
if (FC_yk > Wytop) Clip1_Top();
++visible;
break;
/* Снизу слева */
case 0x50: Clip0_Left();
if (FC_yn < Wybot) Clip0_Bottom();
++visible;
case 0x51: break; /* Отброшен */
case 0x52: Clip1_Right();
if (FC_yk < Wybot) break; /* Отброшен */
Clip0_Bottom();
if (FC_xn < Wxlef) Clip0_Left();
++visible;
case 0x54:
case 0x55:
case 0x56: break; /* Отброшен */
case 0x58: Clip1_Top();
if (FC_xk < Wxlef) break; /* Отброшен */
Clip0_Bottom();
if (FC_xn < Wxlef) Clip0_Left();
++visible;
case 0x59: break; /* Отброшен */
case 0x5A: Clip0_Left();
if (FC_yn > Wytop) break; /* Отброшен */
Clip1_Right();
if (FC_yk < Wybot) break; /* Отброшен */
if (FC_yn < Wybot) Clip0_Bottom();
if (FC_yk > Wytop) Clip1_Top();
++visible;
break;
/* Снизу-справа */
case 0x60: Clip0_Right();
if (FC_yn < Wybot) Clip0_Bottom();
++visible;
break;
case 0x61: Clip1_Left() ;
if (FC_yk < Wybot) break; /* Отброшен */
Clip0_Bottom();
if (FC_xn > Wxrig) Clip0_Right();
++visible;
case 0x62:
case 0x64:
case 0x65:
case 0x66: break; /* Отброшен */
case 0x68: Clip1_Top();
if (FC_xk > Wxrig) break; /* Отброшен */
Clip0_Right();
if (FC_yn < Wybot) Clip0_Bottom();
++visible;
break;
case 0x69: Clip1_Left() ;
if (FC_yk < Wybot) break; /* Отброшен */
Clip0_Right();
if (FC_yn > Wytop) break; /* Отброшен */
if (FC_yk > Wytop) Clip1_Top();
if (FC_yn < Wybot) Clip0_Bottom();
++visible;
case 0x6A: break; /* Отброшен */
/* Сверху */
case 0x80: Clip0_Top();
++visible;
break;
case 0x81: Clip0_Top();
if (FC_xn < Wxlef) break; /* Отброшен */
Clip1_Left() ;
++visible;
break;
case 0x82: Clip0_Top();
if (FC_xn > Wxrig) break; /* Отброшен */
Clip1_Right();
++visible;
break;
case 0x84: Clip0_Top();
Clip1_Bottom();
++visible;
break;
case 0x85: Clip0_Top();
if (FC_xn < Wxlef) break; /* Отброшен */
Clip1_Left() ;
if (FC_yk < Wybot) Clip1_Bottom();
++visible;
break;
case 0x86: Clip0_Top();
if (FC_xn > Wxrig) break; /* Отброшен */
Clip1_Right();
if (FC_yk < Wybot) Clip1_Bottom();
++visible;
case 0x88:
case 0x89:
case 0x8A: break; /* Отброшен */
/* Сверху-слева */
case 0x90: Clip0_Left();
if (FC_yn > Wytop) Clip0_Top();
++visible;
case 0x91: break; /* Отброшен */
case 0x92: Clip1_Right();
if (FC_yk > Wytop) break; /* Отброшен */
Clip0_Top();
if (FC_xn < Wxlef) Clip0_Left();
++visible;
break;
case 0x94: Clip1_Bottom();
if (FC_xk < Wxlef) break; /* Отброшен */
Clip0_Left();
if (FC_yn > Wytop) Clip0_Top();
++visible;
case 0x95: break; /* Отброшен */
case 0x96: Clip0_Left();
if (FC_yn < Wybot) break; /* Отброшен */
Clip1_Right();
if (FC_yk > Wytop) break; /* Отброшен */
if (FC_yn > Wytop) Clip0_Top();
if (FC_yk < Wybot) Clip1_Bottom();
++visible;
case 0x98:
case 0x99:
case 0x9A: break; /* Отброшен */
/* Сверху-справа */
case 0xA0: Clip0_Right();
if (FC_yn > Wytop) Clip0_Top();
++visible;
break;
case 0xA1: Clip1_Left() ;
if (FC_yk > Wytop) break; /* Отброшен */
Clip0_Top();
if (FC_xn > Wxrig) Clip0_Right();
++visible;
case 0xA2: break; /* Отброшен */
case 0xA4: Clip1_Bottom();
if (FC_xk > Wxrig) break; /* Отброшен */
Clip0_Right();
if (FC_yn > Wytop) Clip0_Top();
++visible;
break;
case 0xA5: Clip1_Left() ;
if (FC_yk > Wytop) break; /* Отброшен */
Clip0_Right();
if (FC_yn < Wybot) break; /* Отброшен */
if (FC_yk < Wybot) Clip1_Bottom();
if (FC_yn > Wytop) Clip0_Top();
++visible;
case 0xA6: /* Отброшен */
case 0xA8:
case 0xA9:
case 0xAA: break;
/* Ошибка */
default: visible= -1;
break;
} /* switch */
if (visible > 0) {
*x0= FC_xn; *y0= FC_yn;
*x1= FC_xk; *y1= FC_yk;
}
return (visible);
} /* V_FCclip */
0.18.6 V_LBclip - алгоритм Лианга-Барски
/*--------------------------------------------------- V_LBclip
* Реализует алгоритм отсечения Лианга-Барски
* с параметрическим заданием линий
*
* int V_LBclip (float *x0, float *y0, float *x1, float *y1)
*
* Отсекает отрезок, заданный значениями координат его
* точек (x0,y0), (x1,y1), по окну отсечения, заданному
* глобальными скалярами Wxlef, Wybot, Wxrig, Wytop
*
* Возвращает:
* 0 - отрезок не видим
* 1 - отрезок видим
*/
static float LB_t0, LB_t1;
static int LB_tclip (p, q)
float p, q;
{
int accept;
float r;
accept= 1; /* Отрезок принят */
if (p == 0) {
if (q < 0) accept= 0; /* Отбрасывание */
} else {
r= q/p;
if (p < 0) {
if (r > LB_t1) accept= 0; /* Отбрасывание */
else if (r > LB_t0) LB_t0= r;
} else {
if (r < LB_t0) accept= 0; /* Отбрасывание */
else if (r < LB_t1) LB_t1= r;
}
}
return (accept);
} /* LB_tclip */
int V_LBclip (x0, y0, x1, y1)
float *x0, *y0, *x1, *y1;
{ int visible;
float dx, dy;
visible= 0;
LB_t0= 0; LB_t1= 1;
dx= *x1 - *x0;
if (LB_tclip (-dx, *x0-Wxlef)) {
if (LB_tclip (dx, Wxrig-*x0)) {
dy= *y1 - *y0;
if (LB_tclip (-dy, *y0-Wybot)) {
if (LB_tclip (dy, Wytop-*y0)) {
if (LB_t1 < 1) {
*x1= *x0 + LB_t1*dx;
*y1= *y0 + LB_t1*dy;
}
if (LB_t0 > 0) {
*x0= *x0 + LB_t0*dx;
*y0= *y0 + LB_t0*dy;
}
++visible;
}
}
}
}
return (visible);
} /* V_LBclip */
0.18.7 V_CBclip - алгоритм Кируса-Бека
/*--------------------------------------------------- V_CBclip * Реализует алгоритм отсечения Кируса-Бека * по произвольному выпуклому многоугольнику * с параметрическим заданием линий * * int V_CBclip (float *x0, float *y0, float *x1, float *y1) * * Отсекает отрезок, заданный значениями координат его * точек (x0,y0), (x1,y1), по окну отсечения, заданному * глобальными скалярами: * int Windn - количество вершин в окне отсечения * float *Windx, *Windy - массивы X,Y координат вершин * float *Wnormx, *Wnormy - массивы координат нормалей * к ребрам * * Возвращает: * 0 - отрезок не видим * 1 - отрезок видим */
int V_CBclip (x0, y0, x1, y1)
float *x0, *y0, *x1, *y1;
{ int ii, jj, visible, kw;
float xn, yn, dx, dy, r;
float CB_t0, CB_t1; /* Параметры концов отрезка */
float Qx, Qy; /* Положение относ ребра */
float Nx, Ny; /* Перпендикуляр к ребру */
float Pn, Qn; /**/
kw= Windn - 1; /* Ребер в окне */
visible= 1;
CB_t0= 0; CB_t1= 1;
dx= *x1 - (xn= *x0);
dy= *y1 - (yn= *y0);
for (ii=0; ii<=kw; ++ii) { /* Цикл по ребрам окна */
Qx= xn - Windx[ii]; /* Положения относ ребра */
Qy= yn - Windy[ii];
Nx= Wnormx[ii]; /* Перепендикуляр к ребру */
Ny= Wnormy[ii];
Pn= dx*Nx + dy*Ny; /* Скалярные произведения */
Qn= Qx*Nx + Qy*Ny;
/* Анализ расположения */
if (Pn == 0) { /* Паралл ребру или точка */
if (Qn < 0) {visible= 0; break; }
} else {
r= -Qn/Pn;
if (Pn < 0) { /* Поиск верхнего предела t */
if (r < CB_t0) {visible= 0; break; }
if (r < CB_t1) CB_t1= r;
} else { /* Поиск нижнего предела t */
if (r > CB_t1) {visible= 0; break; }
if (r > CB_t0) CB_t0= r;
}
}
}
if (visible) {
if (CB_t0 > CB_t1) visible= 0; else {
if (CB_t0 > 0) {
*x0= xn + CB_t0*dx;
*y0= yn + CB_t0*dy;
}
if (CB_t1 < 1) {
*x1= xn + CB_t1*dx;
*y1= yn + CB_t1*dy;
}
}
}
return (visible);
} /* V_CBclip */
0.18.8 Тест процедур отсечения
/*=================================================== T_CLIP.C
*
* ТЕСТ ПРОЦЕДУР ОТСЕЧЕНИЯ
*/
#include <time.h>
#include <stdio.h>
/*--------------------------------------------------- V_DMclip
* Пустышка для процедур отсечения
*/
int V_DMclip (x0, y0, x1, y1)
float *x0, *y0, *x1, *y1;
{ int visible;
visible= 1;
return (visible);
} /* V_DMclip */
/*---------------------------------------------------- ClipMsg
* Печатает сообщение о результатах отсечения
*/
void ClipMsg (proc, visible, x0, y0, x1, y1, dt)
char *proc; int visible; float x0, y0, x1, y1, dt;
{
if (visible < 0) {
printf("*** ERROR (%s LineClip) - ", proc);
printf("ошибка в координатах окна. ");
printf("Прерывание с кодом ошибки 1.");
exit (1);
} else if (visible == 0)
printf ("%s: Line is no visible dt=%f\n", proc, dt);
else
printf ("%s: ClipLine: x0=%f y0=%f x1=%f y1=%f dt=%f\n",
proc, x0, y0, x1, y1, dt);
} /* ClipMsg */
/*---------------------------------------------- MAIN T_CLIP.C
*/
void main (void)
{
float Wxn, Wyn, Wxk, Wyk;
float Xn, Yn, Xk, Yk, x0, y0, x1, y1;
int ii, numb= 1;
float X_wind[100], Y_wind[100];
float X_norm[100], Y_norm[100];
int visible;
float dt;
time_t t1, t2;
long ll, powt=10l;
if (numb) goto set_win;
m0:printf ("----Вершин= %d ? ", numb);
scanf ("%d", &numb);
for (ii=0; ii<numb; ++ii) {
printf ("X_wind[%d], Y_wind[%d] ? ", ii, ii);
scanf ("%f%f", &X_wind[ii], &Y_wind[ii]);
}
ii= V_SetPclip (numb, X_wind, Y_wind, X_norm, Y_norm);
printf ("V_SetPclip= %d\n", ii);
if (ii) goto m0;
for (ii=0; ii<numb; ++ii)
printf ("ind=%d X_norm=%f, Y_norm=%f\n",
ii, X_norm[ii], Y_norm[ii]);
if (ii) goto m0;
/* Задание окна отсечения */
set_win:
powt= 1l;
V_GetRclip (&Wxn, &Wyn, &Wxk, &Wyk);
for (;;) {
printf ("Window: (Xn=%f Yn=%f Xk=%f Yk=%f) ? ",
Wxn, Wyn, Wxk, Wyk);
scanf ("%f%f%f%f", &Wxn, &Wyn, &Wxk, &Wyk);
if (!V_SetRclip (Wxn, Wyn, Wxk, Wyk)) break;
printf ("Error in a window boundarys\n");
}
/* Ввод координат отрезка */
Xn= Wxn-1.0; Yn= Wyn-1.0; Xk= Wxk+1.0; Yk= Wyk+1.0;
for (;;) {
printf ("------------- ");
printf ("ClipWindow: Xn=%f Yn=%f Xk=%f Yk=%f\n",
Wxlef, Wybot, Wxrig, Wytop);
printf ("New Line: (Xn=%f Yn=%f Xk=%f Yk=%f) ? ",
Xn, Yn, Xk, Yk);
scanf ("%f%f%f%f", &Xn, &Yn, &Xk, &Yk);
ll= powt;
t1= time(NULL);
do {
x0= Xn; y0= Yn; x1= Xk; y1= Yk;
visible= V_DMclip (&x0, &y0, &x1, &y1);
} while (--ll > 0l);
t2= time (NULL);
dt= ((float)(t2 - t1));
ClipMsg ("DM", visible, x0, y0, x1, y1, dt);
ll= powt;
t1= time(NULL);
do {
x0= Xn; y0= Yn; x1= Xk; y1= Yk;
visible= V_CSclip (&x0, &y0, &x1, &y1);
} while (--ll > 0l);
t2= time (NULL);
dt= ((float)(t2 - t1));
ClipMsg ("CS", visible, x0, y0, x1, y1, dt);
ll= powt;
t1= time(NULL);
do {
x0= Xn; y0= Yn; x1= Xk; y1= Yk;
visible= V_FCclip (&x0, &y0, &x1, &y1);
} while (--ll > 0l);
t2= time (NULL);
dt= ((float)(t2 - t1));
ClipMsg ("FC", visible, x0, y0, x1, y1, dt);
ll= powt;
t1= time(NULL);
do {
x0= Xn; y0= Yn; x1= Xk; y1= Yk;
visible= V_LBclip (&x0, &y0, &x1, &y1);
} while (--ll > 0l);
t2= time (NULL);
dt= ((float)(t2 - t1));
ClipMsg ("LB", visible, x0, y0, x1, y1, dt);
ll= powt;
t1= time(NULL);
do {
x0= Xn; y0= Yn; x1= Xk; y1= Yk;
visible= V_CBclip (&x0, &y0, &x1, &y1);
} while (--ll > 0l);
t2= time (NULL);
dt= ((float)(t2 - t1));
ClipMsg ("CB", visible, x0, y0, x1, y1, dt);
}
}
Список литературы
- [4]
- Фоли Дж., вэн Дэм А. Основы интерактивной машинной
графики: В 2-х книгах. Пер. с англ. М.: Мир, 1985.
- [29]
- Cyrus M., Beck J. Generalized two- and
threedimensional clipping// Computer and Graphics, Vol. 3,
pp. 23-28, 1978.
- [32]
- You-Dong Liang and Brian A. Barsky. A new concept and
method for line clipping// ACM Transaction on Graphics, Vol.
3, No. 1, January 1984, pp. 1-22.
- [33]
- Tina M. Nicholl, D.T.Lee and Robin A. Nicholl. An
efficient new algoritm for 2-D line clipping: its development
and analysis// Computer Graphics, V. 21, N. 4, July 1987, pp.
253-262.
- [34]
- R.Pinkman, M.Novak, K.Guttag. Video-RAM exels at fast
graphics// Electronics Design, pp. 161-171 (August 18 1983).
- [35]
- H.-P. Seidel. PC Graphics Hardware // Eurographics
'88. Tutorial/Cours 8. Nice, 12.-16. September 1988.
France, Nice. 44 p.
- [36]
- Smit A.R., Tint Fill, SIGGRAPH'79 Proceedings //
Computer Graphics, Vol.13(2), Aug. 1979, pp. 276-283.
- [37]
- Mark S. Sobkow, Paul Pospisil and Yee-Hong Yang. A
Fast Two-Dimensional Line Clipping Algoritm via Line
Encoding//Computer & Graphics, Vol. 11, No. 4, pp. 459-467,
1987.
- [38]
- Robert F. Sproull and Ivan E. Sutherland. A Clipping
Divider // AFIP Fall Joint Computer Conference. San
Francisco, 1968.
Вверх по странице, к оглавлению и навигации.