Инкрементный алгоритм построчного закрашивания многоугольников. 0. 1Алгоритм построчного заполнения многоугольника
 Скачать 89.76 Kb.
|
|
0.1. Алгоритм построчного заполнения многоугольника. 1 0.1 Алгоритм построчного заполнения многоугольника. Контур многоугольника определяется вершинами, которые соединены отрезками прямых, без самопересечений. Это— векторная форма задания фигуры. Рассмотрим один из наиболее популярных алгоритмов заполнения многоугольника. Его основная идея — закрашивание фигуры отрезками прямых линий. Обычно используют горизонтали. Алгоритм представляет собою цикл вдоль оси y, в ходе этого цикла выполняется поиск точек сечения линии контура с соответствующей горизонталью (сканирующей строкой). Этот алгоритм получил название XY–алгоритма. В этом алгоритме используется свойство топологии контура фигуры. Оно состоит в том, что любая прямая линия пересекает любой замкнутый контур четное количество раз. Пары отсортированных точек пересечения задают интервалы заливки. Кроме того, если какие-либо ребра пересекались i-й строкой, то они скорее всего будут пересекаться также и i + 1–ой строкой. Это свойство называется когерентностью ребер. При переходе к новой (i + 1–ой) строке легко вычислить новую x-координату точки пересечения ребра, используя x-координату старой точки пересечения (с i–ой строкой) и тангенс угла наклона ребра: X i+1 = X i + ∆x ∆y В алгоритме для каждой строки сканирования рассматриваются только те ребра, которые пересекают стро- ку. Они задаются списком активных ребер (AET — Active Edge Table). При переходе к следующей строке для пересекаемых ребер перевычисляются x-координаты пересечений. При появлении в строке сканирования вер- шин производится перестройка AET. Ребра, которые перестали пересекаться, удаляются из AET, а все новые ребра, пересекаемые строкой заносятся в него. А ЛГОРИТМ 1 (А ЛГОРИТМ ПОСТРОЧНОГО ЗАПОЛНЕНИЯ МНОГОУГОЛЬНИКА ). Вход: Множество ребер многоугольника без самопересечений. Выход: Закрашенный многоугольник. 1. Будем предполагать, что начальной точкой любого ребра многоугольника является точка с меньшей y– координатой. Отсортировать ребра многоугольника по возрастанию y–координаты начальной точки 2. Определить пределы заполнения по оси y — Y min и Y max . Стартуя с текущим значением Y current = Y min , исполнять пункты 3–8 до завершения раскраски. 3. Определить число вершин, расположенных на строке Y current — текущей строке сканирования. 4. Если вершины есть, то для каждой из вершин дополнить список активных ребер, используя информацию о соседних вершинах. Для каждого ребра, у которого начальная точка лежит на строке сканирования, занести в список активных ребер: • максимальное значение y–координаты ребра (y–координату конечной точки ребра), • приращение x–координаты — ∂x при увеличении y на 1, • начальное значение x–координаты (x–координату начальной точки ребра). 2 Если обнаруживаются горизонтальные ребра, то они просто закрашиваются и информация о них в список активных ребер не заносится. Если после этого обнаруживается, что список активных ребер пуст, то заполнение закончено. 5. По списку активных ребер и списку ребер, не заносившихся в AET определяется Y next — y–координата ближайшей вершины. (Вплоть до Y next можно не заботиться о модификации AET а только менять x– координаты пересечений строки сканирования с активными ребрами). 6. В цикле от Y current до Y next : • выбрать из списка активных ребер и отсортировать x–координаты пересечений активных ребер со строкой сканирования; • определить интервалы и выполнить закраску; • перевычислить координаты пересечений для следующей строки сканирования. 7. Проверить не достигли ли максимальной y–координаты. Если достигли, то заливка закончена, иначе выполнить пункт 8. 8. Очистить список активных ребер от ребер, закончившихся на строке Y next и перейти к пункту 3. 0.2 Алгоритм удаления поверхностей с Z–буфером Алгоритм предложен Эдом Кэтмулом и представляет собой обобщение буфера кадра. Обычный буфер кадра хранит коды цвета для каждого пиксела в пространстве изображения. Идея алгоритма состоит в том, чтобы для каждого пиксела дополнительно хранить еще и координату z (глубину). При занесении очередного пиксела в буфер кадра значение его z–координаты сравнивается с z–координатой пиксела, который уже находится в буфере. Если z–координата нового пиксела больше, чем координата старого, т.е. он ближе к наблюдателю, то атрибуты нового пиксела и его z–координата заносятся в буфер, если нет, то ни чего не делается. Этот алгоритм наиболее простой из всех алгоритмов удаления невидимых поверхностей, но требует боль- шого объема памяти. Данные о глубине для реалистичности изображения обычно достаточно иметь с раз- рядностью порядка 20 бит. В этом случае при изображении нормального телевизионного размера в 768 × 576 пикселов для хранения z–координат необходим объем памяти порядка 1 Мбайта. Суммарный объем памяти при 3 байтах для значений RGB составит более 2.3 Мбайта. Время работы алгоритма не зависит от сложности сцены. Многоугольники, составляющие сцену, могут обрабатываться в произвольном порядке. Алгоритм работает в экранной системе координат. Это означает, что если точки разных граней проектиру- ются в одну и ту же точку на экране (а значит координаты x и y этих точек совпадают, а координаты z могут быть различными), то изображается только та из них, которая имеет наименьшую координату z. Рассмотрим алгоритм с Z-буфером в виде модификации алгоритма заполнения многоугольника многоуголь- ника. Здесь производится заполнение ортографической проекции на окно наблюдения каждого многоугольника трехмерной сцены. Легко сделать пошаговое вычисление z–координаты очередного пиксела, дополнительно храня z–координаты его вершин и вычисляя приращение δz z–координаты при перемещении вдоль x на 1. А ЛГОРИТМ 2 (А ЛГОРИТМ УДАЛЕНИЯ ПОВЕРХНОСТЕЙ С ПОМОЩЬЮ Z– БУФЕРА ). Вход: Трехмерная сцена в виде набора граней в экранной системе координат. Каждая грань — набор ребер многоугольника без самопересечений. Выход: Образ трехмерной сцены без невидимых граней. • Взять Z-буфер — массив чисел Z[x, y], размерность которого — количество точек в окне вывода изоб- ражения на экране. Будем предполагать, что элемент Z–буфера Z[x, y] будет соответствовать точке с координатами (x, y) на окне проекции. • Обнулить элементы Z–буфера. (Обнуление делаем вследствие того, что любая видимая точка в экранной системе координат имеет отрицательную координату z) • Выполнить шаги 1—8 для каждой грани трехмерной сцены. 1. Будем предполагать, что начальной точкой любого ребра многоугольника является точка с меньшей y –координатой. Отсортировать ребра многоугольника по возрастанию y–координаты начальной точки 2. Определить пределы заполнения по оси y — Y min и Y max . Стартуя с текущим значением Y current = Y min , исполнять пункты 3–8 до завершения раскраски. 0.2. Алгоритм удаления поверхностей с Z–буфером 3 3. Определить число вершин, расположенных на строке Y current — текущей строке сканирования. 4. Если вершины есть, то для каждой из вершин дополнить список активных ребер, используя ин- формацию о соседних вершинах. Для каждого ребра, у которого начальная точка лежит на строке сканирования, занести в список активных ребер: – максимальное значение y–координаты ребра (y–координату конечной точки ребра), – приращение x–координаты — ∂x при увеличении y на 1, ∂x = ∆x ∆y , – приращение z–координаты — ∂z при увеличении y на 1, ∂z = ∆z ∆y , – начальное значение x–координаты (x–координату начальной точки ребра), – начальное значение z–координаты (z–координату начальной точки ребра). Если обнаруживаются горизонтальные ребра, то они просто закрашиваются с помощью алгоритма 3 и информация о них в список активных ребер не заносится. Если после этого обнаруживается, что список активных ребер пуст, то заполнение закончено. 5. По списку активных ребер и списку ребер, не заносившихся в AET определяется Y next — y– координата ближайшей вершины. (Вплоть до Y next можно не заботиться о модификации AET а только менять x–координаты пересечений строки сканирования с активными ребрами). 6. В цикле от Y current до Y next : – выбрать из списка активных ребер и отсортировать x–координаты пересечений активных ребер со строкой сканирования; – определить интервалы и выполнить закраску по алгоритму 3; – перевычислить координаты x и z для следующей строки сканирования. 7. Проверить не достигли ли максимальной y–координаты. Если достигли, то заливка закончена, иначе выполнить пункт 8. 8. Очистить список активных ребер от ребер, закончившихся на строке Y next и перейти к пункту 3. А ЛГОРИТМ 3 (З АКРАСКА ЛИНИИ В АЛГОРИТМЕ С Z– БУФЕРОМ ). Вход: Точки P 1 и P 2 концов закрашиваемого отрезка, заданные своими координатами (x 1 , y, z 1 ) и (x 2 , y, z 2 ) соответственно. Z—Z–буфер. Выход: Видимая часть отрезка P 1 P 2 1. Вычислить приращение z–координаты — δz, при перемещении вдоль x на 1 δz = z 2 − z 1 x2 − x1 2. Положить Z current = z 1 3. В цикле для каждого целого X current от x 1 до x 2 : • Если Z[X current , y] > Z current то Положить Z[X current , y] = Z current и изобразить точку с координа- тами (X current , y, Z current ) , • Положить Z current = Z current + δz Основной недостаток алгоритма с Z-буфером - дополнительные затраты памяти. Для их уменьшения можно разбивать изображение на несколько прямоугольников или полос. В пределе можно использовать Z-буфер в виде одной строки. Понятно, что это приведет к увеличению времени, так как каждый прямоугольник будет обрабатываться столько раз, на сколько областей разбито пространство изображения. Уменьшение затрат времени в этом случае может быть обеспечено предварительной сортировкой многоугольников на плоскости. |