Компьютерная геометрия и графика. Лекция 9

План занятия: Алгоритм построчного сканирования. Основная идея метода. Алгоритм построчного сканирования с использованием Z-буфера Интервальный алгоритм построчного сканирования.

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

экран Секущая плоскость

Теперь вместо определения того, какие части граней закрывают друг друга при проектировании на плоскость, необходимо определить какие части отрезков закрывают друг друга при проектировании на прямую. Задача значительно упрощается.

Существует много методов для решения задачи удаления невидимых частей отрезков. Мы рассмотрим только некоторые из них: 1. Построчное сканирование с использованием Z-буфера. 2. Интервальный метод построчного сканирования.

Алгоритм построчного сканирования с использованием Z-буфера.

Создаем одномерный Z-буфер - массив с количеством элементов равным длине строки. В отличии от двумерного Z-буфера, который помещал в себя целые прямоугольные области экрана, одномерный Z-буфер в этой задаче совмещает в себе крайнюю простоту с весьма небольшими затратами памяти даже при высоком расширении картинной плоскости. Никаких проблем с переполнением памяти больше нет!

Отрезки в строке рассматриваем в любом порядке. Просматриваем каждую точку каждого отрезка, для этого можно использовать модифицированный алгоритм Брезенхема: то есть мы не рисуем точки благодаря нему, а только ищем, и к каждой найденной мы задаем вопрос об удаленности от нас. If (ZZ<ZB[XX]) {putpixel (XX,YY,1);ZB[XX]=ZZ}

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

Например, после сортировки по вертикали мы получили некоторый результат. Упорядочили все объекты. Теперь при работе с Z-буфером будет гораздо меньше проверок. Например, если мы сканируем строку А, то мы будем проверять плоскость на пересечение только с объектом 1. В строке N вообще никаких проверок делать не нужно N A

Результат сечения этих объектов плоскостью, проходящей через строку А выглядит так: N A

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

Чем хорош именно этот алгоритм построчного сканирования и чем плохи другие? В других алгоритмах обязательно: - либо пробегать по всем Х и смотреть точки соответствующие им на отрезках. - либо пробегать по всем точкам отрезка, что еще сложнее, так как отрезков очень много. ?

В этом алгоритме мы не используем ни тот, ни другой метод. Рассмотрим два случая: 1. Многогранники не пересекаются 2. Многогранники на картинной плоскости пересекаются.

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

Многогранники пересекаются: разбиваем весь экран на интервалы, но они теперь формируются не только из граничных точек, но и из точек пересечения отрезков. Все остальные рассуждения сохраняются.

Чтобы алгоритм работал быстрее, есть смысл упорядочить отрезки по удаленности от левого края экрана. То есть на каждом интервале мы будем знать, какие отрезки уже начались, а какие еще не закончились

Находить пересечение отрезков легко и это довольно быстрая процедура. Проблема возникает только тогда, когда этих пересечений очень много. Быстрота работы алгоритма очень резко снижается. Что нужно сделать, чтобы быстро решить проблему с поиском пересечений? ?

Можно находить не все точки пересечения! В начале в качестве интервалов берем только (!) концы отрезков. Двигаемся по тому отрезку, который сейчас видим. -Если следующая точка, означающая конец интервала, принадлежит этому же отрезку, и из этой точки ближайший к нам отрезок тот же самый, то рисуем этот отрезок на экран (или ту его часть, которая находится в текущем интервале). -Если следующая точка принадлежит другому отрезку, то рассматриваем полуинтервалы - ищем пересечение этих отрезков.

Алгоритм: Находим концы отрезка Xi, получаем интервалы (n штук) Находим j: j =R(Xo) Procedure L возвращает для Хi какой отрезок (исключая левые границы) самый ближайший. Procedure R возвращает для Хi какой отрезок (исключая правые границы) самый ближайший.

Цикл, который перебирает отрезки от 1 до n if (j=K) then {line( X i-1, X i ); X i =X i+1 ;} if (j<>K) then {repeat X=Т. Пер.; K=L(X); until j=k} line (X i-1,X); X i =X; K=L(Xi);

КОНЕЦ.