stringtranslate.com

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

Фрактальный ландшафт , отрисованный с помощью алгоритма художника на Amiga

Алгоритм художника (также алгоритм сортировки по глубине и приоритетная заливка ) — это алгоритм для определения видимой поверхности в трехмерной компьютерной графике , который работает по принципу «полигон за полигоном», а не по принципу «пиксель за пикселем» , «строка за строкой» или «область за областью», как другие алгоритмы удаления скрытых поверхностей . [1] [2] [3] Алгоритм художника создает изображения, сортируя полигоны в изображении по их глубине и размещая каждый полигон в порядке от самого дальнего к самому близкому объекту. [4] [5]

Алгоритм художника был первоначально предложен в качестве базового метода решения проблемы определения скрытых поверхностей Мартином Ньюэллом , Ричардом Ньюэллом и Томом Санча в 1972 году, когда все трое работали в CADCentre . [4] Название «алгоритм художника» относится к технике, используемой многими художниками, когда они начинают с рисования удаленных частей сцены, прежде чем тех, которые находятся ближе, тем самым покрывая некоторые области удаленных частей. [6] [7] Аналогично, алгоритм художника сортирует все полигоны в сцене по их глубине, а затем рисует их в этом порядке, от самых дальних к самым близким. [8] Он закрасит части, которые обычно не видны, — таким образом решая проблему видимости — ценой закрашивания невидимых областей удаленных объектов. [9] Порядок, используемый алгоритмом, называется « порядком глубины» и не обязательно должен учитывать числовые расстояния до частей сцены: существенное свойство этого порядка заключается, скорее, в том, что если один объект закрывает часть другого, то первый объект рисуется после объекта, который он закрывает. [9] Таким образом, допустимый порядок можно описать как топологическое упорядочение направленного ациклического графа, представляющего преграды между объектами. [10]

Сначала рисуются дальние горы, затем луга поближе; наконец, рисуются деревья. Хотя некоторые деревья находятся дальше от точки обзора, чем некоторые части лугов, порядок (горы, луга, деревья) формирует допустимый порядок глубины, поскольку ни один объект в порядке не закрывает какую-либо часть более позднего объекта.

Алгоритм

Концептуально алгоритм Пэйнтера работает следующим образом:

  1. Сортировать каждый полигон по глубине
  2. Разместите каждый полигон от самого дальнего полигона до самого ближайшего полигона.

Псевдокод

сортировка  полигонов по глубине для каждого  полигона  p : для каждого  пикселя , который покрывает p : закрасить  p.color на пикселе

Сложность времени

Временная сложность алгоритма художника зависит от алгоритма сортировки, используемого для упорядочивания полигонов. При условии оптимального алгоритма сортировки, алгоритм художника имеет наихудшую сложность O ( n log n + m*n ), где n — количество полигонов, а m — количество пикселей для заполнения.

Сложность пространства

В худшем случае пространственная сложность алгоритма художника составляет O ( n+m ), где n — количество полигонов, а m — количество пикселей, которые нужно заполнить.

Преимущества

Существуют два основных технических условия, благоприятствующих использованию алгоритма художника.

Базовая графическая структура

Алгоритм художника не так сложен по структуре, как другие его аналоги алгоритма сортировки глубины. [9] [11] Такие компоненты, как порядок рендеринга на основе глубины, используемые алгоритмом художника, являются одним из самых простых способов обозначения порядка графического производства. [8] Эта простота делает его полезным в базовых сценариях вывода компьютерной графики, где несложный рендеринг должен быть выполнен с небольшими усилиями. [9]

Эффективность памяти

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

Ограничения

Перекрывающиеся полигоны могут привести к сбою алгоритма

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

Циклическое перекрытие

В случае циклического перекрытия, как показано на рисунке справа, полигоны A, B и C перекрывают друг друга таким образом, что невозможно определить, какой полигон находится выше других. В этом случае проблемные полигоны должны быть отсечены, чтобы обеспечить сортировку. [4]

Пронзающие полигоны

Случай пронзающих полигонов возникает, когда один полигон пересекает другой. Подобно циклическому перекрытию, эта проблема может быть решена путем разрезания проблемных полигонов. [4]

Эффективность

В базовых реализациях алгоритм художника может быть неэффективным. Он заставляет систему визуализировать каждую точку на каждом полигоне в видимом наборе, даже если этот полигон закрыт в готовой сцене. Это означает, что для детализированных сцен алгоритм художника может чрезмерно нагружать компьютерное оборудование.

Варианты

Расширенный алгоритм художника

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

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

Другой вариант алгоритма художника включает в себя алгоритм обратного художника . Алгоритм обратного художника сначала рисует объекты, ближайшие к зрителю — с правилом, что краска никогда не должна применяться к частям изображения, которые уже окрашены (если они не являются частично прозрачными). В компьютерной графической системе это может быть очень эффективно, поскольку нет необходимости рассчитывать цвета (используя освещение, текстурирование и т. п.) для частей удаленной сцены, которые скрыты близлежащими объектами. Однако обратный алгоритм страдает от многих из тех же проблем, что и стандартная версия.

Другие алгоритмы компьютерной графики

Недостатки алгоритма художника привели к разработке методов Z-буфера , которые можно рассматривать как развитие алгоритма художника путем разрешения конфликтов глубины на попиксельной основе, что снижает необходимость в порядке рендеринга на основе глубины. [13] Даже в таких системах иногда используется вариант алгоритма художника. Поскольку реализации Z-буфера обычно полагаются на регистры буфера глубины с фиксированной точностью, реализованные в оборудовании, существуют проблемы с видимостью из-за ошибки округления. Это наложения или зазоры на стыках между полигонами. Чтобы избежать этого, некоторые графические движки реализуют «перерисовку», [ требуется цитата ] рисуя затронутые края обоих полигонов в порядке, заданном алгоритмом художника. Это означает, что некоторые пиксели фактически рисуются дважды (как в полном алгоритме художника), но это происходит только на небольших участках изображения и имеет незначительный эффект на производительность.

Ссылки

  1. ^ Appel, Arthur (1968). Morrel, AJH (ред.). "О вычислении иллюзии реальности" (PDF) . Обработка информации, Труды Конгресса IFIP 1968, Эдинбург, Великобритания, 5-10 августа 1968 г., Том 2 - Аппаратное обеспечение, приложения : 945–950. Архивировано (PDF) из оригинала 2008-07-20.
  2. ^ Ромни, Гордон Уилсон (1969-09-01). «Компьютерная сборка и рендеринг твердых тел». Архивировано из оригинала 2 ноября 2020 г. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  3. ^ Гэри Скотт Уоткинс. 1970. «Алгоритм видимой поверхности в реальном времени. Кандидатская диссертация». Университет Юты. Номер заказа: AAI7023061.
  4. ^ abcde Newell, ME; Newell, RG; Sancha, TL (1972-08-01). "Решение проблемы скрытой поверхности" (PDF) . Труды ежегодной конференции ACM по - ACM'72 . ACM '72. Том 1. Бостон, Массачусетс, США: Ассоциация вычислительной техники. стр. 443–450. doi :10.1145/800193.569954. ISBN 978-1-4503-7491-0. S2CID  13829930. Архивировано (PDF) из оригинала 2020-09-22.
  5. ^ Букнайт, В. Джек (1970-09-01). "Процедура генерации трехмерных полутоновых компьютерных графических презентаций". Сообщения ACM . 13 (9): 527–536. doi : 10.1145/362736.362739 . ISSN  0001-0782. S2CID  15941472.
  6. ^ Берланд, Дина (1995). Исторические методы живописи, материалы и студийная практика (PDF) . Институт консервации Гетти.
  7. ^ Wylie, Chris; Romney, Gordon; Evans, David; Erdahl, Alan (1967-11-14). "Полутоновые перспективные рисунки на компьютере". Труды 14-16 ноября 1967 года, осенняя совместная компьютерная конференция - AFIPS '67 (осень) . Анахайм, Калифорния: Ассоциация вычислительной техники. стр. 49–58. doi :10.1145/1465611.1465619. ISBN 978-1-4503-7896-3. S2CID  3282975.
  8. ^ аб Десаи, Апурва (2008). Компьютерная графика. PHI Learning Pvt. ООО ISBN 9788120335240.
  9. ^ abcde de Berg, Mark (2008). Computational Geometry (PDF) . Springer. Архивировано (PDF) из оригинала 2016-08-03.
  10. ^ де Берг, Марк (1993). Лучевая стрельба, порядки глубины и удаление скрытых поверхностей. Конспект лекций по информатике. Том 703. Springer. стр. 130. ISBN 9783540570202..
  11. ^ Уорнок, Джон Э. (1969-06-01). «Алгоритм скрытой поверхности для компьютерных полутоновых изображений». Архивировано из оригинала 8 ноября 2020 г. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  12. ^ Фрейзер, М.; Маркус, П. (июнь 1969). «Обзор некоторых физических ограничений элементов компьютера». IEEE Transactions on Magnetics . 5 (2): 82–90. Bibcode : 1969ITM.....5...82F. doi : 10.1109/TMAG.1969.1066403. ISSN  1941-0069.
  13. ^ Нюберг, Дэниел (2011). Анализ двух распространенных алгоритмов удаления скрытых поверхностей: алгоритма художника и Z-буферизации.
На Викискладе есть медиафайлы по теме «Проблема Пейнтера» .

Внешние ссылки