Растровая развертка окружностей
Четырехсторонняя симметрия
Рис. 3.7
Существует несколько простых, но не эффективных способов развертки окружности. Рассмотрим окружность с центром в начале координат:
.
Чтобы изобразить окружности, можно x с 0 до R и на каждом шаге вычислить y. Остальные четверти получаются симметричным отображением. Этот метод неэффективен, т.к. в него входят операции “ ” и “ ”. Более того, при значениях x близких к R в окружности появляются незаполненные промежутки. Можно было бы воспользоваться расчетом координат окружности, заданной в полярных координатах – , путем пошагового изменения от 00 до 900. Но недостатки остаются все те же.
Восьмисторонняя симметрия
Процесс преобразования окружностей в растровую форму можно улучшить, если полнее использовать симметричную окружности. Поэтому удобно вычислить значения окружности на дуге в 450, а потом симметрично отобразить их.
Алгоритм Брезенхэма для окружностей
Брезенхэм разработал пошаговый генератор дуг, который более эффективен, чем рассмотренные ранее. Необходимо сгенерировать только 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: ( - снаружи)
( - снаружи)
.
После некоторых математических выводов было получено:
.
если ( ) если ( )
Дата добавления: 2016-07-18; просмотров: 2155;