ДВУХМЕРНОЕ ОТСЕЧЕНИЕ ЛИНИИ
На рис. 6.11 иллюстрируются возможные положения прямых отрезков относительно стандартного отсекающего окна. Алгоритм отсечения линии обрабатывает каждую
Рис. 6.11. Отсечение прямых отрезков с использованием стандартного прямоугольного отсекающего окна линию на сцене с помощью последовательности проверок и расчетов точек пересечения, позволяющих определить, нужно ли записывать линию или ее часть. Ресурсоемкой частью процедуры отсечения линии является расчет точек пересечения линии со сторонами окна. Следовательно, главная цель любого алгоритма отсечения линии - минимизировать расчет точек пересечения. Чтобы это сделать, можно вначале выполнить проверку и определить, не находится ли участок линии полностью внутри или полностью снаружи отсекающего окна. Определить, что линия полностью внутри отсекающего окна, легко, гораздо сложнее идентифицировать все линии, полностью лежащие за окном. Если мы не можем отнести линию к полностью внутренним или полностью внешним, нужно вычислить точки пересечения линии с периметром окна.
Обработка отрезков на сцене с использованием простого подхода отсечения, описанного в предыдущем абзаце, является прямолинейной, но не очень эффективной. Вообще, исходную проверку и расчет точек пересечения можно переформулировать так, чтобы сократить время обработки набора прямых отрезков, и в настоящее время разработано несколько более быстрых схем отсечения линий. Некоторые из этих алгоритмов явно разработаны для двухмерных изображений, некоторые легко адаптируются для наборов трехмерных отрезков.
ОТСЕЧЕНИЕ ЛИНИЙ КОЭНА-САЗЕРЛЕНДА
Одним из первых алгоритмов, разработанных для быстрого отсечения линий, является схема Коэна-Сазерленда (Cohen-Sutherland), и разновидности этого метода очень широко используются. Время обработки в этом методе сокращено за счет большего числа проверок перед обработкой (нахождением точек пересечения). Изначально всем конечным точкам линий на изображении присваивается четырехзначное двоичное значение, называемое кодом области, и каждый двоичный разряд указывает, находится точка внутри или вне одной границы отсекающего окна. Границы окна можно пронумеровать в любом порядке, и на рис. 6.12 иллюстрируется одно возможное упорядочение, когда двоичные разряды нумеруются от 1 до 4 слева направо. Следовательно, при таком упорядочении крайний справа разряд (бит 1) соответствует левой границе отсекающего окна, а крайний слева разряд (бит 4) соответствует верхней границе окна. Значение 1 (или true) в любом разряде указывает, что конечная точка находится вне данной границы окна. Аналогично значение 0 (или false) в любом разряде указывает, что конечная точка не находится снаружи (внутри или на границе) соответствующей стороны окна. Иногда код области называется “командой на выключение”, поскольку значение 1 в любом разряде указывает, что пространственная точка находится вне соответствующей границы отсечения.
Каждая сторона отсекающего окна делит двухмерное пространство на внутреннюю половину пространства и внешнюю. Всего четыре границы окна формируют девять областей, а на рис. 6.13 перечислены значения двоичного кода во всех этих областях. Следовательно, конечной точке, которая находится ниже и слева от отсекаfl