Алгоритм художника
Алгоритм художника (также алгоритм сортировки по глубине и приоритетная заливка ) — это алгоритм определения видимой поверхности в трехмерной компьютерной графике , который работает на основе полигона за полигоном, а не попиксельно , построчно или по площади. базис площади других алгоритмов удаления скрытых поверхностей . [ 1 ] [ 2 ] [ 3 ] Алгоритм художника создает изображения, сортируя многоугольники внутри изображения по их глубине и размещая каждый многоугольник в порядке от самого дальнего до самого близкого объекта. [ 4 ] [ 5 ]
Алгоритм художника был первоначально предложен в качестве основного метода решения определения скрытой поверхности проблемы Мартином Ньюэллом , Ричардом Ньюэллом и Томом Санчей в 1972 году, когда все трое работали в CADCentre . [ 4 ] Название «алгоритм художника» относится к технике, используемой многими художниками, когда они начинают с рисования удаленных частей сцены, а затем частей, которые находятся ближе, тем самым покрывая некоторые области удаленных частей. [ 6 ] [ 7 ] Аналогичным образом алгоритм художника сортирует все полигоны сцены по глубине, а затем рисует их в таком порядке, от самого дальнего к ближайшему. [ 8 ] Он будет закрашивать части, которые обычно не видны — тем самым решая проблему видимости — за счет закрашивания невидимых областей удаленных объектов. [ 9 ] Порядок, используемый алгоритмом, называется « порядком глубины» и не обязательно должен учитывать числовые расстояния до частей сцены: главное свойство этого порядка заключается, скорее, в том, что если один объект закрывает часть другого, то первый объект рисуется после объекта, который он скрывает. [ 9 ] Таким образом, допустимое упорядочение можно описать как топологическое упорядочение ориентированного ациклического графа, представляющего перекрытия между объектами. [ 10 ]
Алгоритм
[ редактировать ]Концептуально алгоритм Художника работает следующим образом:
- Сортировка каждого многоугольника по глубине
- Разместите каждый многоугольник от самого дальнего многоугольника до ближайшего многоугольника.
Псевдокод
[ редактировать ]sort polygons by depth
for each polygon p:
for each pixel that p covers:
paint p.color on pixel
Временная сложность
[ редактировать ]Временная сложность алгоритма художника во многом зависит от алгоритма сортировки, используемого для упорядочивания полигонов. Предполагая использование наиболее оптимального алгоритма сортировки, алгоритм художника имеет сложность в худшем случае 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-буфера обычно полагаются на регистры буфера глубины фиксированной точности, реализованные аппаратно, существует вероятность проблем с видимостью из-за ошибки округления. Это перекрытия или пробелы в местах соединения полигонов. Чтобы избежать этого, некоторые графические движки реализуют «чрезмерный рендеринг». [ нужна ссылка ] рисование затронутых краев обоих многоугольников в порядке, заданном алгоритмом художника. Это означает, что некоторые пиксели на самом деле рисуются дважды (как в полном алгоритме рисования), но это происходит только на небольших частях изображения и оказывает незначительное влияние на производительность.
Ссылки
[ редактировать ]- Фоли, Джеймс ; Файнер, Стивен К.; Хьюз, Джон Ф. (1990). Компьютерная графика: принципы и практика . Ридинг, Массачусетс, США: Аддисон-Уэсли . п. 1174 . ISBN 0-201-12110-7 .
- ^ Аппель, Артур (1968). Моррел, AJH (ред.). «О расчете иллюзии реальности» (PDF) . Обработка информации, Труды Конгресса ИФИП, 1968 г., Эдинбург, Великобритания, 5–10 августа 1968 г., Том 2 - Аппаратное обеспечение, Приложения : 945–950. Архивировано (PDF) из оригинала 20 июля 2008 г.
- ^ Ромни, Гордон Уилсон (1 сентября 1969 г.). «Компьютерная сборка и визуализация твердых тел» . Архивировано из оригинала 2 ноября 2020 года.
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Гэри Скотт Уоткинс. 1970. «Алгоритм видимой поверхности в реальном времени. Кандидатская диссертация». Университет Юты. Номер заказа: AAI7023061.
- ^ Перейти обратно: а б с д и Ньюэлл, Мэн; Ньюэлл, Р.Г.; Санча, ТЛ (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 г.
- ^ Букнайт, В. Джек (1 сентября 1970 г.). «Процедура создания трехмерных полутоновых презентаций компьютерной графики» . Коммуникации АКМ . 13 (9): 527–536. дои : 10.1145/362736.362739 . ISSN 0001-0782 . S2CID 15941472 .
- ^ Берланд, Дина (1995). Техники, материалы и студийная практика исторической живописи (PDF) . Институт охраны природы Гетти.
- ^ Уайли, Крис; Ромни, Гордон; Эванс, Дэвид; Эрдал, Алан (14 ноября 1967). «Полутоновые перспективные рисунки на компьютере» . Материалы осенней совместной компьютерной конференции AFIPS '67 (осень) , состоявшейся 14–16 ноября 1967 г. Анахайм, Калифорния: Ассоциация вычислительной техники. стр. 49–58. дои : 10.1145/1465611.1465619 . ISBN 978-1-4503-7896-3 . S2CID 3282975 .
- ^ Перейти обратно: а б Десаи, Апурва (2008). Компьютерная графика . PHI Learning Pvt. ООО ISBN 9788120335240 .
- ^ Перейти обратно: а б с д и де Берг, Марк (2008). Вычислительная геометрия (PDF) . Спрингер. Архивировано (PDF) из оригинала 3 августа 2016 г.
- ^ де Берг, Марк (1993). Лучевая стрельба, порядок глубины и удаление скрытых поверхностей . Конспекты лекций по информатике. Том. 703. Спрингер. п. 130. ИСБН 9783540570202 . .
- ^ Уорнок, Джон Э. (1 июня 1969 г.). «Алгоритм скрытой поверхности для компьютерных полутоновых изображений» . Архивировано из оригинала 8 ноября 2020 года.
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Фрейзер, М.; Маркус, П. (июнь 1969 г.). «Обзор некоторых физических ограничений элементов компьютера» . Транзакции IEEE по магнетизму . 5 (2): 82–90. Бибкод : 1969ITM.....5...82F . дои : 10.1109/TMAG.1969.1066403 . ISSN 1941-0069 .
- ^ Нюберг, Дэниел (2011). Анализ двух распространенных алгоритмов удаления скрытых поверхностей: алгоритма художника и Z-буферизации .
