Алгоритм художника
Не путать со Схлемиилом алгоритм художника .
Алгоритм художника, Также известный как приоритетная заливка , является одним из самых простых решений проблемы видимости в 3D-компьютерной графике . При проецировании 3D-сцены на 2D-плоскость необходимо в какой-то момент решить, какие полигоны видны, а какие скрыты .
Проекция[править]
Название "алгоритм художника" относится к технике, используемой многими художниками для рисования удаленных частей сцены до частей, которые находятся ближе, тем самым охватывая некоторые области удаленных частей. Алгоритм художника сортирует все полигоны в сцене по их глубине, а затем рисует их в таком порядке, от самого дальнего до самого близкого. Он будет закрашивать части, которые обычно не видны — таким образом, решая проблему видимости — за счет окрашивания невидимых областей удаленных объектов. Порядок, используемый алгоритмом, называется порядком глубины, и не нужно учитывать числовые расстояния до частей сцены: существенным свойством этого порядка является, скорее, то, что если один объект заслоняет часть другого, то первый объект окрашивается после объекта, который он затемняет. Таким образом, допустимое упорядочение можно описать как топологическое упорядочение направленного ациклического графа, представляющего собой окклюзии между объектами.
В некоторых случаях алгоритм может завершиться ошибкой, включая циклическое перекрытие или прокалывание полигонов. В случае циклического перекрытия, как показано на рисунке справа, полигоны A, B и C перекрывают друг друга таким образом, что невозможно определить, какой полигон находится выше других. В этом случае нарушающие полигоны должны быть вырезаны, чтобы разрешить сортировку. Алгоритм Ньюэлла, предложенный в 1972 году, предоставляет метод для вырезания таких полигонов. Многочисленные методы были также предложены в области вычислительной геометрии.
Случай прокалывания полигонов возникает, когда один полигон пересекает другой. Как и в случае циклического перекрытия, эта проблема может быть решена путем вырезания нарушающих полигонов.
Критика[править]
В основных реализациях алгоритм художника может быть неэффективным. Это заставляет систему отображать каждую точку на каждом полигоне в видимом наборе, даже если этот полигон закрыт в готовой сцене. Это означает, что для детальных сцен алгоритм художника может чрезмерно нагружать компьютерное оборудование.
Иногда используется алгоритм обратного рисования, в котором объекты, ближайшие к зрителю, окрашиваются первыми — с правилом, что краска никогда не должна применяться к частям изображения, которые уже окрашены (если они не являются частично прозрачными). В компьютерной графической системе это может быть очень эффективно, так как нет необходимости вычислять цвета (используя освещение, текстурирование и т. д.) Для частей гораздо удаленной сцены, которые скрыты соседними объектами. Однако обратный алгоритм страдает от многих из тех же проблем, что и стандартная версия.
Эти и другие недостатки алгоритма привели к разработке Z-буфера методы, которые можно рассматривать как развитие алгоритма художника, путем разрешения конфликтов глубины на основе пикселя за пикселем, уменьшая необходимость в порядке рендеринга на основе глубины. Даже в таких системах иногда используется вариант алгоритма художника. Поскольку реализации Z-буфера обычно полагаются на регистры глубинного буфера фиксированной точности, реализованные в аппаратных средствах, существует область для проблем видимости из-за ошибки округления. Это перекрытия или зазоры в местах стыковки полигонов. Чтобы избежать этого, некоторые реализации графического движка "overrender" [требуется цитирование], рисование затронутых ребер обоих полигонов в порядке, заданном алгоритмом painter. Это означает, что некоторые пиксели фактически рисуются дважды (как и в полном алгоритме художника), но это происходит только на небольших частях изображения и имеет незначительный эффект производительности.