46167 (Сравнительные характеристики трёх наиболее эффективных алгоритмов рисования отрезка)

Сравнительные характеристики трёх наиболее эффективных алгоритмов рисования отрезка

Введение

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

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

Автоматизация научных исследований (АСНИ).

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

Автоматизация процессов обучения.

Издательская деятельность, реклама, компьютерные игры, мультипликация.

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

Объектом исследования в нашей работе будут являться методы генерации отрезков.

Цель нашей работы – рассмотреть методы генерации отрезков, выделить их основные характеристики, сделать вывод об их эффективности, быстродействии.

Для достижения поставленной цели определены следующие задачи:

1. На основе анализа литературы рассмотреть алгоритмы генерации отрезков, выделить их достоинства и недостатки.

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

3. Продемонстрировать различные алгоритмы генерации отрезков.

4. Сравнить быстродействие используемых алгоритмов.

5. Сделать вывод об эффективности различных алгоритмов генерации отрезков.

Методы исследования: теоретический, экспериментальный.

В данной программе реализованно три алгоритма вычерчивания отрезков: Цифровой дифференциальный анализатор (ЦДА), алгоритм Брезенхема и процедуру LineTo.

1. Теоретическая часть

1.1. Компьютерная графика

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

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

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

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

1.2 Растровая графика

В растровой графике основным элементом является точка. При экранном изображение эта точка называется пикселем.

Основная проблема и недостаток при использовании растровых изображений - это большие объемы данных. Для работ с большеразмерными иллюстрациями типа журнальной полосы требуются компьютеры с большими размерами оперативной памяти (128 Мбайт и более). Такие компьютеры, естественно, должны при этом иметь и высокопроизводительные процессоры.

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

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

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

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

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

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

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

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

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

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

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

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

1.3 Векторная графика

Как в растровой графике основным элементом изображения является точка, так в векторной графике основным элементом изображения является линия, при этом не важно, прямая это линия или кривая.

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

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

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

Как и все объекты, линии имеют свойства. К этим свойствам относятся: форма линии, ее толщина, цвет, характер линии (сплошная, пунктирная и т.п.). Замкнутые линии имеют свойство заполнения. Внутренняя область замкнутого контура может быть заполнена цветом, текстурой, картой. Простейшая линия, если она не замкнута, имеет две вершины, которые называются узлами. Узлы тоже имеют свойства, от которых зависит, как выглядит вершина линии и как две линии сопрягаются между собой.

1.4 Алгоритмы вычерчивания отрезков

Поскольку экран растрового дисплея с электронно-лучевой трубкой (ЭЛТ) можно рассматривать как матрицу дискретных элементов (пикселов), каждый из которых может быть подсвечен, нельзя непосредственно провести отрезок из одной точки в другую. Процесс определения пикселов, наилучшим образом аппроксимирующих заданный отрезок, называется разложением в растр. В сочетании с процессом построчной визуализации изображения он известен как преобразование растровой развертки. Для горизонтальных, вертикальных и наклоненных под углом 45° отрезков выбор растровых элементов очевиден. При любой другой ориентации выбрать нужные пикселы труднее, что показано на рис. 1.1.

Рис. 1.1 Разложение в растр отрезков прямых

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