Алгоритм средней точки круга

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

Круг радиуса 23, нарисованный по алгоритму Брезенхэма.

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

Краткое содержание

Этот алгоритм рисует все восемь октантов одновременно, начиная с каждого кардинального направления (0 °, 90 °, 180 °, 270 °) и расширяет оба направления до ближайшего числа, кратного 45 ° (45 °, 135 °, 225 °, 315 °). ). Он может определить, где остановиться, потому что при y = x угол достиг 45°. Причина использования этих углов показана на рисунке выше: при увеличении x не пропускается и не повторяется значение x до тех пор, пока не достигнет 45°. Таким образом, во время while цикла x увеличивается на 1 с каждой итерацией, а y время от времени уменьшается на 1, никогда не превышая 1 за одну итерацию. Это изменяется при угле 45°, потому что это точка, где касательная равна подъему = пробегу . Тогда как подъем>бежать до и подниматься<бежать после.

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

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

Алгоритм

Цель алгоритма — аппроксимировать круг , более формально говоря, аппроксимировать кривую. $x^{2}+y^{2}=r^{2}$ использование пикселей; с точки зрения непрофессионала, каждый пиксель должен находиться примерно на одинаковом расстоянии от центра, как и определение круга. На каждом шаге путь расширяется за счет выбора соседнего пикселя, удовлетворяющего условию $x^{2}+y^{2}\leq r^{2}$ но максимизирует $x^{2}+y^{2}$. Поскольку пиксели-кандидаты являются соседними, арифметика для вычисления последнего выражения упрощается и требует только битовых сдвигов и сложений. Но можно сделать упрощение, чтобы понять битовый сдвиг. Имейте в виду, что битовый сдвиг двоичного числа влево аналогичен умножению на 2. Следовательно, битовый сдвиг радиуса влево дает только диаметр , который определяется как радиус, умноженный на два.

Этот алгоритм начинается с уравнения окружности . Для простоты предположим, что центр круга находится в точке $(0,0)$. Для начала рассмотрим только первый октант и нарисуем кривую, которая начинается в точке $(r,0)$ и продолжается против часовой стрелки, достигая угла 45°.

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

Из уравнения окружности получается преобразованное уравнение $x^{2}+y^{2}-r^{2}=0$, где $r^{2}$ вычисляется только один раз во время инициализации.

Пусть точки на окружности представляют собой последовательность координат вектора точки (в обычном базисе). Очки нумеруются в соответствии с порядком их выпадения, при этом $n=1$ отнесен к первой точке $(r,0)$.

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

${\begin{aligned}x_{n}^{2}+y_{n}^{2}=r^{2}\end{aligned}}$

Это можно переставить следующим образом:

${\begin{aligned}x_{n}^{2}=r^{2}-y_{n}^{2}\end{aligned}}$

И аналогично по следующему пункту:

${\begin{aligned}x_{n+1}^{2}=r^{2}-y_{n+1}^{2}\end{aligned}}$

Поскольку для первого октанта следующая точка всегда будет как минимум на 1 пиксель выше последней (но также не более чем на 1 пиксель выше для сохранения непрерывности), верно следующее:

${\begin{aligned}y_{n+1}^{2}&=(y_{n}+1)^{2}\\&=y_{n}^{2}+2y_{n}+1\end{aligned}}$

${\begin{aligned}x_{n+1}^{2}=r^{2}-y_{n}^{2}-2y_{n}-1\end{aligned}}$

Итак, переработайте уравнение следующей точки в рекурсивное, заменив $x_{n}^{2}=r^{2}-y_{n}^{2}$:

${\begin{aligned}x_{n+1}^{2}=x_{n}^{2}-2y_{n}-1\end{aligned}}$

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

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

Инициализация термина ошибки получается из смещения в ½ пикселя в начале. До пересечения с перпендикулярной линией это приводит к накопленному значению $r$ в термине ошибки, так что это значение используется для инициализации.

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

Вариант с целочисленной арифметикой

Как и в случае с линейным алгоритмом Брезенхема , этот алгоритм можно оптимизировать для вычислений на основе целых чисел. Из-за симметрии, если можно найти алгоритм, который вычисляет пиксели только для одного октанта, пиксели можно отразить, чтобы получить весь круг.

Мы начинаем с определения ошибки радиуса как разницы между точным представлением круга и центральной точкой каждого пикселя (или любой другой произвольной математической точки на пикселе, при условии, что она одинакова для всех пикселей). Для любого пикселя с центром в $(x_{i},y_{i})$, ошибка радиуса определяется как:

$RE(x_{i},y_{i})=\left\vert x_{i}^{2}+y_{i}^{2}-r^{2}\right\vert$

Для ясности эта формула для круга выводится в начале координат, но алгоритм можно изменить для любого места. Полезно начать с пункта $(r,0)$ на положительной оси X. Поскольку радиус будет целым числом пикселей, очевидно, что ошибка радиуса будет равна нулю:

$RE(x_{i},y_{i})=\left\vert x_{i}^{2}+0^{2}-r^{2}\right\vert =0$

Поскольку он начинается в первом положительном октанте против часовой стрелки, он будет двигаться в направлении наибольшего перемещения , направлении Y, поэтому ясно, что $y_{i+1}=y_{i}+1$. Кроме того, поскольку это касается только этого октанта, значения X имеют только два варианта: остаться такими же, как на предыдущей итерации, или уменьшиться на 1. Можно создать переменную решения, которая определяет, верно ли следующее:

$RE(x_{i}-1,y_{i}+1)<RE(x_{i},y_{i}+1)$

Если это неравенство выполнено, то постройте график $(x_{i}-1,y_{i}+1)$; если нет, то постройте $(x_{i},y_{i}+1)$. Итак, как определить, выполняется ли это неравенство? Начните с определения ошибки радиуса:

${\begin{aligned}RE(x_{i}-1,y_{i}+1)&<RE(x_{i},y_{i}+1)\\\left\vert (x_{i}-1)^{2}+(y_{i}+1)^{2}-r^{2}\right\vert &<\left\vert x_{i}^{2}+(y_{i}+1)^{2}-r^{2}\right\vert \\\left\vert (x_{i}^{2}-2x_{i}+1)+(y_{i}^{2}+2y_{i}+1)-r^{2}\right\vert &<\left\vert x_{i}^{2}+(y_{i}^{2}+2y_{i}+1)-r^{2}\right\vert \\\end{aligned}}$

Функция абсолютного значения не помогает, поэтому возведите в квадрат обе стороны, поскольку квадрат всегда положителен:

${\begin{aligned}\left[(x_{i}^{2}-2x_{i}+1)+(y_{i}^{2}+2y_{i}+1)-r^{2}\right]^{2}&<\left[x_{i}^{2}+(y_{i}^{2}+2y_{i}+1)-r^{2}\right]^{2}\\\left[(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})\right]^{2}&<\left[x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right]^{2}\\\left(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right)^{2}+2(1-2x_{i})(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})^{2}&<\left[x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right]^{2}\\2(1-2x_{i})(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})^{2}&<0\\\end{aligned}}$

Поскольку x > 0, член $(1-2x_{i})<0$, поэтому деление дает:

${\begin{aligned}2\left[(x_{i}^{2}+y_{i}^{2}-r^{2})+(2y_{i}+1)\right]+(1-2x_{i})&>0\\2\left[RE(x_{i},y_{i})+Y_{\text{Change}}\right]+X_{\text{Change}}&>0\\\end{aligned}}$

Таким образом, критерий принятия решения меняется с использования операций с плавающей запятой на простое сложение, вычитание и битовый сдвиг целых чисел (для операций умножения на 2). Если ⁠ $2(RE+Y_{\text{Change}})+X_{\text{Change}}>0$⁠ , затем уменьшите значение x . Если ⁠ $2(RE+Y_{\text{Change}})+X_{\text{Change}}\leq 0$⁠ , то сохраните то же значение x . Опять же, отражая эти точки во всех октантах, получается полный круг.

Мы можем сократить вычисления, вычисляя только дельту между значениями этой формулы решения на основе ее значения на предыдущем шаге. Начнем с присвоения ⁠ $E$⁠ как ⁠ $3-2r$⁠ что является начальным значением формулы в ⁠ $(x_{0},y_{0})=(r,0)$⁠ , то как указано выше на каждом шаге, если ⁠ $E>0$⁠ мы обновляем его как ⁠ $E=E+2(5-2x+2y)$⁠ (и уменьшить X ), в противном случае ⁠ $E=E+2(3+2y)$⁠ затем увеличьте Y, как обычно.

Метод Джеско

Алгоритм уже в значительной степени объяснен, но есть и дальнейшие оптимизации.

Новый представленный метод справляется всего с 5 арифметическими операциями на шаг (для 8 пикселей) и поэтому лучше всего подходит для низкопроизводительных систем. В операции «если» проверяется только знак (положительный? Да или Нет) и происходит присвоение переменной, что также не считается арифметической операцией. Инициализация в первой строке (сдвиг на 4 бита вправо) сделана только для красоты и не особо нужна.

Таким образом, мы получаем счетные операции внутри основного цикла:

1. Сравнение x >= y (считается вычитанием: x - y >= 0 )
2. у=у+1 [у++]
3. т1 + у
4. т1 - х
   1. Сравнение t2 >= 0 НЕ учитывается, поскольку никаких действительных арифметических действий не происходит. В представлении переменных с дополнением до двух необходимо проверять только знаковый бит.
5. х=х-1 [х--]

Операций: 5

t1 = r / 16
x = r
y = 0
Repeat Until x < y
    Pixel (x, y) and all symmetric pixels are colored (8 times)
    y = y + 1
    t1 = t1 + y
    t2 = t1 - x
    If t2 >= 0
        t1 = t2
        x = x - 1

Рисование неполных октантов

Приведенные выше реализации всегда рисуют только полные октанты или круги. Чтобы нарисовать только определенную дугу под углом $\alpha$ под углом $\beta$, алгоритму необходимо сначала вычислить $x$ и $y$ координаты этих конечных точек, где необходимо прибегнуть к тригонометрическим или корневым вычислениям (см. Методы вычисления квадратных корней ). Затем алгоритм Брезенхэма запускается по всему октанту или кругу и устанавливает пиксели только в том случае, если они попадают в желаемый интервал. После завершения этой дуги алгоритм может быть завершен преждевременно.

Если углы заданы как наклоны , то ни тригонометрия, ни квадратные корни не нужны: просто проверьте, что $y/x$ находится между желаемыми склонами.

Обобщения

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

Внешние ссылки

• Рисование кругов - статья о рисовании кругов, которая переходит от простой схемы к эффективной.
• Алгоритм средней точки круга на нескольких языках программирования