Глава 4. алгоритмы растровой графики

Рисование отрезков прямых

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

Термин “пиксел” образован от английского pixel (picture element - элемент изображения) - то есть точка на экране. Будем считать, что пикселы имеют целочисленные координаты. На первый взгляд кажется, что эта задача имеет простое решение. Пусть конечные точки отрезка имеют целочисленные координаты, и уравнение прямой, содержащей отрезок: глава 4. алгоритмы растровой графики - student2.ru . Не нарушая общности, будем также считать, что тангенс угла наклона прямой лежит в пределах от 0 до 1. Тогда для изображения отрезка на растре достаточно для всех целых глава 4. алгоритмы растровой графики - student2.ru , принадлежащих отрезку, выводить на экран точки с координатами глава 4. алгоритмы растровой графики - student2.ru . Однако в этом методе присутствует операция умножения глава 4. алгоритмы растровой графики - student2.ru . Хотелось бы иметь алгоритм без частого использования операции умножения вещественных чисел. Избавиться от операции умножения можно следующим образом. Поскольку глава 4. алгоритмы растровой графики - student2.ru , то один шаг по целочисленной сетке на оси глава 4. алгоритмы растровой графики - student2.ru будет соответствовать глава 4. алгоритмы растровой графики - student2.ru . Отсюда получаем, что глава 4. алгоритмы растровой графики - student2.ru будет увеличиваться на величину глава 4. алгоритмы растровой графики - student2.ru . Итерационная последовательность выглядит следующим образом:

глава 4. алгоритмы растровой графики - student2.ru , глава 4. алгоритмы растровой графики - student2.ru

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

 
  глава 4. алгоритмы растровой графики - student2.ru

операции с вещественными числами, в том числе операции умножения и деления.

Для вывода формул алгоритма Брезенхема рассмотрим рис. 30.

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

глава 4. алгоритмы растровой графики - student2.ru , глава 4. алгоритмы растровой графики - student2.ru , глава 4. алгоритмы растровой графики - student2.ru

глава 4. алгоритмы растровой графики - student2.ru глава 4. алгоритмы растровой графики - student2.ru

глава 4. алгоритмы растровой графики - student2.ru .

Поскольку знак глава 4. алгоритмы растровой графики - student2.ru совпадает со знаком разности глава 4. алгоритмы растровой графики - student2.ru , то будем проверять знак выражения глава 4. алгоритмы растровой графики - student2.ru . Так как глава 4. алгоритмы растровой графики - student2.ru и глава 4. алгоритмы растровой графики - student2.ru , то глава 4. алгоритмы растровой графики - student2.ru .

Пусть на предыдущем шаге глава 4. алгоритмы растровой графики - student2.ru , тогда глава 4. алгоритмы растровой графики - student2.ru и глава 4. алгоритмы растровой графики - student2.ru . Если же на предыдущем шаге глава 4. алгоритмы растровой графики - student2.ru , то глава 4. алгоритмы растровой графики - student2.ru и глава 4. алгоритмы растровой графики - student2.ru .

Осталось узнать, как вычислить глава 4. алгоритмы растровой графики - student2.ru . Так как при глава 4. алгоритмы растровой графики - student2.ru :

глава 4. алгоритмы растровой графики - student2.ru , глава 4. алгоритмы растровой графики - student2.ru .

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

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}

Отсечение

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

глава 4. алгоритмы растровой графики - student2.ru

глава 4. алгоритмы растровой графики - student2.ru .

Для глава 4. алгоритмы растровой графики - student2.ru эти уравнения определяют точки, находящиеся между глава 4. алгоритмы растровой графики - student2.ru и глава 4. алгоритмы растровой графики - student2.ru . Специальной проверки требует случай, когда отрезок параллелен стороне окна. Пусть координата x точки пересечения найдена, тогда

глава 4. алгоритмы растровой графики - student2.ru глава 4. алгоритмы растровой графики - student2.ru глава 4. алгоритмы растровой графики - student2.ru

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

глава 4. алгоритмы растровой графики - student2.ru Для работы алгоритма вся плоскость в которой лежит окно разбивается на девять подобластей или квадрантов, как показано на рис. 31.

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

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

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

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

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

Иначе биту присваивается нулевое значение. Значения этих битов для конечных точек отрезков легко определить по знакам соответствующих разностей: глава 4. алгоритмы растровой графики - student2.ru - для 1-го бита, глава 4. алгоритмы растровой графики - student2.ru - для 2-го бита, глава 4. алгоритмы растровой графики - student2.ru - для 3-го бита и глава 4. алгоритмы растровой графики - student2.ru - для 4-го бита. Отрезок рисуется без отсечения, то есть принимается целиком, если оба кода равны 0000, или глава 4. алгоритмы растровой графики - student2.ru ИЛИ глава 4. алгоритмы растровой графики - student2.ru , где ИЛИ – бинарная операция. Отрезок отбрасывается без вычислений если оба его конца находятся выше, ниже, правее или левее окна. В этих случаях соответствующие биты в обоих кодах равны 1 и это легко определить, умножив эти коды по бинарной операции И. Если результат операции И равен 0000, то отрезок нельзя ни принять ни отбросить, так как он может пересекаться с окном. В этом случае применяется последовательное разделение отрезка, так что на каждом шаге конечная точка отрезка с ненулевым кодом вне/внутри заменяется на точку, лежащую на стороне окна или на прямой содержащей сторону. При этом порядок перебора сторон окна не имеет значения.

Далее приводится текст процедуры на языке Паскаль, с довольно изящной реализацией этого метода. Отрезок задан граничными точками глава 4. алгоритмы растровой графики - student2.ru , глава 4. алгоритмы растровой графики - student2.ru , границы окна: 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}

Наши рекомендации