Алгоритм художника

Поделись знанием:
(перенаправлено с «Z-сортировка»)
Перейти к: навигация, поиск

Алгоритм художника — простейший программный вариант решения «проблемы видимости» в трехмерной компьютерной графике.

Название «алгоритм художника» относится к технике, используемой многими живописцами: сначала рисуются наиболее удалённые части сцены, потом части которые ближе. Постепенно ближние части начинают перекрывать отдаленные части более удалённых объектов. Задача программиста при реализации алгоритма художника — отсортировать все полигоны по удалённости от наблюдателя и начать выводить, начиная с более дальних.

Наиболее удалённые горы рисуются в первую очередь. Затем рисуется луг, а потом деревья. Можно заметить, что некоторые части луга ближе, чем некоторые деревья. Однако правильный порядок сортировки (горы -> луг -> деревья) позволяет получить корректную картину, без перекрытия деревьев частями луга


Проблемы алгоритма

Алгоритм не позволяет получить корректную картину в случае взаимноперекрывающихся полигонов. В этом случае, как показано на рисунке справа, полигоны А, В и С накладываются друг на друга таким образом, что невозможно определить, в каком порядке их следует рисовать. В этом случае, следует разбить конфликтный полигон на несколько меньших, например алгоритмом Ньюэлла[1], предложенным в 1972 году.

Второй распространённой проблемой является то, что система прорисовывает также области, которые впоследствии будут перекрыты, на что тратится лишнее процессорное время.

Эти недостатки привели к разработке метода Z-буфера, который можно рассматривать как развитие алгоритма художника.

См. также

Напишите отзыв о статье "Алгоритм художника"

Примечания

  1. [en.wikipedia.org/wiki/Newell%27s_algorithm Newell's algorithm].

Отрывок, характеризующий Алгоритм художника

Пьер уже чувствовал в себе этот освежающий источник блаженства, теперь радостью и умилением переполнявший его душу.


Скоро после этого в темную храмину пришел за Пьером уже не прежний ритор, а поручитель Вилларский, которого он узнал по голосу. На новые вопросы о твердости его намерения, Пьер отвечал: «Да, да, согласен», – и с сияющею детскою улыбкой, с открытой, жирной грудью, неровно и робко шагая одной разутой и одной обутой ногой, пошел вперед с приставленной Вилларским к его обнаженной груди шпагой. Из комнаты его повели по коридорам, поворачивая взад и вперед, и наконец привели к дверям ложи. Вилларский кашлянул, ему ответили масонскими стуками молотков, дверь отворилась перед ними. Чей то басистый голос (глаза Пьера всё были завязаны) сделал ему вопросы о том, кто он, где, когда родился? и т. п. Потом его опять повели куда то, не развязывая ему глаз, и во время ходьбы его говорили ему аллегории о трудах его путешествия, о священной дружбе, о предвечном Строителе мира, о мужестве, с которым он должен переносить труды и опасности. Во время этого путешествия Пьер заметил, что его называли то ищущим, то страждущим, то требующим, и различно стучали при этом молотками и шпагами. В то время как его подводили к какому то предмету, он заметил, что произошло замешательство и смятение между его руководителями. Он слышал, как шопотом заспорили между собой окружающие люди и как один настаивал на том, чтобы он был проведен по какому то ковру. После этого взяли его правую руку, положили на что то, а левою велели ему приставить циркуль к левой груди, и заставили его, повторяя слова, которые читал другой, прочесть клятву верности законам ордена. Потом потушили свечи, зажгли спирт, как это слышал по запаху Пьер, и сказали, что он увидит малый свет. С него сняли повязку, и Пьер как во сне увидал, в слабом свете спиртового огня, несколько людей, которые в таких же фартуках, как и ритор, стояли против него и держали шпаги, направленные в его грудь. Между ними стоял человек в белой окровавленной рубашке. Увидав это, Пьер грудью надвинулся вперед на шпаги, желая, чтобы они вонзились в него. Но шпаги отстранились от него и ему тотчас же опять надели повязку. – Теперь ты видел малый свет, – сказал ему чей то голос. Потом опять зажгли свечи, сказали, что ему надо видеть полный свет, и опять сняли повязку и более десяти голосов вдруг сказали: sic transit gloria mundi. [так проходит мирская слава.]