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

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

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

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

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

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

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

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

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

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

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


Commons-logo.svg