Алгоритм художников - Википедия - Painters algorithm

Не путать с Алгоритм Шлемиля Художника.

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

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

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

Алгоритм

Концептуально алгоритм Painter's работает следующим образом:

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

Псевдокод

1  Сортировать полигоны к глубина2  для каждого многоугольник п:3      для каждого пиксель который п обложки: 4 краска p.color на пиксель

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

Сложность алгоритма рисования во многом зависит от алгоритма сортировки, используемого для упорядочивания многоугольников. Если предположить, что используется наиболее оптимальный алгоритм сортировки, алгоритм художника имеет сложность наихудшего случая О (п бревно п + т * п), куда п количество многоугольников и м - количество пикселей для заливки.

Космическая сложность

Наихудшая пространственная сложность алгоритма художника составляет О(п + м), куда п количество многоугольников и м - количество пикселей для заливки.

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

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

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

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

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

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

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

Ограничения

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

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

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

Пробивающие многоугольники

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

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

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

Варианты

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

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

Обратный алгоритм художника

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

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

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

Рекомендации

  • Фоли, Джеймс; Файнер, Стивен К .; Хьюз, Джон Ф. (1990). Компьютерная графика: принципы и практика. Ридинг, Массачусетс, США: Эддисон-Уэсли. п.1174. ISBN  0-201-12110-7.
  1. ^ Аппель, Артур (1968). Моррель, А. Дж. Х. (ред.). «По расчету иллюзии реальности» (PDF). Обработка информации, Материалы Конгресса ИФИП, 1968 г., Эдинбург, Великобритания, 5-10 августа 1968 г., Том 2 - Аппаратное обеспечение, приложения: 945–950.
  2. ^ Ромни, Гордон Уилсон (1969-09-01). «Компьютерная сборка и визуализация твердых тел». Цитировать журнал требует | журнал = (помощь)
  3. ^ Гэри Скотт Уоткинс. 1970 г. "Алгоритм видимой поверхности в реальном времени. Докторская диссертация". Университет Юты. Номер заказа: AAI7023061.
  4. ^ а б c d е Newell, M.E .; Newell, R.G .; Санча, Т. Л. (1972-08-01). «Решение проблемы скрытой поверхности» (PDF). Материалы ежегодной конференции ACM - Том 1. ACM '72. Бостон, Массачусетс, США: Ассоциация вычислительной техники. 1: 443–450. Дои:10.1145/800193.569954. ISBN  978-1-4503-7491-0. S2CID  13829930.
  5. ^ Букнайт, У. Джек (1970-09-01). «Процедура создания трехмерных полутоновых презентаций компьютерной графики». Коммуникации ACM. 13 (9): 527–536. Дои:10.1145/362736.362739. ISSN  0001-0782. S2CID  15941472.
  6. ^ Берляндия, Дина (1995). Исторические техники живописи, материалы и студийная практика. https://www.getty.edu/conservation/publications_resources/pdf_publications/pdf/historical_paintings.pdf: Институт охраны природы Гетти.
  7. ^ Уайли, Крис; Ромни, Гордон; Эванс, Дэвид; Эрдал, Алан (1967-11-14). «Полутоновые перспективные рисунки на компьютере». Материалы осенней совместной компьютерной конференции 14–16 ноября 1967 г.. AFIPS '67 (осень). Анахайм, Калифорния: Ассоциация вычислительной техники: 49–58. Дои:10.1145/1465611.1465619. ISBN  978-1-4503-7896-3. S2CID  3282975.
  8. ^ а б Десаи, Апурва (2008). Компьютерная графика. https://books.google.com/books?id=WQiIj8ZS0IoC&pg=PA256&lpg=PA256&dq=%22hewells%22+painter%27s+algorithm&source=bl&ots=HbWXoialNt&sig=ACfU3U0do0uKya5QGDaBUKKrXoYJ3uULdA&hl=en&sa=X&ved=2ahUKEwjh1tC14MHsAhUogK0KHWS5BsQQ6AEwAnoECAoQAg#v=onepage&q&f=false: PHI Learning Pvt. ОООCS1 maint: location (связь)
  9. ^ а б c d е де Берг, Марк (2008). Вычислительная геометрия. https://people.inf.elte.hu/fekete/algoritmusok_msc/terinfo_geom/konyvek/Computational%20Geometry%20-%20Algorithms%20and%20Applications,%203rd%20Ed.pdf: Springer.CS1 maint: location (связь)
  10. ^ де Берг, Марк (1993). Съемка лучей, заказы глубины и удаление скрытых поверхностей. Конспект лекций по информатике. 703. Springer. п. 130. ISBN  9783540570202 {{противоречивые цитаты}}.
  11. ^ Варнок, Джон Э. (1969-06-01). «Алгоритм скрытой поверхности для компьютерных полутоновых изображений». Цитировать журнал требует | журнал = (помощь)
  12. ^ Freiser, M .; Маркус, П. (июнь 1969 г.). «Обзор некоторых физических ограничений компьютерных элементов». IEEE Transactions on Magnetics. 5 (2): 82–90. Bibcode:1969ITM ..... 5 ... 82F. Дои:10.1109 / TMAG.1969.1066403. ISSN  1941-0069.
  13. ^ Ниберг, Дэниел (2011). Анализ двух общих алгоритмов удаления скрытых поверхностей, алгоритма Пейнтера и Z-буферизации.

Внешняя ссылка