Глава 4. алгоритмы растровой графики
Рисование отрезков прямых
Растром называется прямоугольная сетка точек, формирующих изображение на экране компьютера. Каждая точка растра характеризуется двумя параметрами: своим положением на экране и своим цветом, если монитор цветной, или степенью яркости, если монитор черно-белый. Поскольку растровые изображения состоят из множества дискретных точек, то для работы с ними необходимы специальные алгоритмы. Рисование отрезка прямой линии - одна из простейших задач растровой графики. Смысл ее заключается в вычислении координат пикселов, находящихся вблизи непрерывных отрезков, лежащих на двумерной растровой сетке.
Термин “пиксел” образован от английского 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}