Лекция 7

Растеризация (растеризация) - процесът на определяне на пикселите, които най-добре приближават едно непрекъснато изображение. Процесът на растеризация е тясно свързан с процеса на изобразяване на изображения (растерно сканиране).

Алгоритми за почистване на линии.

Основната задача на алгоритъма за обхождане на линията е да изчисли координатите на пикселите, които се намират близо до отсечките на линията на двумерна растерна мрежа. При решаването на този проблем се приема, че началната и крайната точка на сегмента имат цели числа .

един. Алгоритъм за чертане на сегмент "челно".

2. Алгоритъм на цифровия диференциален анализатор.

3. Алгоритъм на Integer Bresenham.

Реалните променливи изобщо не се използват и следователно не се изисква закръгляване.

4. Обобщение на алгоритъма на Брезенхам.

Растерно разгъване на полигони.

Обектът е зададен в каркасна рамка в GSK. Полигонална мрежа се използва за представяне на най-простите форми. S = (...) + атрибути на лицето. За да покажете обект на екрана, трябва да научите как да показвате полигони. Той се основава на метода на растерно сканиране.

В реда на сканираните линии от лъча на екрана определете принадлежността на точката към полигона и покажете с посочените атрибути.

Повтаряйки този процес за всяка сканираща линия, която пресича полигона, ще растеризираме целия полигон. Този процес обаче е неефективен, тъй като последователността от съседни пиксели обикновено принадлежи на многоъгълник.

Свойство за кохерентност на растерни низове: съседните пиксели имат един атрибут, промяната на атрибута се случва в пресечната точка с ръбовете. Линията за сканиране 8 (Фигура 11.25) съдържа две ивици пиксели вътре в полигона, които могат да бъдат боядисани в три стъпки:

1. Намерете пресечните точки на сканиращата линия с всички ръбове на многоъгълника.

2. Подредете точките на пресичане във възходящ ред на координатата x.

3. Оцветете всички пиксели между двойки точки на пресичане.

За фиг. 11.25 в подредения списък с n-координати на точките на пресичане ще има числа (2, 4, 9, 13). Следователно всички панели се боядисват през интервалите 2-4 и 9-13.

В първата стъпка се правят прости изчисления на пресичанията на всяка сканирана линия с всеки ръб на многоъгълника, който пресича тази линия. Хоризонталните ръбове не могат да пресичат сканиращите линии и следователно не се вземат предвид. Следващите две стъпки са сортиране и боядисване.

Трудности могат да възникнат при сортиране и боядисване на елементите. Ако броят на пресечните точки в сортирания списък е нечетен, процедурата за оцветяване не работи правилно. Това е възможно, когато сканиращата линия пресича връх, в резултат на което две точки на пресичане се въвеждат в списъка на пресичанията. Да разгледаме например ред с y = 3 (Фигура 11.25). Той се пресича с ръбовете на многоъгълника в точки 2, 2 и 10. Тогава последователността на Pels от 2 до 2 (т.е. Pels в точка i = 2, y = 3) ще бъде боядисана, колекцията на Pels от 3 до 9 ще останат неоцветени и последователността от 10 до дясната граница на буфера ще бъде боядисана. Всъщност трябва да се боядисва само група пили от 2 до 10.

Очевидно преминаването на сканиращата линия през върха трябва да се брои като едно пресичане. Това обаче не води до коректни резултати в случаите, когато линии 1, 7, 9 или 11 се пресичат с върхове. всички останали върхове се броят като едно пресичане. Локален минимум се достига във връх, когато y-координатите на предишния и следващите върхове са по-големи от тези на въпросния връх. Местният максимум се определя по подобен начин. Върховете, разположени на сканиращи линии 1 и 7, са локални минимуми, а върховете на линии 9 и 11 са локални максимуми. Всички те се броят като две пресичания със съответните сканиращи линии, а върховете, през които преминават линии 3 и 5, се броят като едно пресичане. Доста лесно е да се гарантира, че такива междинни върхове се пресичат само веднъж: един от съседните ръбове се съкращава преди изчисляването на пресечните точки (Фигура 11.26). Такова съкращаване се извършва само ако върхът лежи върху сканиращата линия, което се случва винаги, когато координатите на върховете са цели числа и рядко, ако координатите на върховете са представени с по-висока резолюция от самата растрова мрежа.

Кохерентност на ребрата и алгоритъм за сканиране на линии.

Първата стъпка в процедурата, т.е. изчисляването на кръстовищата, може да бъде бавна. Всеки ръб на многоъгълника трябва да бъде сравнен с всяка сканирана линия. В много случаи само малък брой ръбове ще представляват интерес. Освен това трябва да се отбележи, че много от ръбовете, пресечени с права i, също ще бъдат пресечени с линия i + l. Тази кохерентност на ръба (подобно на кохерентността на сканираната линия, обсъдена по-горе) се появява винаги, когато сканиращите линии пресичат ръб. Когато се премествате от една линия на друга, можете да изчислите новата x-координата на пресечната точка на ръба, като използвате x-координатата на старата пресечна точка (подобно на случая на разгъване на сегменти):

където m е тангенсът на ъгъла на реброто. Параметърът m е равен на y/x и y = l, така че 1/m = x;.

Можете да се възползвате от кохерентността на ръбовете и да премахнете ненужните сравнения между сканираните линии и ръбове, като растеризирате полигона линия по линия отдолу нагоре (или отгоре надолу), използвайки алгоритъм за сканиране на линии. За всяка сканирана линия се вземат предвид само онези ръбове, които пресичат линията. Те се определят от таблицата на активните ръбове (TAP). При преминаване към следващия ред новите стойности на х-координатите на точките на пресичане се изчисляват с помощта на уравнение (11.14), всички нови ръбове, пресечени от следващата сканираща линия, се добавят към TAP и онези ръбове, които се съдържат в TAP, но не се пресичат със следващия ред, се премахват ... Ръбовете, съдържащи се в TAP, са подредени по x-координатите на точките на пресичане, така че лесно можете да намерите пикселните последователности, които да рисувате.

За ефективното изпълнение на включването на ръбове в TAP се въвежда таблица на ръбовете (TP), която съдържа всички ръбове, подредени по стойностите на техните по-малки y-координати. TR обикновено се изграждат с помощта на групово сортиране, като се подчертават толкова групи, колкото са сканиращите линии. Във всяка група ръбовете са подредени във възходящ ред на х-координатите на най-ниските точки. Този ред се установява чрез сортиране на вмъкване. Всеки TP елемент съдържа голямата y-координата на ръба (y max), x-координатата на долната точка (x min) и x стъпката, използвана за преместване от една сканираща линия към следващата (1/m).

На фиг. 11.27 показва как ще бъдат сортирани шестте ръба на фигура 11. 11.25, като приемем, че съответните ръбове преди това са били съкратени по една линия, за да се избегнат двойни пресичания. На фиг. 11.28 показва TAP в случай на сканиране на линии 9 и 10 за полигона, показан на фиг. 11.25.

След като се формира TP, алгоритъмът за сканиране по ред се състои от следните стъпки:

1. Задайте y да бъде равно на минималната стойност на координатата y между елементите на TP, т.е. съвпадаща с координатата y на първата непразна група.

2. Инициализирайте TAP, направете го празен.

3. Повторете стъпка 3, докато TAP и TP се изпразнят:

3.1. Обединете информация от група y в TP с информация в TAP, запазвайки подреждането по x-координата.

3.2. Въведете желаните стойности в пиксели на сканиращата линия, дефинирана от текущата y стойност, като използвате двойки координати x от TAP.

3.3. Премахнете от TAP онези елементи, в които y = ymax

3.4. За всички елементи, съдържащи се в TAP, заменете x с x + 1/m. По този начин пресичането със следващата сканираща линия се въвежда във всеки TAP елемент.

3.5. Тъй като на предишната стъпка подреждането на TAP в x може да бъде нарушено, пресортирайте TAP.

3.6. Увеличете y с 1 и по този начин преминете към следващата линия за сканиране.

Този алгоритъм използва съгласуваността на ръбовете на сканираните линии, както и сортирането, за да преобразува ефективно полигона в растерна форма. В гл. 15 показва как

алгоритъмът може да се приложи за премахване на скрити повърхности.

Калкулатор

Безплатна услуга за оценка

Попълнете заявлението. Експертите ще изчислят цената на вашата работа
Изчисляването на разходите ще бъде изпратено по пощата и чрез SMS

Номер на вашето заявление

Автоматично писмо за потвърждение с информация за приложението ще бъде изпратено на пощата точно сега.