Загрузка...

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


Формирование растра. Растровая развертка в реальном времени. Методы группового и клеточного кодирования. Буфер кадра.

Разложение в растр нелинейных фрагментов рассмотрим на примере окружности. Брезенхемом предложено одно из наиболее удачных решений. Процесс идет в два этапа: формирование сегмента и выполнение последовательных отражений для всего контура относительно заданных осей. Так, для октанта это прямая y = x, для квадрантов оси координат

Возьмем 1-ю четверть. Если окружность радиусом R имеет центр в начале координат и начинается с точки (0, R), то при движении по часовой стрелке функция y(x) монотонно ?(если взять началом (R, 0), то при обратном движении функция x(y) монотонно ­), что видно на Рис.2. Для 1-го варианта очередным пикселом будет находящийся: правее (mH), ниже (mV) или диагонально ниже (mD), как показано на Рис.3. Алгоритм выбирает пиксел, для которого абсолютное значение разности квадратов от центра до пиксела и от центра до окружности минимально. Если эти расстояния определить, то получится:

?mH = |(xi + 1)^2 + (yi)^2 – R^2)|

(1) ?mD = |(xi + 1)^2 + (yi – 1)^2 – R^2)|

?mV = |(xi)^2 + (yi — 1)^2 – R^2)|

Вычисления будут упрощены, если заметить, что в окрестности (xi, yi) возможны только 5 типов пересечения окружности и точки растра. По аналогии с разложением отрезка в растр также используем метод определение знака ошибки. Для диагонального пикселя обозначим разность через DI. Из (1) видно, что DI = (xi+1)2 + (yi-1)2 — R2. (2). Тогда, если DI < 0, то диагональная точка (xi+1, yi-1) находится внутри реальной окружности (случай 1 и 2), то выбирают либо пиксель с координатами (xi+1,yi), т.е. mH, либо (xi+1,yi-1), т.е. mD.

Рассмотрим сначала случай 1. Проверим разность квадратов расстояний от окружности до пикселов в горизонтальном и диагональном направлениях. Обзначим этот параметр через d. Тогда: (3) d = mH — mD =|(xi + 1)2 + (yi)2 — R2| — |(xi + 1)2 +(yi — 1)2 — R2|. Если d < 0, то расстояние от окружности до диагонального пиксела больше, чем до горизонтального. Если d > 0 — то наоборот.

Т.о. при d ? 0 вычерчивается mH, при d > 0 — mD, а при d = 0 — горизонталный шаг.

Если учесть, что в случае 1 (xi+1)2 + yi2 — R2 ? 0, и (xi+1)2 + (yi-1)2 < 0, т.к. диагональный пиксел лежит всегда внутри окружности, а горизонтальный вне ее. Подставив (с учетом знаков) эти выражения в (3) получим: d = (xi + 1)2 + (yi)2 — R2 + (xi + 1)2 + (yi — 1)2 — R2 /добавим до полного квадрата yi2.

d = 2?[(xi+1)2 + (yi-1)2 — R2] + 2yi — 1 = 2?DI + 2?yi — 1 = 2?(DI + yi) — 1.

Теперь рассмотрим случай 2 (Рис.4), когда DI < 0. В такой ситуации и горизонтальные и диагональные пиксели лежат внутри окружности. Знак d < 0 и при использовании такого же критерия будет выбран горизонтальный пиксель (xi+1,yi). Значит: (xi+1)2 + (yi)2 — R2 < 0 и (xi+1) + (yi-1)2 — R2 < 0.

Если погрешность d ? 0, то имеем дело со случаями 3 и 4 (Рис.4). Аналогично ранее рассмотренному принципу можно получить критерий выбора для случая 3 и проверив разность между квадратами расстояний от окружности до диагонального пикселя (mD), и от окружности до вертикального пикселя (mV). Получаем:

d? = mD — mV = |(xi+1)2 + (yi-1)2 — R2| — |(xi2 + (yi-1)2 — R2|. При d? < 0 расстояние до вертикального пиксела (xi, yi-1) больше ® надо выбирать диагональный шаг mD; если d? > 0 ® выбирают вертикальный шаг (xi, yi-1); если d? = 0 ® диагональный шаг mD.

Провекрка компонент d? показывает, что:

(xi + 1)2 + (yi — 1)2 — R2 ? 0 и (xi)2 + (yi — 1)2 — R2 < 0 (т.к. диагональный пиксел вне окружности, а вертикальный внутри для 3-го случая). Тогда d? можно записать так:

d? = (xi + 1)2 + (yi — 1)2 — R2 + (xi)2 + (yi — 1)2 — R2. Дополним до полного квадрата (xi)2 с помощью добавления и вычитания 2?xi + 1. Получим:

d? = 2[(xi + 1)2 + (yi — 1)2 — R2] — 2xi — 1 = 2(DI — xi) — 1.

Рассмотрим случай 4. Ясно, что следует применять вертикальный пиксел, т.е. (xi, yi — 1), поскольку в этом случае y(x) — монотонно ?. Проверка компонент показывает, что: (xi + 1)2 + (yi — 1)2 — R2 > 0 и (xi)2 + (yi — 1)2 — R2 > 0 (оба пиксела вне окружности). Т.о. d? > 0 ® выбор падает на mV.

Для случая 5, т.е. случай, когда диагональный пиксел — на окружности (DI = 0). Проверка элементов d показывает: (xi + 1)2 + (yi — 1)2 — R2 > 0 и (xi)2 + (yi — 1)2 — R2 = 0. Следовательно d > 0 ® выбирается диагональный пиксел. Для вертикального шага:

(xi + 1)2 + (yi — 1)2 — R2 = 0 и (xi)2 + (yi — 1)2 — R2 < 0 ® d? < 0 ® выбираем диагональный вариант пиксела.

Р е з ю м е. При DI < 0 для d ? 0 выбираем пиксел (xi + 1, yi) ® mH;

для d > 0 выбираем пиксел (xi + 1, yi -1) ® mD.

При DI > 0 для d? ? 0 выбираем пиксел (xi + 1, yi -1) ® mD; для d? > 0 выбираем пиксел (xi, yi — 1) ® mV.

При DI = 0 выбираем пиксел (xi + 1, yi -1) ® mD.

На основании этих данных легко получить рекурентные формулы для реализации пошагового алгоритма. Предварительно рассмотрим горизонтальный шаг к пикселу, обозначив это новое положение пиксела, как (I + 1). Тогда координаты нового пиксела и значение DI будут: xi+1 = xi + 1; yi+1 = yi; DI+1 = (xi+1 + 1)2 + (yi+1 — 1)2 — R2 = (xi+1)2 + 2?xi+1 + 1 + (yi — 1)2 — R2 = (xi + 1)2 + (yi — 1)2 — R2 + 2xi+1 + 1 = DI + 2?xi+1 + 1.

Подобным образом определим координаты нового пиксела и значение D i для шага mD: xi+1 = xi + 1; yi+1 = yi — 1; DI+1 = ?I + 2?xi+1 — 2?yi+1 + 2. То же самое для шага mV:xi+1 = xi; yi+1 = yi — 1; DI+1 = DI — 2?yi+1 + 1.

Загрузка...