Алгоритм определения видимых поверхностей в 3D-графике
Painter's algorithm
Алгоритм художника: определение видимых поверхностей в 3D графике. Сортировка полигонов по глубине для реалистичного отображения сцен. История и принцип работы.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Алгоритм определения видимой поверхности в 3D-графике
Algorithm for visible surface determination in 3D graphics
Алгоритм живописца (также алгоритм сортировки по глубине и приоритетное заполнение) — это алгоритм определения видимой поверхности в 3D-компьютерной графике, который работает с многоугольниками по отдельности, а не с пикселями, строками или областями, как другие алгоритмы удаления скрытых поверхностей. Алгоритм живописца создает изображения, сортируя многоугольники в сцене по глубине и размещая каждый многоугольник в порядке от самых дальних до самых близких объектов. Впервые этот алгоритм был предложен Мартином Ньюэллом, Ричардом Ньюэллом и Томом Санчей в 1972 году как базовый метод решения проблемы определения видимой поверхности, когда все трое работали в CADCentre. Название "алгоритм живописца" отсылает к технике, используемой многими художниками, которые начинают с изображения дальних частей сцены, а затем переходят к более близким, перекрывая при этом некоторые области дальних объектов. Аналогично, алгоритм живописца сортирует все многоугольники в сцене по глубине и затем отрисовывает их в этом порядке, от самых дальних до самых близких. Он закрашивает части, которые обычно не видны, тем самым решая проблему видимости, но при этом закрашивает невидимые области дальних объектов. Порядок, используемый алгоритмом, называется "порядком глубины" и не обязан соответствовать числовым расстояниям до частей сцены: ключевым свойством этого порядка является то, что если один объект перекрывает часть другого, то первый объект отрисовывается после перекрываемого объекта.
The painter's algorithm (also depth sort algorithm and priority fill) is an algorithm for visible surface determination in 3D computer graphics that works on a polygon by polygon basis rather than a pixel by pixel, row by row, or area by area basis of other Hidden Surface Removal algorithms. The painter's algorithm creates images by sorting the polygons within the image by their depth and placing each polygon in order from the farthest to the closest object. The painter's algorithm was initially proposed as a basic method to address the Hidden surface determination problem by Martin Newell, Richard Newell, and Tom Sancha in 1972, while all three were working at CADCentre. The name "painter's algorithm" refers to the technique employed by many painters where they begin by painting distant parts of a scene before parts that are nearer, thereby covering some areas of distant parts. Similarly, the painter's algorithm sorts all the polygons in a scene by their depth and then paints them in this order, farthest to closest. It will paint over the parts that are normally not visible — thus solving the visibility problem — at the cost of having painted invisible areas of distant objects. The ordering used by the algorithm is called a 'depth order' and does not have to respect the numerical distances to the parts of the scene: the essential property of this ordering is, rather, that if one object obscures part of another, then the first object is painted after the object that it obscures.
Временная сложность
Временная сложность алгоритма живописца сильно зависит от алгоритма сортировки, используемого для упорядочивания многоугольников. При условии использования наиболее оптимального алгоритма сортировки, алгоритм живописца имеет наихудшую сложность O(n log n + m*n), где n — количество многоугольников, а m — количество пикселей для заполнения.
The painter's algorithm's time complexity is heavily dependent on the sorting algorithm used to order the polygons. Assuming the use of the most optimal sorting algorithm, painter's algorithm has a worst case complexity of O(n log n + m*n), where n is the number of polygons and m is the number of pixels to be filled.
Сложность пространства
Наихудшая пространственная сложность алгоритма художника — O(n+m), где n — количество многоугольников, а m — количество пикселей для заливки.
The painter's algorithm's worst case space complexity is O(n+m), where n is the number of polygons and m is the number of pixels to be filled.
Преимущества
Существует два основных технических условия, благоприятствующих использованию алгоритма художника.
There are two primary technical requisites that favor the use of the painter's algorithm.
Основная графическая структура
Алгоритм художника не так сложен по структуре, как другие алгоритмы глубинной сортировки. Такие компоненты, как порядок рендеринга, основанный на глубине, используемый в алгоритме художника, являются одним из самых простых способов определения последовательности графического вывода. Это требовало от программ максимально эффективного управления памятью для выполнения масштабных задач без сбоев. Алгоритм художника отдает приоритет эффективному использованию памяти, но ценой большей вычислительной нагрузки, поскольку необходимо отрисовать все части всех изображений. Даже в таких системах иногда применяется вариант алгоритма художника. Поскольку реализации Z-буфера обычно полагаются на аппаратные регистры буфера глубины с фиксированной точностью, существует вероятность возникновения проблем с видимостью из-за ошибок округления. Это проявляется в виде наложений или зазоров на стыках полигонов. Чтобы избежать этого, некоторые графические движки реализуют "дополнительную отрисовку", прорисовывая затронутые края обоих полигонов в порядке, определяемом алгоритмом художника. Это означает, что некоторые пиксели фактически отрисовываются дважды (как и в полном алгоритме художника), но это происходит лишь на небольших участках изображения и оказывает пренебрежимо малое влияние на производительность.
The painter's algorithm is not as complex in structure as its other depth sorting algorithm counterparts. Components such as the depth based rendering order, as employed by the painter's algorithm, are one of the simplest ways to designate the order of graphical production. This required programs to manage memory as efficiently as possible to conduct large tasks without crashing. The painter's algorithm prioritizes the efficient use of memory but at the expense of higher processing power since all parts of all images must be rendered. Even in such systems, a variant of the painter's algorithm is sometimes employed. As Z buffer implementations generally rely on fixed precision depth buffer registers implemented in hardware, there is scope for visibility problems due to rounding error. These are overlaps or gaps at joints between polygons. To avoid this, some graphics engines implement "over rendering", drawing the affected edges of both polygons in the order given by the painter's algorithm. This means that some pixels are actually drawn twice (as in the full painter's algorithm), but this happens on only small parts of the image and has a negligible performance effect.