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. ^ Аппель, Артур (1968). Моррел, AJH (ред.). «О расчете иллюзии реальности» (PDF) . Обработка информации, Труды Конгресса ИФИП, 1968 г., Эдинбург, Великобритания, 5–10 августа 1968 г., Том 2 - Аппаратное обеспечение, Приложения : 945–950. Архивировано (PDF) из оригинала 20 июля 2008 г.
  2. ^ Ромни, Гордон Уилсон (1 сентября 1969). «Компьютерная сборка и визуализация твердых тел». Архивировано из оригинала 2 ноября 2020 года. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
  3. ^ Гэри Скотт Уоткинс. 1970. «Алгоритм видимой поверхности в реальном времени. Кандидатская диссертация». Университет Юты. Номер заказа: AAI7023061.
  4. ^ abcde Ньюэлл, Мэн; Ньюэлл, Р.Г.; Санча, ТЛ (1 августа 1972 г.). «Решение проблемы скрытой поверхности» (PDF) . Материалы ежегодной конференции ACM-ACM'72 . АКМ '72. Том. 1. Бостон, Массачусетс, США: Ассоциация вычислительной техники. стр. 443–450. дои : 10.1145/800193.569954. ISBN 978-1-4503-7491-0. S2CID  13829930. Архивировано (PDF) из оригинала 22 сентября 2020 г.
  5. ^ Букнайт, В. Джек (1 сентября 1970 г.). «Процедура создания трехмерных полутоновых презентаций компьютерной графики». Коммуникации АКМ . 13 (9): 527–536. дои : 10.1145/362736.362739 . ISSN  0001-0782. S2CID  15941472.
  6. ^ Берланд, Дина (1995). Техники, материалы и студийная практика исторической живописи (PDF) . Институт охраны природы Гетти.
  7. ^ Уайли, Крис; Ромни, Гордон; Эванс, Дэвид; Эрдал, Алан (14 ноября 1967). «Полутоновые перспективные рисунки на компьютере». Материалы осенней совместной компьютерной конференции AFIPS '67, состоявшейся 14–16 ноября 1967 г. (осень) . Анахайм, Калифорния: Ассоциация вычислительной техники. стр. 49–58. дои : 10.1145/1465611.1465619. ISBN 978-1-4503-7896-3. S2CID  3282975.
  8. ^ аб Десаи, Апурва (2008). Компьютерная графика. PHI Learning Pvt. ООО ISBN 9788120335240.
  9. ^ Абде де Берг, Марк (2008). Вычислительная геометрия (PDF) . Спрингер. Архивировано (PDF) из оригинала 3 августа 2016 г.
  10. ^ де Берг, Марк (1993). Лучевая стрельба, порядок глубины и удаление скрытых поверхностей. Конспекты лекций по информатике. Том. 703. Спрингер. п. 130. ИСБН 9783540570202..
  11. ^ Варнок, Джон Э. (1969-06-01). «Алгоритм скрытой поверхности для компьютерных полутоновых изображений». Архивировано из оригинала 8 ноября 2020 года. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
  12. ^ Фрейзер, М.; Маркус, П. (июнь 1969 г.). «Обзор некоторых физических ограничений компьютерных элементов». Транзакции IEEE по магнетизму . 5 (2): 82–90. Бибкод : 1969ITM.....5...82F. дои : 10.1109/TMAG.1969.1066403. ISSN  1941-0069.
  13. ^ Нюберг, Дэниел (2011). Анализ двух распространенных алгоритмов удаления скрытых поверхностей: алгоритма художника и Z-буферизации.
Викискладе есть медиафайлы, связанные с проблемой Пейнтера .

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