Алгоритм Вейлера-Азертона

Включает в себя 4 шага:

1. предварительная сортировка по глубине по Zmax;

2. сортировка многоугольников на плоскости;

3. удаление экранированных многоугольников;

4. рекурсивное подразбиение и окончательная сортировка.

На основе предварительной сортировки находится наиболее приближенный к наблюдателю многоугольник, он выбирается в качестве отсекающего. Далее производится сортировка на плоскость: все многоугольники проецируются на плоскость и разрезаются на части по границе отсекающего. Фрагменты многоугольников, попавшие внутрь отсекающего, формируют внутренний список, остальные – внешний. Если ни одна вершина внутреннего списка не превышает Zmin отсекающего, то все элементы из внутреннего списка экранируются отсекающим – эти многоугольники удаляются, а отсекающий отображается, иначе многоугольник, нарушивший порядок, выбирается отсекающим и проводится повторная процедура формирования внутреннего списка. Если снова есть нарушение порядка, то получаем циклическое экранирование – нужно резать многоугольники и т.д.

Алгоритм трассировки лучей

Алгоритм может учитывать эффекты отражения, прозрачности, затенения, а так же использовать различные методы устранения ступенчатости. Предполагается, что наблюдатель находится на оси Z, картинная плоскость перпендикулярна оси. Фрагмент этой картины отображается в поле вывода, поэтому с каждым пикселем поля вывода можно сопоставить некоторый луч, который необходимо отразить. Наиболее важным алгоритмом является поиск пересечений лучей с объектами. Чтобы повысить эффективность сцены для объектов сцены вводятся объемлющие оболочки – либо сферические, либо прямоугольные. Очевидно, что если луч не пересекает оболочку, то пересечения с объектом нет, иначе – оно допустимо. Для дальнейшего получения эффективности можно ввести оболочки для группы объектов, т.к. они занимают не всю сцену, а находятся группой.

Сначала создается список объектов, содержащий следующую информацию: тип объекта, свойства поверхности, описание сферической оболочки, описание прямоугольной оболочки. Прямоугольной оболочки может не быть, поэтому заводится специальный флаг о ее наличии. Далее для каждого луча:

1. Выполнить тест на пересечение со сферической оболочкой в исходной системе координат.

2. Если луч пересекает сферу, занести объект в список активных объектов.

В противном случае перенести и повернуть луч так, чтобы он совпал с осью Z видовой системы.

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