Основные алгоритмы компьютерной графики

ОТСЕЧЕНИЕ ОТРЕЗКОВ

Если изображение выходит за пределы экрана, то на части дисплеев увеличивается время построения за счет того, что изображение строится в "уме". В некоторых дисплеях выход за пределы экрана приводит к искажению картины, так как координаты просто ограничиваются при достижении ими граничных значений, а не выполняется точный расчет координат пересечения (эффект "стягивания" изображения). Некоторые, в основном, простые дисплеи просто не допускают выхода за пределы экрана. Все это, особенно в связи с широким использованием технологии просмотра окнами, требует выполнения отсечения сцены по границам окна видимости.

В простых графических системах достаточно двумерного отсечения, в трехмерных пакетах используется трех и четырехмерное отсечение. Последнее выполняется в ранее рассмотренных однородных координатах, позволяющих единым образом выполнять аффинные и перспективные преобразования.

Программное исполнение отсечения достаточно медленный процесс, поэтому, естественно, в мощные дисплеи встраивается соответствующая аппаратура. Первое сообщение об аппаратуре отсечения, использующей алгоритм отсечения делением отрезка пополам и реализованной в устройстве Clipping Divider, появилось в 1968 г. [38]. Этот алгоритм был рассмотрен при изучении технических средств. Здесь мы рассмотрим программные реализации алгоритма отсечения.

Отсекаемые отрезки могут быть трех классов - целиком видимые, целиком невидимые и пересекающие окно. Очевидно, что целесообразно возможно более рано, без выполнения большого объема вычислений принять решение об видимости целиком или отбрасывании. По способу выбора простого решения об отбрасывании невидимого отрезка целиком или принятия его существует два основных типа алгоритмов отсечения - алгоритмы, использующие кодирование концов отрезка или всего отрезка и алгоритмы, использующие параметрическое представление отсекаемых отрезков и окна отсечения. Представители первого типа алгоритмов - алгоритм Коэна-Сазерленда (Cohen-Sutherland, CS-алгоритм) [4] и FC-алгоритм (Fast Clipping - алгоритм) [37]. Представители алгоритмов второго типа - алгоритм Кируса-Бека (Curus-Beck, CB - алгоритм) и более поздний алгоритм Лианга-Барски (Liang-Barsky, LB-алгоритм) [32].

Алгоритмы с кодированием применимы для прямоугольного окна, стороны которого параллельны осям координат, в то время как алгоритмы с параметрическим представлением применимы для произвольного окна.

Вначале мы рассмотрим алгоритм Коэна-Сазерленда, являющийся стандартом де-факто алгоритма отсечения линий и обладающий одним из лучших быстродействий при компактной реализации. Затем рассмотрим наиболее быстрый, но и чрезвычайно громоздкий FC-алгоритм. Далее рассмотрим алгоритм Лианга-Барски для отсечения прямоугольным окном с использованием параметрического представления. Быстродействие этого алгоритма сравнимо с быстродействием алгоритма Коэна-Сазерленда при большей компактности и наличии 3D и 4D реализаций. Последним рассмотрим алгоритм Кируса-Бека, который использует параметрическое представление и позволяет отсекать произвольным выпуклым окном. В заключение сравним быстродействие различных алгоритмов.

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

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

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

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

Окно отсечения и прилегающие к нему части плоскости вместе образуют 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 нельзя просто отбросить. Для решения этой проблемы Коэн и Сазерленд предложили заменять конечную точку с ненулевым кодом конца на точку, лежащую на стороне окна, либо на ее продолжении.

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

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

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

2. Если логическое И кодов конечных точек не равно 0, то отрезок целиком вне окна. Он отбрасывается и отсечение закончено.

3. Если оба кода равны 0, то отрезок целиком видим. Он принимается и отсечение закончено.

4. Если начальная точка внутри окна, то она меняется местами с конечной точкой.

5. Анализируется код начальной точки для определения стороны окна с которой есть пересечение и выполняется расчет пересечения. При этом вычисленная точка пересечения заменяет начальную точку.

6. Определение нового кода начальной точки.

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

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

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

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

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

здесь 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.

Из этих восьми случаев легко симметрично сгенерировать все остальные.

Главное отличие FC-алгоритма от алгоритма Коэна-Сазерленда состоит в упорядочивании действий по отсечению. Эффективность алгоритма Коэна-Сазерленда ограничивается последовательным характером и фиксированным порядком действий по отсечению. Как пример (см. рис. 0.2.6) отрезок RW будет отсекаться в порядке: сверху, снизу, справа и слева. Число же отсечений для определения видимости равно 2 - снизу и слева. В FC-алгоритме, напротив, для каждого значения LineCode имеется свой набор действий по отсечению. Для приведенного выше примера потребуется только одно отсечение для определения невидимости отрезка RW. Кроме этого, повышению эффективности FC-алгоритма по сравнению с CS-алгоритмом способствует отсутствие ненужных циклов и, следовательно, перевычислений кодов конечных точек.

В Приложении 7 приведена C-подпрограмма V_FCclip, реализующая FC-алгоритм и свободная от ошибок в подпрограмме, приведенной в [37]. Можно заметно сократить объем ее программного кода учтя симметрию и использовав указатели на данные либо переставляя данные. Например, в подпрограмме V_FCclip для отрезка LH (см. рис. 0.2.5, если он идет слева-направо вначале выполняется отсечение для начальной точки по левой стороне окна и затем для конечной - по правой. Если же отрезок идет справа-налево, то вначале вычисляется отсечение начальной точки по правой стороне и затем конечной - по левой. Очевидно, что эти два случая идентичны если поменять местами координаты начальной и конечной точек.

В 1982 г. Лианг и Барски [32] предложили алгоритмы отсечения прямоугольным окном с использованием параметрического представления для двух, трех и четырехмерного отсечения. По утверждению авторов, данный алгоритм в целом превосходит алгоритм Коэна-Сазерленда. Однако в работе [37] показывается, что это утверждение справедливо только для случая когда оба конца видимого отрезка вне окна и окно небольшое (до 50×50 при разрешении 1000×1000). Приведенное далее изложение двумерного варианта алгоритма следует, основном, работе [32].

Как уже говорилось, при 2D отсечении прямые отсекаются по 2D области, называемой окном отсечения. В частности, внутренняя часть окна отсечения может быть выражена с помощью следующих неравенств (рис. 0.2.7).

#tth_closerowВнутренняя часть окна отсечения

Продолжим каждую из четырех границ окна до бесконечных прямых. Каждая из таких прямых делит плоскость на 2 области. Назовем "видимой частью" ту, в которой находится окно отсечения, как это показано на рис. 0.2.8. Видимой части соответствует внутренняя сторона линии границы. Невидимой части плоскости соответствует внешняя сторона линии границы.

Таким образом, окно отсечения может быть определено как область, которая находится на внутренней стороне всех линий границ.

Или в общем виде для отрезка, заданного точками V₀ и V₁:

Для точек V₀ и V₁ параметр t равен 0 и 1, соответственно. Меняя t от 0 до 1 перемещаемся по отрезку V₀V₁ от точки V₀ к точке V₁. Изменяя t в интервале от -Ґ до +Ґ, получаем бесконечную (далее удлиненную) прямую, ориентация которой - от точки V₀ к точке V₁.

Однако вернемся к формальному рассмотрению алгоритма отсечения.

Подставляя параметрическое представление, заданное уравнениями (0.2.2) и (0.2.3), в неравенства (0.2.1), получим следующие соотношения для частей удлиненной линии, которая находится в окне отсечения:

Заметим, что соотношения (0.2.5) - неравенства, описывающие внутреннюю часть окна отсечения, в то время как равенства определяют его границы.

Рассматривая неравенства (0.2.5), видим, что они имеют одинаковую форму вида:

Здесь использованы следующие обозначения:

Вспоминая определения внутренней и внешней стороны линии границы (см. рис. 0.2.8), замечаем, что каждое из неравенств (0.2.6) соответствует одной из граничных линий (левой, правой, нижней и верхней, соответственно) и описывает ее видимую сторону. (Например, для i=1 имеем: P₁·t    Ј   Q₁ Ю -dx·t    Ј   x0 - XлевЮ x0   +  dx·t    і   Xлев). Удлиним V₀V₁ в бесконечную прямую. Тогда каждое неравенство задает диапазон значений параметра t, для которых эта удлиненная линия находится на видимой стороне соответствующей линии границы. Более того, конкретное значение параметра t для точки пересечения есть t = Q_i/P_i. Причем знак Q_i показывает на какой стороне соответствующей линии границы находится точка V₀. А именно, если Qi    і   0, тогда V₀ находится на видимой стороне линии границы, включая и ее. Если же Q_i    <   0, тогда V₀ находится на невидимой стороне.

Рассмотрим P_i в соотношениях (0.2.7). Ясно, что любое P_i может быть меньше 0, больше 0 и равно 0.

Если P_i    <   0, тогда соответствующее неравенство становится:

Для пояснения на рис. 0.2.10 показано пересечение с левой и правой границами при P_i    <   0.

Очевидно, что диапазон значений параметра t, для которых удлиненная линия находится на видимой стороне соответствующей граничной линии, имеет минимум в точке пересечения направленной удлиненной линии, заданной вектором V₀V₁ и идущей с невидимой на видимую сторону граничной линии (так как только на границе t равно Q_i   /  P_i, а в остальной части видимой стороны больше).

Аналогично, если P_i    >   0, тогда соответствующее неравенство становится:

Для пояснения на рис. 0.2.11 показано пересечение с левой и правой границами при P_i    >   0.

Так как значения параметра t только на границе равны Q_i/P_i, а в остальной видимой части меньше Q_i/P_i, то значение параметра t имеет максимум на границе.

Наконец, если P_i    =   0, тогда соответствующее неравенство превращается в:

Заметим, что здесь нет зависимости от t, т.е. неравенство выполняется для всех t, если Q_i    і   0 и не имеет решения при Q_i   <   0. Для пояснения на рис. 0.2.12 иллюстрируется случай P_i    =   0.

Геометрически, если P_i    =   0, то нет точек пересечения удлиненной линии, определяемой точками V₀V₁, с линиями границы. Более того, если Q_i    <   0, то удлиненная линия находится на внешней стороне линии границы, а при Q_i    і   0 находится на внутренней стороне (включая ее). В последнем случае отрезок V₀V₁ может быть видим или нет в зависимости от того где находятся точки V₀V₁ на удлиненной линии. В предыдущем же случае нет видимого сегмента, так как удлиненная линия вне окна, т.е. это случай тривиального отбрасывания.

Все эти случаи суммированы на блок-схеме, представленной на рис. 0.2.13.

Итак, рассмотрение четырех неравенств дает диапазон значений параметра t, для которого удлиненная линия находится внутри окна отсечения. Однако, отрезок V₀V₁ только часть удлиненной линии и он описывается значениями параметра t в диапазоне: 0    Ј   t   Ј   1. Таким образом, решение задачи двумерного отсечения эквивалентно решению неравенств (0.2.6) при условии 0    Ј   t    Ј   1. Решение этой задачи сводится к далее описанному отысканию максимумов и минимумов.

Вспомним, что для всех i таких, что P_i    <   0, условие видимости имеет вид: t    і   Q_i  /  P_i. Из условия принадлежности точек удлиненной линии отрезку V₀V₁ имеем t    і   0. Таким образом, нужно искать:

Аналогично, для всех i таких что P_i    >   0, условие видимости - t    Ј   Q_i  /  P_i и, следовательно, Ј 1.

Наконец, для всех i, таких что P_i    =   0 следует проверить знак Q_i. Если Q_i    <   0, то это случай тривиального отбрасывания, задача отсечения решена и дальнейшие вычисления не нужны. Если же Q_i    і   0, то информации, даваемой неравенством, недостаточно и это неравенство игнорируется.

Правая часть неравенств (0.2.11) и (0.2.12) - значения параметра t, соответствующие началу и концу видимого сегмента, соответственно. Обозначим эти значения как t₀ и t₁:

Если сегмент отрезка V₀V₁ видим, то ему соответствует интервал параметра:

Следовательно, необходимое условие видимости сегмента:

Но это недостаточное условие, так как оно игнорирует случай тривиального отбрасывания при P_i    =   0, если Q_i    <   0. Тем не менее это достаточное условие для отбрасывания, т.е. если t₀    >   t₁, то отрезок должен быть отброшен. Алгоритм проверяет, если P_i    =   0     c    Q_i    <   0, или t₀ > t₁ и в этом случае отрезок немедленно отбрасывается без дальнейших вычислений.

В алгоритме t₀ и t₁ инициализируются в 0 и 1, соответственно. Затем последовательно рассматривается каждое отношение Q_i/P_i.

Если P_i    <   0, то отношение вначале сравнивается с t₁ и, если оно больше t₁, то это случай отбрасывания. В противном случае оно сравнивается с t₀ и, если оно больше, то t₀ должно быть заменено на новое значение.

Если P_i > 0, то отношение вначале сравнивается с t₀ и, если оно меньше t₀, то это случай отбрасывания. В противном случае оно сравнивается с t₁ и, если оно меньше, то t₁ должно быть заменено на новое значение.

Наконец, если Pi    =   0   и  Q_i < 0, то это случай отбрасывания.

На последнем этапе алгоритма, если отрезок еще не отброшен, то t₀ и t₁ используются для вычисления соответствующих точек. Однако, если t₀ = 0, то конечная точка равна V₀ и не требуется вычислений. Аналогично, если t₁ = 1, то конечная точка - V₁ и вычисления также не нужны.

Геометрический смысл этого процесса состоит в том, что отрезок удлиняется для определения где эта удлиненная линия пересекает каждую линию границы. Более детально, каждая конечная точка заданного отрезка V₀V₁ используется как начальное значение для конечных точек отсеченного отрезка C₀C₁. Затем вычисляются точки пересечения удлиненной линии с каждой линией границы (эти вычисления соответствуют вызову процедуры LB_tclip в программе). Если для данной линии границы направление, определяемое V₀V₁, идет с невидимой на видимую сторону линии границы, то эта точка пересечения вначале сравнивается с С₁. Если точка находится далее вдоль линии, тогда C₁ (и таким образом, С₀С₁) должна быть на невидимой стороне линии, поэтому отрезок должен быть отброшен. В противном случае точка пересечения сравнивается с С₀; если точка далее вдоль линии, тогда С₀ перемещается вперед к этой точке.

С другой стороны, если направление с видимой на невидимую сторону, тогда точка пересечения вначале сравнивается с С₀. Если С₀ далее вдоль линии, чем точка пересечения, тогда C₀ (и, следовательно C₀C₁) находится на невидимой стороне линии границы, т.е. отрезок должен быть отброшен. В противном случае точка пересечения сравнивается с С₁ и, если С₁ далее вдоль линии, тогда С₁ перемещается назад к точке пересечения.

Наконец, если удлиненная линия параллельна граничной линии и она на невидимой стороне, то отрезок отбрасывается. В конце алгоритма, если отрезок не отброшен, тогда C₀ и С₁ используются как конечные точки видимой части отрезка.

В Приложении 7 приведена C-подпрограмма V_LBclip, реализующая описанный выше алгоритм.

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

Из предыдущего пункта ясно, что для выполнения отсечения в параметрическом представлении необходимо иметь способ определения ориентации удлиненной линии, содержащей отсекаемый отрезок, относительно линии границы - с внешней стороны на внутреннюю или с внутренней на внешнюю, а также иметь способ определения расположения точки, принадлежащей отрезку, относительно окна - вне, на границе, внутри.

Для этих целей в алгоритме Кируса-Бека [29], реализующем отсечение произвольным выпуклым многоугольником, используется вектор внутренней нормали к ребру окна.

Внутренней нормалью N_в в точке А к стороне окна называется нормаль, направленная в сторону области, задаваемой окном отсечения.

Рассмотрим основные идеи алгоритма Кируса-Бека.

Так как многоугольник предполагается выпуклым, то может быть только две точки пересечения отрезка с окном. Поэтому надо найти два значения параметра t, соответствующие начальной и конечной точкам видимой части отрезка.

Пусть N_i - внутренняя нормаль к i-й граничной линии окна, а P = V₁ - V₀ - вектор, определяющий ориентацию отсекаемого отрезка, тогда ориентация отрезка относительно i-й стороны окна определяется знаком скалярного произведения P_i    =   N_i ·V, равного произведению длин векторов на косинус наименьшего угла, требуемого для поворота вектора N_i до совпадения по направлению с вектором V:

a) Изнутри наружу

б) Параллельно границе

в) Снаружи внутрь

Для определения расположения точки относительно окна вспомним параметрическое представление отсекаемого отрезка:

Рассмотрим теперь скалярное произведение внутренней нормали N_i к i-й границе на вектор Q(t) = V(t) - F_i, начинающийся в начальной точке ребра окна и заканчивающийся в некоторой точке V(t) удлиненной линии.

Аналогично предыдущему имеем (рис. 0.2.15):

a) Точка V вне

б) Точка V на границе

в) Точка V внутри

Подставляя в (0.2.19) параметрическое представление (0.2.18), получим условие пересечения отрезка с границей окна:

Раскрывая скобки, получим:

Используя (0.2.16) и (0.2.19) перепишем (0.2.21):

Разрешая (0.2.22) относительно t, получим:

Это уравнение и используется для вычисления значений параметров, соответствующих начальной и конечной точкам видимой части отрезка.

Как следует из (0.2.17), P_i равно нулю если отрезок либо вырожден в точку, либо параллелен границе. В этом случае следует проанализировать знак Q_i и принять или не принять решение об отбрасывании отрезка целиком в соответствии с условиями (0.2.17).

Если же P_i не равно 0, то уравнение (0.2.24) используется для вычисления значений параметров t, соответствующих точкам пересечений удлиненной линии с линиями границ.

Алгоритм построен следующим образом:

Искомые значения параметров t₀ и t₁ точек пересечения инициализируются значениями 0 и 1, соответствующими началу и концу отсекаемого отрезка.

Затем в цикле для каждой i-й стороны окна отсечения вычисляются значения скалярных произведений, входящих в (0.2.23).

Если очередное P_i равно 0, то отсекаемый отрезок либо вырожден в точку, либо параллелен i-й стороне окна. При этом достаточно проанализировать знак Q_i. Если Q_i < 0, то отрезок вне окна и отсечение закончено иначе рассматривается следующая сторона окна.

Если же P_i не равно 0, то по (0.2.24) можно вычислить значение параметра t для точки пересечения отсекаемого отрезка с i-й границей. Так как отрезок V₀V₁ соответствует диапазону 0 Ј t Ј 1, то все решения, выходящие за данный диапазон следует отбросить. Выбор оставшихся решений определяется знаком P_i.

Если P_i < 0, т.е. удлиненная линия направлена с внутренней на внешнюю стороны граничной линии, то ищутся значения параметра для конечной точки видимой части отрезка. В этом случае определяется минимальное значение из всех получаемых решений. Оно даст значение параметра t₁ для конечной точки отсеченного отрезка. Если текущее полученное значение t₁ окажется меньше, чем t₀, то отрезок отбрасывается, так как нарушено условие t₀    Ј   t₁.

Если же P_i    >   0, т.е. удлиненная линия направлена с внешней на внутреннюю стороны граничной линии, то ищутся значения параметра для начальной точки видимой части отрезка. В этом случае определяется максимальное значение из всех получаемых решений. Оно даст значение параметра t₀ для начальной точки отсеченного отрезка. Если текущее полученное значение t₀ окажется больше, чем t₁, то отрезок отбрасывается, так как нарушено условие t₀    Ј   t₁.

На заключительном этапе алгоритма значения t₀ и t₁ используются для вычисления координат точек пересечения отрезка с окном. При этом, если t₀ = 0, то начальная точка осталась V₀ и вычисления не нужны. Аналогично, если t₁ = 1, то конечная точка осталась V₁ и вычисления также не нужны.

Все эти случаи пояснены на блок-схеме, представленной на рис. 0.2.16.

Вычисления значений параметров t₀ и t₁ выполняются в соответствии с выражениями (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 и предназначенной для установки многоугольного окна отсечения.

Разбиение невыпуклых многоугольников

Одновременное проведение операций проверки на выпуклость и разбиение простого невыпуклого многоугольника на выпуклые обеспечивается методом переноса и поворотов окна.

Алгоритм метода при обходе вершин многоугольника против часовой стрелки состоит в следующем:

1. Для каждой i-й вершины многоугольник сдвигается для переноса упомянутой вершины в начало координат.
2. Многоугольник поворачивается против часовой стрелки для совмещения (i+1)-й вершины с положительной полуосью X.
   Вектор внутреннего перпендикуляра к ребру, образованному вершинами i-й и (i+1)-й, вычисляется поворотом ребра на -90^° против часовой стрелки.
3. Анализируется знак Y-координаты (i+2)-й вершины.
   Если Y_i+2 і 0, то в (i+1)-й вершине выпуклость.
   Если Y_i+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

в) Невыпуклость после вершины 5

Повторное применение алгоритма в многоугольнику, образованному вершинами 2, 3, 4, 6, 7, [7\tilde], показано на рис. 0.2.18 в).

Данный алгоритм не обеспечивает минимальность числа вновь полученных выпуклых многоульников и некорректно работает если имеется самопересечение сторон, как это показано на рис. 0.2.19.

Во многих работах приводятся качественные соображения по быстродействию различных алгоритмов отсечения. В части работ, например, [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).

НОВОСТИ ФОРУМА Рыцари теории эфира

10.11.2021 - 12:37: ПЕРСОНАЛИИ - Personalias -> WHO IS WHO - КТО ЕСТЬ КТО - Карим_Хайдаров. 10.11.2021 - 12:36: СОВЕСТЬ - Conscience -> РАСЧЕЛОВЕЧИВАНИЕ ЧЕЛОВЕКА. КОМУ ЭТО НАДО? - Карим_Хайдаров. 10.11.2021 - 12:36: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от д.м.н. Александра Алексеевича Редько - Карим_Хайдаров. 10.11.2021 - 12:35: ЭКОЛОГИЯ - Ecology -> Биологическая безопасность населения - Карим_Хайдаров. 10.11.2021 - 12:34: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> Проблема государственного терроризма - Карим_Хайдаров. 10.11.2021 - 12:34: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> ПРАВОСУДИЯ.НЕТ - Карим_Хайдаров. 10.11.2021 - 12:34: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Вадима Глогера, США - Карим_Хайдаров. 10.11.2021 - 09:18: НОВЫЕ ТЕХНОЛОГИИ - New Technologies -> Волновая генетика Петра Гаряева, 5G-контроль и управление - Карим_Хайдаров. 10.11.2021 - 09:18: ЭКОЛОГИЯ - Ecology -> ЭКОЛОГИЯ ДЛЯ ВСЕХ - Карим_Хайдаров. 10.11.2021 - 09:16: ЭКОЛОГИЯ - Ecology -> ПРОБЛЕМЫ МЕДИЦИНЫ - Карим_Хайдаров. 10.11.2021 - 09:15: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Екатерины Коваленко - Карим_Хайдаров. 10.11.2021 - 09:13: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Вильгельма Варкентина - Карим_Хайдаров.