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

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

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

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

Закрашенная многоугольная область определяется списком вершин, а процедуры отсечения многоугольников должны содержать информацию о том, как извлеченные стороны соединяются при передаче многоугольника по различным этапам обработки. В алгоритме Сазерленда-Ходгмана пары вершин закрашенной области последовательно обрабатываются всеми процедурами отрезания по границе обработки, и информация по данной стороне немедленно передается следующей процедуре отсечения, что позволяет параллельно выполнять четыре процедуры обработки (отсечение слева, справа, снизу и сверху). Данный алгоритм является эффективным методом отсечения закрашенных областей в виде вогнутых многоугольников. Однако, если обрезаемый вогнутый многоугольник содержит несвязанные области, алгоритм Сазерленда-Ходгмана дает посторонние соединяющие отрезки. Расширения процедур параметрического отсечения, таких как метод Лианга-Барски, также могут использоваться для отсечения выпуклых закрашенных областей. Алгоритм Уэйлера-Азертона, в котором применяется обход границы, позволяет корректно обрабатывать как выпуклые, так и вогнутые закрашенные области.


⇐ вернуться назад | | далее ⇒