11496

Алгоритмы растровой графики

Практическая работа

Информатика, кибернетика и программирование

Алгоритмы растровой графики Растром называется прямоугольная сетка точек формирующих изображение на экране компьютера. Каждая точка растра характеризуется двумя параметрами: своим положением на экране и своим цветом если монитор цветной или степенью яркости если м...

Русский

2013-04-08

153 KB

6 чел.

Алгоритмы растровой графики

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

Рис. 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}


 

А также другие работы, которые могут Вас заинтересовать

41083. Три покоління розвитку інформаційних систем 2.19 MB
  Для головних компонентів інформаційних систем даних і обчислень важливе значення має така ознака як їх надмірність. Протягом розвитку інформаційних систем організаційного типу структура і надмірність даних та процедури обчислень значно змінювалися що було критеріями для виділення поколінь цих систем. В інформаційних системах першого покоління які в зарубіжній літературі відомі під назвою Dt Processing System DPS системи оброблення даних синоніми електронне оброблення даних системи електронного оброблення даних а у...
41084. Перспективні засоби і напрями розвитку інформаційних систем 97.5 KB
  Перспективні засоби і напрямирозвитку інформаційних систем Загальна характеристикаінформаційних систем Сучасний етап розвитку економіки і бізнесу характеризується широким застосуванням для оброблення інформації та комп’ютерної підтримки рішень новітніх засобів інформаційних технологій основним вираженням яких є інформаційні системи різного призначення й різної проблемної орієнтації. Для проблематики економіки й бізнесу використовуються здебільшого інформаційні системи організаційного типу. Інформаційні системи організаційного типу ІСОТ...
41085. Віртуальний офіс і віртуальна організація 33.5 KB
  Віртуальний офіс Забезпечувана в останні роки технічними і програмними засобами можливість автоматизації офісу щодо електронного зв’язку між людьми зробила доступною новий напрям забезпечення функціонування офісу що навіть усунуло потребу роботи яка виконується в офісі [100]. Цей термін означає що робота офісу може бути виконана фактично незалежно від географічного розміщення службовців оскільки робоча територіальна мережа з’єднує кілька фіксованих розміщень фірми деяким типом електронної системи зв’язку. Очевидність віртуального офісу...
41086. Сучасне розуміння поняття «інформація» 62 KB
  Сучасне розуміння поняття інформація Інформація і дані У контексті автоматизованого оброблення інформації та інформаційних систем термін інформація має виключно важливе значення і від правильної його інтерпретації значною мірою залежить ефективність людиномашинних систем. Згідно з Державним стандартом України ДСТУ 293894 Системи оброблення інформації. Через те що вартість інформації включаючи витрати на збирання зберігання пошук і оброблення значна величезну перевагу має її колективне використання. Отже однією з головних цілей...
41087. Озеленення міст. Влаштування озеленення на штучних поверхнях 275.5 KB
  Природоохоронні та історіко культурні ландшафти Внаслідок його експлуатації сформувалися гірничо промислові ландшафти. Тому шкільна географічна освіта в Україні потребує узагальнюючих праць про сучасні антропогенні ландшафти на території нашої країни. У працях що розглядають антропогенні ландшафти України територія Полтавщини характеризувалася побіжно у складі геосистем вищого рангу.
41088. Рішення в організаційному управлінні. Сутність створення рішення 136.5 KB
  Рішення в організаційному управлінніСутність створення рішення Комп’ютерна інформаційна система СППР використовується для підтримки різних видів діяльності в процесі прийняття рішень: вибору загальної стратегії дій визначення спеціальних завдань делегування відповідальності оцінювання результатів ініціювання змін. Проблеми прийняття рішень і особи які їх приймають останнім часом заслуговують на все більшу увагу. Це зумовлено зростаючим динамізмом навколишнього середовища збільшенням взаємозалежності багатьох рішень стрімким темпом...
41089. Процеси створення рішень 70.5 KB
  Процеси створення рішень Загальна модель процесу прийняття рішення Як індивіди і групи осіб розробляють і приймають рішення Які кроки можна вважати безперечно ефективними Модель послідовного процесу прийняття рішення може допомогти аналізувати те як рішення розробляються і як це слід робити. Саймон 1960 року виділив такі три стадії в послідовному процесі прийняття рішень: інтелектуальна intelligence виявлення обставин можливостей для розроблення рішення збирання та упорядкування інформації і знань передбачення можливих варіантів...
41090. Структура і загальна характеристика СППР 2.07 MB
  Структура і загальна характеристика Еволюція концепції і структури СППР Концепція систем підтримки прийняття рішень виникла в кінці 60х років ХХ століття разом з ідеєю розподіленого комп’ютерного обчислення. Терміна СППР DSS не було до 1971 року. Як уже зазначалося не існує загальноприйнятого визначення СППР.
41091. Сфери та приклади застосування СППР 63.5 KB
  Сфери та приклади застосування СППР Галузі застосування СППР Системи підтримки прийняття рішень набули широкого застосування в економіках передових країн світу причому їх кількість постійно зростає. На рівні стратегічного управління використовується ряд СППР зокрема для довго середньо і короткострокового а також для фінансового планування включаючи систему для розподілу капіталовкладень. Орієнтовані на операційне управління СППР застосовуються в маркетингу для прогнозування та аналізу збуту дослідження ринку і цін за виконання...