Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Алгоритм художника, також відомий як пріоритетне заповнення, є одним з найпростіших рішень проблем які виникають в комп'ютерній 3D графіці. При проектуванні 3D-сцени на 2D площину, необхідно в якийсь момент вирішити, які багатокутники видно, і які приховані або частково приховані.
Алгоритм художника
Назва «алгоритм художника» відноситься до техніки, яка використовується багатьма художниками живопису для віддалення частин сцени, які перекриваються частинами, розташованими ближче до спостерігача. Алгоритм художника сортує всі багатокутники в сцені по їх глибині і потім малює їх у порядку від найвіддаленішого до найближчого. Алгоритм буде зафарбувати ті частини, які зазвичай не видно — тим самим вирішуючи проблему видимості — ціною фарбування областей віддалених об'єктів, які не будуть видимими. Порядок, який використовує алгоритмом називається «порядок глибини», який використовує числову відстань до частин сцени: істотна властивість цього впорядкування, полягає в тому, якщо один об'єкт заступає частину іншого, тому перший об'єкт буде забарвлений після об'єкта, який він приховує. Таким чином, такий порядок може бути описаний як топологічне впорядкування орієнтованого ациклічного графу, що представляє розташування об'єктів.
Алгоритм може не може розташувати об'єкти в деяких випадках. Зокрема при циклічному перекритті або обробці багатокутників. У разі циклічного перекриття, як показано на малюнку справа, багатокутники A, B, і C перекривають один одного таким чином, що неможливо визначити, який багатокутник найближчий. У цьому разі багатокутники повинні бути розрізані, для подальшого сортування. Алгоритм Невілла, запропонований в 1972, описує спосіб розрізання таких багатокутників. Багато таких способів є в обчислювальній геометрії.
Випадок «проколювання» багатокутників виникає тоді, коли один багатокутник перетинає площину іншого. Як і з циклічним перекриттям, ця проблема може бути вирішена за рахунок розрізання відповідного багатокутника.
В основних реалізаціях алгоритм живописця може бути не ефективним. Це змушує систему на надання кожній точці на кожному багатокутнику у видимій зоні, навіть якщо це багатокутник оклюзії в готовій сцені. Це означає, що для отримання докладних сцен, алгоритм живописця може бути податком комп'ютерного обладнання.
Зворотній алгоритм художника
Зворотній алгоритм художника виводить впорядковані об'єкти починаючи з найближчого закінчуючи найвіддаленішим за правилом, що фарба не повинна бути застосована до тої частини зображення, яка вже пофарбована. При побудові зображення, це може бути дуже ефективним, оскільки відпадає потреба в розрахунку зображення (а для цього потрібен розрахунок освітлення, текстурування та інше) для частин більш віддалених від сцени, які закриті ближчими об'єктами. Однак у зворотнього алгоритму такі ж недоліки, як і у стандартного.
Ці та інші недоліки алгоритму призвели до розвитку методу Z-буфера, який можна розглядати як розвиток алгоритму художника, який попіксельно розв'язує питання глибини об'єкта. Навіть в таких системах, іноді використовується алгоритм художника. Так як реалізації Z-буфера звичайно використовують фіксовану точність регістрів буфера, яка реалізовано на апаратному рівні, тому можливі проблеми видимості через помилки округлення. Такі як дублювання або прогалини у з'єднанні між многокутниками. Щоб уникнути цього, деякі графічні реалізації «накладають» ребра таких многокутників, так само як і в алгоритмі художника. Це означає, що деякі пікселі будуть обчислені два рази (як і в алгоритмі художника), але це буде лише на невеликих ділянках зображення і незначно впливає на продуктивність всього алгоритму.
Примітки
- de Berg, Mark (1993), , Lecture Notes in Computer Science, т. 703, Springer, с. 130, ISBN , архів оригіналу за 30 червня 2014, процитовано 1 червня 2014.
Джерела
- Foley, James; [en]; Feiner, Steven K.; [en] (1990). [en]. Reading, MA, USA: Addison-Wesley. с. 1174. ISBN .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm hudozhnika takozh vidomij yak prioritetne zapovnennya ye odnim z najprostishih rishen problem yaki vinikayut v komp yuternij 3D grafici Pri proektuvanni 3D sceni na 2D ploshinu neobhidno v yakijs moment virishiti yaki bagatokutniki vidno i yaki prihovani abo chastkovo prihovani Algoritm hudozhnikaNazva algoritm hudozhnika vidnositsya do tehniki yaka vikoristovuyetsya bagatma hudozhnikami zhivopisu dlya viddalennya chastin sceni yaki perekrivayutsya chastinami roztashovanimi blizhche do sposterigacha Algoritm hudozhnika sortuye vsi bagatokutniki v sceni po yih glibini i potim malyuye yih u poryadku vid najviddalenishogo do najblizhchogo Algoritm bude zafarbuvati ti chastini yaki zazvichaj ne vidno tim samim virishuyuchi problemu vidimosti cinoyu farbuvannya oblastej viddalenih ob yektiv yaki ne budut vidimimi Poryadok yakij vikoristovuye algoritmom nazivayetsya poryadok glibini yakij vikoristovuye chislovu vidstan do chastin sceni istotna vlastivist cogo vporyadkuvannya polyagaye v tomu yaksho odin ob yekt zastupaye chastinu inshogo tomu pershij ob yekt bude zabarvlenij pislya ob yekta yakij vin prihovuye Takim chinom takij poryadok mozhe buti opisanij yak topologichne vporyadkuvannya oriyentovanogo aciklichnogo grafu sho predstavlyaye roztashuvannya ob yektiv Daleki gori pofarbovani pershim a potim bilsh blizki lugi i dereva Hocha deyaki dereva dali vid tochki zoru nizh deyakih chastini lugiv uporyadkuvannya gori luki dereva oskilki nezalezhno vid ob yekta vporyadkuvannya prihovuye bud yaku chastinu ob yekta yakij znahoditsya piznishe Ciklichne perekrittya bagatokutnikiv nemaye najblizhchogo Algoritm mozhe ne mozhe roztashuvati ob yekti v deyakih vipadkah Zokrema pri ciklichnomu perekritti abo obrobci bagatokutnikiv U razi ciklichnogo perekrittya yak pokazano na malyunku sprava bagatokutniki A B i C perekrivayut odin odnogo takim chinom sho nemozhlivo viznachiti yakij bagatokutnik najblizhchij U comu razi bagatokutniki povinni buti rozrizani dlya podalshogo sortuvannya Algoritm Nevilla zaproponovanij v 1972 opisuye sposib rozrizannya takih bagatokutnikiv Bagato takih sposobiv ye v obchislyuvalnij geometriyi Vipadok prokolyuvannya bagatokutnikiv vinikaye todi koli odin bagatokutnik peretinaye ploshinu inshogo Yak i z ciklichnim perekrittyam cya problema mozhe buti virishena za rahunok rozrizannya vidpovidnogo bagatokutnika V osnovnih realizaciyah algoritm zhivopiscya mozhe buti ne efektivnim Ce zmushuye sistemu na nadannya kozhnij tochci na kozhnomu bagatokutniku u vidimij zoni navit yaksho ce bagatokutnik oklyuziyi v gotovij sceni Ce oznachaye sho dlya otrimannya dokladnih scen algoritm zhivopiscya mozhe buti podatkom komp yuternogo obladnannya Zvorotnij algoritm hudozhnikaZvorotnij algoritm hudozhnika vivodit vporyadkovani ob yekti pochinayuchi z najblizhchogo zakinchuyuchi najviddalenishim za pravilom sho farba ne povinna buti zastosovana do toyi chastini zobrazhennya yaka vzhe pofarbovana Pri pobudovi zobrazhennya ce mozhe buti duzhe efektivnim oskilki vidpadaye potreba v rozrahunku zobrazhennya a dlya cogo potriben rozrahunok osvitlennya teksturuvannya ta inshe dlya chastin bilsh viddalenih vid sceni yaki zakriti blizhchimi ob yektami Odnak u zvorotnogo algoritmu taki zh nedoliki yak i u standartnogo Ci ta inshi nedoliki algoritmu prizveli do rozvitku metodu Z bufera yakij mozhna rozglyadati yak rozvitok algoritmu hudozhnika yakij popikselno rozv yazuye pitannya glibini ob yekta Navit v takih sistemah inodi vikoristovuyetsya algoritm hudozhnika Tak yak realizaciyi Z bufera zvichajno vikoristovuyut fiksovanu tochnist registriv bufera yaka realizovano na aparatnomu rivni tomu mozhlivi problemi vidimosti cherez pomilki okruglennya Taki yak dublyuvannya abo progalini u z yednanni mizh mnogokutnikami Shob uniknuti cogo deyaki grafichni realizaciyi nakladayut rebra takih mnogokutnikiv tak samo yak i v algoritmi hudozhnika Ce oznachaye sho deyaki pikseli budut obchisleni dva razi yak i v algoritmi hudozhnika ale ce bude lishe na nevelikih dilyankah zobrazhennya i neznachno vplivaye na produktivnist vsogo algoritmu Primitkide Berg Mark 1993 Lecture Notes in Computer Science t 703 Springer s 130 ISBN 9783540570202 arhiv originalu za 30 chervnya 2014 procitovano 1 chervnya 2014 DzherelaFoley James en Feiner Steven K en 1990 en Reading MA USA Addison Wesley s 1174 ISBN 0 201 12110 7