Вінницький державний технічний університет

Берник Олена Валеріївна

УДК 638.327

МЕТОД ОЦІНЮВАЛЬНОЇ ФУНКЦІЇ У МОДЕЛЮВАННІ КРИВИХ ТА ПОВЕРХОНЬ ДРУГОГО ПОРЯДКУ

Спеціальність 01.05.02 - математичне моделювання та обчислювальні методи

Автореферат

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

кандидата технічних наук

Вінниця – 2002

Дисертацією є рукопис.

Робота виконана у Вінницькому державному технічному університеті

Міністерства освіти і науки України.

Науковий керівник: доктор технічних наук, професор Квєтний Роман Наумович, Вінницький державний технічний університет, завідувач кафедри автоматики та інформаційно-вимірювальної техніки.

Офіційні опоненти: доктор фізико-математичних наук, старший науковий співробітник Фінін Георгій Семенович, міжнародний Соломонів університет, перший проректор;

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

Провідна установа: Національний університет “Львівська політехніка”, кафедра автоматики та телемеханіки, Міністерство освіти і науки України, м. Львів.

Захист відбудеться 14.02. 2003 р. о 14-й годині

на засіданні спеціалізованої вченої ради Д 05.052.01

у Вінницькому державному технічному університеті за адресою:

21021, м. Вінниця, Хмельницьке шосе, 95.

З дисертацією можна ознайомитись у бібліотеці ВДТУ

за адресою: 21021, м. Вінниця, Хмельницьке шосе, 95.

Автореферат розісланий 10.01.2003 р.

Вчений секретар

спеціалізованої вченої ради Захарченко С.М.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Із прийняттям нової редакції Закону України (від 11 липня 2001 року №2627-III) “Про авторське право і суміжні права” від 23 грудня 1993 року №3792-XII, комп'ютерні програми стають інтелектуальною власністю, і їх використання з комерційною метою без згоди автора заборонено. Через велику вартість обмежується кількість відомих програмних продуктів іноземного виробництва, і зокрема, програм для побудови кривих та поверхонь другого порядку, доступних широкому колу користувачів. Крім того, у зв'язку із постійним зростанням обсягів інформації та кількості даних залишається актуальною проблема підвищення ефективності функціонування програмного забезпечення обчислювальної техніки. Тому метою даної дисертаційної роботи є розробка нових та вдосконалення існуючих власних графічних систем для побудови кривих та поверхонь другого порядку.

Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалася в рамках теми “Розробка математичних моделей та алгоритмізація сучасних задач інформаційних систем”, що виконувалась у 2000-2001 роках у Вінницькому державному технічному університеті, номер державної реєстрації 0100U002939.

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

Задачі дослідження:

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

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

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

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

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

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

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

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

Наукова новизна одержаних результатів

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

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

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

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

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

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

Окремі теоретичні результати дисертаційної роботи та програмне забезпечення впроваджено в учбовий процес по викладанню дисципліни “Комп'ютерна графіка” (спеціальність 07.091401 – Системи автоматики і управління) та “Інженерна та комп'ютерна графіка” (спеціальність 07.091302 – Метрологія та вимірювальна техніка) на кафедрі автоматики та інформаційно-вимірювальної техніки Вінницького державного технічного університету.

Алгоритми та програмне забезпечення прийнято до впровадження на науково-виробничій та впровадницькій фірмі “Роботметалургінвест” і в інструментальному виробництві ВАТ “Маяк”.

Впровадження підтверджується відповідними актами.

Особистий внесок здобувача. Всі основні результати дисертаційної роботи були отримані автором особисто. Для одержання результатів, опублікованих у співавторстві здобувач: в роботі [1] прийняла участь у розробці програм для комп'ютерного експерименту, у формулюванні та перевірці результатів дослідження; у роботі [7] розробила математичний апарат та перевірила правильність теоретичних припущень, сформульованих науковим керівником у рамках теми дисертаційної роботи.

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

џ п'ятій міжнародній науково-технічній конференції "Контроль і управління в складних системах" (КУСС) (Вінниця, 1999);

џ шостій міжнародній науково-технічній конференції "Контроль і управління в складних системах" (КУСС) (Вінниця, 2001);

џ дев'ятій міжнародній науково-практичній конференції “Сучасні інформаційні та енергозберігаючі технології життєзабезпечення людини” (СІЄТ9-01) (Чернівці, 2001);

џ п'яти науково-практичних конференціях професорсько-викладацького складу, співробітників та студентів ВДТУ з участю інженерно-технічних працівників підприємств міста Вінниці та області (Вінниця, 1998, 1999, 2000, 2001, 2002).

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

Структура і обсяг дисертації. Дисертація складається зі вступу, 4 розділів, висновків, списку використаних джерел і додатків. Основний зміст викладено на 118 сторінках, дисертація містить 30 рисунків. Список використаних джерел, який містить 160 найменувань, подано на 13 сторінках. Додатки містять 29 сторінок. Повний обсяг дисертації 160 сторінок.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

Методом, що враховує геометричні властивості фігур другого порядку та оснований на їх поданні в аналітичному виді є метод оцінювальної функції (МОФ).

Розглянуто еволюцію алгоритмів (зокрема, алгоритмів Брезенхема), що базуються на цьому методі, їх модифікації, узагальнення тощо. Звертається увага на те, що в порівнянні з іншими алгоритмами генерації плоских кривих алгоритми, основані на МОФ відрізняються високою швидкодією та точністю відображення, що робить доцільним їх застосування для відображення як статичних, так і динамічних сцен. Зауважується, що в переважній більшості випадків узагальнюючі версії не набули поширення через їх орієнтацію на апаратну реалізацію.

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

Проаналізовано методи та алгоритми (наскільки це було можливо) побудови дуг КДП у пакетах комп'ютерної графіки.

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

Проведений огляд та аналіз літератури визначили напрямок та постановку задач дослідження.

Значний внесок у розвиток та популяризацію методу оцінювальної функції внесли вчені Дж. Брезенхем (J.E.Bresenham), який розробив алгоритми лінійної та колової інтерполяції за методом оцінювальної функції, Л. Аммерал (L. Ammeral), Дж. Фолі (J.D. Foley), А. Ван Дем (A. van Dam), Девід Роджерс (David F. Rogers), підручники яких є основою сучасної комп'ютерної графіки, представники наукової школи колишнього Радянського Союзу Анішин М.С., Вашкевич С.М., Тормишев Ю.І., Яблонський Ф.М., до яких долучаються вчені-науковці Вінницького державного технічного університету Пєтух А.М., Обідник Д.Т., Романюк О.Н. та інші.

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

- зміна одного параметру оцінювальної функції (ОФ) призводить до побудови іншого виду кривої (параболи, гіперболи чи еліпса);

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

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

Вираз узагальненої оцінювальної функції має вид:

,

де p, q – параметри форми кривої, k – параметр виду кривої, для гіперболи для параболи для еліпса

На рис.1 відображено ділянки інтерполювання та відповідні типи приростів. Опишемо послідовні кроки, що потрібно виконати для побудови бажаної кривої у першій чверті декартової координатної площини:

Рис.1. Зміна типів приростів для різних ділянок інтерполювання

1. Задати коефіцієнт k, який визначить вид кривої, параметри а та b, що опишуть форму кривої.

2. Розрахувати значення коефіцієнтів p і q (необхідно запобігти випадку ділення на 0, при а=0) та початкове значення оцінювальної функції

.

3. Поки

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

4. Поки

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

5. Поки

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

6. Поки інтерполювання здійснюється вертикальними кроками (координата у зменшується, х – залишається незмінною) та діагональними (координата х збільшується на одиницю, а координата у – зменшується).

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

Шляхом введення коефіцієнтів одержано вирази, що дозволяють застосовувати узагальнений МОФ до сполучення двох точок дугами КДП у різних координатних чвертях, при чому для цього можна використовувати криві з полярними центрами кривини. Дуга вписується в прямокутник зі сторонами a, b (рис.2).

Рис. 2. Напрямки інтерполювання та типи приростів для дуг,

побудованих за МОФ в різних чвертях декартової площини

Формули побудови кривої типу 1 (рис.2) для будь-якого октанту запишуться так:

,

,

,

.

У першій чверті , , для другої чверті , , для третьої чверті , , у четвертій чверті , .

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

, , , ,

тому , ,

.

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

Із врахуванням форми кривої та типів приростів у тому чи іншому квадранті формули перепишуться:

,

,

,

.

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

Шляхом повороту системи координат відносно центру, можна змінити кривину дуги.

Криві, утворені при повороті місцевої системи координат на кути , (, , , ) показані на рис.3, початкова крива - еліпс з параметрами а=8, b=8.

Рис.3. Криві, що проходять через задані точки при повороті місцевої системи координат на деякий кут

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

Рис.4. Сполучення трьох вузлів кривими другого порядку за МОФ,

вузли 1, 2 з'єднуються параболою чи гіперболою

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

У третьому розділі розглянуто способи підвищення швидкодії: 1) за рахунок збільшення потужності виконавчого органу (процесора); 2) шляхом розпаралелення обчислювального процесу. Визначено, що хоча на даному етапі перевага надається першому способу, не слід відкидати другого, оскільки завдяки цьому можна значно підвищити швидкодію при залученні менших коштів. Щодо способів реалізації паралельних алгоритмів, відмічено, що найкращих показників швидкодії можна досягнути при створенні спеціалізованих апаратних пристроїв, але це потребує значних грошових витрат, програмна реалізація є найдешевшою, але відповідно забезпечує нижчі показники.

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

Точка, для якої виконується умова (рис.5.в):

,

є граничною, оскільки розміщена лівіше по відношенню до всіх інших випадків, відображених на рис.5. Ця точка розділить октант на два сектори S1 та S2 (рис.6).

Рис. 5. Граничні варіанти формування двох послідовних діагональних приростів

в залежності від характеру проходження траєкторії

Рис. 6. Поділ траєкторії кола на сектори

У секторі S1 неможлива поява двох послідовних діагональних приростів. У секторі S2 неможлива поява двох послідовних гори-зонтальних координатних приростів.

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

Послідовність формування восьмої частини траєкторії парними та непарними точками запишеться наступним чином:

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

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

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

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

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

6) Кроки 1-5 повторюються поки не буде побудована дуга кривої.

На рис. 7 показана ділянка траєкторії кола радіусом 20 проінтерпольована спочатку парними, а потім непарними точками, з використанням значень незалежних ОФ. На рисунку показано виконання прогнозуючого кроку для парних точок траєкторії.

Рис. 7. Ділянка траєкторії кола проінтерпольована

парними та непарними точками

Визначено відповідні формули для побудови дуг кіл у різних октантах декартової координатної площини.

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

У четвертому розділі розроблено алгоритмічне і програмне забезпечення для узагальненого та модифікованого методу оцінювальної функції, що дозволяє відображати КДП, а також порівнювати точність та швидкодію розроблених алгоритмів з класичними. Програма створювалася засобами візуального програмування Borland Delphi і носить назву “Метод оцінювальної функції і його використання для побудови кривих другого порядку” [4].

Визначено, що в разі використання алгоритму за узагальненим МОФ кількість операцій в середньому для побудови однієї точки кривої менша на 25%, ніж у випадку застосування трьох разом узятих класичних алгоритмів (побудови еліпса, параболи і гіперболи). А порівняльний аналіз оцінювальних функцій показав, що їх значення за класичним методом та узагальненим однакові, отже точність алгоритму не погіршується, залишається рівною половині кроку дискретизації.

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

На рис.8 відображена поверхня однопорожнинного гіперболоїда (в аксонометричній проекції), побудована за узагальненим МОФ.

Рис.8. Однопорожнинний гіперболоїд

Значення оцінювальних функцій за модифікованим МОФ і класичним показані у табл.1 (у дужках записується номер інтерпольованої точки):

Таблиця 1.

Інтерполювання кола (радіус 20)

Оцінювальні функції за алгоритмом Брезенхема Оцінювальні функції за модифікованим методом

f_Br (0) = -19,75 f_MMOF (0) = - 19,75

f_Br (1) = -18,75 f_MMOF (2) = -15,75

f_Br (2) = -15,75 f_MMOF (4) = -3,75

f_Br (3) = -10,75 f_MMOF (6) = -22,75

f_Br (4) = -3,75 f_MMOF (8) = -31,75

f_Br (5) = -33,75 f_MMOF (10) = -30,75

f_Br (6) = -22,75 f_MMOF (12) = -19,75

f_Br (7) = -9,75 f_MMOF (14) = -27,75

f_Br (8) = -31,75 f_MMOF (1) = -18,75

f_Br (9) = -14,75 f_MMOF (3) = -10,75

f_Br (10) = -30,75 f_MMOF (5) = -33,75

f_Br (11) = -9,75 f_MMOF (7) = -9,75

f_Br (12) = -19,75 f_MMOF (9) = -14,75

f_Br (13) = -25,75 f_MMOF (11) = -9,75

f_Br (14) = -27,75 f_MMOF (13) = -25,75

Експериментальне дослідження точності побудови різних дуг (аналізувалась побудова дуг з радіусами 0..1024, що забезпечує покриття усіх дуг та кіл, що відображаються дисплеєм з розподільчою здатністю 1024ґ768) за модифікованим МОФ та класичним МОФ показало, що криві, відображувані за цими методами є абсолютно ідентичними.

Для порівняння швидкодії використовувалися засоби паралельного програмування Borland Delphi. Проводилось обчислення координат точок 100000 кіл із радіусом R=100 за алгоритмами модифікованого МОФ та Брезенхема. Експеримент показав, що формування точок за модифікованим МОФ здійснюється швидше в середньому на 18..25% в порівнянні з алгоритмом Брезенхема. Цей показник варіюється в залежності від потоків та процесів операційної системи, які одночасно виконуються в регістрах процесора. Ці потоки та процеси можна спостерігати та відстежувати у програмі WinSight32, яка поставляється із стандартним набором інструментів Borland Delphi.

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

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

ВИСНОВКИ

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

Проведений аналіз літературних джерел та програмних продуктів показав, що:

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

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

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

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

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

В результаті досліджень у цьому напрямку:

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

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

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

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

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

6. Програмне забезпечення було апробовано у науково-виробничій та впровадницькій фірмі “Роботметалургінвест”, в інструментальному виробництві ВАТ “Маяк” і впроваджено у навчальний процес на кафедрі “Автоматики та інформаційно-вимірювальної техніки” у Вінницькому державному технічному університеті.

Публікації за матеріалами дисертаційної роботи:

1. Романюк О.Н., Якубішин І.М., Сіденко О.В. Нові підходи до реалізації функції колової інтерполяції // Вісник ВПІ. – 2000. – №3. – С.85-88.

2. Сіденко О.В. Методи та алгоритми побудови поверхонь другого порядку // Вісник ВПІ. – 2001. – №6. – С.119-121.

3. Сіденко О.В. Узагальнення методу оцінювальної функцій для інтерполювання кривих другого порядку // Вимірювальна та обчислювальна техніка в технологічних процесах. – 2001. – №1. – C.130-133.

4. Комп'ютерна програма “Метод оцінювальної функції і його використання для побудови кривих другого порядку”: Свідоцтво про державну реєстрацію прав автора №5111 ПА. Україна / О.В. Сіденко (Україна) – Заявлено 26.12.2001; Видано 28.01.2002.

5. Романюк О.Н. Сіденко О.В. Дослідження властивостей крокових приростів траєкторій кола та еліпса. Вінниц. держ. техн. Ун-т. – Вінниця, 1998. – 8 с.: іл. – Укр. – Деп. в ДНТБ України, 23.01.1998р, № 146 – Ук98.

6. Сиденко Е.В. Применение нового подхода к построению графических примитивов (окружностей) // Информационный листок Винницкого ГЦНТЭИ. – 2001. – №28.

7. Квєтний Р.Н., Сіденко О.В. Застосування методу оцінювальної функції до апроксимації кривих другого порядку в машинній графіці / Спеціальне видання Міжнародного науково-технічного журналу “Вимірювальна та обчислювальна техніка в технологічних процесах” за матеріалами міжнародної науково-практичної конференції “СІЄТ9-01”, м. Чернівці, 12-15 червня 2001 року. – Київ: “ФАДА, ЛТД”, 2001. – С.297-299.

8. Сіденко О.В. Нові алгоритми формування кривих другого порядку (кіл та еліпсів)/ Контроль і управління в складних системах (КУСС-99). Книга за матеріалами п'ятої міжнародної науково-технічної конференції. м. Вінниця, 3-5 лютого 1999 року. У 3-х томах. Том 1. – Вінниця: “УНІВЕРСУМ-Вінниця”, 1999. – С.198-201.

анотаціЯ

Берник О.В. Метод оцінювальної функції у моделюванні кривих та поверхонь другого порядку. – Рукопис.

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

В дисертації виконано узагальення методу оцінювальної функції, при чому крім самого узагальенння, яке дозволяє зміною одного параметру оцінювальної функції визначати вид інтерполяції (еліптичну, параболічну чи гіперболічну), враховано деякі модифікації, що засосовувались до окремих фігур, а саме, зменшення похибки до половини кроку дискретизації, відсутність корегуючих формул при переході через границі інтерполяційних секторів. Узагальнений МОФ застосовано до апроксимації довільних кривих та поверхонь другого порядку.

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

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

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

анотацИЯ

Берник О.В. Метод оценочной функции при моделировании кривых и поверхностей второго порядка. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 – математическое моделирование и вычислительные методы. Винницкий государственный технический университет. Винница, 2003.

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

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

Также исследованы условия построения поверхностей второго порядка с использованием обобщенного МОФ.

Разработана модель, которая позволяет модифицировать метод оценочной функции для кругового интерполирования с условием реализации алгоритма на параллельных структурах ЭВМ. В этом случае быстродействие формирования примитива повышается приблизительно в 1,4 раза.

Предложенные модели и алгоритмы были апробированы с помощью разработанного программного обеспечения. Название программы “Метод оценочной функции и его использование для построения кривых второго порядка”.

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

ANNOTATION

Bernyk O. Method of Evaluationing Function for Second Level Curves and Surface Modeling. –

Dissertation submited degree of the candidate of technical sciences on speciality – 01.05.02 – mathimatical modeling and computaional mmethods. Vinnitsa State Technical University. Vinnitsa, 2003.

Generalization of method of the evaluational function (MoEF) is made in this dissertation, except generalization itself which allows by changing single parameter of evaluational function to determ type of interpolation (elliptical, parabolical or hyperbolical), token to account previous modifications, namely reducing of error value up to the half of discretization step, elimination of correction formulas in borders transactions of the interpolation sectors. Generalized MoEF applied to approximation of any curves and surfaces second level.

The model is developed, which is allowed to be applied with method of evaluation function to circle interpolation on parallel structures of PC.

Proposed models and algorithms was researched by developed software. Programs name is “The Method of Evaluation Function and its Application to Building of Second Level Curves”.

Keywords: algorithm, method of the evaluationing function, Brezenghems algorithm, interpolation, approximation, computer graphics, second level curve, spline, second level surfaces.

Підписано до друку 10.01.2003 р. Формат 29.7х42ј

Наклад 100 прим. Зам. №2003-001

Віддруковано в комп'ютерному інформаційно-видавничому центрі

Вінницького державного технічного університету.

м. Вінниця, Хмельницьке шосе, 95. Тел.: 44-01-59.