На рис.2.7.1. показана плоская сцена и отсекающее окно регулярной формы. Окно задается левым (Л), правым (П), верхним (В) и нижним (Н) двумерными ребрами. Регулярным отсекающим окном является прямоугольник, стороны которого параллельны осям координат объектного пространства или осям координат экрана. Целью алгоритма отсечения является определение тех точек, отрезков или их частей, которые лежат внутри отсекающего окна. Эти точки, отрезки или их части остаются для визуализации. А все остальное отбрасывается.

Поскольку в обычных сценах или картинках необходимо отсекать большое число отрезков или точек, то эффективность алгоритмов отсечения представляет особый интерес. Во многих случаях подавляющее большинство точек или отрезков лежит целиком внутри или вне отсекающего окна. Поэтому важно уметь быстро отбирать отрезки, подобные аb, или точки, подобные р, и отбрасывать отрезки, подобные ij, или точки, подобные q на рис.2.7.1.

Точки, лежащие внутри отсекающего окна, удовлетворяют условию:

x_л <= х <= x_п и у_н <= у <= у_в.

рис. 2.7.1.

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

Отрезок лежит внутри окна и, следовательно, является видимым, если обе его концевые точки лежат внутри окна, например отрезок ab на рис. 2.7.1. Однако если оба конца отрезка лежат вне окна, то этот отрезок не обязательно лежит целиком вне окна, например отрезок gh на рис. 2.7.1. Если же оба конца отрезка лежат справа, слева, выше или ниже окна, то этот отрезок целиком лежит вне окна, а значит, невидим. Проверка последнего условия устранит все отрезки, помеченные ij на рис. 2.7.1. Но она не устранит ни отрезка gh, который видим частично, ни отрезка kl, который целиком невидим.

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

Алгоритм Коэна-Сазерленда

Для решения задачи определения принадлежности отрезка полю вывода используется следующий метод. Пространство разбивается на 9 областей, каждая из областей кодируется бинарным 4-х битным кодом рис. 2.7.2.

«Кодирование пространства» рис. 2.7.2.

Для каждого отрезка рассчитываются коды концов (К₁, К₂) затем производится экспресс анализ:

· Если, тогда отрезок лежит вне поля вывода – отрезок отбрасывается

· Если , тогда отрезок полностью лежит внутри поля вывода – отсечение не нужно, отрезок полностью прорисовывается

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

Алгоритм отсечения по прямоугольной области

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

«Отсечение отрезка по прямоугольной области» рис.2.7.3.

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

На каждом шаге отсечения вычисляются новые координаты одной точек, найдем формулы для вычисления новых координат.

рис.2.7.4.

Формулы для расчета новых координат:

а) б)

;