Скачать программы Все программы автораАлгоритмы растровой графикиРастром называется прямоугольная сетка точек, формирующих изображение на экране компьютера. Каждая точка растра характеризуется двумя параметрами: своим положением на экране и своим цветом, если монитор цветной, или степенью яркости, если монитор черно-белый. Поскольку растровые изображения состоят из множества дискретных точек, то для работы с ними необходимы специальные алгоритмы. Рисование отрезка прямой линии - одна из простейших задач растровой графики. Смысл ее заключается в вычислении координат пикселов, находящихся вблизи непрерывных отрезков, лежащих на двумерной растровой сетке.
Рис. 28. Растеризация отрезка прямой линии.
Термин “пиксел” образован от английского pixel (picture element - элемент изображения) - то есть точка на экране. Будем считать, что пикселы имеют целочисленные координаты. На первый взгляд кажется, что эта задача имеет простое решение. Пусть конечные точки отрезка имеют целочисленные координаты, и уравнение прямой, содержащей отрезок: . Не нарушая общности, будем также считать, что тангенс угла наклона прямой лежит в пределах от 0 до 1. Тогда для изображения отрезка на растре достаточно для всех целых , принадлежащих отрезку, выводить на экран точки с координатами . Однако в этом методе присутствует операция умножения . Хотелось бы иметь алгоритм без частого использования операции умножения вещественных чисел. Избавиться от операции умножения можно следующим образом. Поскольку , то один шаг по целочисленной сетке на оси будет соответствовать . Отсюда получаем, что будет увеличиваться на величину . Итерационная последовательность выглядит следующим образом: , Когда , то шаг по будет приводить к шагу по , поэтому и следует поменять ролями, придавая единичное приращение, а будет увеличиваться на единиц. Этот алгоритм все же не свободен от операций с вещественными числами. Наиболее изящное решение задачи растровой развертки отрезков прямых было найдено Брезенхемом. В его алгоритме вообще не используются операции с вещественными числами, в том числе операции умножения и деления. Для вывода формул алгоритма Брезенхема рассмотрим рис. 29.
Рис. 29. Рисование отрезков прямых по методу Брезенхема.
Пусть начало отрезка имеет координаты , а конец . Обозначим , . Не нарушая общности, будем считать, что начало отрезка совпадает с началом координат, и прямая имеет вид , где . Считаем что начальная точка находится слева. Пусть на -м шаге текущей точкой отрезка является . Выбор следующей точки или зависит от знака разности . Если , то и тогда , , если же , то и тогда , . , ,
. Поскольку знак совпадает со знаком разности , то будем проверять знак выражения . Так как и , то . Пусть на предыдущем шаге , тогда и . Если же на предыдущем шаге , то и . Осталось узнать как вычислить . Так как при : , . Далее приводится листинг процедуры на языке Паскаль, реализующей алгоритм Брезенхема.
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}
Перед тем, как исследовать методы получения изображений более сложных, чем отрезки прямых, рассмотрим проблему, незримо присутствующую в большинстве задач компьютерной графики. Эта проблема отсечения изображения по некоторой границе, например, по границе экрана, или, в общем случае, некоторого прямоугольного окна. Рассмотрим эту задачу применительно к отрезкам прямых. Некоторые из них полностью лежат внутри области экрана, другие целиком вне ее, а некоторые пересекают границу экрана. Правильное отображение отрезков означает нахождение точек пересечения их с границей экрана и рисование только тех их частей, которые попадают на экран. Один из очевидных способов отсечения отрезков состоит в определении точек пересечения прямой, содержащей отрезок, с каждой из четырех прямых, на которых лежат границы окна и проверки не лежит ли хотя бы одна точка пересечения на границе. В этом случае для каждой пары сторона-отрезок необходимо решать систему из двух уравнений, используя операции умножения и деления. При этом удобно параметрическое задание прямых:
. Рассмотрим алгоритм Коэна-Сазерленда для отсечения отрезков прямых. Этот алгоритм позволяет легко определять нахождение отрезка полностью внутри или полностью снаружи окна, и если так, то его можно рисовать или не рисовать, не заботясь об отсечении по границе окна. Для работы алгоритма вся плоскость в которой лежит окно разбивается на девять подобластей или квадрантов, как показано на рис. 30.
Рис. 30. Разбиение на подобласти в методе Коэна-Сазерленда.
Окну соответствует область обозначенная кодом 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} |