РОЗДІЛ 2
МЕТОДИ ГЕОМЕТРИЧНОГО МОДЕЛЮВАННЯ, ОПИСУ ТА ВІЗУАЛІЗАЦІЇ ФУНКЦІОНАЛЬНО ЗАДАНИХ СГО
2.1. Синтез СГО з непохідних елементів кругової форми
Вибір математичного підходу до представлення графічної інформації є надзвичайно важливою задачею, а від її розв'язання в значній мірі залежить ефективність і якість роботи ІАС, а також організація алгоритмічного та програмного забезпечення [11, 33, 34, 44, 45, 73]. З точки зору ефективності найбільш перспективними є підходи, які дозволяють кодувати геометричну інформацію за допомогою деяких аналітичних конструкцій [11, 17, 41, 42, 49, 50, 150, 182, 188, 189]. Аналітичний підхід дає можливість не тільки ефективно описувати СГО, але й синтезувати їх з більш простих (елементарних, непохідних) елементів. Крім цього даний підхід дозволяє істотно, в порівнянні з іншими підходами, зменшити об'єм даних при зберіганні. Однак візуалізація в реальному часі об'єктів заданих таким чином, пов'язана з ростом необхідних обчислень через високий порядок функцій, які описують СГО. Отже, необхідною є розробка таких методів та алгоритмів, які б дозволили понизити порядок результуючого аналітичного виразу, а також зменшити необхідний об'єм обчислень при візуалізації.
Моделлю СГО можна вважати множину точок в полі уваги або просторі зображення. В попередньому розділі, на основі аналізу існуючих підходів та методів, обгрунтовано, що найбільшим ступенем узагальненості характеризуються R-функції [34, 42, 188].
СГО будується з непохідних об'єктів простішої форми трьома способами [50]:
a) частковим накладанням та "склеюванням" (рис.2.1.а);
b) "склеюванням впритул" (рис.2.1.б);
c) розміщенням на заданій відстані і орієнтуванням стосовно один одного (рис.2.1.в).
Рис.2.1. Способи побудови СГО
Побудовані таким чином СГО володіють деякими властивостями і знаходяться у визначених відношеннях між собою. Тому опис та синтез цих СГО визначає застосування функцій алгебри логіки, які за своєю природою є дискретними функціями як дискретних, так і неперервних аргументів.
Розглянемо функцію , яка всюди визначена, і двозначний предикат [16, 50]:
В деяких випадках доцільно розглядати тризначний предикат:
Для синтезу СГО достатньо двозначного предиката. Нехай функції , відповідає предикат , який розбиває простір на дві частини: , де ; , де .
Оскільки будь-яка дійсна величина додатна, від'ємна або рівна нулю, то приналежність величин і до одного з цих класів можна визначити з допомогою предикатів:
Розглянемо всі можливі набори двійкових змінних X, Y: (0,0;0,1;1,0;1,1). Кожному набору , можна поставити у відповідність область .
Означення 1. Будь-яка функція , називається R2 ?функцією, якщо в кожній з часткових областей виконується умова:
де ?змінна двозначної логіки (0 або 1).
R2 ?функцію можна визначити і наступним чином.
Означення 2. Оскільки кожному набору змінних , відповідає визначена часткова область і величина , то можна отримати деяку функцію таку, що
Якщо виконується дане співвідношення, то буде ?функцією.
При виборі непохідних елементів необхідно дотримуватись умови, що побудовані для них R-функції не будуть надто громіздкими, а їх порядок не буде високим, адже подальше застосування до цих функцій R-операцій підвищить їх порядок. Розглянемо спершу, як непохідні об'єкти, елементи, що характеризуються круговою формою (кола та дуги кіл). Другим кроком буде застосування опуклих багатокутників в ролі непохідних елементів і нарешті, вкінці, поєднаємо ці два типи непохідних елементів з метою синтезу СГО довільної геометричної форми.
Отже, якщо непохідним елементом для синтезу СГО, що характеризуються більш складною формою, вибрано кола, то R-функція, яка описує даний непохідний елемент, має вигляд:
(2.1)
де - координати центра кола, - радіус кола.
Якщо об'єкти визначаються нерівностями , , а логіку побудови об'єкта задано за допомогою об'єктів , то виникає задача визначення такої функції , при якій нерівність визначала би об'єкт . Дана задача розв'язується, використовуючи таку теорему [41].
Теорема. Якщо об'єкти визначаються нерівностями , а логіка синтезу об'єкта задана булевою функцією , то нерівність
визначає об'єкт , де ? - функція, яка відповідає булевій функції .
Загальна функція , яка описує синтезований об'єкт будується за допомогою функцій та R-операцій. Побудовані таким способом функції зберігають фундаментальну властивість R-функцій - вони зберігають знак на границі і всередині об'єктів, які вони описують. В [41-43, 83, 150, 171, 188, 189] запропоновано ряд методів розв'язання задачі побудови результуючої функції СГО . Ці методи базуються на застосуванні різного роду операцій, деякі з яких було розглянуто в п.1.3.
Метод точних булевих операцій, аналітичний вигляд яких описує формула (1.8), має ряд переваг перед іншими методами, адже вимагає найменшу кількість операцій при реалізації, однак дані операції мають розрив при .
В [41-43, 188, 189] запропоновано ряд систем R-операцій. Система вигляду (1.9) визначає ціле сімейство R-операцій в залежності від значень параметра . Частковим випадком даної системи операцій також є операції виду (1.8). Для забезпечення неперервності використовують модифікацію R-функцій виду (1.10). Основним недоліком операцій (1.9) та (1.10) є те, що в їх аналітичному вигляді присутні корені. Застосування операцій такого вигляду до (2.1) приведе до того, що результуюча функція матиме високий порядок, а візуалізація об'єкта навіть в двовимірному просторі вимагатиме великих обчислювальних затрат.
Для вирішення цієї проблеми в [42] запропоновано систему R-операцій (2.2) у формі однорідних поліноміальних сплайнів степені , що належать до і мають єдину для похідних -го порядку лінію розриву, яка визначається рівнянням .
(2.2)
Інший спосіб розв'язання даної задачі полягає у використанні псевдобулевих операцій (1.11), що й реалізовано в