else begin

x:=x1;

y:=y1;

xend:=x2; end;

PutPixel(x,y,Color); {первая точка отрезка} While x<xend do begin

x:=x+1; if d<0 then

d:=d+incr1{выбираем нижнюю точку}

else begin

y:=y+1;

d:=d+incr2; {выбираем верхнюю точку, y-возрастает} end;

PutPixel(x,y,Color); end;{while} end;{procedure}

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

x - x1 + t(x2 - x\)

y - y1 +1 (y 2 - y1). Для t e [0,1] эти уравнения определяют точки, находящиеся между (x1, y1) и (x2, y2). Специальной проверки требует случай, когда отрезок

параллелен стороне окна. Пусть координата x точки пересечения найдена, тогда

x xix xi /\

t - --- == y - y1 + --- (y 2 - y1)

Рассмотрим алгоритм Коэна-Сазерленда для отсечения отрезков прямых. Этот алгоритм позволяет легко определять нахождение отрезка полностью внутри или полностью снаружи окна, и если так, то его можно рисовать или не рисовать, не заботясь об отсечении по границе окна.

Для работы алгоритма вся плоскость в которой лежит окно разбивается на девять подобластей или квадрантов, как показано на рис. 30.

Рис. 30. Разбиение на подобласти в методе Коэна-Сазерленда.

Окну соответствует область обозначенная кодом 0000. Конечным точкам отрезка приписывается 4-битный код "вне/внутри" в зависимости от нахождения отрезка в соответствующей подобласти. Каждому биту присваивается значение 1 в соответствии со следующим правилом.

Бит 1 - точка находится выше окна;

Бит 2 - точка находится ниже окна;

Бит 3 - точка находится справа от окна;

Бит 4 - точка находится слева от окна;

Иначе биту присваивается нулевое значение. Значения этих битов для конечных точек отрезков легко определить по знакам соответствующих разностей: (ymax - y) - для 1-го бита, (y - ymm) - для 2-го бита, (xmax - x) -

для 3-го бита и (x - xmm) - для 4-го бита. Отрезок рисуется без отсечения, то

есть принимается целиком, если оба кода равны 0000, или [KodP1] ИЛИ [KodP 2] = 0000, где ИЛИ - бинарная операция. Отрезок отбрасывается без вычислений если оба его конца находятся выше, ниже, правее или левее окна. В этих случаях соответствующие биты в обоих кодах равны 1 и это легко определить, умножив эти коды по бинарной операции И. Если результат операции И равен 0000, то отрезок нельзя ни принять ни отбросить, так как он может пересекаться с окном. В этом случае применяется последовательное разделение отрезка, так что на каждом шаге конечная точка отрезка с ненулевым кодом вне/внутри заменяется на точку, лежащую на стороне окна или на прямой содержащей сторону. При этом порядок перебора сторон окна не имеет значения.

Далее приводится текст процедуры на языке Паскаль, с довольно изящной реализацией этого метода. Отрезок задан граничными точками P1 = (x1, y1), P 2 = (x 2, y 2), границы окна: xmin, xmax, ymin, ymax.

Используются вызовы процедур: AcceptCheck - выполняет проверку на полное принятие отрезка; RejectCheck - на полный отказ от рисования отрезка; Outcodes - вычисляет 4-х битовый код "вне/внутри"; SWAP - меняет местами координаты двух точек.

Procedure CLIP(x1,x2,y1,y2,xmin,xmax,ymin,ymax: real);

type

outcode = array[1..4] of boolean; var

accept,reject,done: boolean; outcode1,outcode2,

outcode3,outcode4:outcode;{коды вне/внутри} begin

accept:= false;

reject:= false;

done:= false; repeat

Outcodes(x1,y1,outcode1); Outcodes(x2,y2,outcode2); { проверка на отбрасывание}