Маъруза №1. Компьютер графикасига кириш

Текисликда (2D) соҳани бўяш 1.

• 
  1.Соҳани ташкил этувчи ташқи нуқталари билан, яъни соҳани ичида ётувчи ҳар бир пиксел бирор бир ранг (oldcolor) билан берилади (чегарадаги пикселлар бу қийматга эга эмас).
  
• 
  Function fill4(int x,int y:int newcolor, int oldcolor);
  
• 
  {
  
• 
  If (getpixel(x,y)==oldcolor)
  
• 
  {
  
• 
  PutPixel (x,y,newcolor);
  
• 
  fill4(x,y-1,newcolor,oldcolor);
  
• 
  fll4(x,y+1,newcolor,oldcolor); fill4(x-1,y,newcolor,oldcolor);
  
• 
  fill4(x+1.y,newcolor,oldcolor);
  
• 
  }}
  

Текисликда (2D) соҳани бўяш 2.

• 
  Бундан ташқари 4 ва 8 боғланишлик соҳалар учун алгоритмлар мавжуд.
  

Ички oldcolor ранг билан берилган янги newcolor ранг билан
4боғланишлик соҳани бўяш оддий рекурсия алгоритмини келтирамиз.

• 
  Function fill4(int x,int y:int newcolor, :word);
  
• 
  {
  
• 
  If GetPixel(x,y)==bcolor and GetPixel(x,y)==newcolor
  
• 
  {
  
• 
  PutPixel (x,y,newcolor);
  
• 
  fill4(x,y-1,bcolor,newcolor);
  
• 
  fill4(x,y+1,bcolor,newcolor);
  
• 
  fill4(x-1,y,bcolor,newcolor);
  
• 
  fill4(x+1,y,bcolor,newcolor);
  
• 
  }}
  

Эътиборингиз учун рахмат!

Маъруза 13. Растр графикаси алгоритмлари. Брезенхейм ва Сазерланд-Кохен алгоритми

• 
  Мақсад: Растр графикасининг алгоритмларини ўрганиш.
  
• 
  Калит сўзлари: Растр графикаси, кесма брезенхейм алгоритми, Сазерланд-Кохен алгоритми
  
• 
  Режа:
  
• 
  1. Кесма Брезенхейм алгоритми
  
• 
  2. Сазерланд-Кохен алгоритми
  

Брезенхейм алгоритми. Кесманинг растр тасвири

• 
  (𝑥₁, 𝑦₁) ва (𝑥₂, 𝑦₂) туташтирувчи кесманинг растр тасвирини қуриш масаласини кўрамиз.
  
• 
  Фараз қиламизки
  

0 ≤ 𝑦₁ ≤ 𝑦₂ ≤ 𝑥₁ ≤ 𝑥₂
Берилган иккита нуқтадан ўтувчи тўғри чизиқ тенгламасини тузамиз
𝑥 − 𝑥₁ 𝑦 − 𝑦₁
=
𝑥2 − 𝑥1 𝑦2 − 𝑦1

• 
  Унда кесма қуйидаги тенглама билан берилади:
  

𝑦 = 𝑦1 + 𝑥𝑦22−−𝑦𝑥11 (𝑥 − 𝑥1),
x∈ 𝑥₁, 𝑥₂

• 
  Ёки бу ерда
  

Ушбу алгоритм камчиликларга эга, яъни бутун сонли сетка устида амаллар бажаришда ҳақиқий сонларга мурожааат қилиш.
𝑦 = 𝑘𝑥 + 𝑏, 𝑘 = ^{𝑦2−𝑦1}, 𝑏 = 𝑦₁ − 𝑘𝑥₁,
𝑥2−𝑥1

• 
  1965 йилда Брезенхейм томонидан кесманинг растр тасвирини қуриш учун оддий бутун сонли алгоритмни тавсия қилган (𝑥₁, 𝑦₁) ва (𝑥₂, 𝑦₂) нуқталари орқали ифодаланувчи кесманинг Брезенхейм алгоритмини келитирамиз. Кесмани шундай қилиб кўчирамизки (0, 0) нуқта боши ва (dx, dy) (бу ерда dx= (𝑥₂ − 𝑥₁), dy= (𝑦₂ − 𝑦₁) ) нуқта охири бўлсин. Кесма ётувчи тўғри чизиқ
  

𝑑𝑦 тенгламаси қуйидагича: 𝑦 = ∗ 𝑥)
𝑑𝑥

Кесманинг 𝑃_𝑖−1 = 𝑥_𝑖−1, 𝑦_𝑖−1 = (𝑟, 𝑞) нуқтасини кўрамиз, унда кейинги нуқта

𝑆_𝑖 = (𝑟 + 1, 𝑞) ёки 𝑇_𝑖 = (𝑟 + 1, 𝑞 + 1)
бўлиши мумкин. Тўғри чизиқ (кесма) унга яқин жойлашган пикселлар (𝑆_𝑖, 𝑇_𝑖 )
орасидаги масофалар қуйидагича:
𝑑𝑦𝑑𝑦
𝑆 = 𝑟 + 1 − 𝑞 , 𝑡 = 𝑞 + 1 − 𝑟 + 1
𝑑𝑥𝑑𝑥
𝑑𝑦
𝑆 − 𝑡 = 2 𝑟 + 1 − 2𝑞 − 1
𝑑𝑥
кўрамиз.
Агар 𝑆−𝑡 <бўлса0 𝑆_𝑖 нуқта танланади акс ҳолда 𝑇_𝑖 нуқта
d𝑥 > 0 ҳисобга олган ҳолда d𝑥(𝑆 − 𝑡) ҳам кўраверсак бўлади ва уни 𝑑_𝑖 деб белгалаймиз 𝒅_𝒊 = 𝟐𝒅𝒚 𝒓 + 𝟏 − 𝟐𝒒𝒅𝒙 − 𝒅𝒙
𝑟 = 𝑥_𝑖−1 ва 𝑞 = 𝑦_𝑖−1 ҳисобга олган ҳолда
𝒅_𝒊 = 𝟐𝒅𝒚𝒙_𝒊−𝟏 − 𝟐𝒅𝒙𝒚_𝒊−𝟏 + 𝟐𝒅𝒚 − 𝒅𝒙
Кейинги қадамда яъни 𝑖 + 1
𝒅_𝒊+𝟏 = 𝟐𝒅𝒚𝒙_𝒊 − 𝟐𝒅𝒙𝒚_𝒊 + 𝟐𝒅𝒚 − 𝒅𝒙
𝑑_𝑖+1 дан 𝑑_𝑖 ни айирамиз ва 𝑥_𝑖 − 𝑥_𝑖−1 ни ҳисобга олган ҳолда:
𝒅_𝒊+𝟏 = 𝒅_𝒊 + 𝟐𝒅𝒚 − 𝟐𝒅𝒙(𝒚_𝒊 − 𝒚_𝒊−𝟏)
Агар яъни ^𝑑_𝑖 <0 бўлса ^𝑆_𝑖 танланади, у ҳолда
𝑦𝑖 = 𝑦𝑖−1 ва 𝑑𝑖+1 = 𝑑𝑖 + 2𝑑𝑦
Акс ҳолда, яъни 𝑑_𝑖 ≥ 0 бўлса 𝑇_𝑖 танланади ва у ҳолда 𝑦_𝑖 − 𝑦_𝑖−1 = 1
𝒅_𝒊+𝟏 = 𝒅_𝒊 + 𝟐(𝒅𝒚 − 𝒅𝒙)
Шундай қилиб биз 𝑑_𝑖+1 ни 𝑑_𝑖 нинг қиймати орқали ҳисоблаш ва 𝑆_𝑖, 𝑇_𝑖 нуқталарни танлаш учун интерактив усулни ҳосил қилдик. Бошланғич ҳолатда 𝑑₁ = 2𝑑𝑦 − 𝑑𝑥 (𝑥₀, 𝑦₀ ) = 0,0 ни ҳисобга олган ҳолда 𝑖 = 1 топилади.