Построчный алгоритм с Z-буфером
Алгоритм удаления поверхностей с Z-буфером
Алгоритмы удаления линий
Классификация методов удаления невидимых частей
Удаление скрытых линий и поверхностей
Применение - векторные устройства. Могут применяться и в растровых для ускорения процесса визуализации, но при этом не используется основное ценное качество растрового дисплея - возможность закраски поверхностей.
Наиболее известный ранний алгоритм - алгоритм Робертса (1963 г.). Работает с только выпуклыми телами в пространстве объектов. Каждый объект сцены представляется многогранным телом, полученным в результате пересечения плоскостей. Т.е. тело описывается списком граней, состоящих из ребер, которые в свою очередь образованы вершинами.
Вначале из описания каждого тела удаляются не лицевые плоскости, экранированные самим телом. Затем каждое из ребер сравнивается с каждым телом для определения видимости или невидимости. Т.е. объем вычислений растет как квадрат числа объектов в сцене. Наконец вычисляются новые ребра, полученные при протыкании телами друг друга.
Алгоритм предложен Эдом Кэтмулом и представляет собой обобщение буфера кадра. Обычный буфер кадра хранит коды цвета для каждого пикселя в пространстве изображения. Идея алгоритма состоит в том, чтобы для каждого пикселя дополнительно хранить еще и координату Z или глубину. При занесении очередного пикселя в буфер кадра значение его Z-координаты сравнивается с Z-координатой пикселя, который уже находится в буфере. Если Z-координата нового пикселя больше, чем координата старого, т.е. он ближе к наблюдателю, то атрибуты нового пикселя и его Z-координата заносятся в буфер, если нет, то ни чего не делается.
Общая схема алгоритма с Z-буфером:
· Инициализировать кадровый и Z-буфера. Кадровый буфер закрашивается фоном. Z-буфер закрашивается минимальным значением Z.
· Выполнить преобразование каждого многоугольника сцены в растровую форму. При этом для каждого пиксела вычисляется его глубина z. Если вычисленная глубина больше, чем глубина, уже имеющаяся в Z-буфере, то занести в буфера атрибуты пиксела и его глубину, иначе никаких занесений не выполнять.
· Выполнить, если это было предусмотрено, усреднение изображения с понижением разрешения.
Рассмотрим теперь алгоритм с Z-буфером размером в одну строку, который представляет собой обобщение алгоритма построчной заливки многоугольника, представленный в процедурах V_FP0 и V_FP1 в приложениях. Модификация должна учесть то, что для каждой строки сканирования теперь может обрабатываться не один многоугольник.
Общая схема такого алгоритма следующая:
· Подготовка данных.
Для каждого многоугольника определить максимальную Y-координату.
Занести многоугольник в группу многоугольников, соответствующую данной Y-координате.
· Собственно заливка.