Войти
Воспроизвести медиа Фрактал пейзаж, формируемый с использованием алгоритма живописца на Commodore Amiga В алгоритме художника (также алгоритм глубины сортировки и приоритет заполнение) представляет собой алгоритм для видимого определения поверхности в 3D компьютерной графике, которая работает на многоугольник по-многоугольник основе, а не пиксель за пикселем, строка за строкой, или областью, основа других алгоритмов удаления скрытых поверхностей. Алгоритм художника создает изображения, сортируя многоугольники в изображении по их глубине и размещая каждый многоугольник в порядке от самого дальнего до ближайшего объекта.
Алгоритм художника первоначально был предложен в качестве основного метода для решения проблемы определения невидимых поверхности проблемы, Мартин Ньюэлл, Ричард Ньюэлл, и Том Санчем в 1972 году, в то время как все три работал в CADCentre. Название «алгоритм художника» относится к технике, используемой многими художниками, когда они начинают с рисования отдаленных частей сцены перед частями, которые находятся ближе, тем самым покрывая некоторые области удаленных частей. Аналогичным образом алгоритм рисовальщика сортирует все полигоны в сцене по их глубине, а затем раскрашивает их в этом порядке, от самого дальнего к ближайшему. Он закрашивает части, которые обычно не видны, - таким образом решая проблему видимости - за счет закрашивания невидимых областей удаленных объектов. Упорядочение, используемое алгоритмом, называется « порядком глубины» и не должно учитывать числовые расстояния до частей сцены: существенным свойством этого порядка является, скорее, то, что если один объект скрывает часть другого, то первый объект рисуется после объекта, который он закрывает. Таким образом, действительное упорядочение может быть описано как топологическое упорядочение в виде направленного ациклического графа, представляющих окклюзии между объектами.
Сначала нарисованы далекие горы, а затем луга ближе; наконец, деревья раскрашены. Хотя некоторые деревья находятся дальше от точки обзора, чем некоторые части лугов, порядок (горы, луга, деревья) формирует допустимый порядок глубины, потому что ни один объект в этом порядке не закрывает какую-либо часть более позднего объекта. Концептуально алгоритм Painter's работает следующим образом:
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 - количество пикселей, которые нужно заполнить.
Есть два основных технических требования, которые способствуют использованию алгоритма художника.
Алгоритм рисовальщика не такой сложный по структуре, как его другие аналоги алгоритма сортировки по глубине. Такие компоненты, как порядок рендеринга на основе глубины, используемый алгоритмом художника, являются одним из самых простых способов обозначить порядок графического производства. Эта простота делает его полезным в базовых сценариях вывода компьютерной графики, где простой рендеринг должен выполняться без особых усилий.
В начале 70-х, когда был разработан алгоритм художника, физическая память была относительно небольшой. Это требовало от программ максимально эффективного управления памятью для выполнения больших задач без сбоев. Алгоритм художника отдает приоритет эффективному использованию памяти, но за счет более высокой вычислительной мощности, поскольку должны быть отрисованы все части всех изображений.
Перекрывающиеся полигоны могут привести к сбою алгоритма В некоторых случаях алгоритм может давать сбой, в том числе циклическое перекрытие или пересечение полигонов.
В случае циклического перекрытия, как показано на рисунке справа, многоугольники A, B и C перекрывают друг друга таким образом, что невозможно определить, какой многоугольник находится над другими. В этом случае проблемные полигоны должны быть обрезаны для сортировки.
Случай пробивки многоугольников возникает, когда один многоугольник пересекает другой. Подобно циклическому перекрытию, эта проблема может быть решена путем вырезания проблемных полигонов.
В базовых реализациях алгоритм рисовальщика может быть неэффективным. Он заставляет систему визуализировать каждую точку на каждом многоугольнике в видимом наборе, даже если этот многоугольник закрыт в готовой сцене. Это означает, что для детализированных сцен алгоритм художника может слишком сильно нагружать компьютерное оборудование.
Алгоритм Ньюэлла, предложенный как расширенный алгоритм для алгоритма рисования, обеспечивает метод разрезания циклических и пронизывающих многоугольников.
Другой вариант алгоритма рисования включает алгоритм обратного рисования. Алгоритм обратного рисования сначала рисует ближайшие к зрителю объекты - с правилом, согласно которому краска никогда не должна применяться к уже окрашенным частям изображения (если только они не являются частично прозрачными). В компьютерной графической системе это может быть очень эффективным, поскольку нет необходимости вычислять цвета (с использованием освещения, текстурирования и т. Д.) Для частей удаленной сцены, которые скрыты близлежащими объектами. Однако обратный алгоритм страдает многими из тех же проблем, что и стандартная версия.
Недостатки алгоритма рисовальщика привели к разработке методов Z-буфера, которые можно рассматривать как развитие алгоритма рисовальщика, разрешая конфликты глубины на попиксельной основе, уменьшая необходимость в порядке рендеринга на основе глубины. Даже в таких системах иногда используется вариант алгоритма художника. Поскольку реализации Z-буфера обычно полагаются на регистры буфера глубины фиксированной точности, реализованные на оборудовании, существует область для проблем с видимостью из-за ошибки округления. Это перекрытия или зазоры на стыках полигонов. Чтобы избежать этого, некоторые реализации графического движка «перерисовывают», отрисовывая затронутые края обоих полигонов в порядке, заданном алгоритмом рисовальщика. Это означает, что некоторые пиксели на самом деле отрисовываются дважды (как в полном алгоритме рисовальщика), но это происходит только на небольших частях изображения и имеет незначительный эффект производительности.
|journal=( помощь )|journal=( помощь )