Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






 

 
 

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

 

 

Рис. 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: ( - снаружи)

( - снаружи)

 

.

 

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

 

.

 

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


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.008 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал