целиком невидимым (отрезок 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.Определение нового кода начальной точки.
4.3.6. Отсечение многоугольника
Многоугольники особенно важны в растровой графике как средство задания поверхностей.
77
Будем называть многоугольник, используемый в качестве окна отсечения, отсекателем, а многоугольник, который отсекается, – отсекаемым.
Алгоритм отсечения многоугольника должен в результате отсечения -да вать один или несколько замкнутых многоугольников(см. рисунок 38). При этом могут быть добавлены новые ребра, а имеющиеся или сохранены или разделены или даже отброшены. Существенно, чтобы границы окна, которые не ограничивают видимую часть отсекаемого многоугольника, не входили в состав результата отсечения. Если это не выполняется, то возможна излишняя закраска границ окна (см. рисунок 35.).
Рисунок 35 – Отсечение окном PQRS многоугольников ABCDEFGHIJ и KLMN
В принципе эту задачу можно решить с использованием рассмотренных выше алгоритмов отсечения линий, если рассматривать многоугольник просто как набор векторов, а не как сплошные закрашиваемые области. При этом вектора, составляющие многоугольник, просто последовательно отсекаются сторонами окна (см. рисунок 36).
78
Рисунок 36 – Отсечение окном PQRS многоугольника ABCD, рассматриваемого как набор векторов.
Генерируется вывод из двух векторов BsCs и DsAs.
Если же в результате отсечения должен быть получен замкнутый многоугольник, то формируется вектор, соединяющий последнюю видимую точку с точкой пересечения с окном (см. рисунок 37). Проблема возникает при окружении отсекаемым многоугольником угла окна (см. рисунок 37).
Рисунок 37 – Отсечение сплошного многоугольника окном.
Рассмотрим алгоритмы корректно решающие задачу отсечения сплошного многоугольника. Первый алгоритм быстро работает, но генерирует лишние ребра, как это продемонстрировано на рис. Второй алгоритм свободен от указанного недостатка.
79
В общем, при отсечении многоугольников возникают два типа задачотображение части изображения попавшей в окно и наоборотображение, изображения, находящегося вне окна. Все здесь рассматриваемые алгоритмы могут использоваться в обоих случаях.
4.3.6.1. Алгоритм Сазерленда-Ходгмана
Простой метод решения проблемы охвата отсекаемым многоугольником вершины окна предлагается в алгоритме Сазерленда-Ходгмана, когда весь многоугольник последовательно отсекается каждой границей окна, как это показано на рисунке 38.
Рисунке 38 – Последовательное отсечение многоугольника сторонами окна.
При отсечении ребра, соединяющего очередную пару вершин K и L, возможны 4 случая взаимного расположения (рисунок 39):
1)ребро на внутренней стороне границы,
2)ребро выходит из окна наружу,
3)ребро на внешней стороне границы,
4)ребро входит снаружи в окно.
Рисунок 39 – Относительные расположения ребра и границы окна
80