КГ_3глава (Компьютерная графика), страница 2

Рис. 3.3. Восьмисвязность

Известны также четырехсвязные алгоритмы (рис. 3.4).

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

только 7.

"Ail

Рис. 3.4. Четырехсвязность

3.2. Алгоритм вывода окружности

Для вывода контура круга можно использовать соотношение между коорди­натами X и Y для точек круга X² + Y² = R² и построить алгоритм прямого вычисления координат. Однако тогда необходимо вычислять квадратный ко­рень, а это в цифровом компьютере выполняется медленно.

Дадим запись Инкрементного алгоритма Брезенхэма на языке C++:

В этом алгоритме использована симметрия круга— в основном цикле вы­числяются координаты точек круга только для одного октанта и сразу рису­ются восемь симметрично расположенных пикселов [33].

3.3. Алгоритм вывода эллипса

Инкрементный алгоритм для эллипса подобен алгоритму для круга, но более сложный. Этот алгоритм приведен в [33].

В этом алгоритме использована симметрия эллипса по квадрантам (рис. 3.5). Алгоритм состоит из двух циклов. Сначала от х=0 до x=dxt, где

а потом цикл до точки х =а, у = 0.

Рис. 3.5. Вывод эллипса

3.4. Кривая Безье

Разработана математиком Пьером Безье. Кривые и поверхности Безье были использованы в 60-х годах компанией "Рено" для компьютерного проектиро­вания формы кузовов автомобилей. В настоящее время они широко исполь­зуются в компьютерной графике.

Кривые Безье описываются в параметрической форме:

Значение t выступает как параметр, которому отвечают координаты отдель­ной точки линии. Параметрическая форма описания может быть более удоб­ной для некоторых кривых, чем задание в виде функции у=f(х). Это потому, что функция f(х) может быть намного сложнее, чем P_x(t) и P_y(i), кроме того, f(x) может быть неоднозначной.

Многочлены Безье для Р_х и Р_у имеют такой вид:

где С_mⁱ— сочетание т по i (известное также по биному Ньютона), С_mⁱ = m! /( i! (т - i)!), а х_i, и у_i, — координаты точек-ориентиров P _i. Значение т можно рассматривать и как степень полинома, и как значение, которое на единицу меньше количества точек-ориентиров.

Рассмотрим кривые Безье, классифицируя их по значениям т.

m = 1 (no двум точкам).

Кривая вырождается в отрезок прямой линии, определяемый концевыми точ­ками Р_о и Р1, как показано на рис. 3.6.

Рис. 3.6. Кривая Безье (т = 1) т = 2 (по трем точкам, рис. 3.7)

Рис. 3.7. Кривая Безье (т=2)

m = 3 (по четырем точкам, кубическая, рис. 3.8). Используется довольно час­то, в особенности в сплайновых кривых.

Рис. 3.8. Кубические кривые Безье (т = 3)

Геометрический алгоритм для кривой Безье

Этот алгоритм позволяет вычислить координаты (x, у) точки кривой Безье по значению параметра t. Алгоритм описан в [19].

1. Каждая сторона контура многоугольника, проходящего по точкам-ориен­тирам, делится пропорционально значению t.

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

3. Стороны нового контура снова делятся пропорционально значению t. И так далее. Это продолжается до тех пор, пока не будет получена единст­венная точка деления. Эта точка и будет точкой кривой Безье (рис. 3.9).

Рис. 3.9. Геометрический алгоритм для кривых Безье

Приведем запись геометрического алгоритма на языке C++:

for ( i = 0; i <= m; i++)

R[i] = P[i]; //формируем вспомогательный массив R[ ] for ( j = m; j > 0; j - -) for ( i = 0; i < j; i++)

R[i] = R[i] + t * (R[i+1] - R[i]);

Результат работы алгоритма— координаты одной точки кривой Безье — записываются в R[0].

3.5. Алгоритмы вывода фигур

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

В общем случае линий контура может быть несколько — когда объект имеет внутри пустоты. В этом случае для описания таких фигур необходимы два и более контуров (рис. 3.10).

Диагональное расположение можно получить, если сдвигать четные строки ячеек (рис. ] .44).

Координаты пикселов ячеек можно вычислять следующим образом:

Для того чтобы получить диагональную структуру растра подобную той, что используется для печати газет, можно использовать квадратное расположе­ние ячеек другого типа (рис. 1.45).

Рис. 1.44. Пример диагонального размещения ячеек

Рис. 1.45. Еще один пример диагональной структуры

Вы, наверное, уже заметили, что для всех приведенных выше примеров дизе­ринга ячейки образовывают точки переменного размера с постоянным ша­гом. Однако часто используется иной подход— переменная густота распо­ложения точек постоянного размера. Такой способ получил название частот­ной модуляции (ЧМ) (рис. 1.46).

Рис. 1.46. ЧМ-ячейки 6*6

Положительная черта способа ЧМ — меньшая заметность структуры растра. Однако его использование затруднено в случае, когда размер пикселов боль­ше, чем их шаг. Начиная с определенной густоты, пикселы смыкаются. Кро­ме того, на дискретном растре невозможно обеспечить плавное изменение густоты (частоты), в особенности для ячеек небольшого размера. Рассмотрим пример ячеек 5 ><5, реализующих ЧМ-дизеринг (рис. 1.47).

Рис. 3.10. Пример фигуры

В некоторых графических системах одним объектом может считаться и более сложная многоконтурная фигура — совокупность островов с пустотами.

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

Для вывода точек заполнения известны методы, разделяющиеся в зависимо­сти от использования контура на два типа— алгоритмы закрашивания от внутренней точки к границам произвольного контура и алгоритмы, которые используют математическое описание контура.

Алгоритмы закрашивания

Рассмотрим алгоритмы закрашивания произвольного контура, который уже нарисован в растре. Сначала находится пиксел внутри контура фигуры. Цвет этого пиксела изменяем на нужный цвет заполнения. Потом проводится ана­лиз цветов всех соседних пикселов. Если цвет некоторого соседнего пиксела не равен цвету границы контура или цвету заполнения, то цвет этого пиксела изменяется на цвет заполнения. Потом анализируется цвет пикселов, сосед­них с предыдущими. И так далее, до тех пор, пока внутри контура все пиксе­лы не перекрасятся в цвет заполнения.

Пикселы контура — это граница, за которую нельзя выходить в ходе после­довательного перебора всех соседних пикселов. Соседними могут считаться только четыре пиксела (справа, слева, сверху и снизу — четырехсвязность), или все восемь пикселов (восьмисвязность). Не всякий контур может слу­жить границей закрашивания (рис. 3.11).

Простейший алгоритм закрашивания. Для всех алгоритмов закрашивания нужно задавать начальную точку внутри контура с координатами х₀, у₀ - Про­стейший алгоритм можно описать так [32]:

Рис. 3.11. Особенности восьмисвязного закрашивания Функцию закрашивание () определим так:

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

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

Волновой алгоритм закрашивания. Алгоритм был разработан авторами работы [38] и предназначался для расчета центра тяжести объектов по соот­ветствующим изображениям. Идея была навеяна волновым алгоритмом по­иска трассы на графе, известным в САПР электронных схем. Суть подобных алгоритмов состоит в том, что для начальной точки (вершины на графе) на­ходятся соседние точки (другие вершины), которые отвечают двум условиям: во-первых — эти вершины связаны с начальной; во-вторых — эти вершины еще не отмечены, то есть они рассматриваются впервые. Соседние вершины

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

Запишем волновой алгоритм закрашивания на языке C++ с использованием графических функций API Windows.

Здесь цвет закрашивания и цвет контура — черный цвет (код 0). Пример ра­боты алгоритма приведен на рис. 3.12.

От начальной точки распространяется волна пикселов закрашивания в виде ромба. В одном цикле onestep закрашиваются пикселы вдоль линии пери­метра ромба (или нескольких ромбов в зависимости от сложности фигуры). В качестве рабочих массивов для текущего сохранения координат пикселов фронтов волн использованы динамические массивы емкостью по 10 000 эле­ментов. Максимальная емкость массивов обуславливается размерами контура и рассчитывается эмпирически.

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

Необходимо заметить, что этот алгоритм не является самым быстрым из из­вестных алгоритмов закрашивания, особенно если для его реализации использовать медленную функцию setPixel для рисования отдельных пикселов в программах для Windows. Большую скорость закрашивания обеспечивают алгоритмы, которые обрабатывают не отдельные пикселы, а сразу большие блоки из многих пикселов, которые образовывают прямоугольники или линии.