Мета завдання - отримання навичок роботи з геометричними об'єктами в дво- і тривимірному просторах, поняття про морфірованія геометричних об'єктів, навичок найпростішої візуалізації даних за допомогою OpenGL.
Потрібно створити програму, що дозволяє здійснювати Морфірованіє дво- і тривимірних об'єктів певної форми.
Рис.1 Приклади морфірованія в дво- і тривимірному просторах.
Ви можете завантажити приклад реалізації завдання в тривимірному просторі.
пропонований алгоритм
Ми наведемо можливу реалізацію для плоских опуклих фігур. Алгоритм очевидно узагальнюється для випадку тривимірних фігур.
Детальний опис алгоритму можна переглянути в документації до завдання статті.
Розглянемо процес морфірованія опуклою Фігури А в опуклу Фігуру B.
Нехай морфинг проводиться протягом проміжку часу [0,1]. Необхідно вказати для кожного моменту часу t з [0,1] фігуру AB (t) таку, що AB (0) = A. AB (1) = B. причому зміна AB з плином часу - плавне.
Етап I. Створення описують фігур.
Через межі фігури А проводяться прямі - назвемо їх обмежують прямими. Фігура, обмежена цими прямими - A ''.
Проводиться паралельний перенос обмежують прямих таким чином, щоб A '' була мінімальною фігурою, що містить фігуру B (Рис. 2). Паралельний перенос граней окремо показаний на Ріс.2a, 2b, 2c. На Рис. 2d показаний результат: початкова фігура "описала" кінцеву. Якщо виробляти перенесення протягом кінцевого проміжку часу, отримаємо морфинг А в А '':
Аналогно створюється образ B '' фігури B. містить фігуру А. і морфинг B '= B' (t). Побудова образу показано на Рис. 3a-d.
Рис.2 Створення описують фігур.
Рис.3 Створення описують фігур.
Етап II. Морфірованіє.
Для того, щоб побудувати безперервне Морфірованіє фігур A і B один в одного, одночасно проводиться морфинг A в A 'і B' в B. Для кожного t з [0,1] будується фігура AB '(t). що є перетином A '(t) і B' (t). Процес отримання проміжних фігур показаний на Рис. 4а. Результат показаний на риc. 4b.
Рис.4а Процес морфинга.
Ріс.4b Процес морфинга.
AB '(0) = A
AB '(1) = B
AB змінюється плавно з плином часу
Детальний опис алгоритму для тривимірного випадку
Примітка: людям, охочим поупражнять розум лінійної алгеброю, рекомендується пропустити цей розділ. Для інших докладно описується, як вирішувати задачу.
Крок 1. Побудова описують фігур.
Припустимо, що нормалі граней фігури А спрямовані назовні, будемо називати полупространство щодо межі (або площини, що містить грань) фігури А позитивним (P + (a)), якщо нормаль грані спрямована в це полупространство.
Задамося дозволом морфинга (кількістю проміжних фігур між A і B) - N.
Візьмемо грань фігури А. позначимо площину, її містить, a. Обчислимо мінімальний вектор d. такий що фігури А і B будуть цілком лежати по один бік від межі a '. отриманої з a шляхом зсуву на d.
Серед всіх вершин фігури В знайдемо вершину M, найбільш віддалену від площини a і знаходиться в P + (a). Проекція вектора з довільної точки a в M на нормаль a буде шуканим вектором d.
Позначимо площину, отриману з a шляхом додавання до неї d * (i / N). як a (i).
Повторимо крок 1 для всіх граней фігур А. Безліч отриманих граней для кожного i позначимо A (i).
Для фігури B повторимо ту ж саму процедуру, за винятком: позначення b (i) для граней фігури B означатиме b + d * (N-i / N).
Крок 2. Генерація морфинга.
Для отримання i -го кроку морфинга необхідно знайти фігуру, що обмежується множинами площин A (i) і B (i). Об'єднання цих множин назвемо C (i).
Знайдемо безліч Q 'точок, де перетинаються три або більше граней з С (i).
Отримати з Q 'безліч Q шляхом відкидання точок, що знаходяться в позитивному напівпросторі хоча б однієї з площин з C (i).
Сформуємо межі проміжної фігури з точок Q.
Для кожної площині з C (i) знайдемо точки з Q. належать їй (відстань від площини до точки дорівнює нулю). Ці точки стануть вершинами межі.
Занумеруем точки так, щоб вони утворили опуклий багатокутник. Виберемо вектор b. з'єднує дві довільно вибрані точки A і B з розглянутого набору. Позначимо n - нормаль до площини, якій належать точки набору (площину можна знайти по будь-яким трьом точкам набору). Нумерацію точок набору проведемо відповідно до кута, на який потрібно повернути b навколо A. щоб площина, що проходить через n і q. включила відмінну від A і B точку С з набору, тобто між векторами b і c = AC. Примітка: при нумерації майте на увазі, що потім вам знадобиться знайти нормаль отриманої межі.
Примітка: вирішується на етапі 3 завдання - суть знаходження випулой оболонки для безлічі точок Q. Існують більш витончені алгоритми вирішення цього завдання. Реалізація подібних алгоритмів - привід для отримання бонусу.
обов'язкова частина
Обов'язкова частина передбачає реалізацію морфірованія опуклих багатокутників в двовимірному просторі. У програмі є жорстко певні початковий і кінцевий багатокутники. За командою користувача запускається процес морфірованія.
Процес морфірованія повинен бути добре видно на екрані - швидкість процесу повинна бути розумною.
Вихідна і кінцева фігури повинні істотно відрізнятися: різну кількість вершин, ребер і т.п.
Замість плоских фігур (або додатково до них) можна реалізувати Морфірованіє в тривимірному просторі - за цей варіант дається більшу кількість балів. Візуалізація процесу проводиться із застосуванням бібліотеки OpenGL.
Додаткова частина
Нижче наведені можливості, за реалізацію яких можна отримати додаткові бали.
Управління ходом морфірованія: кнопки вперед, назад, призупинити, зробити один крок морфірованія.
Зчитування моделей багатокутників або багатогранників з файлу.
Формат файлу для двовимірного випадку:
У кожному рядку зберігається розділені пропуском координати вершин. Номер вершини збігається з номером рядка. Вершини нумерується за годинниковою стрілкою. Координати вершини - дійсні числа, знаходяться в діапазоні [-1,1].
Формат файлу для тривимірного випадку:
MESH_FILE. =
MESH_VERTEX_LIST <>
MESH_FACE_LIST <>
>
Примітка: в описі символ <и лексемы MESH_VERTEX_LIST, MESH_FACE_LIST нужно рассматривать как строковые константы. - целое неотрицательное число, - вещественное число в диапазоне [-1,1].
Блендінг кольору або текстури. Блендінг кольору - поступова зміна кольору в процесі морфірованія однієї фігури в іншу. Блендінг текстури: на вихідну і цільову моделі багатогранників накладаються текстури. Текстура проміжних моделей морфинга вдає із себе суміш текстур вихідної та кінцевої моделей, отриману засобами мультитекстурирования OpenGL (див. Матеріали для виконання завдання).
Приклади моделей багатокутників і багатогранників:
оформлення
Оформлення не відрізняється від звичайного.
ZIP-архів вихідних текстів і виконуваними файлами, названий за схемою GZV_nnnnnnnn.zip (де G - остання цифра номера групи, Z - номер завдання, V - номер версії завдання, nnnnnnnn - номер студентського квитка) надсилайте на [email protected]. msu.su
Наприклад, студент 206 групи з номером студентського квитка 06529042, який здає оновлену (другу) версію програми по другому завданням, повинен надіслати архів з ім'ям 622_06529042.zip.
Не забудьте покласти в архів файл readme.txt. У файлі описати інтерфейс програми (алгоритм роботи з програмою, пункти меню, керуючі клавіші)
Результати роботи
Результати дивіться в інтернеті і / або на стенді біля кімнати 703.
Примітки
- Завдання виконується строго індивідуально. За спільну роботу або обмін шматками коду ставиться -5 балів всім учасникам, якщо факт командної роботи не було зазначено в readme.txt завдань.
- Рекомендується написання програми під сімейство ОС Windows. Написання під інші операційні системи небажано і може викликати затримки з перевіркою таких робіт.