Материал: Конспект лекций по дисциплине «Компьютерная графика». Лейкин М.А

1, у постоянно изменяется на единицу, а критерий ошибки Брезенхема используется для принятия решения об изменении величины x. Выбор постоянно изменяющейся (на + 1 или - 1) координаты зависит от квадранта.

//инициализация переменных x = x1

y = y1

dх = abs (х2 - x1) dy = abs (y2 - y1) s1 = Sign (x2 - х1) s2 = Sign (y2 - y1)

//обмен значений dx и dy в зависимости от углового коэффициента if dy > dх then

temp = dх dх = dy dy = temp Change = 1

else

Change = 0 end if

//инициализация E с поправкой на половину пиксела

E = 2 * dy - dх

// основной цикл for i = 1 to dх

Plot(x, y) while (E >= 0)

if Change = 1 then x = x + s1

else

y = y + s2 end if

E = E - 2 * dх end while

if Change = 1 then y = y + s2

else

x = x + s1 end If

E = E + 2 * dy next i

finish

АЛГОРИТМ БРЕЗЕНХЕМА ДЛЯ ГЕНЕРАЦИИ ОКРУЖНОСТИ

Для начала заметим, что сгенерировать надо только 1/8 часть окружности. Остальные ее части могут быть получены последовательными отражениями.

Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим образом приближающий окружность: горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. Эти направления обозначим соответственно mH, mD, mV. Алгоритм выбирает пиксел, для которого минимален квадрат расстояния между одним из этих пикселов и окружностью, т.е. минимум из

mH = abs((Xi + 1)*(Xi + 1) + Yi*Yi - R*R)

mD = abs((Xi + 1)*(Xi + 1) + (Yi - 1)*(Yi - 1) - R*R) mV = abs(Xi*Xi + (Yi - 1)*(Yi - 1) - R*R)

Вычисления можно упростить, если заметить, что в окрестности точки (Xi,Yi) возможны только пять типов пересечений окружности и сетки растра.

Разность между квадратами расстояний от центра окружности до диагонального пиксела (Xi + 1, Yi - 1) и от центра до точки на окружности R*R равна

Di = (Xi + 1)* (Xi + 1) + (Yi - 1)* (Yi - 1) - R*R .

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

x = 0 y = R

D = 2*(1 - R) Limit = 0

1Plot(x, y)

if y <= Limit then 4 If D < 0 then 2

If D > 0 then 3 if D = 0 then 20

2A = 2*D + 2*y - 1 if A <= 0 then 10 if A > 0 then 20

3A = 2*D + 2*х - 1 If A <= 0 then 20 if A > 0 then 30

//выполнение шагов

//шаг mH

10х = х + 1

D = D + 2*х + 1 goto 1

// шаг mD

20х = х + 1 y = y - 1

D = D + 2*х - 2*y + 2 goto 1

// шаг mV

30y = y - 1

D = D - 2*y + 1 goto 1

4 finish

Переменная предела устанавливается в нуль для окончания работы алгоритма на горизонтальной оси, в результате генерируется окружность в первом квадранте. Если необходим лишь один из октантов, то второй октант можно получить с помощью установки Limit = Integer (R /sqrt(2)), а первый - с помощью отражения второго октанта относительно прямой у = х .

РАСТРОВАЯ РАЗВЕРТКА - СПОСОБ ГЕНЕРАЦИИ ИЗОБРАЖЕНИЯ

Для вывода на видеомонитор разложенный в растр образ необхо-

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

РАСТРОВАЯ РАЗВЕРТКА В РЕАЛЬНОМ ВРЕМЕНИ

При развертке в реальном времени или "на лету" сцена произвольно представляется в терминах визуальных атрибутов и геометрических характеристик. Типичными визуальными атрибутами являются цвет, оттенок и интенсивность, тогда как координаты х, у, углы наклона и текст относятся к геометрическим характеристикам. Последние упорядочены по координате Y. Во время воспроизведения каждого кадра процессор сканирует эту информацию и вычисляет интенсивность каждого пиксела на экране. При такой развертке не нужны большие количества памяти. Требования на память обычно ограничиваются необходимостью хранить дисплейный список плюс одну сканирующую строку. Более того, поскольку информация о сцене хранится в произвольно организованном дисплейном списке, добавление или удаление информации из списка осуществляется легко, а это удобно для динамических приложений. Однако сложность выводимого изображения ограничивается скоростью дисплейного процессора. Обычно это означает, что ограничено число отрезков или многоугольников в картине, количество пересечений со сканирующей строкой или число цветов или полутонов серого.

Для получения пересечений (если они есть) каждого отрезка дисплейного списка со сканирующей строкой в простейшей реализации метода всякий раз при изображении строки обрабатывается весь дисплейный список. При регенерации видеоизображения на каждую сканирующую строку, а значит, и на обработку всего списка приходится только 63.5 микросекунды. Столь малое время позволяет использовать данный метод только для рисования несложных чертежей, не более. Так как в общем случае не каждый отрезок в сцене пересекает каждую сканирующую строку, то количество вычислений может быть сокращено путем введения списка активных ребер (САР). Этот список содержит те отрезки изображения, которые пересекают сканирующую строку.

Для организации и управления CAP можно использовать ряд методов. Сначала отрезки изображения сортируются по наибольшей координате Y. В одном из простых методов такой сортировки используются два перемещающихся указателя в отсортированном списке. Указатель начала используется для обозначения начала списка активных ребер, а указатель конца - для обозначения конца этого списка. При сканировании изображения необходимо корректировать САР, при этом указатель конца передвигают вниз, чтобы включить в список новые отрезки, начинающиеся на сканирующей строке или выше ее. В то же самое время указатель начала передвигают вниз, чтобы исключить отрезки, кончающиеся выше сканирующей строки.

Эту и аналогичные проблемы можно устранить путем введения дополнительной структуры данных. При этом можно упростить также вычисление пересечения каждого отрезка изображения со сканирующими строками. Сначала выполняется групповая сортировка по Y всех отрезков изображения. При групповой сортировке по Y просто созда-

ются области памяти или группы для каждой сканирующей строки. Если, например, применяется 1200 сканирующих строк, то используется 1200 групп. При просмотре отрезков в дисплейном списке информация о каждом отрезке помещается в группу, соответствующую наибольшей величине координаты Y для отрезка. Для простого черно-белого контурного изображения необходимо записывать только координату X точки пересечения с групповой сканирующей строкой, dх - изменение этой координаты х при переходе от одной сканирующей строки к другой, и dy - число сканирующих строк, пересекаемых отрезком. Для простых изображений большинство из Y-групп будет пусто.

Список активных ребер для текущей сканирующей строки формируется добавлением информации из Y-группы, соответствующей этой строке. Координаты X точек пересечения сортируются в порядке сканирования, и ребра из CAP преобразуются в растровую форму. После этого для каждого отрезка из CAP dy уменьшается на единицу. Если dу < 0, то отрезок исключается из списка. И наконец, для каждого отрезка координата X точки пересечения для новой сканирующей строки получается добавлением к прежнему значению величины dx. Этот процесс повторяется для всех сканирующих строк. Если используется фиксированный размер Y-групп, то для пересечений с каждой сканирующей строкой выделяется фиксированное количество памяти. Таким образом, максимальное число пересечений с произвольной сканирующей строкой предопределено заранее и, следовательно, сложность изображения ограничена. Одним из методов, позволяющих преодолеть это ограничение, может служить использование в качестве структуры данных последовательного индексированного списка. В этом случае каждая Y-группа содержит только указатель на расположение в структуре данных информации для первого отрезка из группы (т. е. начинающегося на этой сканирующей строке).

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

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

ГРУППОВОЕ КОДИРОВАНИЕ

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

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

Сжатие данных для изображений, закодированных группами, может приближаться к 10:1. Это существенно не только потому, что групповое кодирование просто экономит память, но и потому, что оно экономит память для машинно-синтезированных последовательностей кадров или фильма. Оно также экономит время передачи фотографий и факсов, в которых широко используется групповое кодирование. Рассмотрим, например, потребность в памяти для изображений с разрешением 512х512х8 в 30-секундном фильме, в котором кадры следуют с частотой видеогенерации, т. е. 30 кадр/с. Требуемая память составляет

(512х512х8х30х30)/(8 бит/байт) = 236 Мбайт Однако даже умеренное сжатие 4:1 при групповом кодировании позволит хранить его на одном диске малого или среднего размера.

У группового кодирования есть и недостатки. Добавление или удаление отрезков или текста из изображения является трудоемкой операцией и занимает много времени из-за последовательного хранения длин участков. Кодирование и декодирование изображения влечет за собой накладные расходы. Наконец, для коротких участков одинаковой интенсивности может потребоваться в два раза больше памяти, чем при попиксельном хранении.

КЛЕТОЧНОЕ КОДИРОВАНИЕ

В методе группового кодирования изображение рассматривается как линейная или одномерная совокупность пикселов. В методе клеточного кодирования сделана попытка с помощью минимума ин формации представить целые области изображения, т. е. клетки. Для того чтобы в простейшем алфавитно-цифровом терминале с ЭЛТ можно было выполнять операции в реальном времени, используется клеточное кодирование. В таком терминале область экрана разбивается на клетки или области, достаточно большие, чтобы содержать одну литеру. Например, экран можно разбить на области размером 8х8 пикселов. Для телевизионного дисплея 640 х 480 со стандартным видовым отношением 4:3 получится 80 х 60 клеток. Обычно клетка 8х8 пикселов используется для вывода литер с точечной матрицей размером 7х5. Дополнительные пикселы используются для разделения литер, а также для строчных литер с нижними выносными элементами. Шаблоны, составленные из пикселов, для каждой литеры могут храниться в постоянном запоминающем устройстве (ПЗУ).

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

БУФЕРЫ КАДРА

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

Буферы кадров можно также реализовать с помощью сдвиговых регистров. Схематично сдвиговый регистр можно считать стеком типа

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

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

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

¦¦

------------------------------

Хотя первая схема позволяет процессору ЭВМ самому манипулировать буфером кадра, обычно более эффективно добавить к системе специализированный графический процессор. При получении команд от глав-

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

АДРЕСАЦИЯ РАСТРА

Для простоты изложения будем считать, что пиксел в растре или буфере кадра имеет двумерные координаты X и Y. Цифровая память, однако, организована в один линейный список адресатов, и необходимо, таким образом, преобразование координатного представления в линейное. Предположим, что начальный адрес в памяти не равен нулю, тогда преобразование задается формулой

адрес = (Xmах - Xmin)*(Y - Ymin) + (X - Xmin) +

базовый адрес

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

Как правило, для заданного буфера кадра величины Xmax, Xmin, Ymin и базовый адрес постоянны. Уравнение можно переписать в виде

Адрес = K1 + K2*Y + X

где K1 = базовый адрес - К2*Ymin - Xmin K2 = Xmax - Xmin

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

Адрес(X+1, Y) = K1 + K2*Y + X + 1 = Адрес(X, Y) + 1 Aдpec(X, Y+1) = K1 + K2*(Y+1) + X = Адрес(X, Y) + K2

Адрес(X+1, Y+1) = K1 + K2*(Y+1) + X + 1 = Адрес(X, Y)+ K2 + 1

Аналогичные выражения (заменой знака "плюс" на "минус") получаются при уменьшении координат. Здесь для горизонтального или вертикального приращения в растре требуется только одно сложение или вычитание, а для диагонального приращения - только два сложения или вычитания. Операция умножения полностью исключена из вычислений.

ИЗОБРАЖЕНИЕ ОТРЕЗКОВ

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

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

Для уменьшения затрат можно использовать оболочечный или минимаксный текст. Отрезок AB могут пересекать только те отрезки, которые проходят через прямоугольную оболочку, сформированную из минимальных и максимальных значений координат X, Y отрезка AB. Тесты для каждого отрезка выглядят следующим образом:

// Минимаксный или оболочечный тест if (Хотр_mах < Хобол_min) or

(Xoтp_min > Хобол_mах) or (Yoтp_max < Yo6oл_min) or (Yoтp_min > Yобол_mах)

then

пересечения нет

else

вычислить пересечение

end if

РАСТРОВАЯ РАЗВЕРТКА СПЛОШНЫХ ОБЛАСТЕЙ

Для сих пор речь шла о представлении на растровом графическом устройстве отрезков прямых линий. Однако одной из уникальных характеристик такого устройства является возможность представления сплошных областей. Генерацию сплошных областей из простых описаний ребер будем называть растровой разверткой сплошных областей, заполнением многоугольников или заполнением контуров. Для этого можно использовать несколько методов, которые обычно делятся на две широкие категории: растровая развертка и затравочное заполнение.

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

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

АЛГОРИТМЫ С УПОРЯДОЧЕННЫМ СПИСКОМ РЕБЕР

Алгоритм 1. Подготовить данные:

Определить для каждого ребра многоугольника точки пересечений со сканирующими строками, проведенными через середины интервалов, т. е. через Y + 1/2. Для этого можно использовать алгоритм Брезенхема или ЦДА. Горизонтальные ребра не учитывать. Поместить

координату X точки пересечения в группу, соответствующую Y.

Для каждой группы отсортировать список координат X точек пересечений в порядке возрастания; т. е. X1 предшествует X2, если

X1 <= X2.

Преобразовать эти данные в растровую форму:

Для каждой сканирующей строки выделить из списка координат X точек пересечений пары точек пересечений. Активировать на сканирующей строке Y пикселы для целых значений X, таких, что X1 <= X +

1/2 <= X2.

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

Хотя в этой версии алгоритма задача сортировки проста, в ней либо ограничено число пересечений с данной сканирующей строкой, либо требуется резервирование большого количества памяти, значительная часть которой не будет использоваться. Этот недостаток можно преодолеть благодаря использованию связного списка, т. е. путем введения добавочной структypы данных. Предварительное вычисление пересечения каждой сканирующей строки с каждым ребром многоугольника требует больших вычислительных затрат и значительных объемов памяти. Bведя список активных ребер (CAP), как это предполагалось для рacтpoвoй развертки в реальном времени, можно сократить потребность в памяти и вычислять пересечения со сканирующими строками в пошаговом режиме. Алгоритм, получившийся в результате всех улучшений, выглядит следующим образом:

Алгоритм 2. Подготовить данные:

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

Занести ребро многоугольника в Y-группу, соответствующую этой сканирующей строке.

Сохранить в связном списке значения: начальное значение координат X точек пересечения, dY - число сканирующих строк, пересекаемых ребром многоугольника, и dX - шаг приращения по X при переходе от одной сканирующей строки к другой.

Преобразовать эти данные в растровую форму:

Для каждой сканирующей строки проверить соответствующую Y-группу на наличие новых ребер. Новые ребра добавить в CAP. Отсортировать координаты X точек пересечения из CAP в порядке возрастания; т. е. X1 предшествует X2, если X1 <= X2.

Выделить пары точек пересечений из отсортированного по X списка. Активировать на сканирующей строке Y пикселы для целых значений X, таких, что X1 <= X + 1/2 <= X2. Для каждого ребра из CAP уменьшить dY на 1. Если dY < 0, то исключить данное ребро из CAP. Вычислить новое значение координат X точек пересечения: X =

X + dX.

Перейти к следующей сканирующей строке.

АЛГОРИТМ СО СПИСКОМ РЕБЕР И ФЛАГОМ

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

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

Обрисовка контура:

Используя соглашение о середине интервала между сканирующими строками для каждого ребра, пересекающего сканирующую строку, отметить самый левый пиксел, центр которого лежит справа от пересечения; т. е. X + 1/2 > Хпересечения

Заполнение:

Для каждой сканирующей строки, пересекающей многоугольник Внутри = FALSE

for X = 0 (левая граница) to X == Xmax (правая граница) if пиксел в точке X имеет граничное значение

then инвертировать значение переменной Внутри if Внутри = TRUE

then присвоить пикселу в X значение цвета многоугольника else присвоить пикселу в X значение цвета фона

end if next x

В данном алгоритме каждый пиксел обрабатывается только один раз, так что затраты на ввод/вывод значительно меньше, чем в алгоритме со списком ребер. При программной реализации алгоритм с упорядоченным списком ребер и алгоритм со списком ребер и флагом работают примерно с одинаковой скоростью. Однако алгоритм со списком ребер и флагом годится для аппаратной или микропрограммной реализации, в результате чего он выполняется на один-два порядка быстрее, чем алгоритм с упорядоченным списком ребер. Для простых изображений даже возможна анимация в реальном времени.

АЛГОРИТМЫ ЗАПОЛНЕНИЯ С ЗАТРАВКОЙ

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

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