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

 

Суть задачи отсечения двухмерных отрезков поясняется на рисунке 8.1. Проецирование уже выполнено и имеется двухмерное описание изображения в картинной плоскости. На этой же плоскости определена и рамка отсечения, которая соответствует видовому окну на экране дисплея. Все параметры заданы вещественными числами.

 

 

 

Рис. 8.1. Двумерное отсечение

 

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

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

 

Рис.8.2. Характеристические коды областей

 

Каждой области присваивается четырехразрядный двоичный номер - характеристический код(b₀b₁b₂b₃),который формируется следующим образом. Пусть (х,у)— координаты некоторой точки на картинной плоскости. Тогда

Аналогично, b₁, приравнивается 1, если у < у_тin, а значения b₂ и b₃ определяются отношением между компонентой х и абсцисcами левой и правой границ рамки отсечения. В результате девяти областям присваиваются коды, представленные на рис.8.2.

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

Рассмотрим отрезок, конечные точки которого имеют ха­рактеристические коды o1=outcode(x1,y1) и о2=outcode(x2, y2). Возможны четыре варианта сочетания характеристических кодов двух конечных точек (рис.8.1).

1. (о1 = o2 = 0). Обе конечные точки лежат внутри рамки отсечения — этот случай пред­ставлен отрезком АВ на рис.8.1. Весь отрезок при этом также находится внутри рамки отсечения и может быть передан дальше для выполнения растрового преобразования.

2. (o1≠0, o2 = 0 или наоборот). Одна точка находится внутри рамки отсечения, а вто­рая — вне ее (отрезок CD на рис. 8.1). В этом случае отрезок необходимо разделить.

3. (о1 & o2≠;0). По результату побитовой операции AND над характеристическими кодами крайних точек можно выяснить, лежат ли они по одну сторону от границы рамки или по разные. Если результат отличен от нуля, то конечные точки лежат по одну сторону от какой-либо границы, а значит, весь отрезок лежит вне рамки отсечения и его можно спокойно отбросить (отрезок EF на рис.8.1).

4. (o1 & о2 = 0). Обе конечные точки лежат вне рамки отсечения, но по разные стороны от двух ее границ. Этот вариант представлен отрезками GH и IJ на рис.8.1. Здесь нельзя с уверенностью сказать, пересекает отрезок зону видимости или нет. Требу­ется более тщательный анализ — нужно вычислить точку пересечения с одной из границ рамки и проанализировать характеристические коды крайних точек двух но­вых отрезков.

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