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

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

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

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

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

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

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

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

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

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

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

x(t) = x₀ + Δx * t

y(t) = y₀ + Δy * t

t ϵ [0,1]

где

Δx = (x₁ – x₀) / L

Δy = (y₁ – y₀) / L

L = max( |x₁ – x₀| , |y₁ – y₀| )

○ Если е < ½ , то идём вправо и увеличиваем ошибку е = е + 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) = x² + y² - R²

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

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

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

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

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