2. Процедуры машинной графики

2.2. Алгоритмы отсечения векторов

 
 

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

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

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

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

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

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

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

X = XЛ,      Х = ХП,

Y = YЛ,      Y = YП.

Подставляя в уравнение отрезка прямой Y=k·Х+b значение XЛ, ХП находят ординаты пересечения соответственно с левой и правой границами окна. Аналогично находят и точки пересечения с верхней и нижней границами окна. Для этого в уравнение прямой подставляют известные значения YЛ, YП.

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

Провести тестирования полной видимости или невидимости отрезков можно с помощью алгоритма Д.Коэна и А.Сазерленда.

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

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

1 0 0 1     1 0 0 0     1 0 1 0

0 0 0 1     0 0 0 0     0 0 1 0

0 1 0 1      0 1 0 0     0 1 1 0

Единицы в соответствующих разрядах кода означают:

*  в первом – точка над верхним краем области индикации;

*  во втором – точка под нижним краем области индикации;

*  в третьем – точка по правую сторону от области индикации;

*  в четвертом – точка слева от левого края области индикации.

Рассмотрим характерные случаи.

Четырехразрядные коды граничных точек отрезка прямой AB, который полностью принадлежит окну (рис.2.3), нулевые.

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

1.     Четырехразрядные коды граничных точек отрезка прямой, который размещен по одну из сторон окна (рис.2.3, отрезок QL), совпадают. Для установления указанного достаточно выполнить операцию логического умножения этих двух кодов, что для указанного случая даст ненулевой результат.

2.     Четырехразрядные коды граничных точек отрезка прямой, который частично находится в области индикации (рис.2.3, отрезки KD, HZ) не совпадают. Результат логического умножения этих кодов даст нулевой результат.

Для указанного случая необходимо выполнить отсечения. Координаты точки отрезка, которая принадлежит одной из границ окна, находят из уравнения отрезка y=k·x+b подстановкой в него соответствующих координат граничных точек окна и нахождением неизвестной координаты.

Для отрезка HZ находят точку пересечения F, которая делит отрезок на два составных. Вдальнейшем для каждого полученного отрезка выполняем алгоритм Коэна-Сазерленда. В результате анализа отрезок FZ отбрасывается.

Наиболее сложным для отсечения есть случай, когда отрезок прямой дважды пересекает границы окна (рис.2.3, отрезок KD). В этом случае алгоритм Коэна-Сазерленда выполняется для трех составных отрезков – KE, EP, PD.

3.     Если отрезок прямой лежит за областью окна и при этом его граничные точки не принадлежат одинаковым подобластям (рис.2.3, отрезок SV), то результат логического умножения четырехразрядных кодов даст нулевой результат. Для определения полной видимости необходимо проверять значения кодов обоих концов в отдельности.

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

Рис. 2.3. Размещение отрезков прямых относительно окна

Алгоритм был предложен Спрулом и Сазерлендом и включает в себя в качестве составного алгоритм Коэна-Сазерленда. Алгоритм используется тогда, когда алгоритм Коэна-Сазерленда не дает положительных результатов на предмет принадлежности отрезка окну или его расположения вне окна.

В алгоритме отсечения методом деления отрезка пополам используются коды конечных точек отрезка и проверки, которые выявляют полную видимость отрезков, например отрезок a на рис.2.4, и тривиальную невидимость отрезков, например отрезок b на рис.2.4.

 

Рис. 2.4. Реализация отсечения согласно алгоритма деления отрезка пополам

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

Xm = (X2+X1)/2,

Ym = (Y2+Y1)/2.

Аналогичные действия применяются к каждым полученным половинам отрезков до тех пор, пока не будет определено пересечение с одной из сторон окна или длина рассматриваемого отрезка станет слишком малой, то есть, пока он не превратится в точку. Количество шагов данного алгоритма равно log2N, где N – длина отрезка.

Данный метод проиллюстрирован на примере отрезка с (рис.2.4). Точка Р1 запоминается, как текущая видимая точка, а отрезок с разбивается пополам точкой Pm1. Отрезок Р2Pm1 отбрасывается, как невидимый, а отрезок Р1Pm1 разбивается пополам точкой Pm2. Отрезок Pm1Pm2 отбрасывается, а в окне остается отрезок P1Pm2 потому, что проверка по алгоритму Коэна-Сазерленда показывает, что данный отрезок полностью лежит в области индикации.

Контрольные  вопросы.

1.  В чем состоит процедура отсечения?

2.  Чем обусловлено появление метода деления отрезка пополам?

3.  Какие действия выполняются согласно метода Коэна-Сазерленда?

     Содержание