9.Удаления невидимых линий и поверхностей. Алгоритм, использующий z-буфер.

Главное преимущество алгоритма – его простота. Алгоритм решает задачу об удалении невидимых поверхностей и делая тривиальной задачу пересечения сложных поверхностей. Сцены могут быть любой сложности, поскольку габариты пространства изображения фиксированы. Оценка вычислительной трудоемкости алгоритма линейна. Тк элементы сцены можно заносить в буфер Кадра в произвольном порядке, их ненужно сортировать по глубине. Основной недостаток алгоритма – большой объем требуемой памяти. Информацию о глубине можно обрабатывать с большой точностью, чем координатную информацию на плоскости. Обычно бывает достаточно 20 бит. Буфер кадра размером 512*512*24, комбинации z-буфера размером 512*512*20. Требует приблизительно 1,5 Мбайта памяти. Уменьшение требуемой памяти достигается разбиением пространства на 4, 16 или более квадратов или полос. Поскольку каждый элемент сцены обрабатывается несколько раз, то сегментирование z-буфера, приводит к увеличения времени, необходимого для обработки сцены. В таком случае сортировка на плоскости, позволяющая не обрабатывать все многоугольники в каждом из квадратов или полос, может значительно сократить этот рост. Следующий недостаток z-буфера состоит в трудоемкости и высокой стоимости устранении лестничного эффекта, а так же реализации эффектов прозрачности и просвечивания. Поскольку алгоритм заносит пиксели в алгоритм Карда в произвольном порядке, то сложно получить информацию необходимую, для устранения лестничного эффекта, основанную на предварительной фильтрации. При реализации эффекта прозрачности пиксели могут заносится в буфер кадра в некорректном порядке, что ведет к локальным ошибкам. Общая схема алгоритма:

Шаг 1: заполнить буфер кадра фоновым изображением.

Шаг 2: заполнить z-буфер, минимальным значением z.

Шаг 3: преобразовать каждый полигон в растровую форму в произвольном порядке.

Шаг 4: для каждого пикселя (х, у) вычислить внутри полигона его глубину (z, х, у).

Шаг 5: сравнить глубину (z, х, у) со значением z-буфера, хранящемся в z-буфере в той же позиции. Если z(х,у) больше чем Zб(х,у), то записать атрибуты этого многоугольника в буфер кадра и заменить значение Zб(х,у) на z(х,у).

Шаг 6: в противном случае ничего не делать.

Дополнительно: в качестве предварительного шага, где это целесообразно, применяется удаление не лицевых граней.

10.Удаления невидимых линий и поверхностей. Алгоритм Вейлера-Азертона.

Данный алгоритм работает в пространстве объекта, выходными данными служат многоугольники, алгоритм можно легко использовать для удаления невидимых линий и поверхностей. Для удаления невидимых поверхностей алгоритм состоит из 4-х шагов.

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

Шаг 2: отсечение на границе ближайших наблюдателей многоугольника, называемая сортировкой многоугольников на плоскости.

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

Шаг 4: если требуется, то используется рекурсивное разбиение и окончательная сортировка для устранения всех неопределенностей. Предварительная сортировка по глубине нужна для формирования приблизительных приоритетов. В процессе работы алгоритма, если происходит разбиение многоугольников на части, то эти приоритеты уточняются. С помощью данного алгоритма, все многоугольники отсекаются по границам отсекающего многоугольника, т.е. фактически производится двумерная операция отсечения проекций. Используются два списка: внутренний и внешний. Часть отсекаемого многоугольника, находящаяся внутри отсекающего, заносится во внутренний список. Оставшаяся часть, если имеется, заносится во внешний список.