Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
В большинстве приложений используется одно из существенных достоинств растровых устройств - возможность заполнения областей экрана.
Существует две разновидности заполнения:
·первая, связанная как с интерактивной работой, так и с программным синтезом изображения, служит для заполнения внутренней части многоугольника, заданного координатами его вершин.
·вторая, связанная в первую очередь с интерактивной работой, служит для заливки области, которая либо очерчена границей с кодом пиксела, отличающимся от кодов любых пикселов внутри области, либо закрашена пикселами с заданным кодом;
Простейший способ заполнения многоугольника, заданного координатами вершин, заключается в определении принадлежит ли текущий пиксел внутренней части многоугольника. Если принадлежит, то пиксел заносится.
Определить принадлежность пиксела многоугольнику можно, например, подсчетом суммарного угла с вершиной на пикселе при обходе контура многоугольника. Если пиксел внутри, то угол будет равен 360°, если вне - 0°(рис.).
Вычисление принадлежности должно производиться для всех пикселов экрана и так как большинство пикселов скорее всего вне многоугольников, то данный способ слишком расточителен. Объем лишних вычислений в некоторых случаях можно сократить использованием прямоугольной оболочки - минимального прямоугольника, объемлющего интересующий объект, но все равно вычислений будет много. Другой метод определения принадлежности точки внутренней части многоугольника будет рассмотрен ниже при изучении отсечения отрезков по алгоритму Кируса-Бека.
Построчное заполнение
Реально используются алгоритмы построчного заполнения, основанные на том, что соседние пикселы в строке скорее всего одинаковы и меняются только там где строка пересекается с ребром многоугольника. Это называется когерентностью растровых строк (строки сканирования Yi, Yi+1, Yi+2на рис.). При этом достаточно определить X-координаты пересечений строк сканирования с ребрами. Пары отсортированных точек пересечения задают интервалы заливки.
Рис. 0.4.2:Построчная закраска многоугольника
Кроме того, если какие-либо ребра пересекались i-й строкой, то они скорее всего будут пересекаться также и строкой i+1. (строки сканирования Yiи Yi+1на рис.0.2). Это называется когерентностью ребер. При переходе к новой строке легко вычислить новую X-координату точки пересечения ребра, используя X-координату старой точки пересечения и тангенс угла наклона ребра:
(тангенс угла наклона ребра - k = dy/dx, так как dy = 1, то 1/k = dx).
Смена же количества интервалов заливки происходит только тогда, когда в строке сканирования появляется вершина.
Учет когерентности строк и ребер позволяет построить для заполнения многоугольников различные высокоэффективные алгоритмы построчного сканирования. Для каждой строки сканирования рассматриваются только те ребра, которые пересекают строку. Они задаются списком активных ребер (САР). При переходе к следующей строке для пересекаемых ребер перевычисляются X-координаты пересечений. При появлении в строке сканирования вершин производится перестройка САР. Ребра, которые перестали пересекаться, удаляются из САР, а все новые ребра, пересекаемые строкой заносятся в него.
Общая схема алгоритма, динамически формирующего список активных ребер и заполняющего многоугольник снизу-вверх, следующая:
Подготовить служебные целочисленные массивы Y-координат вершин и номеров вершин.
Совместно отсортировать Y-координаты по возрастанию и массив номеров вершин для того, чтобы можно было определить исходный номер вершины.
Определить пределы заполнения по оси Y - Y_мin и Y_max. Стартуя с текущим значением Y_tek = Y_min, исполнять пункты 4-9 до завершения раскраски.
Определить число вершин, расположенных на строке Y_tek - текущей строке сканирования.
Если вершины есть, то для каждой из вершин дополнить список активных ребер, используя информацию о соседних вершинах.
Для каждого ребра в список активных ребер заносятся:
максимальное значение Y-координаты ребра,
приращение X-координаты при увеличении Y на 1,
начальное значение X-координаты.
Если обнаруживаются горизонтальные ребра, то они просто закрашиваются и информация о них в список активных ребер не заносится.
Если после этого обнаруживается, что список активных ребер пуст, то заполнение закончено.
По списку активных ребер определяется Y_след - Y-координата ближайшей вершины. (Вплоть до Y_след можно не заботиться о модификации САР а только менять X-координаты пересечений строки сканирования с активными ребрами).
В цикле от Y_tek до Y_след:
выбрать из списка активных ребер и отсортировать X-координаты пересечений активных ребер со строкой сканирования;
определить интервалы и выполнить закраску;
перевычислить координаты пересечений для следующей строки сканирования.
Проверить не достигли ли максимальной Y-координаты. Если достигли, то заливка закончена, иначе выполнить пункт.
Очистить список активных ребер от ребер, закончившихся на строке Y_след и перейти к пункту 4.
Дата публикования: 2015-06-12; Прочитано: 339 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!