Алгоритм художника

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Алгоритм художника — простейший программный вариант решения «проблемы видимости» в трехмерной компьютерной графике.

Название «алгоритм художника» относится к технике, используемой многими живописцами: сначала рисуются наиболее удалённые части сцены, потом части которые ближе. Постепенно ближние части начинают перекрывать отдаленные части более удалённых объектов. Задача программиста при реализации алгоритма художника — отсортировать все полигоны по удалённости от наблюдателя и начать выводить, начиная с более дальних.

Наиболее удалённые горы рисуются в первую очередь. Затем рисуется луг, а потом деревья. Можно заметить, что некоторые части луга ближе, чем некоторые деревья. Однако правильный порядок сортировки (горы -> луг -> деревья) позволяет получить корректную картину, без перекрытия деревьев частями луга
Наиболее удалённые горы рисуются в первую очередь. Затем рисуется луг, а потом деревья. Можно заметить, что некоторые части луга ближе, чем некоторые деревья. Однако правильный порядок сортировки (горы -> луг -> деревья) позволяет получить корректную картину, без перекрытия деревьев частями луга

Проблемы алгоритма[править | править код]

Взаимноперекрывающиеся полигоны при любой сортировке будут выведены неверно

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

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

Эти недостатки привели к разработке метода Z-буфера, который можно рассматривать как развитие алгоритма художника.

См. также[править | править код]

Примечания[править | править код]

  1. Newell's algorithm.