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

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

Алгоритмы взяты из прекрасной книги
П.В.Вельтмандер «Машинная графика»

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


1 Алгоритм Брезенхема

Для простоты и без ограничения общности рассмотрим генерацию 1/8 окружности, центр которой лежит в начале координат. Остальные части окружности могут быть получены последовательными отражениями (использованием симметрии точек на окружности относительно центра и осей координат).

Окружность с центром в начале координат описывается уравнением:

X 2 + Y 2 = R 2

Алгоритм Брезенхема пошагово генерирует очередные точки окружности, выбирая на каждом шаге для занесения пиксела точку растра Pi(Xi, Yi), ближайшую к истинной окружности, так чтобы ошибка:

Ei(Pi) = (Xi 2 + Yi 2 ) — R 2

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

Рассмотрим генерацию 1/8 окружности по часовой стрелке, начиная от точки X=0, Y=R.

Проанализируем возможные варианты занесения i+1-й точки, после занесения i-й.

При генерации окружности по часовой стрелке после занесения точки (Xi, Yi) следующая точка может быть (см. рис. 0.1а) либо Pg = (Xi+1, Yi) — перемещение по горизонтали, либо Pd = (Xi+1, Yi-1) — перемещение по диагонали, либо Pv = (Xi, Yi-1) — перемещение по вертикали.

Для этих возможных точек вычислим и сравним абсолютные значения разностей квадратов расстояний от центра окружности до точки и окружности:

| Dg |

=

| (X+1) 2

+

Y 2

R 2 |

| Dd |

=

| (X+1) 2

+

(Y-1) 2

R 2 |

| Dv |

=

| X 2

+

(Y-1) 2

R 2 |

Выбирается и заносится та точка, для которой это значение минимально.

Выбор способа расчета определяется по значению Dd. Если Dd 0, то диагональная точка вне окружности. Это варианты 5-7. И, наконец, если Dd = 0, то диагональная точка лежит точно на окружности. Это вариант 4. Рассмотрим случаи различных значений Dd в только что приведенной последовательности.

Случай Dd

Здесь в качестве следующего пиксела могут быть выбраны или горизонтальный — Pg или диагональный — Pd.

Для определения того, какой пиксел выбрать Pg или Pd составим разность:

di

=

| Dg | — | Dd | =

| (X+1) 2 + Y 2 — R 2 | — | (X+1) 2 + (Y-1) 2 — R 2 |

И будем выбирать точку Pg при di Ј 0, в противном случае выберем Pd.

Рассмотрим вычисление di для разных вариантов.

Для вариантов 2 и 3:

Dg і 0 и Dd

di = (X+1) 2 + Y 2 — R 2 + (X+1) 2 + (Y-1) 2 — R 2 ;

Добавив и вычтя (Y-1) 2 получим:

di = 2 ·[(X+1) 2 + (Y-1) 2 — R 2 ] + 2·Y — 1

В квадратных скобках стоит Dd, так что

di = 2 ·(Dd + Y) — 1

Для варианта 1:

Ясно, что должен быть выбран горизонтальный пиксел Pg. Проверка компонент di показывает, что Dg Случай Dd > 0

Здесь в качестве следующего пиксела могут быть выбраны или диагональный — Pd или вертикальный Pv.

Для определения того, какую пиксел выбрать Pd или Pv составим разность:

si

=

| Dd | — | Dv | =

| (X+1) 2 + (Y-1) 2 — R 2 | — | X 2 + (Y-1) 2 — R 2 |

Если si Ј 0, то расстояние до вертикальной точки больше и надо выбирать диагональный пиксел Pd, если же si > 0, то выбираем вертикальный пиксел Pv.

Рассмотрим вычисление si для разных вариантов.

Для вариантов 5 и 6:

Dd > 0 и Dv Ј 0, так как диагональный пиксел вне, а вертикальный либо вне либо на окружности.

si = (X+1) 2 + (Y-1) 2 — R 2 + X 2 + (Y-1) 2 — R 2 ;

Добавив и вычтя (X+1) 2 получим:

si = 2 ·[(X+1) 2 + (Y-1) 2 — R 2 ] — 2·X — 1

В квадратных скобках стоит Dd, так что

si = 2 ·(Dd — X) — 1

Для варианта 7:

Ясно, что должен быть выбран вертикальный пиксел Pv. Проверка компонент si показывает, что Dd > 0 и Dv > 0, причем si > 0, так как диагональная точка больше удалена от окружности, т.е. по критерию si > 0 как и в предыдущих случаях следует выбрать вертикальный пиксел Pv, что соответствует выбору для вариантов 5 и 6.

Случай Dd = 0

Для компонент di имеем: Dg > 0 и Dd = 0, следовательно по критерию di > 0 выбираем диагональный пиксел.

С другой стороны, для компонент si имеем: Dd = 0 и Dv Ј 0 также выбираем диагональный пиксел.

Dd Ј 0 — выбор горизонтального пиксела Pg

di > 0 — выбор диагонального пиксела Pd

si Ј 0 — выбор диагонального пиксела Pd

si > 0 — выбор вертикального пиксела Pv

выбор диагонального пиксела Pd.

Выведем рекуррентные соотношения для вычисления Dd для (i+1)-го шага, после выполнения i-го.

1. Для горизонтального шага к Xi+1, Yi

2. Для диагонального шага к Xi+1, Yi-1

3. Для вертикального шага к Xi, Yi-1

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

Dd = (X+1) 2 + (Y-1) 2 — R 2 = 1 + (R-1) 2 — R 2 = 2*(1 — R)

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

В Приложении приведены подпрограмма V_BRcirc, реализующая описанный выше алгоритм и строящая дугу окружности во втором октанте с последующим симметричным занесением пикселов. Эта процедура может строить и 1/4 окружности. Подробнее см. текст Приложения. Там же приведена более короткая подпрограмма, строящая 1/8 окружности методом Мичнера [], (том 1, стр. 152). Остальная часть окружности строится симметрично.
0.15 Приложение 4. Процедуры генерации окружности

В данном приложении помещены процедуры генерации окружностей по алгоритму Брезенхема и Мичнера, а также программа T_Circle для тестирования данных процедур.

Источник

Построение плоских кривых. Выбор шага изменения аргумента. Алгоритм построения эллипса и окружности по методу средней точки.

Задача синтеза сложного динамического изображения. Этапы синтеза изображения. Последовательность и основное содержание.

Компьютерная графика – совокупность методов и средств преобразования информации в и из графической формы с помощью ЭВМ. Деловая графика (графики, диаграммы); научная графика (чертежи, технологии моделирования); иллюстративная графика (карты, генерации символов и результатов операций); инженерная графика (иллюстрации к текстам).

Методы – математические, алгоритмические.
Средства – технические, программные.

  1. Нижнего (базовые – точка, отрезок, эллипс);
  2. Среднего (плоские изображения с использованием готовых примитивов);
  3. Верхнего (трёхмерная графика, удаление невидимых линий, построение реалистических изображений).

  • I – интенсивность источника
  • β – коэффициент пропускания света через атмосферу модели представления: каркасная, поверхностная, объёмная
  • положение поверхности может быть задано радиус- вектором, ориентация – вектором нормали
  • положение наблюдателя (ось Z – направление взгляда)
  1. уравнение поверхности
  2. цвет
  3. оптические свойства (коэффициенты зеркального отражения, диффузионного отражения, пропускания, преломления) Изображение строим в картинной плоскости (расположена перпендикулярно взгляду), на ней задаётся окно обзора (ось z через центр окна обзора)

f = 30-50 Гц – частота генерации изображения

  1. Источник света (положение в пространстве, цвет, интенсивность)
  2. Для динамических объектов – уравнения воздействия, по которым можно рассчитать положение в интересующий момент времени
  3. Характеристики окружающей среды (цвет фона)
  4. Системы координат
  5. Положение картинной плоскости, размер окна обзора

Этапы синтеза изображения

  1. Разработка трёхмерной математической модели синтезируемой визуальной обстановки
  2. Задание: положения наблюдателя, картинной плоскости, размеров окна вывода, значений управляющих сигналов
  3. Определение операторов, осуществляющих пространственное перемещение объектов визуализации
  4. Преобразования координат объектов в координаты наблюдателя
  5. Отсечение объектов сцены по границам пирамиды отсечения (видимости)
  6. Вычисление двумерных перспективных проекций объектов сцены на картинную плоскость
  7. Удаление невидимых линий и поверхностей при заданном положении наблюдателя. Закрашивание и затенение видимых объектов сцены.
  8. Вывод полученного полутонового изображения на экран растрового дисплея.

Преобразования на плоскости. Вывод расчетных соотношений. Матрицы преобразований.

Преобразования на плоскости : (X, Y) → (X1, Y1)

Линейные преобразования – поверхность не вырождается в прямую, а прямая не вырождается в точку, сохраняется параллельность плоскостей и существуют обратные преобразования (detM≠0).

Если определитель матрицы преобразования отличен от нуля, то такое преобразование будет являться аффинным. При аффинном преобразовании плоскость не может вырождаться в линию или точ­ку, параллельные прямые переводятся в параллельные и всегда имеется обратное преобразование.

Для описания преобразований часто используется матричная форма. Однако в ней нельзя описать, например, перенос: приходится использовать однородные координаты [X,Y,W], где w – масштабный коэффициент. В двумерной графике W=1. Декартовы координаты x = X/W y = Y/W

Аффинное преобразование может быть представлено суперпозицией трех преобразований: переноса, масштабирования, поворота.

Масштабирование Однородное масштабирование – коэффициенты одинаковые, неоднородные – с разными коэффициентами. Если коэффициент меньше 1 – изображение уменьшается, точки перемещаются ближе к центру масштабирования. Если больше – увеличиваются, точки перемещаются дальше. Если коэффициент меньше 0 – изображение заодно отзеркаливается.

Поворот В матричной форме: поворот относительно начала координат

Коммутативность – независимость результата преобразований от порядка, в котором они происходят.

(X1 Y1 1) = (X Y 1) * M1 * M2 – если М1 можно умножить на М2, то в ОБЩЕМ случае, М2 умножить на М1 нельзя – в общем случае, преобразование коммутативностью не обладает. Доказательство коммутативности производится через перемножение матриц.

Операция1 Операция2
Перенос Перенос
Масштаб Масштаб
Поворот Поворот
Однородное масштабирование Поворот

Аддитивные и мультипликативные операции – типа сложение и умножение. Аддитивные: перенос-перенос и поворот-поворот. Чтобы найти итоговую матрицу такого поворота, достаточно сложить аргументы. Мультипликативные: перемножить аргументы

Перенос и поворот аддитивны, масштабирование мультипликативно.

Построение плоских кривых. Выбор шага изменения аргумента. Алгоритм построения эллипса и окружности по методу средней точки.

Дата добавления: 2019-01-14 ; просмотров: 529 ; Мы поможем в написании вашей работы!

Источник

Читайте также:  Трапеция дворников на короллу е120
Поделиться с друзьями
Объясняем