Рисование отрезков прямых
Растром называется прямоугольная сетка точек, формирующих изображение на экране компьютера. Каждая точка растра характеризуется двумя параметрами: своим положением на экране и своим цветом, если монитор цветной, или степенью яркости, если монитор черно-белый. Поскольку растровые изображения состоят из множества дискретных точек, то для работы с ними необходимы специальные алгоритмы. Рисование отрезка прямой линии - одна из простейших задач растровой графики. Смысл ее заключается в вычислении координат пикселов, находящихся вблизи непрерывных отрезков, лежащих на двумерной растровой сетке.
Термин “пиксел” образован от английского pixel (picture element - элемент изображения) - то есть точка на экране. Будем считать, что пикселы имеют целочисленные координаты. На первый взгляд кажется, что эта задача имеет простое решение. Пусть конечные точки отрезка имеют целочисленные координаты, и уравнение прямой, содержащей отрезок: 
. Не нарушая общности, будем также считать, что тангенс угла наклона прямой лежит в пределах от 0 до 1. Тогда для изображения отрезка на растре достаточно для всех целых 
, принадлежащих отрезку, выводить на экран точки с координатами 
. Однако в этом методе присутствует операция умножения 
. Хотелось бы иметь алгоритм без частого использования операции умножения вещественных чисел. Избавиться от операции умножения можно следующим образом. Поскольку 
, то один шаг по целочисленной сетке на оси будет соответствовать 
. Отсюда получаем, что 
будет увеличиваться на величину 
. Итерационная последовательность выглядит следующим образом:
, 
Когда 
, то шаг по будет приводить к шагу по 
, поэтому и следует поменять ролями, придавая единичное приращение, а будет увеличиваться на 
единиц. Этот алгоритм все же не свободен от операций с вещественными числами. Наиболее изящное решение задачи растровой развертки отрезков прямых было найдено Брезенхемом. В его алгоритме вообще не используются
 |
операции с вещественными числами, в том числе операции умножения и деления.
Для вывода формул алгоритма Брезенхема рассмотрим рис. 30.
Пусть начало отрезка имеет координаты 
, а конец 
. Обозначим 
, 
. Не нарушая общности, будем считать, что начало отрезка совпадает с началом координат, и прямая имеет вид 
, где 
. Считаем что начальная точка находится слева. Пусть на 
-м шаге текущей точкой отрезка является 
. Выбор следующей точки 
или 
зависит от знака разности 
. Если 
, то 
и тогда , 
, если же 
, то 
и тогда 
, 
.
, 
, 
.
Поскольку знак 
совпадает со знаком разности , то будем проверять знак выражения 
. Так как 
и 
, то 
.
Пусть на предыдущем шаге 
, тогда 
и 
. Если же на предыдущем шаге 
, то 
и 
.
Осталось узнать, как вычислить 
. Так как при 
:
, 
.
Далее приводится листинг процедуры на языке Паскаль, реализующей алгоритм Брезенхема.
Procedure Bresenham(x1,y1,x2,y2,Color: integer);
var
dx,dy,incr1,incr2,d,x,y,xend: integer;
begin
dx:= ABS(x2-x1);
dy:= Abs(y2-y1);
d:=2*dy-dx; {начальное значение для d}
incr1:=2*dy; {приращение для d<0}
incr2:=2*(dy-dx); {приращение для d>=0}
if x1>x2 then {начинаем с точки с меньшим знач. x}
begin
x:=x2;
y:=y2;
xend:=x1;
end
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 точки пересечения найдена, тогда
Рассмотрим алгоритм Коэна-Сазерленда для отсечения отрезков прямых. Этот алгоритм позволяет легко определять нахождение отрезка полностью внутри или полностью снаружи окна, и если так, то его можно рисовать или не рисовать, не заботясь об отсечении по границе окна.
Для работы алгоритма вся плоскость в которой лежит окно разбивается на девять подобластей или квадрантов, как показано на рис. 31.
Окну соответствует область обозначенная кодом 0000. Конечным точкам отрезка приписывается 4-битный код “вне/внутри” в зависимости от нахождения отрезка в соответствующей подобласти. Каждому биту присваивается значение 1 в соответствии со следующим правилом.
Бит 1 - точка находится выше окна;
Бит 2 – точка находится ниже окна;
Бит 3 - точка находится справа от окна;
Бит 4 - точка находится слева от окна;
Иначе биту присваивается нулевое значение. Значения этих битов для конечных точек отрезков легко определить по знакам соответствующих разностей: 
- для 1-го бита, 
- для 2-го бита, 
- для 3-го бита и 
- для 4-го бита. Отрезок рисуется без отсечения, то есть принимается целиком, если оба кода равны 0000, или 
ИЛИ 
, где ИЛИ – бинарная операция. Отрезок отбрасывается без вычислений если оба его конца находятся выше, ниже, правее или левее окна. В этих случаях соответствующие биты в обоих кодах равны 1 и это легко определить, умножив эти коды по бинарной операции И. Если результат операции И равен 0000, то отрезок нельзя ни принять ни отбросить, так как он может пересекаться с окном. В этом случае применяется последовательное разделение отрезка, так что на каждом шаге конечная точка отрезка с ненулевым кодом вне/внутри заменяется на точку, лежащую на стороне окна или на прямой содержащей сторону. При этом порядок перебора сторон окна не имеет значения.
Далее приводится текст процедуры на языке Паскаль, с довольно изящной реализацией этого метода. Отрезок задан граничными точками 
, 
, границы окна: xmin, xmax, ymin, ymax. Используются вызовы процедур: Accept_Check – выполняет проверку на полное принятие отрезка; Reject_Check – на полный отказ от рисования отрезка; 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);
{проверка на отбрасывание}
reject:=Reject_Check(outcode1,outcode2);
if reject then done:= true
else
begin {возможно принятие целиком}
accept:=Accept_Check(outcode1,outcode2);
if accept then done:=true
else
begin {разделить отрезок}
{если P1 внутри, то с помощью SWAP сделать снаружи}
if not((outcode1[1])or(outcode1[2])or
(outcode1[3])or(outcode1[4])) then SWAP;
{теперь P1 перемещается в точку пересечения}
if outcode1[1] then
begin {отбросить верхнюю часть}
x1:=x1+(x2-x1)*(ymax-y1)/(y2-y1);
y1:=ymax;
end
else if outcode1[2] then
if outcode1[1] then
begin {отбросить нижнюю часть}
x1:=x1+(x2-x1)*(ymin-y1)/(y2-y1);
y1:=ymin;
end
else if outcode1[3] then
begin {отбросить правую часть}
y1:=x1+(y2-y1)*(ymax-x1)/(x2-x1);
x1:=xmax;
end
else if outcode1[4] then
begin {отбросить левую часть}
y1:=x1+(y2-y1)*(ymin-x1)/(x2-x1);
x1:=xmin;
end;
end;
end;
until done;
if accept then
Line(x1,y1,x2,y2); {нарисовать отрезок}
end;{procedure}
