Размещено на http://www.allbest.ru/

Міністерство освіти і науки, молоді та спорту України

Київський національний університет будівництва і архітектури

УДК 514.18

Автореферат

дисертації на здобуття наукового ступеня кандидата технічних наук

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

05.01.01 - Прикладна геометрія, інженерна графіка

Каленюк Олександр Сергійович

Київ 2011

Загальна характеристика роботи

Актуальність роботи. Сфера завдань деформаційного моделювання з кожним роком розширюється. Цьому сприяє як швидкий розвиток обчислювальної техніки, який дозволяє використання дедалі складніших алгоритмів для здійснення більш адекватного моделювання, так і постійний розвиток галузей науки та виробництва, де ці алгоритми застосовуються. На сьогодні алгоритми деформації геометричних об'єктів застосовуються як у спеціальних програмах для графічного процесора персонального комп'ютера, так і в системах автоматизованого проектування на потужних робочих станціях. Якщо для перших важливими критеріями є економія пам'яті і висока швидкість обчислення, то для других найважливішою є точність моделювання об'єктів та процесів, з якими вони працюють.

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

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

Зв'язок роботи з науковими програмами, темами, планами. Дисертаційна робота виконувалась у Національному технічному університеті України «КПІ» у відповідності з планом науково-дослідних робіт кафедри автоматизації проектування енергетичних процесів і систем, а також в рамках науково-дослідної роботи «Розробка процесу лазерно-дугового наплавлення та автоматизованої системи визначення його технологічних параметрів» (Тема № 2146-п).

Мета і завдання дослідження. Метою роботи є створення теоретичної та алгоритмічної бази для моделювання деформації точкових геометричних об'єктів.

Мета роботи реалізується вирішенням таких задач:

· дослідити існуючі методи моделювання деформації геометричних об'єктів;

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

· дослідити існуючі методи інтерполяції у контексті задачі побудови векторного поля деформації об'єкта;

· розробити спосіб інтерполяції, який дозволяє позбутися недоліків існуючих методів при моделюванні векторного поля деформації;

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

Об'єктом дослідження є процес деформації геометричних об'єктів.

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

Методи дослідження. Поставлені у роботі задачі розв'язувалися на основі методів нарисної, аналітичної та диференціальної геометрії, комп'ютерної графіки, чисельного аналізу, обчислювальних методів, теорії кривих та поверхонь, дискретного геометричного моделювання. Програмна реалізація методів виконувалася в середовищі програмування Borland Delphi та мовою Python 2.6.

Теоретичною базою досліджень стали роботи провідних вітчизняних та зарубіжних науковців:

· у галузі моделювання поверхонь складних форм та формування їх математичних моделей: Бадаєва Ю.І., Безьє П., Балюби І.Г., Дорошенка Ю.О., Кунса С.А., Куценка Л.М., Леуса В.А., Михайленка В.Є., Найдиша В.М., Обухової В.С., Павлова А.В., Підгорного О.Л., Скидана І.А., Федорова Є.С., Фергюсона Д., Фореста Р.;

· у галузі деформаційного моделювання: Бадаєва Ю.І., Дорошенка Ю.О., Зейделя Г-П., Терцопулоса Д., Йошизави Ш;

· у галузі апроксимації та наближення функцій: Алберга Дж., Алфельда П., Малоземова В.Н., Найдиша В.М., Найдиша А.В., Турчака Л.І.;

· у галузі геометричного моделювання та комп'ютерної графіки: Амерала Л., Бадаєва Ю.І., Гілоя В., Максимея І.В., Сазонова К.О., Фокса А., Пратта М.

Наукова новизна отриманих результатів. Фундаментом розв'язаного в дисертації завдання стали такі запропоновані наукові положення:

вперше:

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

· досліджено спосіб моделювання деформації геометричних об'єктів у векторному полі, побудованому поліноміальною інтерполяцією, середньозваженою інтерполяцією та за інтерполяційним методом Шепарда;

· розроблені спосіб локалізації інтерполяційного методу Шепарда на симплиціальному комплексі та відповідний спосіб екстраполяції.

удосконалено:

· спосіб симплексної вагової інтерполяції за рахунок узваження опорних функцій у лінійному базисі симплекса;

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

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

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

Практичне значення отриманих результатів підтверджується впровадженнями у підсистему моделювання радіоактивного забруднення водоносного шару із урахуванням річної амплітуди рівня ґрунтових вод, яка використовується в роботі «Радіоекологічний моніторинг в районі об'єкта «Укриття» Чорнобильської АЕС» Інституту проблем безпеки атомних електростанцій НАН України; у центральний програмний компонент системи створення інтерактивних програм «Qula», розробки ТОВ «Гештальт Консалтинг Груп», для забезпечення інтерактивної анімації графічних об'єктів; у ТОВ НПО «Мікротерм» при проведенні досліджень технічних характеристик приладів, що розробляються та випускаються з виробництва, а також при проведенні атестації обладнання для моделювання скалярного температурного поля у випробувальних камерах та його зміни у часі.

Особистий внесок здобувача. Основні результати отримані автором дисертації самостійно. У роботах, опублікованих у співавторстві з науковим керівником - к.т.н., доц. Сидоренко Ю.В., автором проведена формалізація та виконано розв'язання задач дослідження, здійснена програмна реалізація запропонованих методів. Особистий внесок здобувача полягає у: дослідженні властивостей обернено-квадратичної вагової інтерполяції [1, 2]; розробці способу зважування опорних функцій у симплексі, який зберігає неперервність і гладкість інтерполяційної функції на всьому симплиціальному комплексі [3]; дослідженні обчислювальної ефективності програмних реалізацій способів розв'язання СЛАР [5]; розробці рекурсивної інтерполяційної функції, яка узагальнює спосіб симплексної вагової інтерполяції на випадок функцій багатьох змінних [6]; дослідженні властивостей вагової інтерполяції у контексті задачі моделювання деформації геометричних об'єктів [7, 9, 10]; дослідженні способів зважування опорних функцій у симплексі у контексті їх обчислювальної ефективності [8, 11].

Апробація результатів дисертації. Основні положення та результати дисертаційної роботи доповідались та обговорювались на конференціях:

· Міжнародна конференція "Моделювання та дослідження стійкості динамічних систем" (Київ, 2007).

· X Всеукраїнська науково-практична конференція студентів, аспірантів та молодих вчених (Сєверодонецьк, 2007).

· Міжнародна науково-практична конференція "Геометричне моделювання та комп'ютерні технології: теорія, практика, освіта" (Харків, 2009).

· XI Міжнародна науково-практична конференція "Актуальні проблеми геометричного моделювання" (Мелітополь, 2009).

· VI кримська науково-практична конференція "Геометричне і комп'ютерне моделювання: енергозбереження, екологія, дизайн" (Симферополь, 2009).

· Міжнародна науково-практична конференція "Геометричне моделювання і комп'ютерний дизайн" (Одеса, 2010).

Публікації. За результатами наукових досліджень опубліковано 11 робіт. Основні результати дисертаційної роботи викладено в 6 друкованих працях у наукових фахових виданнях, які рекомендовано ВАК України, 1 з яких без співавторів.

Структура та обсяг дисертації. Дисертаційна робота складається зі вступу, чотирьох розділів, висновків, списку використаних джерел та одного додатку. Зміст досліджень викладений на 136 сторінках із застосуванням 52 пояснювальних рисунків та 4 таблиць. Список використаних джерел містить 121 найменування. Додаток викладений на 3 сторінках.

Основний зміст роботи

У вступі обґрунтована актуальність теми роботи, визначена наукова новизна та практична цінність отриманих результатів досліджень.

У першому розділі «Аналіз існуючих способів деформаційного моделювання геометричних об'єктів» розглядаються існуючі методи моделювання деформації геометричних об'єктів. Наведений аналіз переваг і недоліків зазначених методів та зроблені висновки про необхідність розробки локального способу моделювання деформацій геометричних об'єктів.

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

Методи моделювання процесів деформації широко використовуються у комп'ютерній графіці, а саме - у системах віртуальної реальності, кінематографі, різноманітних симуляторах, навчальних та розважальних програмах. Разом із тим, доступність та поширеність персональних ЕОМ зумовлює актуальність методів моделювання деформації у реальному часі. Такі методи часто мають невелику точність, хоча можуть бути успішно застосовані у навчальних та розважальних програмних продуктах.

Як для моделювання динамічних процесів, так і для моделювання геометричних об'єктів, що зазнали деформаційних змін, можуть застосовуватись геометричні перетворення.

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

Застосування принципу двоїстості до політканинних перетворень приводить до появи нового виду перетворень, який має назву політочкових перетворень. Базисом політочкових перетворень є скінченна множина точок, а об'єктом перетворень є пряма.

Результат політочкового перетворення залежить від способу завдання точок прообраза. Визначення оптимального способу завдання прообраза ускладнює задачу моделювання його деформації.

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

Якщо метод моделювання деформації не залежить від геометричних властивостей об'єкта, то одна точка простору x, яка належить множині об'єктів T, відображається в результаті кожної з деформацій об'єктів множини T в одну і ту ж саму точку x`. З цього можна зробити висновок, що такий метод моделювання визначає векторне поле векторів A(x)=x`-x на області, у якій він може бути в принципі застосований. У випадку політканинних перетворень, це весь простір, за винятком власне політкані. У випадку політочкових перетворень - це весь n-вимірний простір.

Якщо задано початковий точковий базис деформаційного перетворення і відповідний кінцевий базис, то таке векторне поле може бути побудоване інтерполяцією векторів переносу точок базису із першого стану у другий, визначених у точках початкового базису (рис. 1).

Рис. 1. Перетворення точкового об'єкта у точковому базисі і відповідне векторне поле

У другому розділі «Моделювання деформації геометричних об'єктів на площині» розглядається спосіб деформаційного моделювання геометричних об'єктів із використанням двовимірного інтерполяційного векторного поля деформації та розглядаються деякі способи побудови такого поля. Також пропонується спосіб вагової інтерполяції та екстраполяції функції двох змінних, наводиться алгоритм моделювання деформації точкового об'єкта, який використовує цей спосіб.

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

Багатовекторний каркас дозволяє з одного боку побудувати поле більш складного виду, а з другого боку керування побудовою такого поля значно ускладнюється, адже вид такого поля значною мірою залежить від кожного вектору каркасу. На рис. 2. показано, як передбачуваність перетворення втрачається із додаванням кількості точок базису.

Рис. 2. Приклад моделювання деформації кола у поліноміальному векторному полі, побудованому на 3-6-точковому базисі

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

Метод середньозваженої інтерполяції - це теж один із найпростіших і найпоширеніших методів інтерполяції функції багатьох змінних. Суть полягає у тому, що інтерполяційна функція розраховується як зважена сума значень функції у точках каркасу, де ваговими коефіцієнтами виступає обернена відстань від точки каркасу до розрахункової точки функції.

(1)

де yi - каркасне значення функції, - ваговий коефіцієнт такого виду:

(2)

де - відстань від точки каркасу до точки, в якій розраховується значення інтерполюючої функції.

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

А) Б) В)

Рис. 3. Моделювання деформації точкових об'єктів із використанням середньозваженої інтерполяції:

а) деформація кола у 4-точковому базисі і відповідне векторне поле;

б) деформація квадрата у 4-точковому базисі і відповідне векторне поле;

в) деформація квадрата у 12-точковому базисі

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

Цей спосіб може використовуватися там, де постановка задачі включає в себе достатньо деталізований каркас перетворення. Крім того, він може бути легко узагальнений на n-вимірний простір.

Метод Шепарда є певним поєднанням середньозваженої інтерполяції, та інтерполяції поліноміальної. Так, інтерполянт у цьому методі знаходиться зважуванням вагових функцій, які визначені для кожної точки каркасу, і мають вид поліномів. Таким чином вирішується проблема із тим, що при середньозваженій інтерполяції вектор поля при віддаленні від точок каркасу збігається до середнього арифметичного векторів каркасу, та, разом із тим, не втрачається можливість використовувати докладні багатоточкові каркаси.

У загальному випадку інтерполянт за методом Шепарда визначається як:

(3)

- опорні функції, - вагові коефіцієнти певної форми, N -кількість точок каркасу.

У даній роботі метод Шепарда реалізований із білінійними опорними функціями виду:

(4)

де x1, x2 - координати точки, a, b, c - коефіцієнти певного виду, який залежить від типу каркаса інтерполяції. У випадку побудови векторного поля ці коефіцієнти є векторами, опорні функції також будуть векторними.

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

Рис. 4. Порівняння середньозваженої інтерполяції і методу Шепарда у контексті задачі моделювання деформації

На рис. 4. показане порівняння результату моделювання деформації геометричного об'єкта із використанням векторного поля, побудованого за методом Шепарда, та результату аналогічного моделювання із використанням середньозваженої інтерполяції.

На рис. 5 наводиться приклад моделювання деформації у багатоточковому базисі, аналогічний наведеному на рис. 2. для поліноміальної інтерполяції.

Рис. 5. Приклад моделювання деформації кола із використанням метода Шепарда у 5-, 6- та 8-точковому базисі

Метод Шепарда дозволяє будувати векторні поля для базисів перетворення із довільним числом базисних точок. Разом із тим, інтерполяція за методом Шепарда є глобальною. Вигляд векторного поля залежить від кожного вектора каркасу, який означає, що відокремлення певної області і уточнення векторного поля введенням додаткових векторів каркасів у ній неможливе. Для побудови векторних полів складної конфігурації варто використовувати способи локальної інтерполяції.

Симплексна вагова інтерполяція - це спосіб отримати неперервну функцію, визначену у певному симплиціальному комплексі, на основі наперед заданих значень цієї функції у точках, що утворюють вершини симплексів. Під симплексом мається на увазі евклідів n-симплекс, тобто найменша опукла множина точок, яка включає в себе n+1 точок - вершин симплекса. 0-симплексом є точка, 1-симплексом - відрізок, 2-симплексом - трикутник тощо. Симплиціальним комплексом є така кінцева множина симплексів, у якій разом із кожним симплексом до комплексу входять всі її грані, а також кожні два симплекси комплексу або не перетинаються, або цей перетин є їх спільною гранню.

Симплексна вагова інтерполяція є локальним способом інтерполяції, тобто у кожному окремому симплексі її вид визначається окремо. Разом із тим, симплексна інтерполяція дозволяє отримати неперервну інтерполюючу функцію із гладкістю наперед заданого порядку. Розглянемо докладно задачу знаходження двовимірної симплексної вагової інтерполяційної функції на довільному точковому каркасі.

Нехай задана інтерполяційна сітка із базовими точками {xi,yi,zi}, де хi, yi, zi - довільні числа. Треба знайти таку інтерполюючу функцію F(x,y), що буде визначеною і неперервною на області, що утворюється опуклим багатогранником із вершинами у точках {xi, yi} та таку, що

F(xi, yi)=zi.

На будь-якій довільній множині чотирьох і більше точок у загальному положенні на R2 можна побудувати двовимірний симплиціальний комплекс, який буде повністю покривати опуклий багатогранник із вершинами у точках множини. Для кожної точки можна певним чином побудувати опорну функцію fi(x,y), яка буде визначеною і неперервною у всіх симплексах, що включають у себе точку {xi, yi} та для якої буде виконуватись

fi(xi, yi)=zi.

У кожному симплексі Sijk, що утворений точками {xi, yi}, {xj, yj} та {xk, yk} узагальнена вагова інтерполяційна формула матиме вигляд:

(5)

Кожна з опорних функцій має вигляд:

(6)

Коефіцієнти w(h), q(h) - довільні скалярні функції, що задовольняють умови:

, ,

визначені, неперервні і безперервно спадають при ; hij - відстань від точки {x,y} до відрізка, утвореного точками {xi, yi}, {xj, yj}; - відстань від проекції точки {x,y} на відрізок, утворений точками {xi, yi}, {xj, yj} до точки {xi, yi}.

Кінцевий вигляд функції, її властивості на області інтерполяції, крім визначеності та неперервності, цілком залежать від виду вагових коефіцієнтів w(h), q(h), та опорних функції fi(x, y).

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

моделювання деформація геометричний об'єкт

Рис. 6. Уточнення векторного поля деформації доданням векторів базису:

a) векторне поле побудоване на 6-точковому каркасі;

б) векторне поле побудоване на 6-точковому каркасі із внесенням додаткового вектора (7);

в) векторне поле побудоване на 6-точковому каркасі із внесенням двох додаткових векторів (7,8)

У третьому розділі, «Моделювання деформації геометричних об'єктів із використанням векторного поля деформації у багатовимірному просторі», розглядається спосіб деформаційного моделювання просторових геометричних об'єктів із використанням багатовимірного векторного поля деформації. Наводиться два способи узагальненої симплексної вагової інтерполяції функції багатьох змінних.

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

Векторне поле такого виду можна отримати, використовуючи як глобальні, так і локальні способи інтерполяції.

Спосіб моделювання деформації точкового об'єкта на базі векторного поля деформації, побудованого інтерполяцією векторів каркасу за методом Шепарда у n-вимірному просторі, можна отримати аналогічно до моделювання у двовимірному просторі.

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

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

Також, для того, щоб позбавити цей метод недоліків, притаманних глобальним методам, використовуються вагові функції із компактним носієм, але такий спосіб локалізації методу Шепарда найкраще працює на регулярному точковому каркасі. У випадку каркасу, побудованому множиною точок у загальному положенні, визначення оптимального Ri стає окремою задачею, отже, задача локалізації лишається відкритою.

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

Нехай на Rn заданий інтерполяційний каркас із N базових точок xi = {xi1, xi2, …, xin}, i=1..N, та значень функції у цих точках - yi. У точках xi визначені опорні функції fi(xx), неперервні в області інтерполяції, та такі, що fi(xi) = yi. Треба знайти таку інтерполюючу функцію F(x1, x2, …, xn), яка буде визначеною і неперервною на області, що утворюється опуклим багатогранником із вершинами у точках {xi1, xi2, …, xin}, та таку, що

F(xi1, xi2, …, xin) = yi.

Для будь-якого набору із n+1 точок у n-вимірному просторі можна побудувати n-симплекс. Набір із n+2 та більше точок дозволяє побудувати n-вимірний симплиціальний комплекс, який утворюватиме опуклий багатогранник з вершинами у заданих точках. Кожна точка простору лежить або за межами симплиціального комплексу, або в одному з симплексів, або на гранях симплексу, які також є симплексами порядку 0..(n-1).

Для точки x, що лежить в одному з m-симплексів комплексу - Sm, m=1..n - інтерполяційна функція визначається таким чином:

(7)

xk - проекції точки x на гіперплощину, яка утворюється точками (m-1)- симплексів - граней Sm;

k(h) - довільні скалярні функції, що визначені, неперервні, безперервно спадають при h>0 та відповідають такій умові:

(8)

Як видно з формули (7), функція Frec є рекурсивною. Функція F(x) визначена через Frec(x,x) задля того, аби показати, що хоча зважування на кожній ітерації відбувається по відстані від проекції на гіперплощину k-симплекса до проекції цієї ж проекції далі на гіперплощину (k-1)-симплекса - грані k-симплекса, значення опорних функцій на останній ітерації розраховується у початковій точці. Враховуючи, що проекція точки на 0-симплекс є тією ж самою точкою, що утворює 0-симплекс, можна стверджувати, що умова x=xi виконується тоді, коли симплекс Sm є 0-симплексом, тобто m=0.

Якщо точка x не лежить у жодному з m-симплексів комплексу, треба застосувати спосіб симплексної екстраполяції.

Визначимо порожню множину S елементів типу (Sx, r), де Sx - симплекс (включаючи 0-симплекс - точку), r - число.

Для кожного з m-симплексів комплексу визначимо m (m-1)-граней симплексів комплексу, при m=0..n-1. Знайдемо проекцію точки x на гіперплощину кожної грані, якщо m>0, або відстань до точки - 0-симплексу, якщо m=0. Якщо точка проекції лежить у симплексі, занесемо симплекс і відстань від точки x до ії проекції на симплекс у множину S.

Знайдемо такий елемент у множині S, що має найменший r серед елементів S. Для симплекса Sx такого елемента екстраполяційна функція розраховується за формулою:

(9)

xk - проекції точки x на гіперплощину, яка утворюється точками (m-1)- симплексів - граней Sm;

Такий спосіб інтерполяції зберігає властивості симплексної вагової інтерполяції функції двох змінних, а саме - неперервність, керованість вибором виду функцій вагових коефіцієнтів та опорних функцій; а також і гладкість певного порядку на Rn при виборі відповідних вагових коефіцієнтів та опорних функцій.

На практиці використовуються як симплексна вагова інтерполяція багатьох змінних, для моделювання деформації, поверхонь, скалярних полів тощо, так і інтерполяція функції однієї змінної для моделювання кривих шляхів, гладких поворотів (рис. 7) та ін.

Рис. 7. Приклади застосування симплексної вагової інтерполяції при програмуванні комп'ютерних ігор

Інтерполяційну функцію у симплексах можна модифікувати, щоб позбавитись від рекурсивної природи функції і відповідно швидкого зростання її розрахункової складності.

Модифікована формула виглядає таким чином:

(10)

-- опорні функції визначені і неперервні у всіх симплексах, які включають у себе точку xЇi, та для яких виконується .

-- вагові коефіцієнти, що можуть бути задані як довільні скалярні функції, визначені, неперервні і безперервно спадні при , що відповідають умові:

(11)

-- коефіцієнти лінійної комбінації ребер симплексу, що визначають точку xЇ у симплексі, розраховані для кожної і-ї вершини симплекса.

Аналогічно визначається відповідна екстраполяційна функція.

У четвертому розділі «Впровадження способу деформації геометричних об'єктів із використанням векторного поля деформації» розглядаються проблеми впровадження алгоритму деформаційного моделювання просторових геометричних об'єктів із використанням багатовимірного векторного поля деформації. Наводиться структура та інтерфейс розроблених підсистем моделювання об'єктів, результати роботи програмних продуктів.

Розроблена система моделювання деформації геометричних об'єктів складається із двох демонстраційних програм (рис. 8) та бібліотеки функцій, яка дозволяє створювати власні програмні продукти.

Рис. 8. Демонстраційні програми у складі програмної системи моделювання геометричних об'єктів

Демонстраційна програма SWI_Demo.exe дає змогу досліджувати та вивчати множину методів вагової інтерполяції, яка включає в себе метод середньозваженої інтерполяції, метод Шепарда, простий та модифікований спосіб симплексної вагової інтерполяції, використовуючи графічний інтерфейс користувача. Відкритий формат даних програми дозволяє включати її у склад більш складних систем. Отримані графіки, завдяки високій роздільній здатності, можуть використовуватись у якості ілюстративного матеріалу.

Демонстраційна програма VFD_Demo.exe дає змогу вивчати спосіб моделювання деформації точкового об'єкта із застосуванням векторного поля, отриманого інтерполяцією базисних векторів різними способами інтерполяції. Робота із програмою проводиться із використанням графічного інтерфейсу. Отримані рисунки також можуть бути використані у якості ілюстративного матеріалу.

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

Однією із задач, для розв'язання якої використовується зазначена бібліотека функцій, є моделювання водоносного шару для радіогідроекологічного моніторингу в районі об'єкта «Укриття». У ході радіогідроекологічного моніторингу в районі об'єкта «Укриття» Чорнобильської АЕС виникла задача моделювання радіоактивного забруднення водоносного шару із врахуванням річної амплітуди коливання ґрунтових вод. Проблема полягає у тому, що при коливанні рівня ґрунтових вод, відповідно змінюється і концентрація радіоактивних елементів у воді. Це відбувається не через збільшення маси забруднювачів, а через зменшення об'єму ґрунтових вод. Для цілей моніторингу важливо враховувати зміну об'єму води у водоносному шарі та її вплив на концентрацію радіоактивних елементів.

Задача моделювання об'єму водоносного шару у часі складається з двох етапів. На першому етапі, на підставі даних георозвідки, будуються верхня та нижня границі водоносного шару на певний момент часу (t0). Для побудови поверхні використовується деформаційне моделювання: поверхня рівня моря перетворюється у поверхню границі шару. Базисом є координати замірів глибини верхньої та нижньої границі шару на рівні моря, новим базисом - координати замірів із відповідними глибинами. На рис. 9 показаний приклад такого моделювання.

Рис. 9. Побудова поверхні водоносного шару на підставі даних про глибину у точках

Для використання векторного поля деформації, побудованого симплексною ваговою інтерполяцією, проводиться тріангуляція точкового базису. Інтерполяція застосовується для розрахунку переносу точок поверхні у симплиціальному комплексі, за його межами використовується симплексна вагова екстраполяція.

Моделювання нижньої границі водоносного шару на цьому закінчується, оскільки ця границя практично не змінюється із часом. Верхня границя водоносного шару, натомість, піддається сезонним коливанням, отже її моделювання має бути динамічним: поверхня має відповідати цільовому часу моделювання (ti). Для цього модель повинна базуватися на даних про поточний рівень ґрунтових вод у свердловинах.

Динамічне моделювання верхньої поверхні водоносного шару складає другий етап деформаційного моделювання об'єму водоносного шару. На цьому етапі прообразом об'єкта виступає верхня поверхня водоносного шару, визначена у момент часу t0. Базисом є координати свердловин, у яких замірюється рівень ґрунтових вод, разом із відповідним рівнем на момент часу t0. Новим базисом - координати тих самих свердловин, але із рівнем ґрунтових вод, визначеним у момент часу ti.

На рис. 10 показано, як поверхня деформується, враховуючи виміри глибин у наперед визначених точках (свердловинах).

Рис. 10. Моделювання сезонного коливання верхньої границі водоносного шару

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

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

В цілому запропонована програмна система надає всі необхідні можливості для впровадження, вивчення та поглибленого дослідження основних положень, викладених у цій роботі.

Висновки

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

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

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

При розв'язанні поставлених задач отримані наступні теоретичні і практичні результати:

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

2. Заради подолання недоліків існуючих способів моделювання деформації в роботі запропоновано новий спосіб моделювання деформації точкових геометричних об'єктів -- із застосуванням векторного поля деформації, отриманого ваговою інтерполяцією векторів переносу точок базису.

3. З метою вивчення можливостей та визначення оптимальних шляхів розвитку вищезазначеного способу моделювання деформації, розглянуті та проаналізовані певні існуючі способи інтерполяції.

4. Для подолання недоліків існуючих методів інтерполяції у контексті задачі моделювання деформації, розроблено новий спосіб інтерполяції: зважуванням опорних функцій у симплексі - спосіб симплексної вагової інтерполяції.

5. Досліджено вплив опорних функцій та вагових коефіцієнтів на симплексну вагову інтерполяційну функцію.

6. Розроблено спосіб екстраполяції для симплексної вагової інтерполяції, який, у контексті задачі моделювання деформації, дозволяє визначити модель деформації за границями симплиціального комплексу, утвореного базисом моделі деформації.

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

8. Для модифікованого способу інтерполяції розроблений відповідний спосіб екстраполяції.

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

10. Результати дослідження впроваджено в роботу «Радіоекологічний моніторинг в районі об'єкта «Укриття» Чорнобильської АЕС» Інституту проблем безпеки атомних електростанцій НАН України, у центральний програмний компонент системи створення інтерактивних програм «Qula», розробки ТОВ «Гештальт Консалтинг Груп», а також у ТОВ НПО «Мікротерм» при проведенні досліджень технічних характеристик приладів, що розробляються і випускаються з виробництва, а також при проведенні атестації обладнання для моделювання скалярного температурного поля у випробувальних камерах та його зміни у часі.

Список опублікованих праць за темою дисертації

1. Каленюк О. С. Обернено-квадратична вагова інтерполяція // Міжвідомчий науково-технічний збірник «Прикладна геометрія та інженерна графіка». / О. С. Каленюк, Ю. В. Сидоренко - К.: КНУБА, 2005. - Вип. 75. - С. 142-145.

Особистий внесок здобувача: здобувач запропонував інтерполяційну функцію, дослідив її властивості при використанні із квадратичними опорними функціями.

2. Каленюк О. С. Інтерполяція функцій двох змінних за допомогою обернено-квадратичної вагової інтерполяційної формули / О. С. Каленюк, Ю. В. Сидоренко // Міжвідомчий науково-технічний збірник «Прикладна геометрiя та iнженерна графіка». - К.: КНУБА, 2007. - Вип. 77. - С. 176-180

Особистий внесок здобувача: здобувач дослідив способи зважування опорних функцій та властивості інтерполяційної функції.

3. Каленюк О. С. Симплексна інтерполяція функції двох змінних / О. С. Каленюк, Ю. В. Сидоренко // Наукові нотатки Міжнародної науково-практичної конференції «Сучасні проблеми геометричного моделювання» - Луцьк: ЛДТУ, 2008. - С. 314-319.

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

4. Каленюк О. С. Алгоритм екстраполяції для двовимірної симплексної інтерполяції / О. С. Каленюк // Міжвідомчий науково-технічний збірник «Прикладна геометрiя та iнженерна графіка». - К.: КНУБА, 2009. - Вип. 81. - С. 201-204.

5. Каленюк О. С. “Способ решения СЛАУ, обеспечивающий высокое быстродействие” / О. С. Каленюк, Ю. В. Сидоренко // Тези доповідей X Всеукраїнської науково-практичної конференції студентів, аспірантів та молодих вчених «Технологія 2007». - Сєверодонецьк, 2007. - т. 4 - С. 26.

Особистий внесок здобувача: здобувач дослідив програмні реалізації способів розв'язання СЛАР і зробив висновки щодо їх обчислювальної ефективності.

6. Каленюк О. С. Симплексна інтерполяція функції багатьох змінних / О. С. Каленюк, Ю. В. Сидоренко // Наукові нотатки Міжнародної науково-практичної конференції «Геометричне модулювання та комп'ютерні технології: теорія, практика, освіта» - Харків: НТУ «ХПІ», 2009. - С. 314-319.

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

7. Каленюк О. С. Моделювання векторного поля деформації точкового об'єкта симплексною ваговою інтерполяцією / О. С. Каленюк, Ю. В. Сидоренко // Тези доповідей Міжнародної наукової конференції "Dynamical system modelling and stability investigation". - К.: КНУ, 2009. - с. 246.

Особистий внесок здобувача: здобувач дослідив властивості симплексної вагової інтерполяції у контексті задачі моделювання деформації геометричних об'єктів.

8. Каленюк О. С. Модифікований спосіб симплексної вагової інтерполяції функції багатьох змінних / О. С. Каленюк, Ю. В. Сидоренко // Праці таврійського державного агротехнологічного університету. Випуск 4. Прикладна геометрія та інженерна графіка. - Симферополь: ТДАУ, 2009. - т. 44. - с. 102-106.

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

9. Каленюк О. С. Моделювання векторного поля деформації геометричних об'єктів / О. С. Каленюк, Ю. В. Сидоренко // Тези доповідей Міжнародної наукової конференції "Dynamical system modelling and stability investigation". - К.: КНУ, 2007 р. - с. 326.

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

10. Каленюк О. С. Моделювання векторного поля деформації точкового об'єкта інтерполяцією методом Шепарда / О. С. Каленюк, Ю. В. Сидоренко // Міжвідомчий науково-технічний збірник «Прикладна геометрiя та iнженерна графіка». - К.: КНУБА, 2009. - Вип. 82. - С. 180-184.

Особистий внесок здобувача: здобувач дослідив інтерполяційний метод Шепарда у контексті задачі моделювання деформації геометричних об'єктів.

11. Каленюк О. С. Проблеми обчислювання симплексної вагової інтерполяційної функції / О. С. Каленюк, Ю. В. Сидоренко // Міжвідомчий науково-технічний збірник «Прикладна геометрiя та iнженерна графіка». - 2010. - Вип. 85. - С. 164-167.

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

Анотація

Каленюк О. C. Моделювання деформації геометричних об'єктів із використанням вагової інтерполяції. - Рукопис

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.01.01 - прикладна геометрія і інженерна графіка. - Київський національний університет будівництва і архітектури, Київ, Україна, 2011.

У роботі викладені результати дослідження з моделювання деформації точкових геометричних об'єктів у точковому базисі перетворення. Проаналізовані недоліки існуючих способів моделювання деформації геометричних об'єктів, а саме: методу політканинних перетворень і методу політочкових перетворень. З метою подолання цих недоліків розроблено спосіб моделювання деформації точкових геометричних об'єктів у точковому базисі із використанням векторного поля, побудованого ваговою інтерполяцією векторів переносу точок базису. У контексті цього способу досліджені такі способи інтерполяції, як поліноміальна, середньозважена та метод Шепарда. На підставі аналізу ефективності роботи цих способів у контексті задачі моделювання деформації геометричних об'єктів, розроблено новий симплексний спосіб вагової інтерполяції, який є локалізацією методу Шепарда у симплиціальному каркасі. Цей спосіб узагальнено для інтерполяції функції багатьох змінних. Для нього також розроблений відповідний спосіб екстраполяції та модифікація, що дозволяє застосування симплексної інтерполяції у просторах великої розмірності.

Запропоновані способи інтерполяції та моделювання деформації реалізовані у вигляді бібліотеки функцій мовою Python. Також створені програми для демонстрації можливостей цих способів. У процесі створення програмних продуктів були проаналізовані проблеми програмування та обчислення симплексної вагової інтерполяційної функції і розроблені відповідні рекомендації для їх уникнення. За результатами роботи було здійснено три впровадження, що підтверджується відповідними актами.

Ключові слова: деформаційне моделювання, політочкові перетворення, інтерполяція, симплиціальний комплекс.

Аннотация

Каленюк А. С. Моделирование деформации геометрических объектов с использованием весовой интерполяции. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.01.01 - прикладная геометрия, инженерная графика. - Киевский национальный университет строительства и архитектуры, Киев, Украина, 2011.

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

На основе анализа достоинств и недостатков перечисленных методов интерполяции, был сделан вывод о необходимости разработки такого способа, который обладал бы полезными свойствами метода Шепарда, но был бы локальным. Такой способ - способ симплексной весовой интерполяции, который является локализацией метода Шепарда на симплициальном комплексе - был разработан. Способ симплексной весовой интерполяции, вместе со соответствующим способом экстраполяции, позволяет управлять видом векторного поля путем выбора опорных функций в точках базиса и функций весовых коэффициентов в симплексах. При этом такой способ является локальным, что, применительно к задаче моделирования деформации, позволяет уточнять модель деформации в обособленных подобластях пространства, не влияя на модель за их пределами.

Способ симплексной весовой интерполяции был обобщен на случай произвольного числа переменных, что позволяет использовать его для моделирования деформации точечных объектов в пространстве произвольной размерности. Одновременно с этим было обнаружено, что вычислительная сложность расчетной формулы симплексной весовой интерполяционной функции быстро растет при повышении числа переменных. Практическое применение интерполяционной функции таким образом ограничивается случаем 1-5 переменных. В целях устранения этого ограничения, была предложена модификация симплексной весовой интерполяции, вычислительная сложность расчетного алгоритма которой позволяет использовать ее в пространствах больших, порядка десятков, размерностей.

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

Результаты работы внедрены в подсистему моделирования радиоактивного загрязнения водоносного слоя с учетом годовой амплитуды колебания уровня грунтовых вод, которая используется в работе «Радиоактивный мониторинг в районе объекта «Укрытие» Чернобыльской АЭС» Института проблем безопасности атомных электростанций НАН Украины; в центральный программный компонент системы создания интерактивных программ «Qula», разработки ООО «Гештальт Консалтинг Груп»; в ООО НПО «Микротерм» при проведении исследований технических характеристик выпускаемых приборов, а также при проведении аттестации оборудования для моделирования скалярного температурного поля в испытательных камерах и его изменения во времени.

Ключевые слова: деформативное моделирование, политочечные преобразования, интерполяция, симплициальный комплекс.

Abstract

Kalenuk O. Geometric objects deformation modelling using weighted interpolation. - Manuscript.

A thesis for competition of advanced academic degree of Doctor of Philosophy in discipline 05.01.01 - applied geometry, engineering graphics. - Kyiv National University of Construction and Architecture, Kyiv, Ukraine, 2011.

The thesis presents results of research in point objects deformation modelling. The author offers a method for geometric objects deformation modelling, based on weight interpolation of representing basis points translation vectors. For this method a number of interpolation schemes were considered and, regarding their efficiency, a new simplicial weighted interpolation and extrapolation scheme was developed. This scheme though shown its computational inefficiency in high dimensional space, therefore it needed a modification lowering its computational cost. Such modification was also developed and is provided in this work.

Key words: deformation modelling, polypoint transformation, interpolation, simplicial complex.

Размещено на Allbest.ru

...