русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Алгоритм Брезенхема для рисования окружностей


Дата добавления: 2013-12-23; просмотров: 1012; Нарушение авторских прав


Алгоритм Брезенхема для рисования отрезков

Двумерная растровая графика

Основные требования к алгоритму:

1 Высокая скорость работы.

2 Должна использоваться только целочисленная арифметика.

3 Минимальный расход памяти.

4 Желательно, чтобы алгоритм был инкрементным (цикл не должен делать повторные вычисления, а должен корректировать ранее полученные).

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

 

Методы растеризации отрезка:

1 DDA (Digital Difference Analytics). Интересен с теоретической точки зрения. Каждая точка отрезка определяется как

x(t) = x0 + Δx * t

y(t) = y0 + Δy * t

t ϵ [0,1]

где

Δx = (x1 – x0) / L

Δy = (y1 – y0) / L

L = max( |x1 – x0| , |y1 – y0| )

 

2 Алгоритм Брезенхема. Рассмотрим случай построения отрезка из точки (0,0) в заданную точку в первом октанте (остальные случаи получаются с использованием поворота, симметрии и т.п.) Делаем x шагов, на каждом шаге перемещаемся либо вправо, либо по диагонали вправо-вверх и считаем ошибку е — расстояние между реальной точкой на отрезке и координатами пикселя.  

 

○ Если е < ½ , то идём вправо и увеличиваем ошибку е = е + dy/dx

○ Если e ≥ ½, то идём по диагонали и уменьшаем ошибку: е = е - 1

Недостатки:

○ алиасинг (при большом растре видна ступенчатость)

○ использование вещественной арифметики

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

○ изначально из е вычесть ½

○ сравнивать ошибку не с ½, а с нулём

○ умножить приращения e на 2dx:

■ при шаге вправо: е = е + 2dy,

■ при шаге по диагонали: e = e - 2dx.



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

 

Сам алгоритм (вариант с целочисленной арифметикой):

x = x1;

y = y1;

Dx = x2-x1;

Dy = y2-y1;

e = 2*Dy-Dx; // e = -Dx; ?

for (i = 1; i < Dx; i++)

{

Plot(x, y); //отрисовка точки

if (e >= 0)

{

y++;

e-=2*Dx;

}

x++;

e+=2*Dy;

}

 

 

 

3 Алгоритм Ву (модификация алгоритма Брезенхема)

На каждом шаге рисуем не одну точку, а две, причём яркости распределяем между ними в зависимости от величины ошибки e:

а) шаг по горизонтали б) шаг по диагонали

 

Рассмотрим случай рисования дуги, которая находится в третьем и четвёртом октантах (остальные части окружности рисуются аналогично).

Инициализируем x=-R, y=0. Можем двигаться либо вверх, либо по диагонали вправо-вверх.

Пиксель может находиться либо внутри окружности, либо вне её. Расстояние от пикселя до окружности:

f(x,y) = x2 + y2 - R2

Если f(x,y) > 0, то пиксель находится вне окружности, делаем шаг по диагонали

Иначе — внутри, делаем шаг вверх.

Шаг — это x++ и y++, при этом пересчитываем f(x,y).

При рисовании эллипса необходимо умножать x или y на некоторый коэффициент. До точки касания эллипса с касательной 45° шаг делается по диагонали, либо по горизонтали, а после — по горизонтали либо по вертикали.

 

Отрисовка дуг

  Задаются: центр, радиус R, α и β. Для каждого октанта прорисовывается часть дуги, которая попадает в этот октант. Как проверить, попадает ли пиксель в октант? Можно найти точки Z, и если пиксель попадает в промежуток между ними, то он попадает в октант.


<== предыдущая лекция | следующая лекция ==>
Методы сегментации изображений. Модели описания сегментов | Алгоритмы рисования закрашенного многоугольника


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.091 сек.