ПОӘК 042-14-1-05.1.20.43/03-2008

ПОӘК 042-14-1-05.1.20.43/03-2008 

«18» қыркүйек 2008 ж. №1 басылым 

 

56 беттің 32

 

беті 

 

 

2

 

Брезенхем алгоритмі. 

3

 

Тұйық облыстарды бояу. 

4

 

Көпбұрыштарды толтыру. 

5

 

Облысты толтыру алгоритмдері. 

 

Қадалмен  кеңістікте  сетка  болсын  сонымен  қатар  оның  байламдары  – 

бірегесі квадраттық ортасы. 

Егер  оларды    х  (у)  бірлікке  ерекшеленсе  нүктелер  4-көршілер  деп 

аталады. 

Егер    х  (у)  кеш  дегенде  бірге  ерекшеленсе  –  қатысты  көршілер  онда 

нүктелер 8-көршілер деп аталады. 1 нүктесіне   2..9 нүктелердің барлығы сонда 

нақтылы көрші – тағы да қатыссыз, бірақ керісінше емес.  

4-жол деп көптеген  А

1

 , А

2

 , ..., А

n

 , нүтелер болады, және оларға А

i

 , А

i+1

 

нүктелері  i=1,2,...,n-1 кезінде нақтылы көршілер болып келеді. 

Бұл тығыз байланысқан жол болып саналады. 

8-жол (әлсіз байланысқан) деп  А

1

 ,А

2

 ,...,А

n 

, көптеген нүктелер аталады, 

оларға  А

i

 , А

i+1

 – әлсіз көршілер  i=1,2,...,n-1. 

Егер  А

1

 =А

n

 , жолы тұйықталған болып аталса. 

Егер  кез  келген  2-көптік  нүктені  тығыз  байланысқан  жолмен  қосуға 

болса, онда бұл көптік- тығызбайланысқан. 

Әлсіз  байланысқан  жол  жағдайының  мүмкіндігінде  сәйкесінше  көптік 

нүктелер типі. 

Кеңістіктегі  жай  қисық  деп  көптік  нүктелер  аталады  Оларда  екеуінен 

басқа  нүктелерінде  нақты  екі  көршілер  бар,  ал  алдынғы  екеуінде  –  бір 

көршіден. . 

Жай  тұйықталған  қисық  кеңістікте  деп  көптік  аталады,  және  оларға 

барлық нүктелерінде екі көршіден болады. 

Жай  тұйықталған  тығыз  байланысқан  қисық  кеңістікті  екі  әлсіз 

байланысқан көптікке бөледі. 

 

Көпбұрыштық  стандартты  үзіктің,дұғаның,эллипстің  генерация 

процедураларды бар және т.б    

Дегенімен Растровтық генерацияның мәселесін білу пайдалы: 

- принтер, плоттер,тышқанмен жұмыс істегенде; 

-  пиксел  атрибутының  әлдебір  шарттарға  тәуелділігі  болғанда  мысалға, 

тік немесе ішкі көпбұрыштағы пиксел жағдайында; 

-  кезекті  алгоритмнің  жұмысын  тездету  кезіндегі  стуктурасын  өзгерту 

қажеттілігінде. 

Растровтық үзіктің айналуы  - бұл үзікті бейнелейтін экрандағы көптеген 

пикселдердің кезекті инициализациялау процесі. 

Егер растровтық класс бейнесін жай және растровтық етік шектесек, онда 

- 8- және 4- тік байланысты екі ғана бейне пайда болады. 

"Жай" тапсырманың шешімін қарастырайық. 

ПОӘК 042-14-1-05.1.20.43/03-2008 

«18» қыркүйек 2008 ж. №1 басылым 

 

56 беттің 33 беті 

 

 

Аралық  пикселдерін  (растр  нүктелері)  таңдау  үшін,  идиалды  үзіктен 

алшақтаған  мүмкін  мысалы,  осы  үзікпен  жалғасқан  кеңістікті  барлық  растр 

нүктелерімен инициализация жасау. 

Кезекті нүктелердің генерациялы алгоритмін ұсынуға болады. 

Егер М

1

(х

1

,у

1

), М

2

(х

2

,у

2

) – үзік шегі болса онда оның теңдеуі: 

 

Және одан әрі  0

Онда  растрлы  бұранданы  (бұнда  және  осыдан  кейінгі  жағдайларда 

алгоритмдерді жазу үшін псевдоалгол немесе оқу алголы деп аталатын түсінік 

қолданылады) генерациялау процедурасы келесідей түрге ие:  

Dx := 1; Dy := abs((y2-y1)/(x2-x1)); 

X := x1; y := y1; L := x2-x1; 

for i := 0 to L-1 do begin 

PutPixel(x,Round(y)); 

X := x+Dx; y := y+Dy; end. 

Бұл  алгоритм  қарапайым:  тесікте  кезекті  нүктені  алып  оған  жақын 

пикселдерді құрамыз.   

Условие  k<1  шарты  бұранданың  бір  де  бір  нүктесін  қалдырмай  ратрлы 

кескінін  тұрғызу  үшін  қажетті:    х  бойынша  Dx=1қадамдаймыз,  y  бойынша 

аздап.  Егер  де  k>1,  онда  осы  алгоритмда    x,y  айнымалыларының  орнын 

ауыстыру қажет.   

Жазылған алгоритмде нүктенің толықмәнді абсциссасы әрбір қадамда бір 

бірлікке өзгереді, ал толықмәнді ординатаның мәні Dy өсу аралығы ординат осі 

бойынша көршілес деңгейдің 0.5 аймағына сәйкес келгенде ғана өзгереді. Осы 

бақылауларға сәйкес алгоритмді формасы бойынша негізгі схемасын өзгертпей 

ақ өзгертуге болады: 

х := x1; y := y1; n := x2-x1; m:= y2-y1; d := m/n; e := 0; 

for i := 1 to n do begin  

x := x+1; e := e + d; 

{егер  де  ординат  осінің  ауытқушылығы  берілген  мәннен  ½  көп  болатын 

болса,  онда  у-ті  1-ге  арттырып,  у-тің  жаңа  мәні  бойынша  е-нің  мәнін  түзету 

керек} 

if e > 0.5 then begin y := y+1; e := e - 1; end; 

PutPixel(x,y); 

end; 

Осы  жағдайда  келесі  нүктеде  ауысу  көршілес  8  клетканың  біреуінде 

болатындықтан тесіктің 8-байланысты көрінісі пайда болады.  

Осындай (көбінесе, шектеусіз  k<1) 8 және 4-байланысты бұрандалардың 

алгоритмдердің жалпыланған түрі Брезенхем алгоритмі деп аталады.  

Негізінен есептің екі түрі пайда болады:  

- төбелері мен жақтаулары берілген көпбұрыштардың ішін толтыру; 

ПОӘК 042-14-1-05.1.20.43/03-2008 

«18» қыркүйек 2008 ж. №1 басылым 

 

56 беттің 34

 

беті 

 

 

-  растрлы  бұрандамен  берілген,  жабық  контурмен  шектелген  ішкі 

аймақты толтыру. 

Белгілі болғандай, компьютерлік графикада кез-келген суретті салу үшін 

объект  көрінісі  мен  олардың  атрибуттарын  таңдауға  қажетті  пиксельдерді 

анықтап  алу  қажет.  Осылайша,  растрлы  көріністе  кез-келген  объект  –

пикселдердің  жиынтығы  болып  табылатындықтан,  олар  бос  немесе  толған, 

дөңес  немесе  ойыс  көпбұрыштар  түзеді.  Егер  де  берілген  пиксель  объект 

көрінісіне, ал бұл үнемі көпбұрыш, жататындығын анықтай білсе, онда есептің 

жартысы шешілді деп есептеуге болады.  

Көпбұрышқа қажетті нүктелер тесті 

Көпбұрыш  –  ол  жазықтықта  қарапайым  (өзара  қиылыспайтын),  сынық 

жабық сызықпен шектелген фигура.   

Сынық төбелерімен беріледі А

i 

(х

i

 ,у

i

 ), i = 1,2,...,n. 

Көршілес нүктелер i, i+1 - смежные төбелер. 

Есеп:  көпбұрыштың  растрлы  бұрандамасын  алу,  яғни  оның  ішкі 

нүктелеріне иницирлеу жүргізу.  

 Жордан таеоремасы: 

Қарапайым  жабық  тегіс  сынық  жазықтықты  байланысқан  екі 

компонентке бөледі: 

- шектелген, көпбұрыштың іші ; 

- шектелмеген сыртқы бөлік.  

Бұл  теорема  келесіде  қарастырылатын  алгоритмдердің  барлығы 

шектелген  уақыт  бойынша  жұмыс  істейтіндігін  білдіреді,  себебі  оларда  растр 

элементтерінің  соңғы  саны  қарастырылады.  Алгоритм  сыртқы  және  ішкі 

нүктелерді айыру керек.  

Көпбұрыштың қабырғаларын Е

i

 белгілейік:  [A

i

 , A

i+1

 ], i=1,2,...,n (n+1=1). 

Р

i

(х,у)  –  сыныққа  қатысты  емес  жазықтықтың  кейбір  нүктелері  болсын. 

Ол көпбұрыштың ішінде жатады ма соны анықтау керек.  

Р

i

 нүктесінен солға қараай горизонталь жартылайтүзу жүргіземіз (яғни,  Р

i

 

–нүктесі  жартылайтүзудің  оң  жақ  ұшы).  Р

i

  нүктесінен  Q  нүктесін  алшақтату 

варианттары:  

- көпбұрыш шекарасымен қиылысу болмайды, Р

i

 – сыртқы нүкте; 

- қиылысудың бүтін саны; Р

i

 - сыртқы; 

-  қиылысудың  бөлшек  саны;  Р

i

  –  ішкі 

нүкте. 

 

Егер  ешқандай  төбелеріне  тиместен 

сынықпен  қиылысатын  болса,  онда  мұндай 

қиылысуды маңызды деп атайды. 

Ереже: 

-  тесіктің  горизантальді  қабырғалармен 

қиылысуы есептелмейді; 

-  егер  қиылысу  нүктесі  қабырға  төбесі  болатын  болса,  онда  мұндай 

қиылысу да есептелмейді. Яғни, максимум нүктелерінде қиылысу есептелмейді 

ПОӘК 042-14-1-05.1.20.43/03-2008 

«18» қыркүйек 2008 ж. №1 басылым 

 

56 беттің 35 беті 

 

 

де,  минимум  нүктелерінде  екі  рет  есептеледі,  сонымен  қоса  бүтін  сан 

бұзылмайды.  

Көпбұрыштардың толтырылуы   

Егер де жазықтықта растрдың барлық нүктесін таңдап алып иницирлесе, 

тестқа сәйкес олар ішінде болады; ақыр соңында көпбұрышты бояуға болады. 

Бірақ бұл өте ұзақ және тиімді емес. Осыған байланысты кез-келген алгоритмде 

жұмысты тездету үшін осындай және басқадай әдістер  қолданылады.  

1.  Көпбұрышты  кейбір  жақтаулары  бар,  осьтері  параллель    минимальді 

объемлющий  көпбұрышқа  орналастырып,  осы  көпбұрыш  ішіндегі  нүктелерге 

талдау асау керек.  

2. Барлық горизонтальді түзулер сынықпен көпбұрыштың ішінде немесе 

сыртында  жататын  интервалдарға  жіктеледі.  Осы  интервалдардың  ұштарын 

анықтау  үшін  былай  істейміз.  Көпбұрыштың  ішіндегі  интервалдың  орнын 

анықтау  үшін  горизантальді  түзу  L  –  ді  белгілеп  аламыз.  Осы  түзудің 

көпбұрыш  қабырғаларымен  қиылысу  нүктесін  іздейміз.  Егер  де  қабырға 

ұштары L түзуінен әр түрлі жақта жататын болса онда қиылысу бар деген сөз.  

Сонымен  қоса  жоғарыда  айтылып  өткен  ереже  де  өз  күшінде  болады;  онда 

көпбұрыш  контурымен  қысқа  қиылысу  оның  төбелерінде  дұрыс  есептелетін 

болады. 

Алынған  нүктелерді  қайтадан  нөмірлейміз  және  жұп  бойынша  солдан 

оңға  қарай  біріктіреміз  –  бұл  жұптар  бояуды  қажет  ететін  көпбұрыш  ішіндегі 

интервалдар болып табылады.  

 

Осындай 

схема 

жолдар 

бойынша 

сканерлеу  тәртібі бойынша  толтыру  схемасы  деп 

атап,  ал  алгоритмді  –  жолақ  бойынша  сканерлеу 

дейміз.  

3.  Алгоритмнің  жұмысын  тездету  үшін 

ордината  ұштарынан  қабырғаларды  өсу  тәртібі 

бойынша  реттеу  керек.  Сканерленетін  түзулерді 

жоғарыдан  төмен  қарай  орын  ауыстырған  кезде  максимальді  ординатасының 

мәні  сканерлейтін  түзулер  ординатасынан  көп  болатын  қабырғалар  ғана 

тексеріледі.  Минимальді  ординаталарының  мәні  сканерлейтін  ординаталар 

мәнінен  көп  болатын  қабырғалар  тексерілу  тізімінен  мүлдем  шығарылып 

тасталынады.  

Егер  де  мәселе  дөңес  көпбұрыш  туралы  болатын  болса  онда  онда 

алгоритмді  қарапайымдатып  және  оның  тиімділігін  арттыруға  болады. 

Көпбұрыш шекараларын екі бөлшеккке – оңға және солға бөлуге болады, егер 

сканерлейтін түзулерге параллель болатын болса плюс max 2 қабырға, жоғарғы 

және төменгі  

Онда бөлшектің әрбіреуі L мен тек қана бір-ақ рет қиылысады: егер сол 

және оң шекаралар үшін Брезенхем алгоритмін пайдаланатын болса, онда  L дің 

әрбір  түзуі  үшін  сол  және  оң  пиксельдерді  аламыз.    Олардың  аралықтарының 

барлықтарын толтырып дөңес күпбұрыштың растрлы бұрандасын аламыз.  

ПОӘК 042-14-1-05.1.20.43/03-2008 

«18» қыркүйек 2008 ж. №1 басылым 

 

56 беттің 36

 

беті 

 

 

затравкасы бар аймақты толтыру алгоритмі 

Аумақ шекарасы берілген және оның ішінде затравка нүктесі көрсетілген 

деп болжайық. Одан бояу “ағып” барлық аумақты бояп тастайды. 

Бояу алгоритімін стек көмегімен қарастырып көрейік.  

Сызықты массивтердің үш түрі ажыратылады.  

Тізім  –  бұл  массивке  қойылатын  немесе  алынып  тасталынатын 

элементтердің жиынтығы.  

Кезек–  осындай  массивтен  элемент  онда  қойылған  тәртіпке  сәйкес 

алынып тасталынады.  

Стек  –  бір  жақ  ұшынан  ашық  болып  келетін  элементтердің  сызықты 

массиві.  

Затравочный  пиксел  стекке  орналастырылады.  Ары  қарай,  стек  толып 

тұрған кезде одан кезекті пиксельді бөліп алып, оны бояймыз да, көршілес  

пиксельдерді таңдаймыз. Егер де олардың арасында шекараға жатпайтын 

немесе  қажетті  түспен  боялмаған  пиксельдер  болатын  болса,  онда  оларды 

стекке  орналастырамыз.  Қайтадан  пиксельді  бөліп  алып  оны  бояймыз  және 

т.с.с.  

Осындай  алгоритмнің  жұмысы  біткеннен  кейін  аумақтың  барлық  ішкі 

пиксельдері боялады да, ал стек босап қалады.   

Бұл алгоритм тиімді жұмыс атқармайды, себебі бір пиксель бірнеше рет 

талданады да, ал бұл кезде стек шексіз өсе береді. Өте тиімді алгоритм болып 

затравкамен  толтырылатын  жолақты  алгоритм  болып  табылады.  Оның  негізі 

сканерлеуді затравкамен үйлестіру болып табылады.  

Жолақтардың  қарастырылуы-  онда  бояуға  қажетті  интервалдар  болады. 

Және  осы  интервалдардың  астында  да  боялатын  шекара  немесе  ішкі  аумақ 

болады.  Соңғы  жағдайда  пиксельдер  жоғарыдағы  және  төмендегі  жолақтар 

үшін  затравка  болып  табылады.  Осыны  ескере  отырып  аумақты  толтыру 

облысы келесідей болады: 

1. затравочный пикселді стекке орналастырамыз. 

2.  Стектан  пиксельді  бөліп  алып,  мүмкін  болатын  максимальды 

интервалды шекраға дейін оңға және солға толтырамыз.  

3. Ең шеткі сол және оң нүктелерді есте сақтаймыз.  

4.  Интервал  үстіндегі  және  астындағы  жолақтардан  ішкі  аумақтардағы 

толтырылмаған  ,  интервалдарға  біріккен  пиксельдерді  табамыз  да,  осы  әрбір 

интервалдардағы  ең  шеткі  оң  пиксельді  тауып  –  оны  затравка  ретінде 

қарастырамыз.  

Алгоритм кез-келген дұрыс аумақты тесіктерімен бірге толтырады.  

 

Бақылау сұрақтары  

1. Растр деген не? “Объектінің растрлы көрінісі” деген сөз нені білдіреді? 

2. Қарпайым жағдай үшін Брезенхем алгоритмін жазыңдар  

3. Көпбұрыштың ішкі нүктелеріне қажетті тесті құрастырып көріңіз. Олне 

үшін қолданылады? 

ПОӘК 042-14-1-05.1.20.43/03-2008 

«18» қыркүйек 2008 ж. №1 басылым 

 

56 беттің 37 беті 

 

 

4.  Көпбұрыштың  ішкі  толтырылуының  қарапайым  алгоритмі  қалай 

жұмыс істейді? Осындай алгоритмнің жұмысын тездету әдістерін атап өтіңдер. 

5.  “стек”  деген  не?  Шектелген  аумақты  стек  көмегімен  бояу  алгоритмі 

қалай жұмыс істейді? 

6. Көпбұрыштың ішін стекті жәнежолақты сканерлеуді пайдаланып бояу 

алгоритмі қалай жүзеге асырылады? 

 

Ұсынылатын әдебиеттер  

1 Люкшин Б.А. Компьютерная графика. – Т.: ТУСУР , 1999. – 280 с. 

 

14, 15 Дәріс 

 

Тақырып. Беттің көрінбейтін сызықтарын алып тастау 

 

Сұрақтар 

1

 

Қалқалау есебін  шешудің кейбір жағдайлары. 

2

 

Көпбұрыштың беткі жақтарын алып тастау. 

3

 

Деңгей  сызығы  триангуляциясы.  Екі  айнымалы  функциясы  деңгей 

сызығын құру. 

 

Үшөлшемді  объектілерді  тұрғызған  кездегі  негізгі  проблема  – 

көрінбейтін  сызықтар  мен  жазықтықтар  бөлігін  алып  тастау  болып  табылады. 

Осы  проблемаға  сонымен  қоса  мөлдірлік,  көлеңкенің  тұрғызылуы  және 

отражения келіп қосылады.  

Бақылаушы  проекциялану  центрінде  болады  деп  есептейік  және 

ортоганальді проекциялау кезінде бұл центр шексіздікте жатады.   

Жазықтықтың  Р

1

  нүктесі    S  жазықтығындағы  Р

2 

нүктесін  бүркемелейді, 

егер  де  сурет  жазықтығында  Р

1

  және  Р

2

  проекциялары  сәйкес  келетін  болса, 

онда  Р

2

  Р

1 

мен проекциялану центрі аралығында жатады.  

 Р  нүктесі  басқа  ешқандай  нүктені  бүркемейтін  болса  көрінетін  деп 

аталады.   

Көрінбейтін  сызықтарды  алып  тастайтын  универсалды  алгоритм  жоқ. 

Бүркемелеуге арналған бірнеше есептерді қарастырып көрейік.  

1. Көрініс А және В бөліктеріне бөлінген делік.  Егер де ең алыс А нүктесі 

ең жақын В нүктесіне қарағанда жақынырақ болса, онда В нүктесі В нүктесін 

бүркелей  алмайды.  Сондықтан  Алдымен  В-ны  содан  кейін  А-ны  тұрғызып, 

дұрыс уөріністі аламыз.  

2.  Бір  жағында  А,  бір  жағында  В  нүктесі  бар  жазықтық  тұрғызылады 

делік.  Егер  де  бақылаушы  А  жағында  болса,  онда  В  ешқашан  да  А-ны 

бүркемелемес.  Бұл  қиылыспайтын  екі  шар  негізінде  оңай  тұрғызылады: 

жазықтық  А  және  В  центрларын  байланыстыратын  тесікке  перпендикуляр. 

ПОӘК 042-14-1-05.1.20.43/03-2008 

«18» қыркүйек 2008 ж. №1 басылым 

 

56 беттің 38

 

беті 

 

 

Бақылаушының қай жерде орналасуына байланысты барлық көрініс те көрінеді. 

 

3. Егер барлық көрініс күрделі болатын болса, оны А, В – ға бөледі; одан 

кейін әрбір бөлікті одан ары қарапайым ережені қолдануға келгенше дейін  А

1

, 

А

2

, В

1

, В

2

 –ге бөле береміз.  

 

5. Көріністі бөлмей-ақ, суретті бөліктерге бөліп өңдеуге болады. 

6.  Көрініс  қасиеттері  сурет  қасиеттерімен  байланысты  болғандықтан,  ол 

қасиеттерін  қалқалауды  есептеу  тәсілін  таңдауда  ескеру  қажет.  Мысалы, 

"жақсы  ұйымдасқан"  объектлер  бар.  Олардың  көрінісі  когерентті  болады, 

шығыңқы  көпбұрыштар,  олардың  қырлары  не  толық  көрінеді,  не  тоолық 

көрінбейді. 

Шығыңқы емес қөпбүрыштар да ондай қасиет жоқ. Бірақ бұл жағдайда да 

бір элементтен екінші элементке өткенде көріну өзгерісі регулярлы сипатқа ие 

болады: элемент не толық қөрінеді, не толлық көрінбейді; егер ол тек бөлігімен 

көрінсе,  онда  көпбұрыштың  сурет  жазықтығына  түскен  ұырларының 

проекциялары қиылысады. 

Беттерді көсету тәсілдері: 

-аналитикалық:  бет  аналитикалық  өрнек  арқылы  беріледі,  қарапайым 

жағдайлар үшін- сфера, цилиндр, конус және т.б. 

-полиэндрлі:бет  көпбұрышты  қырлардың  жиынтығы  ретінде  болады, 

қырлар саны- полиэндрлі беттердің негізгі сипаттамасы; 

-параметрлік:  әрқайсысы  параметрлері  берілген  беттердің  жиынтығы 

ретінде. 

Параметрлік  көріністің  қабырғалары  мен  тордың  түзулері  каркастық 

түзулер деп, ал сәйкес сурет-каркастық деп аталады. 

Егер  бет  оның  элементтрінің  жарты  реңді  боялуымен  суреттелсе,  онда 

сурет жарты реңді деп аталады. 

Корініс  анализі  өтетін  кеңістік  типі  бойынша  алгоритмдер  үш  типке 

бөлінеді: 

-объектілі,  онда  объектлі  кеңістікте  орналасқан  беттің  бөлігі  анализден 

өтеді. Мұндай алгоритмнің жүмыс істеу уақыты~ n, n-көріністің объектілерінің 

саны және олардың рұқсат етілулері; 

-картиналық,  мұнда  картиналық  жазықтықтың  әрбір  элементінің  көрініс 

жазықтығындағы көрінуі (пиксель) есептеледі; 

t ~ n*N, 

мұндағы N- реестрдағы нүктелер саны; 

-аралас, анализ кезінде бірінші және екінші амалдар қолданылады. 

Визуализация тәсілі бойынша алгоритмдер екіге бөлінеді: 

-каркастық сурет беретін; 

ПОӘК 042-14-1-05.1.20.43/03-2008 

«18» қыркүйек 2008 ж. №1 басылым 

 

56 беттің 39 беті 

 

 

-жарты реңді. 

Бет  элементінің  тереңдігі  деп  осы  элемент  пен  картиналық  жазықтық 

арасындағы қашықтықты айтады. 

Қалқалау  алгоритмінде  екі  спецификалық  процедура  қолданылады: 

тереңдік тесты мен тиістілік тесты. 

Іріктеу типә 

жүктеу/скачать 0,76 Mb.

Достарыңызбен бөлісу: