КГ_3глава (1024106), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Рис. 3.12. Количество циклов OneStep

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

Приведем запись алгоритма на языке C++. Этот пример взят из [32], незна­чительно усовершенствован и переработан для использования в среде Windows.

В программах функция LineFiii используется таким образом:

Пример работы алгоритма закрашивания линиями приведен на рис. 3.13.

Рис. 3.13. Количество циклов LineFiii

Так же, но немного быстрее, работает функция FloodFiii API Windows. Раз­ница в быстродействии обусловлена тем, что для LineFiii мы использовали стандартные функции для интерфейса прикладных программ, a FloodFiii оптимизирована на системном уровне.

Алгоритмы заполнения, которые используют математическое описание контура

Математическим описанием контура фигуры может служить уравнение у = f(x) для окружности, эллипса или другой кривой. Для многоугольника (полигона) контур задается множеством координат вершин (х_i, у_i). Возможны и другие формы описания контура. В любом случае алгоритмы данного клас­са не предусматривают обязательное предварительное создание пикселов контура растра — контур может совсем не выводиться в растр. Рассмотрим некоторые из подобных алгоритмов заполнения.

Заполнение прямоугольников. Среди всех фигур прямоугольник заполнять наиболее просто. Если прямоугольник задан координатами противополож­ных углов, например, левого верхнего (x_1, у₁) и правого нижнего {х_2, у₂), то­гда алгоритм может заключаться в последовательном рисовании горизон­тальных линий заданного цвета (рис. 3.14).

Рис. 3.14. Заполнение прямоугольника

Заполнение круга. Для заполнения круга можно использовать алгоритм вы­вода контура, который мы уже рассмотрели в разд. 3.2. В процессе выполне­ния этого алгоритма последовательно вычисляются координаты пикселов контура в границах одного октанта. Для заполнения надлежит выводить го­ризонтали, которые соединяют пары точек на контуре, расположенные сим­метрично относительно оси y (рис. 3.15).

Так же может быть построен и алгоритм заполнения эллипса.

Рис. 3.15. Заполнение круга

Заполнение полигонов, контур полигона определяется вершинами, которые соединены отрезками прямых (рис. 3.16). Это— векторная форма задания

фигуры.

Рис. 3.16. Пример полигона

Рассмотрим один из наиболее популярных алгоритмов заполнения полигона. Его основная идея — закрашивание фигуры отрезками прямых линий. Наи­более удобно использовать горизонтали. Алгоритм представляет собою цикл вдоль оси у, в ходе этого цикла выполняется поиск точек сечения линии кон­тура с соответствующими горизонталями. Этот алгоритм получил назва­ние XY [33]:

1. Найти min{y±} и юах{у±} среди всех вершин Pi.

2. Выполнить цикл по у от у = min до у = max .

{

3. Нахождение точек пересечения всех отрезков контура

с горизонталью у. Координаты xj точек сечения записать в массив.

4. Сортировка массива { xj } по возрастанию x.

В этом алгоритме использовано свойство топологии контура фигуры. Оно состоит в том, что любая прямая линия пересекает любой замкнутый контур четное количество раз (рис. 3.17). Для выпуклых фигур точек пересечения с любой прямой всегда две. Таким образом, на шаге 3 этого алгоритма в мас­сив { Xj } всегда должно записываться парное число точек сечения.

Рис. 3.17. Заполнение полигона

При нахождении точек пересечения горизонтали с контуром необходимо принимать во внимание особые точки. Если горизонталь имеет координату (у), совпадающую с у_i вершины Р _I тогда надлежит анализировать то, как горизонталь проходит через вершину. Если горизонталь при этом пересекает контур, как, например, в вершинах Р_о или Р₄, то в массив записывается одна точка сечения. Если горизонталь касается вершины контура (в этом случае вершина соответствует локальному минимуму или максимуму как, например, в вершинах P₁ , P₂, , Р₃ или Р₅), тогда координата точки касания или не записы­вается, или записывается в массив два раза. Это условие четности количества точек пересечения, хранящихся в массиве { xj }.

Процедура определения точек пересечения контура с горизонтальной раз­верткой, учитывая анализ на локальный максимум, может быть достаточно сложной. Это замедляет работу. Радикальным решением для упрощения по­иска точек сечения может быть смещение координат вершин контура или горизонталей заполнения таким образом, чтобы ни одна горизонталь не попала в вершину. Смещение можно выполнять различными способами, на­пример, ввести в растр дробные координаты для горизонталей: y_min ⁺ 0.5,

y_min + 1.5, .... . y_max - 0,5.

Но такое упрощение процедуры нахождения точек пересечения приводит к искажению формы полигона.

Для определения координат (х) точек пересечения для каждой горизонтали необходимо перебирать все п отрезков контура. Координата пересечения от­резка p _i —р_к с горизонталью у равна

Количество тактов работы этого алгоритма:

где y_max , y_min — диапазон координат у, N_гор — число тактов, необходимых

для одной горизонтали.

Оценим величину N_sop как пропорциональную числу вершин

где к — коэффициент пропорциональности, п — число вершин полигона. Возможны модификации приведенного алгоритма для ускорения его работы. Например, можно принять во внимание то, что каждая горизонталь в боль­шинстве случаев пересекает небольшое количество ребер контура. Поэтому если при поиске точек сечения делать предварительный отбор ребер, которые находятся вокруг каждой горизонтали, то можно добиться уменьшения коли­чества тактов работы с N_гор = к п до к п_р, где п_р — число отобранных ребер. Например, разделим диапазон y_min - y_max пополам. Если для диапазона от y_min до у_ср составить список отрезков (или вершин), которые попадают в этот диапазон, то в этот список будет включено приблизительно вдвое меньшее количество, чем для всего диапазона от y_min до у_тax. Почему приблизитель­но — ибо это зависит от формы полигона. Таким образом, при работе алго­ритма для каждой горизонтали в диапазоне y_min до у_ср уже нужно не кп так­тов, а ~ к -п/2.

Аналогично для диапазона у_ср – y_max также можно составить список ребер, который также будет почти вдвое меньшим. Если принять, что подсчеты для каждой горизонтали теперь выполняются за вдвое меньшее количество так­тов, а именно за (N_гор /2), то общее число тактов:

где N_don — количество тактов для создания списка ребер.

Такой способ повышения быстродействия эффективен для большого количества вершин. Контур можно делить не пополам, а на более мелкие части — соответственно повышается скорость.

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

3.6. Стиль линии. Перо

Что общее и что разное у объектов, изображенных на рис. 3.18?

Рис. 3.18. Примеры стилей линий

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

Таблица 3.1

Алгоритмы вывода толстой линии

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

Вывод пиксела (х, у)

Можно представить себе такой алгоритм, как цикл, в котором определяются координаты (х,у) каждого пиксела. Этот алгоритм можно модифицировать для вывода толстой линии следующим образом:

Характеристики

Список файлов книги