Алгоритм Варнака

Этот алгоритм работает в картинной плоскости. Сначала определяются все объекты, лежащие в окне. Если оказывается, что объектов в окне нет, то не рисуют ничего, если в окне один объект – рисуют только его, если же несколько – ищут ближайший из них, если такой есть – выводят, если нет – разбивают окно на четыре части и дальше работают с этими частями. Окно делят до тех пор, пока оно не станет равным пикселю, тогда просто выбирают один из наиболее близких объектов.

Такой алгоритм подходит как для каркасных, так и для сплошных изображений.

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

Это еще один пример метода грубой силы. Полигоны просто сортируются и выводятся в порядке от дальних к ближним. Таким образом, ближайшие к наблюдателю полигоны рисуются поверх дальних и получается правильная картина. Такой алгоритм подходит только для отображения сплошных поверхностей, не для каркасных. Сортировка полигонов тоже вещь нетривиальная. Если сортировать вдоль оси Z, то всегда может быть случай неправильной сортировки. Или вообще ее невозможности. Тем не менее, алгоритм достаточно прост и часто используется при небольшом количествах полигонов, одним из его достоинств является возможность обрабатывать полупрозрачные объекты. Предыдущие алгоритмы требуют значительной модификации для такой возможности. Полупрозрачный объект выводится по формуле С=С*t+Cг*(1-t), где С – текущий цвет пикселя, Cг – цвет пикселя прозрачной грани, t – коэффициент прозрачности [0..1]. Очевидно, что для формирования правильной картинки необходимо знать цвет предыдущего пикселя.

Использование бинарного разбиения пространства для сортировки полигонов

Если в наборе полигонов выбрать одну, то ее плоскость разбивает все пространство на две части. Предположим, что эта плоскость не пересекает остальные полигоны, значит, одна часть полигонов будет лежать с одной стороны от плоскости, а другая – с другой. Тогда, в зависимости, от того, с какой стороны от плоскости находится наблюдатель, можно однозначно определить порядок отрисовки этих групп полигонов. Сначала рисуются полигоны из полупространства, в котором нет наблюдателя, затем полигон с плоскости, и наконец – полигоны из полупространства, в котором находится наблюдатель ((B,C),A,(D,E,F)). Чтобы правильно отсортировать все полигоны – нужно построить дерево таких разбиений. Такое дерево и называется деревом двоичного разбиения пространства (BSP-tree binary space partitioning tree).

В качестве узлов такого дерева выступают плоскости (и полигоны лежащие на них), а в качестве листьев – области, ограниченные этими плоскостями. Для отрисовки дерева его просто обходят, определяя каждый раз положение наблюдателя относительно плоскостей узлов. (B,C,A,F,D,E).

Для общих случаев, в одной плоскости могут лежать несколько полигонов (порядок их вывода не имеет значения), плоскости могут пересекать полигоны, тогда такие полигоны режут на две части и каждую добавляют в свое полупространство. При построении дерева стараются, чтобы разница в количестве узлов слева и справа от текущего было минимальной и разрезанных полигонов было как можно меньше. Тогда оно будет сбалансированным, при этом глубина дерева будет минимальной, это обеспечивает минимум проверок плоскостей. Идеальное решение этой задачи требует слишком много времени, поэтому очередная разбивающая плоскость выбирается по максимуму весовой функции f=lie-a*|left-right|-b*cross, где lie – кол-во полигонов лежащих в плоскости, left,right - кол-во полигонов слева и справа от плоскости, cross - кол-во полигонов, которые пересекаются плоскостью, a,b – какие-то весовые коэффициенты.