Комп'ютерна графіка

Галузь знань: 12 Інформаційні технології
Спеціальність: 121 Інженерія програмного забезпечення
Освітня програма: Програмна інженерія

Викладач: доцент Шкільняк Оксана Степанівна (лекції, лабораторні заняття)

Викладається: в 8-му семестрі бакалаврату.
Загальний обсяг: 144 год, з яких:
  • Лекції – 34 год.
  • Лабораторні роботи – 34 год.
  • Самостійна робота – 76 год.

Мета та завдання дисципліни

Мета та завдання дисципліни – детальне вивчення алгоритмів обчислювальної геометрії як базового апарату комп'ютерної графіки.

Предмет дисципліни

Предмет навчальної дисципліни Комп'ютерна графіка включає в себе розгляд низки різноманітних алгоритмів обчислювальної геометрії для задач опуклості, перетину, геометричного пошуку, близькості, оптимізації.

В результаті вивчення навчальної дисципліни студент повинен
знати:
  • постановку різних типів задач обчислювальної геометрії та основні підходи і методи для їх розв'язання.
вміти:
  • застосовувати оптимальний алгоритм при розв'язанні задач обчислювальної геометрії,
  • правильно впізнавати задачі обчислювальної геометрії в постановках задач комп'ютерної графіки,
  • за необхідності будувати власні алгоритми, що базуються на модифікації відомих технік і обґрунтовувати їх складність.

Вимоги до знань та вмінь

Для вивчення курсу Комп'ютерна графіка студент повинен прослухати наступні курси:
  • дискретна математика,
  • математичний аналіз,
  • алгебра та геометрія,
  • програмування,
  • алгоритми та складність,
  • теорія алгоритмів та математична логіка,
  • об'єктно-орієнтоване програмування.

Програма курсу

Змістовий модуль 1: Геометричний пошук.

Тема 1: Вступ до предмету. Основні означення та структури даних.
  • Напрямки зображувальної інформації та комп'ютерної графіки.
  • Основні означення.
  • Основні класи і типи задач та застосування обчислювальної геометрії.
  • Структури даних: множини, списки, черги, дерево відрізків, реберні списки з подвійними зв'язками.
  • Метод плоского замітання.
Тема 2: Поняття геометричного пошуку. Основні моделі геометричного пошуку.
  • Основні означення.
  • Застосування методу векторного домінування.
  • Застосування методу локусів.
  • Моделі геометричного пошуку.
  • Задача про приналежність простому многокутнику.
  • Задача про приналежність опуклому многокутнику.
Тема 3: Задачі локалізації точки.
  • Локалізація точки на планарному розбитті.
  • Метод смуг.
  • Метод ланцюгів.
  • Регуляризація графа у методі ланцюгів.
  • Метод деталізації триангуляції.
  • Метод трапецій.
Тема 4: Задачі регіонального пошуку.
  • Задача регіонального пошуку.
  • Основні типи дій.
  • Двовимірний випадок: метод 2-d дерева, метод дерева регіонів та його покращення за допомогою техніки fractional cascading.
  • Регіональний пошук у просторах вищих розмірностей.
Модульна контрольна робота 1

Змістовий модуль 2: Побудова опуклої оболонки.

Тема 5: Задача побудови опуклої оболонки. Метод Грехема. Метод Джарвіса.
  • Опуклі оболонки.
  • Основні поняття.
  • Застосування.
  • Постановка та схема розв'язання основних задач.
  • Методи Грехема та Джарвіса побудови опуклої оболонки, їх недоліки та вдосконалення: метод Чана.
Тема 6: Швидкі методи побудови опуклої оболонки.
  • Алгоритм швидкої побудови опуклої оболонки на основі ідеї швидкого сортування Швидкобол (QuickHull).
  • Методи типу "розподіляй та владарюй", алгоритм злиття Шеймоса.
Тема 7: Динамічні методи побудови опуклої оболонки.
  • Динамічні алгоритми побудови опуклої оболонки.
  • Відкриті та закриті алгоритми.
  • Відкритий алгоритм Препарата.
  • Динамічна підтримка опуклої оболонки.
  • Алгоритм апроксимації опуклої оболонки.
  • Опукла оболонка простого многокутника.
Тема 8: Побудова опуклої оболонки в 3D.
  • Алгоритми побудови опуклої оболонки в тривимірному просторі.
  • Метод "загортання подарунку".
  • Алгоритм типу "розподіляй та владарюй".
  • Рандомізований інкрементний алгоритм.
  • Опуклі оболонки вищих розмірностей.
Модульна контрольна робота 2

Змістовий модуль 3: Близькість та перетин.

Тема 9: Постановка основних задач. Пошук найближчої пари методом "розподіляй та владарюй".
  • Основні задачі близькості та їх застосування:
    • найближча пара,
    • найближчий сусід,
    • k найближчих сусідів,
    • усі найближчі сусіди,
    • евклідове мінімальне кістякове дерево,
    • тріагуляція.
  • Пошук найближчої пари методом «розподіляй та владарюй»: одновимірний і двовимірний випадки.
Тема 10: Діаграма Вороного. Властивості та побудова.
  • Означення та властивості діаграми Вороного. Застосування.
  • Методи побудови діаграми Вороного: простий, інкрементний та Форчуна.
  • Метод "розподіляй та володарюй".
  • Алгоритм побудови розділяючого ланцюга.
  • Розв'язання задач на близькість за допомогою діаграми Вороного.
  • Узагальнення діаграми Вороного.
Тема 11: Триангуляція Делоне.
  • Триангуляція Делоне, її властивості та застосування.
  • Алгоритми триангуляції Делоне: метод заміни ребра, інкрементний, підхід "розподіляй та владарюй", замітаючої оболонки.
  • Зв'язок триангуляції Делоне, діаграми Вороного і опуклої оболонки множини точок.
Тема 12: Задачі перетину.
  • Задачі перетину та області їх застосування.
  • Постановка задач перетину відрізків.
  • Перевірка перетину простих многокутників та простоти многокутника.
  • Пошук перетинів відрізків методом плоского замітання.
  • Перетин півплощин.
  • Знаходження перетину опуклих многокутників.
  • Пошук ядра многокутника.
Модульна контрольна робота 3

Рекомендована література

Основна:

  1. Ф. Препарата, М. Шеймос. Вычислительная геометрия: введение. – М.: Мир, 1989.
  2. А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.
  3. В.М. Терещенко, І.В. Кравченко, А.В. Анісімов. Основні алгоритми обчислювальної геометрії. – К., 2002.
  4. S.L. Devadoss, J. O'Rourke. Discrete and Computational Geometry. Princeton University Press, 2011.
  5. M. de Berg, O. Cheong, M. van Kreveld, M. Overmars. Computational Geometry: Algorithms and Applications. 3rd edition. – Springer, 2008.

Додаткова:

  1. J. O'Rourke. Computational Geometry in C. Cambridge University Press, Second Edition, 1998.
  2. D.M. Mount. Lecture notes for the course CMSC 754 Computational Geometry.
  3. D.A. Sinclair. S-hull: a fast radial sweep-hull routine for Delaunay triangulation.
  4. М. Ласло. Вычислительная геометрия и компьютерная графика на C++. – М.: Бином, 1997.