Основные алгоритмы компьютерной графики

ЗАПОЛНЕНИЕ МНОГОУГОЛЬНИКА

0.4.1 Построчное заполнение
0.4.2 Сортировка методом распределяющего подсчета

В большинстве приложений используется одно из существенных достоинств растровых устройств - возможность заполнения областей экрана.

Существует две разновидности заполнения:

· первая, связанная как с интерактивной работой, так и с программным синтезом изображения, служит для заполнения внутренней части многоугольника, заданного координатами его вершин.

· вторая, связанная в первую очередь с интерактивной работой, служит для заливки области, которая либо очерчена границей с кодом пиксела, отличающимся от кодов любых пикселов внутри области, либо закрашена пикселами с заданным кодом;

В данном разделе рассмотрим алгоритм заполнения многоугольника. В следующем разделе будут рассмотрены алгоритмы заливки области.

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

Определить принадлежность пиксела многоугольнику можно, например, подсчетом суммарного угла с вершиной на пикселе при обходе контура многоугольника. Если пиксел внутри, то угол будет равен 360^°, если вне - 0^° (рис. ).

Рис. 0.4.1: Определение принадлежности пиксела многоугольнику

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

0.4.1 Построчное заполнение

Реально используются алгоритмы построчного заполнения, основанные на том, что соседние пикселы в строке скорее всего одинаковы и меняются только там где строка пересекается с ребром многоугольника. Это называется когерентностью растровых строк (строки сканирования Y_i, Y_i+1, Y_i+2 на рис. ). При этом достаточно определить X-координаты пересечений строк сканирования с ребрами. Пары отсортированных точек пересечения задают интервалы заливки.

Рис. 0.4.2: Построчная закраска многоугольника

Кроме того, если какие-либо ребра пересекались i-й строкой, то они скорее всего будут пересекаться также и строкой i+1. (строки сканирования Y_i и Y_i+1 на рис. 0.2). Это называется когерентностью ребер. При переходе к новой строке легко вычислить новую X-координату точки пересечения ребра, используя X-координату старой точки пересечения и тангенс угла наклона ребра:

X_i+1 = X_i + 1/k

(тангенс угла наклона ребра - 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.

В Приложении 5 приведены две подпрограммы заполнения многоугольника - V_FP0 и V_FP1. Первая реализует данный (простейший) алгоритм. Эта программа вполне работоспособна, но генерирует двух и трехкратное занесение части пикселов. Это мало приемлемо для устройств вывода типа матричных или струйных принтеров.

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

Рис. 0.4.3: Сравнение алгоритмов заполнения многоугольника

0.4.2 Сортировка методом распределяющего подсчета

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

Для рассмотрения алгоритма предположим, что надо отсортировать числа, заданные в массиве с именем "Исходный_массив"; количество сортируемых чисел задается скаляром "Кол-во_чисел"; сортируемые числа J удовлетворяют условию:

0 Ј J < Max_число.

Для сортировки потребуются описания:

int  Max_число;        /* Верхняя граница значений */
int  *Повтор;          /* Длина этого массива = Max_число */
int  Кол_чисел;        /* Кол-во сортируемых чисел */
int  *Исходный_массив; /* Длина этого массива >= Кол_чисел */
int  *Результат;       /* Длина этого массива >= Кол_чисел */
int  ii,jj, kk;        /* Рабочие переменные */

Обнуляется служебный массив для подсчета числа повторений исходных кодов.
```
   for (ii=0; ii<Max_число; ++ii) Повтор[ii]= 0;
```
Сортируемый массив просматривается и вычисляется количество раз повторений каждого числа:
```
   for (ii= 0; ii < Кол_чисел; ++ii) {
      jj= Исходный_массив[ii];
      Повтор[jj]= Повтор[jj] + 1;
   }
```
Суммируется количество повторений каждого числа, так что значение Повтор[J] даст начальное расположение группы чисел, равных J, в отсортированном массиве:
```
   jj= 0;
   for (ii=0; ii<Max_число; ++ii) {
      jj= jj + Повтор[ii];
      Повтор[ii]= jj;
   }
```
Просматривается исходный массив и числа из него заносятся в массив результатов той же длины. Индекс занесения числа J в массив результатов равен значению J-го элемента массива Повтор. После занесения числа J значение Повтор[J] уменьшается на 1:
```
   for (ii= 0; ii < Кол_чисел; ++ii) {
      jj= Исходный_массив[ii];
      kk= Повтор[jj];
      Результат[kk]= jj;
      Повтор[jj]= Повтор[jj] - 1;
   }
```

к оглавлению

Знаете ли Вы, что низкочастотные электромагнитные волны частотой менее 100 КГц коренным образом отличаются от более высоких частот падением скорости электромагнитных волн пропорционально корню квадратному их частоты от 300 тысяч кмилометров в секунду при 100 кГц до примерно 7 тыс км/с при 50 Гц.

НОВОСТИ ФОРУМА

Рыцари теории эфира