Лабораторна робота №5

Алгоритм Брезенхема для побудови кола

Мета роботи: освоїти побудову оціночних функцій для формування растрового представлення кола довільного радіуса, ознайомитись з основними етапами використання алгоритму Брезенхема для побудови кола

Постановка задачі

Дано: опис кола, який задано координатами центра кола (x₁;y₁) та довжиною радіуса R.

Необхідно: сформувати растрове представлення кола вказаного радіуса за допомогою алгоритму Брезенхема.

Теоретичні відомості

Існує декілька дуже простих, але не ефективних способів перетворення кіл в растрову форму. Наприклад, розглянемо для простоти коло з центром на початку координат. Її рівняння записується як x² + y² = R². Вирішуючи це рівняння відносно в, отримаємо:

y = ± .

Щоб змалювати четвертую частину кола, будемо змінювати x з одиничним кроком від 0 до R і на кожному кроці обчислювати y. Другим простим методом растрової розгортки кола є використання обчислень x і y по формулах x = R cosα, y = R sinα при покроковій зміні кута α від 0° до 90°.

Для спрощення алгоритму растрової розгортки стандартного кола можна скористатися його симетрією відносно координатних осей і прямих y = ± x; у випадку, коли центр кола не збігається з початком координат, ці прямі необхідно посунути паралельно так, щоб вони пройшли через центр кола. Тим самим достатньо побудувати растрове зображення для 1/8 частини кола, а решту точок отримати симетрією (див. Рис. 3.1).

Рис. 3.1. Восьмистороння симетрія.

Розглянемо ділянку кола з другого октанта x Є [0, R/ ]. Далі опишемо алгоритм Брезенхема для цієї ділянки кола. На кожному кроці алгоритм вибирає точку P_i (x_i, y_i), яка є найближчою до дійсного кола. Ідея алгоритму полягає у виборі найближчої точки за допомогою керуючих змінних, значення яких можна обчислити в покроковому режимі з використанням невеликого числа додавань, віднімань і зсувів.

Розглянемо невелику ділянку сітки пікселів, а також можливі способи (від т.A до т.E) проходження дійсного кола через сітку (Рис. 3.2). Припустимо, що точка P _i-1 була вибрана як найближча до кола при x = x _i-1. Тепер знайдемо, яка з точок (S _i або T _i) розташована ближче до кола при x = x _i-1 + 1.

Рис. 3.2. Варіанти проходження кола через растрову сітку.

Причому похибка при виборі точки P_i (x_i, y_i) дорівнює:

D(P_i) = (x_i ² + y_i ²) – R ².

Запишемо вираз для похибок, які отримуються в результаті вибору точки S_i або T_i:

D(S_i) = [(x_i-1+ 1)² + (y_i-1)²] – R²;

D(T_i) = [(x_i-1+ 1)² + (y_i-1 – 1)²] – R ².

Якщо | D(S_i) | ≥ | D(T_i) |, то T_i ближче до реального кола, в іншому випадку - вибирається S_i.

Введемо d_i = | D(S_i) | – | D(T_i) |. Тоді T_i буде вбиратись при d_i ≥ 0, в іншому випадку буде виставлятись S_i.

Далі запишемо d_i и d_{i+ 1} для різних варіантів вибору точки S_i або T_i.

D ₁ = 3 – 2 R.

Якщо вибирається S_i (коли d_i < 0), то d_{i+ 1} = d_i + 4 x_i-1 + 6.

Якщо вибирається T_i (коли d_i ≥ 0), то d_{i+ 1} = d_i + 4 (x_{i- 1} – y_{i- 1}) + 10.

Рис. 3.3. Блок-схема алгоритму Брезенхема для побудови растрового представлення кола.

Варіанти завдань до лабораторної роботи

Контрольні питання

1. В чому полягає основна ідея алгоритму Брезенхема для побудови растрового представлення кола?

2. Описати графічно основну ідею алгоритму Брезенхема для побудови кола.

3. Які переваги та недоліки алгоритму Брезенхема для побудови кола?

4. Чи накопичується помилка в процесі виконання алгоритму Брезенхема?

5. Скільки пік селів на растровому зображенні кола необхідно для обчислення його радіуса? Яка точність обрахунку радіуса?

6. Описати етапи виконання алгоритму Брезенхема для побудови кола.

Література

1. Роджерс Д.Алгоритмы машинной графики/ Д. Роджерс. – М.: Мир, 1989. – 230 с.

2. Фоли Дж., А. вэн Дэм Основы интерактивной машинной графики. – М.: Мир, 1985, том2. – 287 с.

Поиск по сайту: