Egri chiziqlar va sirtlar uchun Brezenxli algoritmi, ko‘pburchak va murakkab sohalarni bo‘yash (Rendering), kesishma algoritmlari

Egri chiziqlar va sirtlar uchun Brezenxli algoritmi, ko‘pburchak va murakkab sohalarni bo‘yash (Rendering), kesishma algoritmlari (Sazerlend-Koena va boshqalar)

Ma’ruzachi: I.U.Haydarov

Kalit so'zlar

• Brezenxem algoritmi
• ko‘pburchak va murakkab sohalarni bo‘yash (Rendering)

Bresenhamning chiziq algoritmi bu ikki nuqta orasidagi to'g'ri chiziqqa yaqinlashishi uchun ikki o'lchovli rasterning qaysi nuqtalari ranglanishi kerakligini aniqlaydigan algoritmdir. Bu kompyuter grafikasidagi eng qadimgi algoritmlardan biri bo'lib, u Djek Elton Bresenham tomonidan 1962 yilda IBM tomonidan ishlab chiqilgan. Algoritm keng qo'llaniladi, xususan, kompyuter ekranida chiziqlar chizish uchun. 2-darajali egri chiziqlar qurish uchun Bresenham algoritmini umumlashtirish mavjud.

Brezenxem algoritmi

Rasmda Bresenham algoritmining grafik talqini

Brezenxem algoritmi

P(x1, y1) va Q(x2, y2) nuqtalarni bog’lovchi kesma

Brezenxem algoritmi

F(x,y) = 0 - segmentda nuqta

F(x,y) < 0 - yuqoridagi nuqta

F(x,y) > 0 -- quyida nuqta

P nuqta aniqlanadi, keyin o'rta nuqtaning koordinatalari

va ushbu nuqtada funktsiyaning qiymati

Brezenxem algoritmi

Agar d <0 bo'lsa, u holda E tanlanadi va

Agar d  0 bo'lsa, u holda NE tanlanadi

Boshlanish nuqtasida

Bitta muammo - bu 2 ga bo'lishdir.

Haqiqiy arifmetikani buzmaslik uchun biz transformatsiyani qilamiz

d0 = 10 - 7 = 3 > 0 (NE)

d1 = 3 - 4 = -1 < 0 (E)

d2 = -1 + 10 = 9 (NE)

d3 = 9 - 4 = 5 (NE)

d4 = 5 - 4 = 1 (NE)

d5 = 1 - 4 = -3 (E)

d6 = -3 + 10 = 7 (NE)

Brezenxem algoritmi

Brezenxem algoritmi (айлана)

Аниқмас ва аниқ ифодаланиши

Parametrik ko’rinishi

Brezenxem algoritmi (айлана)

Brezenxem algoritmi (айлана)

P nuqtasi koordinata bilan

E pikseli uchun:

SE pikseli uchun:

Murakkab sohalarni bo‘yash (Rendering)

Renderlash (inglizcha rendering - "visualizatsiya") - bu kompyuter dasturidan foydalanib modeldan tasvir olish jarayonini bildiruvchi kompyuter grafikasidagi atama.

Hozirgi vaqtda ko'plab vizual algoritmlar ishlab chiqilgan. Mavjud dastur yakuniy tasvirni olish uchun bir nechta algoritmlardan foydalanishi mumkin.

Segmentlarni kesish

Oddiy qirqish vazifasi segmentlarni kesishdir. Biz bunga aniq misol keltiramiz. Faraz qilamizki, ko’rinish maydoni ABCD to'rtburchak bilan aniqlansin va kesilgan shakl sifatida PRQ uchburchakni olaylik.

Kesish jarayoni to'liq avtomatik bo'lishi kerak. Masalan PRQ uchburchagini chizish uchun faqat PQ; PP'; Q'Q chiziq chizish buyruqlari bajarilishi kerak, P'; Q' nuqtalarining koordinatalari oldindan ma'lum emas.

Amalda, segment va ko’rinish maydonining juda ko'p nisbiy joylashishi mumkin. Bunday xollarda qirqish jarayoni algoritmik nuqtai nazardan juda sezgir emas. Ushbu muammolarni hal qilish uchun qirqish algoritmlari yaratilgan.

Sazerlend-Koen algoritmi

Sutherland va Koen tomonidan taklif qilingan kesish algoritmi juda qiziq. Algoritmning mohiyati shundaki, segmentning uchlariga to'rt bitli kod berilgan: b0, b1, b2, b3. Ushbu to'rt bitli kod, nuqtaning ko’rish maydoniga nisbatan holati haqida ma'lumotni o'z ichiga oladi. Amalda 9 ta kombinatsiya bo’ladi.

Ushbu kodlarni tushuntiramiz:

• agar x≥xmin bo’lsa b0=0;
• agar x
• agar x≤xmax bo’lsa b1=0;
• agar x>xmax bo’lsa b1=1;
• agar y≥ymin bo’lsa b2=0;
• agar y
• agar y≤ymax bo’lsa b3=0;
• agar y>ymax bo’lsa b3=1;

Sazerlend-Koen algoritmi

Kodlarni olgandan so'ng, quyidagi variantlar bo’lishi mumkin

• Kodlar faqat 0 ni o'z ichiga oladi, bu butun segment oynaning ichida joylashganligini va uni to'liq chizish kerakligini anglatadi;
• Kodlar xuddi shu holatda bitta bitni o'z ichiga oladi, bu segment oynaning tashqarisida joylashganligini va chizilmasligini anglatadi;
• Boshqa barcha holatlarda oynaning faqat bir qismi yotadi va bu kesishga ehtiyoj borligini anglatadi.

Birinchi ikkita holat bit tomon mantiqiy operatsiyalar yordamida osongina tekshiriladi. Uchinchi holat alohida qiziqish uyg'otadi. Keling, buni kichik bir aniq misolda ko'rib chiqaylik.

Sazerlend-Koen algoritmi

Agar kod ikkala uchida bitta bitdan iborat bo'lsa, u holda P1 yoki P2 oynaning tashqarisidan uning chegaralaridan biriga (yoki uning davomiga) o'tadi. Masalan, P1 nuqtasi R nuqtasiga, P2 esa U nuqtasiga o'tadi. Yangi nuqtalar uchun biz yana to'rt bitli kodlarni hisoblaymiz. Bizning holatda, segmentning uchlari hali ham deraza tashqarisida yotadi, ya'ni. biz yana bitta harakatga muhtojmiz: R nuqtadan S nuqtaga, U nuqtadan T nuqtasiga o'tamiz. Kesish jarayoni iterativ ekanligi ayon bo'ldi. Har qadamda segmentning uchlari orasidagi masofa qisqarganligi sababli, algoritm birlashadi deb aytishimiz mumkin. Natijada, segment olinadi (bizning holatda (S; T), ular ko'rsatilishi kerak).

Ushbu algoritmning ishlashini boshqa misol yordamida ko'rib chiqamiz.

Segmentning joylashuvi (P1; P2) to'liq ko'rish shartlariga yoki to'liq ko'rinmaslik shartlariga mos kelmaydi, shuning uchun bu holda uzatish punktlarining ishlashiga murojaat qilish kerak.

Segment boshlang'ich kodi

Segment oxirgi kodi

O’tish

Qaysi o’tadi

Qayerga o’tadi

O’tishlar amalga oshirilganidan so'ng, segmentning uchlari kodlari ikkinchi shartni qondiradi, ya'ni. butun segment ekranda ko'rinmaydi