Растровая развертка окружностей

Четырехсторонняя симметрия

Рис. 3.7

Существует несколько простых, но не эффективных способов развертки окружности. Рассмотрим окружность с центром в начале координат:

.

Чтобы изобразить окружности, можно x с 0 до R и на каждом шаге вычислить y. Остальные четверти получаются симметричным отображением. Этот метод неэффективен, т.к. в него входят операции “ ” и “ ”. Более того, при значениях x близких к R в окружности появляются незаполненные промежутки. Можно было бы воспользоваться расчетом координат окружности, заданной в полярных координатах – , путем пошагового изменения от 0⁰ до 90⁰. Но недостатки остаются все те же.

Восьмисторонняя симметрия

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

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

Брезенхэм разработал пошаговый генератор дуг, который более эффективен, чем рассмотренные ранее. Необходимо сгенерировать только 1\8 часть окружности. Остальные части получаются путем отображения:

· 1-ой октант – отражение относительно y=x 1-го октанта;

· 2-ой квадрант – отражение относительно x=0 1-го квадранта;

· нижняя полуокружность – отражение относительно y=0 верхней полуокружности .

Рис. 3.8

Рассмотрим 1-ую четверть окружности с центром в начале координат. Начнем работу в т. x=0, y=R, окружность генерируется по часовой стрелке, y – монотонно убывающая функция аргумента x до т. .

Для любой заданной т. на окружности существует только 2 возможности выбрать следующий , наилучшим образом приближающий окружность.

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

Рис. 3.9

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

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

Рис. 3.10

Если , то ближе к окружности, чем .

Если , то ближе к окружности.

Введем упрощающую переменную :

.

Если

.

Для случаев 1,2: ( - внутри окружности)

( - внутри окружности)

.

Для случая 3: ( - внутри)

( - снаружи)

Для случаев 4,5: ( - снаружи)

( - снаружи)

.

После некоторых математических выводов было получено:

.

если ( ) если ( )