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


Формирование растра. Растровая развертка в реальном времени. Методы группового и клеточного кодирования. Буфер кадра.
Разложение в растр нелинейных фрагментов рассмотрим на примере окружности. Брезенхемом предложено одно из наиболее удачных решений. Процесс идет в два этапа: формирование сегмента и выполнение последовательных отражений для всего контура относительно заданных осей. Так, для октанта это прямая 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 типов пересечения окружности и точки растра. По аналогии с разложением отрезка в растр также используем метод определение знака ошибки. Для диагонального пикселя обозначим разность через ?I. Из (1) видно, что ?I = (xi+1)2 + (yi-1)2 — R2. (2). Тогда, если ?I < 0, то диагональная точка (xi+1, yi-1) находится внутри реальной окружности (случай 1 и 2), то выбирают либо пиксель с координатами (xi+1,yi), т.е. mH, либо (xi+1,yi-1), т.е. mD.
Рассмотрим сначала случай 1. Проверим разность квадратов расстояний от окружности до пикселов в горизонтальном и диагональном направлениях. Обзначим этот параметр через ?. Тогда: (3) ? = mH — mD =|(xi + 1)2 + (yi)2 — R2| — |(xi + 1)2 +(yi — 1)2 — R2|. Если ? < 0, то расстояние от окружности до диагонального пиксела больше, чем до горизонтального. Если ? > 0 — то наоборот.
Т.о. при ??? 0 вычерчивается mH, при ? > 0 — mD, а при ? = 0 — горизонталный шаг.
Если учесть, что в случае 1 (xi+1)2 + yi2 — R2 ? 0, и (xi+1)2 + (yi-1)2 < 0, т.к. диагональный пиксел лежит всегда внутри окружности, а горизонтальный вне ее. Подставив (с учетом знаков) эти выражения в (3) получим: ? = (xi + 1)2 + (yi)2 — R2 + (xi + 1)2 + (yi — 1)2 — R2 /добавим до полного квадрата yi2.
? = 2?[(xi+1)2 + (yi-1)2 — R2] + 2yi — 1 = 2??I + 2?yi — 1 = 2?(?I + yi) — 1.
Теперь рассмотрим случай 2 (Рис.4), когда ?I < 0. В такой ситуации и горизонтальные и диагональные пиксели лежат внутри окружности. Знак ? < 0 и при использовании такого же критерия будет выбран горизонтальный пиксель (xi+1,yi). Значит: (xi+1)2 + (yi)2 — R2 < 0 и (xi+1) + (yi-1)2 — R2 < 0.
Если погрешность ??? 0, то имеем дело со случаями 3 и 4 (Рис.4). Аналогично ранее рассмотренному принципу можно получить критерий выбора для случая 3 и проверив разность между квадратами расстояний от окружности до диагонального пикселя (mD), и от окружности до вертикального пикселя (mV). Получаем:
?? = mD — mV = |(xi+1)2 + (yi-1)2 — R2| — |(xi2 + (yi-1)2 — R2|. При ?? < 0 расстояние до вертикального пиксела (xi, yi-1) больше ? надо выбирать диагональный шаг mD; если ?? > 0 ? выбирают вертикальный шаг (xi, yi-1); если ?? = 0 ? диагональный шаг mD.
Провекрка компонент ?? показывает, что:
(xi + 1)2 + (yi — 1)2 — R2 ? 0 и (xi)2 + (yi — 1)2 — R2 < 0 (т.к. диагональный пиксел вне окружности, а вертикальный внутри для 3-го случая). Тогда ?? можно записать так:
?? = (xi + 1)2 + (yi — 1)2 — R2 + (xi)2 + (yi — 1)2 — R2. Дополним до полного квадрата (xi)2 с помощью добавления и вычитания 2??? + 1. Получим:
?? = 2[(xi + 1)2 + (yi — 1)2 — R2] — 2xi — 1 = 2(?I — xi) — 1.
Рассмотрим случай 4. Ясно, что следует применять вертикальный пиксел, т.е. (xi, yi — 1), поскольку в этом случае y(x) — монотонно ?. Проверка компонент показывает, что: (xi + 1)2 + (yi — 1)2 — R2 > 0 и (xi)2 + (yi — 1)2 — R2 > 0 (оба пиксела вне окружности). Т.о. ?? > 0 ? выбор падает на mV.
Для случая 5, т.е. случай, когда диагональный пиксел — на окружности (?I = 0). Проверка элементов ? показывает: (xi + 1)2 + (yi — 1)2 — R2 > 0 и (xi)2 + (yi — 1)2 — R2 = 0. Следовательно ? > 0 ? выбирается диагональный пиксел. Для вертикального шага:
(xi + 1)2 + (yi — 1)2 — R2 = 0 и (xi)2 + (yi — 1)2 — R2 < 0 ???? < 0 ? выбираем диагональный вариант пиксела.
Р е з ю м е. При ?I < 0 для???? 0 выбираем пиксел (xi + 1, yi) ? mH;
для ? > 0 выбираем пиксел (xi + 1, yi -1) ? mD.
При ?? > 0 для ???? 0 выбираем пиксел (xi + 1, yi -1) ? mD; для ?? > 0 выбираем пиксел (xi, yi — 1) ? mV.
При ?I = 0 выбираем пиксел (xi + 1, yi -1) ? mD.
На основании этих данных легко получить рекурентные формулы для реализации пошагового алгоритма. Предварительно рассмотрим горизонтальный шаг к пикселу, обозначив это новое положение пиксела, как (I + 1). Тогда координаты нового пиксела и значение ?I будут: xi+1 = xi + 1; yi+1 = yi; ?I+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 = ?I + 2?xi+1 + 1.
Подобным образом определим координаты нового пиксела и значение ? i для шага mD: xi+1 = xi + 1; yi+1 = yi — 1; ?I+1 = ?I + 2?xi+1 — 2?yi+1 + 2. То же самое для шага mV:xi+1 = xi; yi+1 = yi — 1; ?I+1 = ?I — 2?yi+1 + 1.