Растровые преобразования окружности и эллипса

 

Существует несколько очень простых, но не эффективных способов преобразования окружностей в растровую форму. Например, рассмотрим для простоты окружность с центром в начале координат. Ее уравнение записывается как x2 + y2 = R2. Решая это уравнение относительно y, получим y = ± .

 

Чтобы изобразить четвертую часть окружности, будем изменять x с единичным шагом от 0 до R и на каждом шаге вычислять y. Вторым простым методом растровой развертки окружности является использование вычисление y по формулам x = R cos α, y = R sin α при пошаговом изменении угла α от 0 до 90 градусов.

 

Для упрощения алгоритма растровой развёртки стандартной окружности можно воспользоваться её симметрией относительно координатных осей и прямых y = ± x; в случае, когда центр окружности не совпадает с началом координат, эти прямые необходимо сдвинуть параллельно так, чтобы они прошли через центр окружности. Тем самым достаточно построить растровое представление для 1/8 части окружности, а все оставшиеся точки получить симметрией.

 

Рассмотрим участок окружности из второго октанта x Є [0, R/ ]. Далее опишем алгоритм Брезенхейма для этого участка окружности.

На каждом шаге алгоритм выбирает точку Pi (xi, yi), которая является ближайшей к истинной окружности. Идея алгоритма заключается в выборе ближайшей точки при помощи управляющих переменных, значения которых можно вычислить в пошаговом режиме с использованием небольшого числа сложений, вычитаний и сдвигов.

Рассмотрим небольшой участок сетки пикселов, а также возможные способы (от A до E) прохождения истинной окружности через сетку.

Предположим, что точка Pi-1была выбрана как ближайшая к окружности при x = xi-1. Теперь найдем, какая из точек (Si или Ti) расположена ближе к окружности при x = xi-1 + 1.

 

Заметим, что ошибка при выборе точки Pi (xi, yi) была равна D(Pi) = (xi2+ yi2) – R2.

Запишем выражение для ошибок, получаемых при выборе точки Si или Ti:

D(Si) = [(xi-1+ 1)2 + (yi-1)2] – R2;

D(Ti) = [(xi-1+ 1)2 + (yi-1 – 1)2] – R2.

 

Если | D(Si) | ≥ | D(Ti) |, то Ti ближе к реальной окружности, иначе выбирается Si.

Введем di = | D(Si) | – | D(Ti) |.

Ti будет выбираться при di ≥ 0, в противном случае будет устанавливаться Si.

 

Опуская алгебраические преобразования, запишем di и di+1 для разных вариантов выбора точки Si или Ti. D1 = 3 – 2 R.

Если выбирается Si (когда di < 0), то di+1 = di + 4 xi-1 + 6.

Если выбирается Ti (когда di ≥ 0), то di+1 = di + 4 (xi-1 – yi-1) + 10.

Существует модификация алгоритма Брезенхейма для эллипса.