ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Процедура виведення дуги елiпса у четвертому квадрантi.

procedure RastrBresEllipse(Xc,Yc,a,b,Color:integer);

var

Sqr_a,TwoSqr_a,Sqr_b,TwoSqr_b,x,y,d,dx,dy:integer;

begin {RastrBresEllipse}

if (a>0)and(b>0)

then begin {(a>0)and(b>0)}

// початкове встановлення змiнних

x:=0; y:=b;

Sqr_a:=sqr(a); Sqr_b:=sqr(b);

TwoSqr_a:=2*Sqr_a; TwoSqr_b:=2*Sqr_b;

dx:=0; dy:=b*TwoSqr_a;

// вивiд при dy/dx>-1

while (dx<dy) do

begin {while (dx<dy)}

Set4Pixels(x,y,xc,yc,Color);

if (d>0)

then begin {d>0}

y:=y-1; dy:=dy-TwoSqr_a; d:=d-dy;

end {d>0}

else begin {d<=0}

x:=x+1; dx:=dx+TwoSqr_b; d:=d+Sqr_b+dx;

end; {d<=0}

end; {while (dx<dy)}

// пiдправка при dy/dx=-1

d:=d+round(3*(Sqr_a-Sqr_b)/4+(dx+dy)/2);

// вивiд при dy/dx<-1

while (y>=0) do

begin {while (y>=0)}

Set4Pixels(x,y,xc,yc,Color);

if (d<0)

then begin {d<0}

x:=x+1; dx:=dx+TwoSqr_b; d:=d+dx;

end {d<0}

else begin {d>=0}

y:=y-1; dy:=dy-TwoSqr_a; d:=d-(Sqr_a+dy);

end; {d>=0}

end; {while (y>=0)}

end; {(a>0)and(b>0)}

end; {RastrBresEllipse}

Лiтература.[11]

 

2.2 Растрова розгортка багатокутникiв.

Поняття растру. Растрова розгортка - це спосiб генерацiї зображення. Для виведення на монiтор розкладеного у растр образу потрiбно представити його у виглядi шаблона, який вимагає дисплей. Це перетворення має назву растрової розгортки. На вiдмiну вiд дисплейного списку для векторного дисплея, який мiстить iнформацiю тiльки про вiдрiзки або лiтери, у цьому випадку дисплейний список повинен мiстити iнформацiю про кожний пiксел. Також необхiдно, щоб ця iнформацiя будувалась i виводилась на екран iз швидкiстю вiдеогенерацiї у порядку сканування рядкiв, тобто зверху до низу i злiва направо.

Iснує чотири способу досягнення такого результату - растрова розгортка у реальному часi, групове кодування, кодування за чарунками i буфер кадру.

Растрова розгортка у реальному часiПри розгортцi у реальному часi ("на льоту") сцена довiльним чином зображається у пам'ятi у термiнах вiзуальних атрибутiв i геометричних характеристик. Типовi вiзуальнi атрибути це колiр, вiдтінок та iнтенсивнiсть, тодi як координати x,y пiкселiв на екранi, кути нахилу i текст вiдносимо до геометричних характеристик. Останнi упорядкованi за координатою y

Пiд час вiдтворення кожного кадру процесор сканує цю iнформацiю i пiдраховує iнтенсивнiсть кожного пiкселя на екранi. Така розгортка не потребує великої кiлькостi пам'ятi. Потрiбно зберiгати дисплейний список i додатково один рядок, що сканується. Бiльш того, iнформацiя зберiгається у списку з довiльною органiзацiєю пам'ятi. Тому легко додати або видалити iнформацiю iз списку, що зручно при динамiчнiй обробцi. Але складнiсть зображення обмежена швидкiстю дiї дисплейного процесора.

Для одержання перетинiв (якщо вони є) кожного вiдрiзка дисплейного списку iз рядком, що сканується, у найпростiшійї реалiзацiї методу кожного разу при зображеннi рядка обробляється весь дисплейний список. При регенерацiї зображення на кожний рядок, що сканується (а тому i на весь список), можна видiлити не бiльш 63.5 мiкросекунди, що дуже обмежує число елементiв списку, якi обробляються. Тому формують список активних ребер (САР). Цей список мiстить вiдрiзки зображення, якi перетинають рядок, що сканується.

Для побудови САР можна використовувати декiлька методiв. Спочатку вiдрiзки зображення сортуються за найбiльшою координатою y. Найпростiше скористатися двома покажчиками, що перемiщуються по вже відсортованому списку. Це покажчики початку b (begin) i кiнця e (end) САР у сортованому списку. На рис. 2.1.1 зображена сцена з трьома характерними рядками, що скануються.

Покажчик b спочатку встановлюється на початок цього списку, тобто на вiдрiзок ВС. При цьому покажчик e встановлюється на тiй останнiй вiдрiзок у списку, який починається вище рядка, що сканується, тобто на вiдрiзок BD. При скануваннi зображення потрiбно коректувати САР, при цьому е-покажчик зсовується униз, щоб додати до САР новi вiдрiзки, що починаються на поточному рядку або є вище його. У той же час b-покажчик також зсовується униз, щоб видалити вiдрiзки, якi закiнчуються вище поточного рядка (див. стовпцi А1, А2, А3 таблицi 2.2.1. Стовпцi B1, B2, B3 i стовпцi C1, C2, C3 таблицi 2.2.1 демонструють проблему, яка виникає при цьому алгоритмi: порядок сортування вiдрiзкiв, що починається з однiєї координати y, впливає на розмiр САР. Цю проблему можна вирiшити завдяки введенню додаткової структури даних i використання групового сортування. Вiдносно вiдповiдного алгоритму див. [5, стор. 75-80]. У таблицi 2.2.1 наведенi промiжнi етапи списку активних ребер при груповому сортуваннi з перемiщенням покажчикiв.

Рис. 2.2.1. Сцена з декiлькома вiдрiзками, що скануються.

 

Таблиця 2.2.1.Список активних ребер (перемiщення покажчикiв)

Рядки A1 A2 A3 B1 B2 B3 C1 C2 C3
  BC-в BC BC BA-b BA-b BA BD-b BD-b BD-b
  BA BA-b BA BC BC BC-b BA BA BA
  BD-e BD BD-b BD-e BD BD BC-e BC BC
  CD CD-e CD CD CD-e CD CD CD-e CD
  AD AD AD-e AD AD AD-e AD AD AD-e

Групове кодування.У методi групового кодування зроблена спроба скористатися тим фактом, що великi дiлянки зображення мають однакову iнтенсивнiсть або колiр. Рядок зображення записуємо як дiлянки груп пiкселiв, що мають постiйнi характеристики (наприклад, iнтенсивність або колiр), тобто данi розгортки записуємо як RGB-iнтенсивностi (R-байт iнтенсивностi червоного, плюс G-байт iнтенсивнiсть зеленого, плюс B-байт iнтенсивностi блакитного, плюс байт довжини - усього 4 байта). Це вже мiстить поняття стискання даних (див. [ 5, стор. 80-83]).

Стискання даних для зображень, що кодуємо групами, може наближатись до 1:1. Це суттєво не тiльки тому, що групове кодування зберiгає пам'ять, а також тому, що воно зберiгає пам'ять для машинно-синтезованих послiдовностей кадрiв фiльму. Воно також зберiгає час при передачi даних телеграфом та iншим каналам зв'язку.

Але групове кодування має й недолiки:

1. Додавання або видалення вiдрiзкiв або тексту iз зображень - це трудомiська операцiя, яка потребує багато часу через послiдовне збереження сегментiв, що упакованi. Отже, кодування та декодування веде до великих витрат часу.

2. Для збереження коротких сегментiв однакової iнтенсивностi може знадобитись удвiчi бiльше пам'ятi нiж при зберiганнi окремими пiкселами.

Кодування за клiтинами.У методi кодування за клiтинами (рос. клеточное кодирование) здiйснюється розбиття зображення на клiтини (чарунки). Для виведення лiтер використовують маски лiтер.

Наприклад, екран можна подiлити на областi розмiрами 8 8 пiкселiв. Для монiторiв з роздільністю 480 640 з стандартним видовим спiввiдношенням 4:3 отримуємо 60 80 чарунок (клiтин). Звичайно, клiтина розмiрами 8 8 використовується для виведення лiтер з точковою матрицею розмiрiв 5 7. Додатковi пiкселi використовуються для розрiзнення лiтер у рядку.

Оскільки для полiпшення сприйняття тексту кожний другий ряд клiтин не використовується, то для дисплеїв з роздільністю 480 640 одержуємо 30 рядкiв по 80 лiтер у рядку, що типово для бiльшостi алфавiтно-цифрових дисплеїв.

Використовуються також iншi розмiри клiтин. Наприклад, для лiтер з матрицею 7 9 звичайно використовують клiтини 8 10 пiкселiв. Тодi дисплей вiдображає 24 рядка з 80-ю лiтерами у кожному рядку. Шаблони, що створенi з пiкселiв для кожної лiтери, зберiгаються у сталому запям'ятовуючому пристрої (СЗП) (рос. постоянному запоминающему устройстве (ПЗУ)).

Розвиненням цього методу є псевдографiка, коли створюються маски сегментiв малюнка. Наприклад, метод клiтинного кодування можна використовувати для креслення лiнiй. Потрiбно у СЗП зберiгати ще й шаблони сегментiв вiдрiзкiв. Тодi для побудови лiнiй можна скористатись комбiнацiями таких сегментiв, що розташованi у сусiднiх клiтинах. Для довiльної клiтини розмiрiв n n пiкселiв iснує можливих шаблонiв.

Але не всi такi шаблони доцільно використовувати для представлення лiнiй. Наприклад, для вiдрiзкiв алгоритму Брезенхема з тангенсами кута нахилу мiж 0 i 1 iснує не бiльш нiж -1 шаблонiв, якi можна використовувати для представлення сегментiв вiдрiзкiв. Жордан i Барет [23] довели, що для клiтини 8 8 при використаннi переносiв (паралельно сторонам клiтини), вiдображень (симетрiй вiдносно осей симетрiї клiтини) i маскувань (маскувань деяких пiдряд розташованих стовпцiв клiтини) треба лише 108 шаблонiв сегментiв вiдрiзкiв.

Буфер кадру. Звичайно буфер кадру - це напiвпровiдникова пам'ять з довiльним доступом, але припустимо використання для буфера кадру диску чи барабана. Вона дозволяє накопичувати деяку iнформацiю перед виведенням її на дисплей. Це виведення можна здiйснювати у потрiбний зручний час.

Буфер кадру можливо реалiзувати за допомогою регiстрiв зсуву. Схематично регiстр зсуву можливо розглядати як стек типу FIFO( First In First Out - Першим прибув -- першим буде оброблений}, рос. первым пришел - первым обслужен). Якщо стек вже заповнений, то при додаваннi до вершини стека нових байтiв даних з дна стеку виштовхуються першi бiти даних. Данi, що виштовхуються зi стеку, можна iнтерпретувати як iнтенсивнiсть вiдповiдного пiксела рядка, що сканується.

Буфери кадрiв на зсувних регiстрах можна реалiзовувати, скориставшись одним регiстром на пiксел у рядку що сканується при довжинi кожного регiстра, що дорiвнює числу рядкiв. Iнший варiант -- це використання одного регiстра з довжиною, яка дорiвнює числу пiкселiв в рядку, який скануємо, помноженому на число рядкiв.

Ми будемо iмiтувати буфер кадру як цiлочисельний двовимiрний масив (array[0..mx-1, 0..my-1] of integer;) розмiрами mx my, де mx my - розмiри екрану (у пiкселях). Таке (iмiтацiйне) використання буфера кадру дозволяє формувати зображення з використанням алгоритмiв векторної графiки у випадках, що не є критичними вiдносно часу виведення на екран.

Генерацiя суцiльних областей.Генерацiю на растровому приладi суцiльних областей (дiлянок), якi обмеженi деякими замкненими кривими будемо називати генерацiєю суцiльних областей. Якщо лінія, що обмежує область є замкненим багатокутником, тодi цю процедуру будемо називати заповненням багатокутникiв або растровою розгорткою багатокутникiв.

Найпростiший метод розв'язання цiєї проблеми -- перевiрка на належнiсть до середини багатокутника кожного пiкселя з растру. Вiдповiдне математичне обгрунтування цього метода -- поняття iндексу точки вiдносно багатокутника.

Нехай на площинi маємо замкнений багатокутник M=A1A2....An без перетинiв сторiн i B - довiльна точка площини , яка не належить до контуру багатокутника, тобто B [Ak, Ak+1], k=1,2, ...,n-1, B [An,A1].

Теорема 1 Нехай через точку B, що не належить до границi багатокутника M, у довiльному напрямку проведено промiнь , який не мiстить нi однiєї вершини багатокутника ( ). Позначимо через число перетинiв цього променя зi сторонами цього багатокутника (нуль, при вiдсутностi точок перетину). Тодi є число парне, якщо точка D знаходиться зовнi багатокутника M, i є число непарне, якщо точка B знаходиться у серединi багатокутника.

Визначення 1 Iндекс ind(B) точки B вiдносно замкненого багатокутника M визначаємо, як число mod 2 (тобто, 0, якщо число парне, i 1, якщо число непарне). Теорема 1 стверджує коректнiсть цього означення.

Тому, для з'ясування положення точки вiдносно багатокутника (зовнi вона або всерединi) потрiбно вибрати деяку пряму (наприклад ту, що визначена рядком, що сканується), знайти точки перетину цiєї прямої з контуром багатокутника. Цi точки дають розбиття прямої на вiдрiзки, якi або лежать у серединi багатокутника, або знаходяться зовнi. Випадок, коли прямi растру можуть проходити через вершини багатокутника, виключаємо наступним чином. Координати вершин багатокутника можна вважати завжди цiлими числами (якщо це потрiбно -- проведемо округлення до цiлих координат). Виберемо пряму, яка вiдповiдає рядку розгортки з номером k (k ≥ 0), з координатою x=k+1/2=k+0,5. Тодi ця пряма нiколи не буде проходити через вершини багатокутника. Цей принцип дiє для всiх алгоритмiв растрової графiки.

2.2.1 Алгоритм заповнення з упорядкованими списками ребер

Скориставшись сформульованою у роздiлi 2.2. теоремою можна розробити ефективнi алгоритми растрової розгортки суцiльних областей, якi мають назву алгоритмiв заповнення з упорядкованими списками ребер. Вони залежать вiд сортування точок перетину ребер багатокутника з рядками, що скануються. Ефективнiсть цих алгоритмiв залежить вiд ефективностi сортування. Наведемо дуже простий алгоритм.

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти