|
4. Poligon to'ldirish algoritmlari.
Ushbu algoritmdan foydalanib siz yopiq joylarni bo'yashingiz mumkin. Ushbu algoritm uchun dastlabki ma'lumotlar mintaqaning chegara ranglari va bu mintaqaga tegishli bo'lgan nuqta (yalang'och piksel deb ataladi). Usulning mohiyati quyidagicha: biz yalang'och nuqta olamiz va uni bo'yalamiz. Har bir bo'yalgan qo'shni uchun biz shunga o'xshash protsedurani bajaramiz. Shunday qilib. biz yassi algoritmga ega bo'lamiz, uning ta'rifi pseudocodda quyida keltirilgan:
1. urug 'pikselini suyakka qo'ying;
2. Pikselni stokdan chiqaring;
3. Istalgan qiymatni pikselga (ichki maydonning rangi) belgilash;
4. Har bir atrofdagi piksel, agar bo'lsa, bu to'plamga qo'shiladi
4.1. Chegar emas;
4.2. Oldin ishlov berilmagan (ya'ni rangi chegara rangidan yoki ichki maydonning rangidan farq qiladi);
5. Agar to'plam bo'sh bo'lmasa, 2-bosqichga o'ting.
Albatta, siz ham to'rtta, ham sakkizta bog'liq bo'lgan qo'shnidan foydalanishingiz mumkin.
Ushbu algoritmning kamchiliklari afzalliklardan kattaroqdir: u asta-sekin va ko'plab xotira uchun sarflanadi, shuning uchun quyidagi algoritm guruhini ko'rib chiqmoqchi bo'lamiz.
Chegaralar ro'yxati bilan algoritmlar
Ushbu algoritm faqat bo'yalgan maydoni ko'pburchak sifatida belgilash mumkin bo'lgan holatlarga mos keladi. Biz P 1 , P 2 , ..., P N vertiklari bo'lgan poligon bilan ishlaymiz va biz uni barcha ichki nuqtalar bilan birgalikda ekranda ko'rsatishni istaymiz. Qulaylik uchun, poligonning har bir tomoni x1 , y 1 va x 2, y 2 ( y 2 ≥ y 1 ) uchlari koordinatalari bilan beriladi. Bundan tashqari, chapdan o'ngga harakatlanishda koordinataning x kattaligini va yuqoridan pastga harakat qilganda koordinataning yga kelishiga rozilik beramiz.
Rostlashtiruvchi ko'pburchak uchun algoritmlarning asosiy qismi quyidagi taxminlarga asoslanadi: har qanday sekantik chiziq poligonning chegarasini bir necha marta kesadi. Ushbu bayonot faqat ikki holatda noto'g'ri.
Ikkilamchi chiziq qirrasini o'z ichiga olgan bo'lsa;
Ikkilamchi chiziq vertikka ega bo'lsa va qo'shni qirralarning ajratilgan liniyaning bir tomonida yotsa.
Bu ikki holni aniqlash juda oson, shuning uchun ko'pburchaklarni rasterlash uchun algoritmlarni ko'rib chiqayotganda yuqoridagi taxminlar har doim to'g'ri ekanligini taxmin qilamiz.
Chegaralar ro'yxati bilan ishlashga asoslangan algoritm uch asosiy bosqichdan iborat:
Birinchi bosqichda poligonning barcha gorizontal bo'lmagan qirralari rasterlashtiriladi. Y ning har bir qiymati uchun rasterizatsiya bilan to'ldirilgan x-koordinatalar ro'yxati tuziladi. Misol uchun, ko'rib chiqilayotgan poligon uchun quyidagi qiymatlarni (soat yo'nalishi bo'yicha harakat qilamiz) olamiz:
Ikkinchi bosqichda har bir qiymat uchun ro'yxatlar ortib boruvchi tartibda buyurtma qilinadi. Shundan so'ng, ro'yxatlar shunday bo'ladi:
Uchinchi bosqichda, har bir y uchun, barcha olingan segmentlar to'ldiriladi. Ushbu algoritmning afzalligi shundaki, har piksel bir marta qayta ishlanadi. Shunday qilib. bu algoritm video xotiraga kirish nisbatan uzoq vaqt talab etadigan qurilmalarga mos kelishini ta'kidlash mumkin.
Xotirani tejash uchun optimallashtirilgan ushbu algoritm modifikatsiyasi mavjud. Har bir qadamda faqat joriy chiziq bilan kesib o'tgan qirralar ishlov beradi.
XOR algoritmlari
Ushbu poligonlarni rasterlash usuli maxsus VEYO (XOR) ning mantiqiy ishining xususiyatlariga asoslanadi.
Bu algoritm, chekka nuqtalar ro'yxati bilan algoritm kabi, chegaralarning rasterlashi bilan boshlanadi.Chegaralar qurib bo'lingandan so'ng, soyaning har bir satrini ikki soyali nuqtalar orasidagi bo'shliqlarga to'ldirish kamayadi.
Tasvir ikkilik qator shaklida ekanligini tasavvur qilaylik. Pixel soyali bo'lmaganda, men [x; y] = 1, piksel silkindi va men [x; y] = 0 deb rozi bo'laylik. Chiziqdagi barcha piksellarga I [x + 1, y] = I [x; y] XOR I [x + 1; y] operatsiyasini qo'llash deyarli ajoyib natijaga olib keladi. Ushbu operatsiya barcha bo'shliqlarni to'ldiradi, lekin har bir bo'shliqdagi oxirgi piksel yoyilmaydi. Ko'pgina hollarda, bu xato ahamiyatsiz va ko'rinmas, ammo aniq natijaga erishmoqchi bo'lsangiz, algoritm tugallangandan so'ng chegaralarni qayta ko'rsatishingiz yoki bu algoritmni kichik o'zgartirishingiz mumkin.
Y uchun: = 1 dan YMax ga
boshlang
fl: = noto'g'ri;
X: = 1 dan XMax uchun
boshlang
agar men [x, y] = 1 bo'lsa
fl: = not fl;
agar bo'lsa, u holda
I [x, y]: = 1;
tugatish;
tugatish;
Ushbu algoritmning afzalligi uning soddaligi va yuqori tezligidir. Kamchiliklari algoritm boshqa rasmlar bo'lsa, ishlamasligi.
Yuzlar uchun XOR algoritmi
Yuzlar uchun XOR usuli quyidagi oddiy algoritm bilan tasvirlangan: Poligondagi har bir chekka uchun barcha qirralarning bu qirralarning o'ng tomonidagi ranglari farqlanadi. Bunday holda, qirralarning kesish tartibi muhim emas. Jadval ushbu algoritmning qadamlarini ko'rsatadi (soat yo'nalishi bo'yicha harakat):
Ushbu algoritmning ahvolga tushishi yuqori vaqt sarflanadi, chunki ba'zi piksellar bir necha marta qayta ishlanadi. Bundan tashqari, tasvir maydonidan ekranning o'ng qirrasiga qadar bo'lgan masofa qancha ko'p bo'lsa, unda keraksiz operatsiyalar bajariladi.
Bo'lishli yuzlar uchun XOR algoritmi
Ba'zi kamchiliklardan yuzlar uchun XOR algoritmining o'zgartirilgan versiyasi. Uni qismlarga ajratish uchun XOR algoritmi deyiladi. Uning fikricha, maydonni ekranning chekkasi va chegarasi o'rtasida emas, balki qirg'oq bilan maxsus vertikal chiziq o'rtasida (septum deb ataladi). Ko'pincha, bu qism poligonni kesib o'tish uchun olinadi. Algoritmning bosqichlari jadvalda keltirilgan.
Do'stlaringiz bilan baham: |
