Նկարչի ալգորիթմ

Վիքիպեդիայից՝ ազատ հանրագիտարանից

Նկարչի ալգորիթմը, որը հայտնի է նաև առաջնային լցոնում անունով, 3D համակարգչային գրաֆիկայում գոյություն ունեցող տեսանելիության խնդրի պարզագույն լուծումներից մեկն է։ Երկչափ հարթության (2D) վրա եռաչափ (3D) տեսարան նախագծելիս որոշ առումով անհրաժեշտ է որոշել, թե որ բազմանկյուններն են տեսանելի, և որոնք՝ թաքնված։

"Նկարչի ալգորիթմ" անվանումը վերաբերում է շատ նկարիչների կողմից աշխատած տեխնիկային. այն է՝ նկարել տեսարանի հեռավոր մասերը նախքան այն մասերը, որոնք ավելի մոտիկ են ու դրա հետևանքով ծածկում են հեռավոր մասերի որոշ տարածքներ։ Նկարչի ալգորիթմը տեսակավորում է տեսարանի բոլոր բազմանկյունները ըստ խորության և հետո դրանք նկարում հետևյալ պայմանով՝ ամենահեռավորից ամենամոտիկը։ Այն կնկարի այն մասերի վրա, որոնք, որպես կանոն, տեսանելի չեն՝ այսպիով լուծելով տեսանելիության խնդիրը՝ հեռավոր առարկաների անպետք մասերը ներկելու գնով։

Տեսարանում համեմատաբար հեռու գտնվող սարերը նկարում են առաջինը, հետո` ավելի մոտ գտնվող մարգագետինը, իսկ վերջում` տեսարանում ամենամոտ առարկաները` ծառերը։
Մասնակիորեն համընկնող բազմանկյունները կարող են ալգորիթմի ձախողման պատճառ հանդիսանալ։

Ալգորիթմը կարող է ձախողվել որոշ դեպքերում՝ պարունակելով պարբերաբար մասնակի կերպով իրար ծածկող կամ թափանցող բազմանկյուններ։ Պարբերաբար մասամբ համընկնելու դեպքում, ինչպես ցույց է տրված աջ կողմի պատկերում, A, B և C բազմանկյունները պարբերաբար մասնակի կերպով միմյանց ծածկում են այնպես որ անհնար է որոշել, թե որ բազմանկյունն է մյուսներից ավելի վերև գտնվում։ Այսպիսի պարագայում խանգարող բազմանկյունները պետք է կտրել՝ տեսակավորում թույլ տալու համար։ Նյուելի ալգորիթմը, որը առաջարկվել է 1972 թվականին, այդպիսի բազմանկյունները կտրելու համար ապահովում է մի մեթոդ։ Բազմաթիվ մեթոդներ առաջարկվել են նաև Համակարգչային երկրաչափության բնագավառում։

Թափանցող բազմանկյունների դեպքը առաջանում է այն ժամանակ, երբ մի բազմանկյունը հատում է մյուսին։ Ինչպես պարբերաբար համընկնող բազմանկյունների դեպքում, այս խնդիրը կարելի է լուծել՝ կտրելով խանգարող բազմանկյունները։

Հիմնականում նկարչի ալգորիթմը կարող է լինել անարդյունավետ։ Այն ստիպում է համակարգին ամեն մի բազմանկյան վրա տեսանելի ձևով ցույց տալ ( render) յուրաքանչյուր կետ, եթե նույնիսկ այդ բազմանկյունը փակ է վերջնական տեսարանում։ Սա նշանակում է, որ մանրակրկիտ տեսարանների համար նկարչի ալգորիթմը կարող է չափազանց լարել համակարգչային սարքավորումները։

Երբեմն օգտագործվում է Նկարչի հակադիր ալգորիթմը, որում դիտողին ամենամոտը գտնվող առարկաները առաջինն են նկարվում այն կանոնով, որ նորից չպետք է ներկել նկարի այն հատվածները, որոնք արդեն ներկված են։ Համակարգչային գրաֆիկայի համակարգում սա կարող է շատ արդյունավետ լինել, քանի որ այստեղ հարկավոր չէ հաշվարկել գույները (լուսավորությունը, կառուցվածքը և այլն) ավելի հեռու գտնվող մասերի համար, որոնք թաքնված են մոտիկ առարկաների հետևում։ Այնուամենայնիվ, հակադիր ալգորիթմը նույնպես ունի նույն թերություններից շատերը, ինչը որ ունի ստանդարտ տարբերակը։

Ալգորիթմի այս և ուրիշ թերությունները տարան Z-բուֆեր տեխնիկայի զարգացմանը, որը կարելի է դիտել որպես նկարչի ալգորիթմի զարգացում՝ լուծելով փիքսել առ փիքսել ելակետի խորը տարաձայնությունները, նվազեցնելով խորը գտնվող կետերը ցույց տալու պահանջը։ Նույնիսկ այսպիսի համակարգերում նկարչի ալգորիթմի տարբերակը երբեմն աշխատող է։ Քանի որ Z-բուֆերի իրականացումը սովորաբար հենվում է ֆիքսված ճշտությամբ խորքային բուֆերի՝ ապարատային միջոցներում իրականացվող գրանցամատյանի վրա, ուստի սխալի կլորացման պատճառով կա տեսանելիության խնդիրների տեղամաս։ Դրանք բազմանկյունների միջև միացման ժամանակ մասամբ համընկնումները կամ բացթողումներն են։ Սրանից խուսափելու համար "overrender" ‌[փա՞ստ] մեխանիզմի որոշ գրաֆիկական իրականացումներ նկարում են բոլոր բազմանկյունների արտահայտված մասերը՝ նկարչի ալգորիթմով տրված հաջորդականությամբ։ Սա նշանակում է, որ որոշ փիքսելներ, փաստորեն, նկարվում են կրկնակի (ինչպես նկարիչների ամբողջական ալգորիթմում), սակայն դա պատահում է նկարի միայն փոքր մասերի հետ և չնչին ազդեցություն է ունենում արդյունքի վրա։

Տեղեկագրություն[խմբագրել | խմբագրել կոդը]