Интервальный алгоритм построчного сканирования | MetodPro.ru

Реклама на сайте

Интервальный алгоритм построчного сканирования


В алгоритме построчного сканирования с использованием z-буфера глубина многоугольника вычисляется для каждого пиксела на сканирующей строке. Количество вычислений глубины можно уменьшить, если использовать понятие интервалов, впервые введенных в алгоритме Ваткинса. На рис. 1, а показано пересечение многоугольников со сканирующей плоскостью. Решение задачи удаления невидимых поверхностей сводится к выбору видимых отрезков в каждом из интервалов, полученных путем деления сканирующей строки проекциями точек пересечения ребер. Из рисунка видно, что возможны только три варианта:

 

Рис. 1. Интервалы для построчного сканирования.

Интервал пуст, как, например, интервал 1 на рис. 1.а. - изображается фон.

Интервал содержит лишь один отрезок, как, например, интервалы 2 и 4 на рис. 1.а. - изображаются атрибуты многоугольника, соответствующего отрезку.

Интервал содержит несколько отрезков, как, например, интервал 3 на рис. 1.а. В этом случае вычисляется глубина каждого отрезка в интервале. Видимым будет отрезок с максимальным значением г. В этом интервале будут изображаться атрибуты видимого отрезка.

Если многоугольники не могут протыкать друг друга, то достаточно вычислять глубину каждого отрезка в интервале на одном из его концов. Если два отрезка касаются, но не проникают в концы интервала, то вычисление глубины производится в середине интервала, как показано на рис. 1.b. Для интервала 3 вычисление глубины, проведенное на его левом конце, не позволяет принять определенное решение. Реализация вычисления глубины в центре интервала дает уже корректный результат, как показано на рис. 1.b.

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

Используя более сложные меептоды порождения интервалов, можно сократить их число, а следовательно, и вычислительную трудоемкость



Методические пособия

  • Системы автоматизированного проектирования
  • Социология молодёжи
  • Общая социология
  • Криптография
  • Проектирование трансляторов
  • Компьютерная графика
  • Моделирование систем
  • Информационная безопасность
  • Теория вычислительных процессов
  • Логические основы искусственного интелекта
  • Проектирование распределённых информационных систем